Game Development Reference
It should be conservative. In other words, all the collisions in the game should
be contained on the list of checks. The coarse collision detector is allowed
to generate checks that end up not being collisions (called “false positives”),
but it should not fail to generate checks that would be collisions (called “false
It should generate as small a list as possible. In combination with the previ-
ous feature, this means that the smallest list it can return is the list of checks
that will lead to contacts. In that case the coarse collision detection will be
performing a fully accurate collision detection, and there will be no need for
further checks. In practice, however, the coarse collision detection usually re-
turns a set of possible checks that contains many false positives.
It should be as fast as possible. It may be possible to generate close to the
optimum number of required checks, but it defeats the object of the coarse
collision detector if it takes a long time to do so.
Two broad approaches are used for coarse collision detection: bounding volume
hierarchies and spatial data structures. We'll look at these in turn.
B OUNDING V OLUMES
A bounding volume is an area of space that is known to contain an object. To represent
the volume for coarse collision detection, a simple shape is used, typically a sphere or
a box. The shape is made large enough so that the whole object is guaranteed to be
inside the shape.
The shape can then be used to perform some simple collision tests. If two objects
have bounding volumes that don't touch, then there is no way in which the objects
within them can be in contact. Figure 12.1 shows two objects with spherical bounding
Ideally bounding volumes should be as close-fitting to their object as possible. If
two close-fitting bounding volumes touch, then their objects are likely to touch. If
most of the space inside the bounding volumes isn't occupied, then touching bound-
ing volumes is unlikely to mean the objects are in contact.
Spheres are convenient because they are easy to represent. Storing the center of
the sphere and its radius is enough: