Game Development Reference
In-Depth Information
After the first intersection is found, the traversal stores the intersected nodeNum
and it is passed to the next traversal iteration. The trail pushes nodes when an
internal node is intersected (just as a classical BVH) and pops nodes when either
an intersection was not found or when a leaf node is intersected. A push is
computed using a bitwise shift-left operation and a pop using a bitwise shift-right
operation.
The algorithm starts with both nodeNum and trail set to 1. When going down
the tree, the algorithm checks the ray's sign along the current split axis. If the
ray is positive, it appends a 0 to nodeNum and 1 otherwise. In this case, it also
appends a 0 to trail (because if the ray goes down the tree, that means that
there was an intersection, which is a push). It is also possible to check which of
the boxes is hit first by the ray (in case an intersection exists). If the left node is
hit first, a 0 should be “pushed” into nodeNum and a 1 otherwise.
When going up the tree, trail = trail + 1 ; and then the number n of con-
secutive 0's starting from the least significant bit (LSB) in trail is counted.
Next, the algorithm sets trail = trail >> n (which corresponds to a pop) and
nodeNum = nodeNum >> n . Finally, nodeNum 's LSB is inverted (to mark the other
branch as visited). The regular BVH traversal checks are also performed. At
each internal node, the ray is intersected with the current box. If there is an
intersection, we go “down” the tree. If there is no intersection, we go “up” the
tree. Traversal ends when nodeNum = 1 , which means that the ray returns to the
root and no intersections were found.
To illustrate the algorithm, let us walk through an example. Figure 1.3 shows
an SLBVH built with 3-bit codes. Each node in the tree is labeled with its index
(in binary notation) and, for internal nodes, the split axis is also specified. Note,
for instance, that the root is labeled 001 so the left child is 1
×
2 = 2 (010 2 )and
the right child is 1
2 + 1 = 3 (011 2 ). Figure 1.3 also shows the signs of an
example ray across each axis. In this case, we have a ray that is positive on the
x -axis and negative on the y -and z -axes. Positive signs for the ray map to 0 and
negative signs to 1. In order to illustrate a full traversal, we will assume that
no primitive intersections are found along the ray but all internal nodes intersect
the ray. In this way, we are forced to visit all the nodes.
Let n and t stand for the current node and the trail, respectively. Initially,
n = 001 2 and t = 001 2 ( Figure 1.3(a) ). The current node is the root and its
split axis is the x -axis (positive sign = 0), so the traversal appends a 0 to n ( n
is now 010 2 ). The trail is always appended with a 0 when going down. Thus, we
endupwith n = 010 2 and t = 010 2 (which means we went down the left child,
see Figure 1.3(b) ). For the current node ( n = 010 2 ), the split was done along
the z -axis (negative sign = 1), so we append a 1 to the current node ( n is now
101 2 )anda0tothetrail( t is now 100 2 ). We now have n = 101 2 and t = 100 2
(1.3(c)). Node n = 101 2 is leaf, so we test the primitives contained in it for an
intersection. Assuming no intersection was found, we need to “backtrack” to the
next sibling.
×