Graphics Reference
In-Depth Information
“descend
B
,” and “descend larger” can easily be implemented in this framework as
follows.
// 'Descend A' descent rule
bool DescendA(BVTree a, BVTree b)
{
return !IsLeaf(a);
}
// 'Descend B' descent rule
bool DescendA(BVTree a, BVTree b)
{
return IsLeaf(b);
}
// 'Descend larger' descent rule
bool DescendA(BVTree a, BVTree b)
{
return IsLeaf(b) || (!IsLeaf(a) && (SizeOfBV(a) >= SizeOfBV(b)));
}
Although the recursive version of the traversal code is quite easy to read and under-
stand, it is not the most effective form of the code. An iterative version with explicit
stacking of variables avoids the overhead of the recursive function calls. More
importantly, it allows the code to exit early if just a single contact point is sought.
The iterative version follows. Note that to traverse the tree in the same order
as the recursive version of the code, pushes to the stack must be given in reverse
order.
// Non-recursive version
void BVHCollision(CollisionResult *r, BVTree a, BVTree b)
{
Stack s = NULL;
Push(s, a, b);
while (!IsEmpty(s)) {
Pop(s, a, b);
if (!BVOverlap(a, b)) continue;
if (IsLeaf(a) && IsLeaf(b)) {
// At leaf nodes. Perform collision tests on leaf node contents
CollidePrimitives(r, a, b);
// Could have an exit rule here (eg. exit on first hit)
