Graphics Reference
In-Depth Information
data sets, hybrid approaches such as a grid of trees is likely to be more effective than
a single tree hierarchy. Hybrid approaches are discussed in Section 7.3.8.
6.3.2
Generic Informed Depth-first Traversal
Many descent rules can be handled by a simple procedure that recurses over the two
hierarchies. First, if their top bounding volumes do not overlap the procedure just
returns. If not, then if both supplied nodes are leaf nodes the low-level routine for
colliding the contained geometry is called. Otherwise, the descent rule is evaluated
and the code is recursively called for the child nodes of the hierarchy selected by the
rule to descend into. Directly translated into code, this becomes:
1
// Generic recursive BVH traversal code.
// Assumes that leaves too have BVs
void BVHCollision(CollisionResult *r, BVTree a, BVTree b)
{
if (!BVOverlap(a, b)) return;
if (IsLeaf(a) && IsLeaf(b)) {
// At leaf nodes. Perform collision tests on leaf node contents
CollidePrimitives(r, a, b);
} else {
if (DescendA(a, b)) {
BVHCollision(a->left, b);
BVHCollision(a->right, b);
} else {
BVHCollision(a, b->left);
BVHCollision(a, b-
>
right);
}
}
}
In the code, the function
BVOverlap()
determines the overlap between two bounding
volumes.
IsLeaf()
returns true if its argument is a leaf node and not an internal
node.
CollidePrimitives()
collides all contained primitives against one another,
accumulating any reported collisions to the supplied
CollisionResult
structure.
DescendA()
implements the descent rule, and returns true if object hierarchy
A
should be descended or false for object hierarchy
B
. It is important that this routine
correctly deal with cases in which the leaves of
A
and
B
have been reached, so that
an attempt to traverse into a leaf is not made. The descent rules of “descend
A
,”
1.
The code format used here is inspired by [Gottschalk00].
