Game Development Reference
bool isLeaf = (g_uNodes[nodeNum].iPrimCount & 4);
// Traverse the tree until we find a leaf node.
while ( !isLeaf )
hit = intersectBox(ray.vfOrigin, invDir, nodeNum);
p = firstbitlow(trail + 1);
// Intersection is better than the current one
// and it's not behind the camera.
if ((hit > bestIntersection.t) ||
(hit < 0.0f))
// does not intersect
// "Pop" node from trail.
trail = (trail >> p) + 1;
// Change to next node.
nodeNum = (nodeNum >> p) ˆ 1;
// "Push" node to trail.
trail = trail << 1;
int axis = g_uNodes[nodeNum].iPrimCount&3;
int direction = dirIsNeg[axis];
// Set next node to visit.
nodeNum = (nodeNum << 1) | direction );
// If we finish on the root, stop traversal.
if (trail <= 1) break ;
Listing 1.4. Setting the next node.
To find the next sibling, we add 1 to the trail, yielding t = 101 2 , and we count
the number of 0's starting from the LSB until we find a 1. In this case, there
are no trailing zeros, so we simply invert the node's LSB, yielding n = 100 2 and
t = 101 2 ( Figure 1.3(d) ). Node n = 100 2 is another leaf node. Assuming no
intersections, we again must find the next sibling. We add 1 to the trail yielding
t = 110 2 . In this case, we get 1 trailing 0, so we remove one bit from the node
and the trail and then invert the node's LSB, yielding n = 011 2 and t = 011 2
( Figure 1.3(e) ). Node n = 011 2 is internal with a split along the y -axis (negative
sign = 1). We append 1 to the node and 0 to the trail, yielding n = 111 2 and
t = 110 2 ( Figure 1.3(f) ). Node n = 111 2 is leaf. Assuming no intersections, we
add 1 to the trail to yield t = 111 2 . Since there are no trailing 0's, we invert the
leaf. Assuming no intersections, we again need to find the next sibling. Adding 1
to the trail yields t = 000 2 with three trailing 0's. Removing three bits from the
node and the trail, and inverting the node's LSB, yields n = 001 2 and t = 000 2
( Figure 1.3(h) ). We have returned to the root, so this is the end of the algorithm.
Listing 1.4 is the code for the walkthrough of Figure 1.3 .