Game Development Reference
However, the prospect of having to break the time step at each instant a collision
occurs is not very rosy, since theoretically, a body could have an infinite number
of collisions within a time interval. So, even though collision detection is per-
formed in space-time, our physics scheme should change velocities and positions
at a limited number of time steps only.
In any case, we will never be able to fully keep bodies from interpenetrating,
and we shouldn't. We simply need to make sure that penetrations are shallow
enough to allow for accurate contact data to be computed. We will present a
definition of “shallow enough” further on, but for now, let us assume that we want
to keep the depths at which bodies interpenetrate within a certain tolerance.
The body trajectories through space-time are not known, or at least, cannot
be derived from the underlying physical simulation model. Using the trajectories
prescribed by the physics model would take a little too much of our math skills.
Even for something as simple as a tumbling brick in free fall, the equations for
the trajectory are way too complex for continuous collision detection. Instead, we
will assume simplified trajectories for moving bodies.
Solutions to the four-dimensional intersection detection problem have been
presented for a restricted class of shapes and motions [Cameron 85, Cameron 90,
Canny 86, Hubbard 93, Schomer and Thiel 95, Eckstein and Schomer 99, Redon
et al. 02]. In the literature on continuous collision detection, the class of shapes
is usually restricted to polytopes and the motions are restricted to rotations and
translations. We use polytope as a generic term for all shapes that are formed by
taking the convex hull of a finite point set. The set of polytopes includes points,
line segments, triangles, tetrahedra, and convex polyhedra. In this chapter, we dis-
cuss solutions for convex objects in general. Besides polytopes, we also consider
quadrics, such as spheres, cylinders, and cones, and shapes that are constructed
from these primitive shapes through convex hulls and Minkowski sums.
The freedom of having any imaginable convex shape type as a collision prim-
itive comes at the cost of restricting the set of continuous motions to translations.
Bodies can still rotate but only at the given time steps. Often, we can get away
with using piecewise linear trajectories for translations only. Angular velocities of
moving bodies are usually not so high, and in cases where they are, the physical
shape usually does not depend on the orientation, for example, wheels of a race
car that are represented by cylinders are invariant under rotations along their axes.
Our solutions for continuous collision detection and contact data computation
are all based on the use of support mappings and the Gilbert-Johnson-Keerthi al-
gorithm (GJK). GJK is an iterative method for computing the distance between
convex objects [Gilbert et al. 88]. GJK turns out to be extremely versatile and
is applicable to all kinds of proximity queries on a large family of convex shape