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

if (IsEmpty(s)) break;
Pop(s, a, b);
}
}
All recursive traversal functions can be transformed into iterative versions in the
manner described here.
6.3.3 Simultaneous Depth-first Traversal
Simultaneous traversal cannot be directly handled by the previous framework.
Because both bounding volumes are descended into at the same time, instead of
two recursive calls there are now four for the node-node case. Code for simultaneous
traversal follows.
// Recursive, simultaneous traversal
void BVHCollision(CollisionResult *r, BVTree a, BVTree b)
{
if (!BVOverlap(a, b)) return;
if (IsLeaf(a)) {
if (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 {
BVHCollision(a, b->left);
BVHCollision(a, b->right);
}
} else {
if (IsLeaf(b)) {
BVHCollision(a- > left, b);
BVHCollision(a- > right, b);
} else {
BVHCollision(a- > left, b- > left);
BVHCollision(a- > left, b- > right);
BVHCollision(a- > right, b- > left);
BVHCollision(a- > right, b- > right);
}
}
}