Game Development Reference
In-Depth Information
12.3.3
S UB -O BJECT H IERARCHIES
Some objects you'll need to simulate are large or have awkward shapes. It is difficult
to create any simple bounding volume that fits tightly around such objects. For any
particular bounding volume shape, there will be additional objects that simply don't
suit that format. In each case the bounding volume is too large and the coarse collision
detector will return too many false positives.
To solve this problem it is possible to use multiple bounding volumes for one
object, arranged in a hierarchy. In figure 12.8 we have a long, thin object with a pro-
trusion. Neither the bounding box nor the sphere fits nicely around it. If we use a hi-
erarchy of bounding objects, we can provide a much closer fit. In this case the bound-
ing boxes provide a better fit, although using a hierarchy of lots of bounding spheres
arranged along its length would also work.
The algorithm for detecting collisions is the same as for the single-object hier-
archical bounding volume. Rather than stopping at the bounding volume for the
whole object, we can perform a finer-grained set of checks while still using the simple
bounding volume comparison.
The same process allows us to build a hierarchy for the game level itself. Clearly
most game levels are so large that their bounding volume is likely to encompass all
other objects (although outdoor levels represented as a box can exclude objects at a
high altitude).
To get a better fit we can decompose the level into a hierarchy of bounding
volumes. Because of the boxlike structure of most game levels (rectangular walls,
flat floors, and so on), a bounding box hierarchy is typically better than bounding
spheres.
Whilethisisacceptable,providesgoodperformance,andhasbeenusedinsome
games, a more popular approach is to use a spatial data structure to work out colli-
sions with the game level.
F IGURE 12.8
A sub-object bounding volume hierarchy.