Game Development Reference
In-Depth Information
jects, a bounding box will fit much more tightly than a bounding sphere. But detect-
ing touching boxes is much more complex than detecting touching spheres, and so
spheres are often a good place to start.
There are other possible bounding volume representations, with their own
strengths and weaknesses. None are very widespread, however, so I will ignore them
for the purpose of this chapter. They are discussed at length in Ericson [2005].
In the rest of this chapter I will use only bounding spheres. Anything that can be
done with bounding spheres can also be done with bounding boxes. Typically the box
version has exactly the same algorithm but will take longer and will use more tricky
mathematics. In learning to use the algorithms, bounding spheres are simpler to work
with.
As a tradeoff, however, it's important to remember that we're using these volumes
as a first check to see whether objects are touching. If we had more accurate bound-
ing volumes, then the first check would be more accurate, so we'd have less follow-up
work to do. In many cases (particularly with lots of boxlike things in the game, such as
crates), bounding spheres will generate many more potential collisions than bound-
ing boxes. Then the time we save in doing the simpler sphere-collision tests will be
lost by having additional potential collisions to reject using the more complex colli-
sion detection routines in this chapter.
12.3.1
H IERARCHIES
With each object enclosed in a bounding volume we can perform a cheap test to see
whether objects are likely to be in contact. If the bounding volumes are touching,
then the check can be returned from the coarse collision detector for a more detailed
examination by the fine collision detector. This speeds up collision detection dramat-
ically, but it still involves checking every pair of objects. We can avoid doing most of
these checks by arranging bounding volumes in hierarchies.
A bounding volume hierarchy (BVH) has each object in its bounding volume at
the leaves of a tree data structure. The lowest level bounding volumes are connected to
parent nodes in the data structure, each of which has its own bounding volume. The
bounding volume for a parent node is big enough to enclose all the objects descended
from it.
We could calculate the bounding box at each level in the hierarchy so it best fits
the object contained within it. This would give us the best possible set of hierar-
chical volumes. Many times, however, we can take the simpler route of choosing a
bounding volume for a parent node that encompasses the bounding volumes of all its
descendents. This leads to larger high-level bounding volumes, but recalculation of
bounding volumes can be much faster. There is a tradeoff, therefore, between query
performance (determining potential collisions) and the speed of building the data
structure.
Figure 12.2 illustrates a hierarchy containing four objects and three layers. Note
that there are no objects attached to parent nodes in the figure. This isn't an absolute