Game Development Reference

In-Depth Information

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