Game Development Reference
In-Depth Information
F IGURE 12.2
A spherical bounding volume hierarchy.
requirement: we could have objects higher in the tree, providing their bounding vol-
ume completely encompasses their descendents. In most implementations, however,
objects are only found at the bottom. It is also common practice to have only two
children for each node in the tree (i.e., a binary tree data structure). There are mathe-
matical reasons for doing this (in terms of the speed of execution of collision queries),
but the best reason to use a binary tree is ease of implementation: it makes the data
structure compact and simplifies several of the algorithms we will meet later.
We can use the hierarchy to speed up collision detection: if the bounding volumes
of two nodes in the tree do not touch, then none of the objects that descend from
those nodes can possibly be in contact. By testing two bounding volumes high in the
hierarchy we can exclude all their descendents immediately.
If the two high-level nodes do touch, then the children of each node need to be
considered. Only combinations of these children that touch can have descendents
that are in contact. The hierarchy is descended recursively; at each stage only those
combinations of volumes that are touching are considered further. The algorithm
finally generates a list of potential contacts between objects. This list is exactly the
same as would have been produced by considering each possible pair of bounding
volumes, but it is typically found many times faster. 3
Assuming that the hierarchy encompasses all the objects in the game, the code to
get a list of potential collisions looks like the following:
3. I say typically because it is possible for the bounding hierarchy to be slower than checking all possible
combinations. If all the objects in the game are touching or nearly touching one another, then almost
every bounding volume check will come up positive. In this case the overhead of descending the hierarchy
adds time. Fortunately this situation occurs only rarely and when there are very few objects. With a larger
number of objects (more than ten, I would estimate; it depends on the shape of the objects), there are
checks that will fail, and the hierarchy becomes faster.