Distance functions

Many collision detection methods benefit from maintaining a distance function, which keeps track of how far the bodies are from colliding. For example, let $ A$ and $ B$ denote the set of all points occupied in $ {\mathbb{R}}^3$ by two different models. If they are in collision, then their intersection $ A \cap B$ is not empty. If they are not in collision, then the Hausdorff distance between $ A$ and $ B$ is the Euclidean distance between the closest pair of points, taking one from $ A$ and one from $ B$.8.3 Let $ d(A,B)$ denote this distance. If $ A$ and $ B$ intersect, then $ d(A,B) = 0$ because any point in $ A \cap B$ will yield zero distance. If $ A$ and $ B$ do not intersect, then $ d(A,B) > 0$, which implies that they are not in collision (in other words, collision free).

If $ d(A,B)$ is large, then $ A$ and $ B$ are mostly likely to be collision free in the near future, even if one or both are moving. This leads to a family of collision detection methods called incremental distance computation, which assumes that between successive calls to the algorithm, the bodies move only a small amount. Under this assumption the algorithm achieves ``almost constant time'' performance for the case of convex polyhedral bodies [181,214]. Nonconvex bodies can be decomposed into convex components.

A concept related to distance is penetration depth, which indicates how far one model is poking into another [182]. This is useful for setting a threshold on how much interference between the two bodies is allowed. For example, the user might be able to poke his head two centimeters into a wall, but beyond that, an action should be taken.

Steven M LaValle 2016-12-31