Bounding Volume Hierarchies - Real-Time Collision Detection - page 278

6.6.7 Grouping Queries
In games it is not uncommon to have a number of test queries originating from the
same general area. A common example is testing the wheels of a vehicle for collision
with the ground. Ideally, these queries can be prearranged into a hierarchy, allowing
any of the previously described traversal methods to be used. However, in some cases
it may be impractical to precompute a hierarchy. In the vehicle example, this is true
perhaps because the vehicle morphs between various drastically different shapes,
with bits potentially blown off.
Now if the wheels are tested for collision independently, because the vehicle is
small with respect to the world the query traversals through the topmost part of
the world hierarchy will most likely be the same. As such, it is beneficial to move
all queries together through the world hierarchy up until the point where they start
branching out into different parts of the tree.
One approach is to compute a hierarchy dynamically for the query objects, which
will automatically move the objects as one. For just a few objects, such as four wheels,
this is probably overkill. Instead, the objects can simply be grouped within a single
bounding volume. This volume is then “dropped down” the hierarchy it is tested
against until it reaches a node where it would have to be dropped down both chil-
dren. At this point in the tree the current node can effectively be used as an alternative
root node for the individual collision queries of the objects with the world hierar-
chy. Assuming the original individual queries were spheres tested against a world
hierarchy, this would appear as follows.
Sphere s[NUM_SPHERES];
...
for(inti=0;i<NUM_SPHERES; i++)
if (SphereTreeCollision(s[i], worldHierarchy))
...
A simple addition to the SphereTreeCollision() routine allows an alternative start
node to be used for the test.
bool SphereTreeCollision(Sphere s, Tree *root)
{
// If an alternative start node has been set, use it;
// if not, use the provided start root node
if (gStartNode != NULL) root = gStartNode;
...original code goes here...
}