5.3.3 Incremental Methods

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 ${\mathbb{R}}^2$. 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 $n$ edges has $2n$ features. Any point outside of the polygon has a closest feature in terms of Euclidean distance. For a given feature, $F$, the set of all points in ${\mathbb{R}}^2$ from which $F$ is the closest feature is called the Voronoi region of $F$ and is denoted $\operatorname{Vor}(F)$. Figure 5.11 shows all ten Voronoi regions for a pentagon. Each feature is considered as a point set in the discussion below.

Figure 5.11: The Voronoi regions alternate between being edge-based and vertex-based. The Voronoi regions of vertices are labeled with a ``V'' and the Voronoi regions of edges are labeled with an ``E.''

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:

• Vertex-Vertex Each point of the closest pair is a vertex of a polygon.
• Edge-Vertex One point of the closest pair lies on an edge, and the other lies on a vertex.
• Edge-Edge Each point of the closest pair lies on an edge. In this case, the edges must be parallel.

Let $P_1$ and $P_2$ be two convex polygons, and let $F_1$ and $F_2$ represent any feature pair, one from each polygon. Let $(x_1,y_1) \in F_1$ and $(x_2,y_2) \in F_2$ denote the closest pair of points, among all pairs of points in $F_1$ and $F_2$, respectively. The following condition implies that the distance between $(x_1,y_1)$ and $(x_2,y_2)$ is the distance between $P_1$ and $P_2$:

$$(x_1,y_1) \in \operatorname{Vor}(F_2) (x_2,y_2) \in \operatorname{Vor}(F_1) .$$ (5.29)

If (5.29) is satisfied for a given feature pair, then the distance between $P_1$ and $P_2$ equals the distance between $F_1$ and $F_2$. This implies that the distance between $P_1$ and $P_2$ can be determined in constant time. The assumption that $P_1$ moves only a small amount relative to $P_2$ is made to increase the likelihood that the closest feature pair remains the same. This is why the phrase ``almost constant time'' is used to describe the performance of the algorithm. Of course, it is possible that the closest feature pair will change. In this case, neighboring features are tested using the condition above until the new closest pair of features is found. In this worst case, this search could be costly, but this violates the assumption that the bodies do not move far between successive collision detection calls.

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.