Graphics Reference
In-Depth Information
void BVHCollision(CollisionResult *r, BVTree a, BVTree b)
{
if (!BVOverlap(a, b)) return;
if (!IsLeaf(a)) {
BVHCollision(a-
>
left, b);
BVHCollision(a->right, b);
} else {
a2 = TransformLeafContentsOnce(a);
BVHCollision2(r, a2, b);
}
}
// The support routine takes what is known to be a leaf and a full
// hierarchy, recursing over the hierarchy, performing the low-level
// leaf-leaf collision tests once the hierarchy leaves are reached
void BVHCollision2(CollisionResult *r, BVTree a, BVTree b)
{
if (!BVOverlap(a, b)) return;
if (!IsLeaf(b)) {
BVHCollision2(a, b-
>
left);
BVHCollision2(a, b-
>
right);
} else {
// At leaf nodes. Perform collision tests on leaf node contents
CollidePrimitives(r, a, b);
}
}
6.4
Sample Bounding Volume Hierarchies
The hierarchy construction methods described earlier in this chapter are all generic
in the sense that they apply to any type of bounding volume. To further illustrate how
they can be used, this section elaborates on a few specific methods suggested in the
literature and used in actual systems. These should not be interpreted as the final
word on any one technique, merely as one way of implementing something.
6.4.1
OBB Trees
The OBB-tree hierarchy construction method presented in [Gottschalk96] proceeds
in a top-down fashion. Initially a tight-fitting OBB is obtained for the original set of
primitives. The OBB is fitted by aligning the box axes with the eigenvectors computed
from the continuous formulation of covariance computed across the whole faces of
the primitives, as described in Section 4.4.3. Given this box, the set is partitioned by
