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

} else {
if (DescendA(a, b)) {
Push(s, a->right, b);
Push(s, a->left, b);
} else {
Push(s, a, b- > right);
Push(s, a, b- > left);
}
}
}
}
Here, the functions Push() , Pop() , and IsEmpty() implement an abstract stack data
type. Studying the flow of the nonrecursive version, it soon becomes clear that unnec-
essary work is performed in pushing a new node pair onto the stack, only for it to be
immediately popped off during the next iteration of the main loop. The redundant
work can be avoided by slightly rearranging the code to allow the last stacked values
to be assigned directly to the variables instead.
// Stack-use optimized, non-recursive version
void BVHCollision(CollisionResult *r, BVTree a, BVTree b)
{
Stack s = NULL;
while (1) {
if (BVOverlap(a, b)) {
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)
} else {
if (DescendA(a, b)) {
Push(s, a- > right, b);
a=a- > left;
continue;
} else {
Push(s, a, b- > right);
b=b- > left;
continue;
}
}
}