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 [183,218]. 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 [184]. 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.