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

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

sign = 1). We append 1 to the node and 0 to the trail, yielding
n
= 111
2
and

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
.

Search Nedrilad ::

Custom Search