Pairwise collision detection

Figure: Two colliding objects, with their intersection shown in black

The basic problem of pairwise collision detection is to determine whether two given objects collide, as illustrated in Figure . Hubbard [#!Hubbard95!#] points out that most collision detection research ignores the time dependence of collision problems. Although methods for fully four dimensional ``spacetime'' collision detection have been known since Boyse's work in 1979 [#!Boyse79!#], the usual approach is to ignore time dependence and treat each timestep or frame of the simulation as a conceptually separate problem^1.1.

To answer the question ``Do these two objects collide?'', we must first decide what we mean by ``objects.'' Computational geometers use a surprising number of fundamentally different ways to represent objects. The most basic division is between solid and boundary representations- a solid representation directly indicates which points are inside the object and which are outside; a boundary representation only gives the outer shell of an object.

With an implicit surface, the value of a (typically continuous) function $f:\Re^3\mapsto\Re$ indicates whether a point is inside or outside the solid. Then $I=\{\vec{x}\in\Re^3\vert f(\vec{x})<0\}$. Without restrictions on $f$, the pairwise collision detection problem is not solvable.^1.2 Popular restricted classes of functions include quadrics and more general polynomials, for which efficient collision tests are known [#!FNO89!#].

Parametric surfaces (such as NURBS or Bézier surfaces [#!LR80!#]) represent the boundary of an object as the image of a lower-dimension shape under a mapping function such as $f:\Re^2\mapsto\Re^3$, so $P=\{f(\vec{x})\vert\vec{x}\in\Re^2\}$. Pairwise collision detection for parametric surfaces are typically based on subdivision.

The constructive solid geometry (CSG) representation constructs solid objects from simple fundamental shapes via set operations such as union, intersection, and difference. Pairwise collision depends on the fundamental shapes chosen, but these are typically chosen to ensure collisions are efficient. A useful formalism for this case is ``S-Bounds,'' described by Cameron in [#!Cam91!#].

Polyhedral decompositions approximate a solid object as the disjoint union of convex polytopes. Several well-known results on polyhedra are those of Lin-Canny [#!LC91!#] and Gilbert-Johnson-Keerthi [#!GJK88!#], which use convex optimization techniques to achieve performance as good as $O(\lg m)$, where $m$ is the number of vertices in the polytope. Further, using temporal coherence, these algorithms exhibit near constant-time performance for slow-moving objects. Sadly, this result is often misinterpreted to mean the $n$-body collision detection problem can be solved in logarithmic time, which is not the case.

The lowest common denominator boundary representation is triangles, often (imprecisely) called polygons. Pairwise collision between triangles takes constant time.

Finally, if the objects intersect, depending on the application, we may also want to know the penetration distance and direction, or the size of the intersection region. For simple shapes, this is often available at little or no extra effort.