Game Development Reference
In-Depth Information
bool isLeaf = (g_uNodes[nodeNum].iPrimCount & 4);
// Traverse the tree until we find a leaf node.
[allow_uav_condition]
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[0] > bestIntersection.t) ||
(hit[1] < 0.0f))
{
// does not intersect
// "Pop" node from trail.
trail = (trail >> p) + 1;
// Change to next node.
nodeNum = (nodeNum >> p) ˆ 1;
}
else
{
// "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
node's LSB to yield n = 110 2 and t = 111 2 ( Figure 1.3(g) ) . Node n = 110 2 is
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 .

Custom Search