This section focuses on a particular approach called incremental distance computation, which assumes that between successive calls to the collision detection 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 [636,702]. Nonconvex bodies can be decomposed into convex components.
These collision detection algorithms seem to offer wonderful performance, but this comes at a price. The models must be coherent, which means that all of the primitives must fit together nicely. For example, if a 2D model uses line segments, all of the line segments must fit together perfectly to form polygons. There can be no isolated segments or chains of segments. In three dimensions, polyhedral models are required to have all faces come together perfectly to form the boundaries of 3D shapes. The model cannot be an arbitrary collection of 3D triangles.
The method will be explained for the case of 2D convex polygons, which are interpreted as convex subsets of . Voronoi regions for a convex polygon will be defined in terms of features. The feature set is the set of all vertices and edges of a convex polygon. Thus, a polygon with edges has features. Any point outside of the polygon has a closest feature in terms of Euclidean distance. For a given feature, , the set of all points in from which is the closest feature is called the Voronoi region of and is denoted . Figure 5.11 shows all ten Voronoi regions for a pentagon. Each feature is considered as a point set in the discussion below.
For any two convex polygons that do not intersect, the closest point is determined by a pair of points, one on each polygon (the points are unique, except in the case of parallel edges). Consider the feature for each point in the closest pair. There are only three possible combinations:
Let and be two convex polygons, and let and represent any feature pair, one from each polygon. Let and denote the closest pair of points, among all pairs of points in and , respectively. The following condition implies that the distance between and is the distance between and :
The 2D ideas extend to 3D convex polyhedra [247,636,702]. The primary difference is that three kinds of features are considered: faces, edges, and vertices. The cases become more complicated, but the idea is the same. Once again, the condition regarding mutual Voronoi regions holds, and the resulting incremental collision detection algorithm has ``almost constant time'' performance.
Steven M LaValle 2012-04-20