Game Development Reference
Generate AABBs for each node. Finally, after the tree is completely built, the
AABBs for each node are computed. Contrary to the previous step, the tree is
now traversed in a bottom-up fashion. This step considers two type of nodes:
internal nodes and leaf nodes. If the node is leaf, then the box is built using the
box of each primitive. If the node is internal, then the thread takes the boxes
of both left and right nodes to create a new box. Using this approach, race
conditions are avoided and no synchronization barriers are needed.
The traversal algorithm has two important characteristics: it uses a bit trail
instead of a stack, and ray traversal restarts on the last node hit (instead of the
root). As far as the authors know, the SLBVH is the first algorithm that uses a
heap representation and arithmetic operations in order to avoid the use of stacks
and pointers. The traversal is similar to a classical BVH. A ray is casted through
the scene. The ray performs ray-box intersection tests until it reaches a node
marked as leaf. At that point, the ray performs ray-primitive intersection tests
and stores the closest intersection to the camera. The difference relies on how the
ray visits the next node and on how the ray comes back to a previous nonvisited
node. The algorithm stops if the ray comes back to the root. This means that
the ray cannot find more intersections.
The trail, which is a “hidden” stack, is a 32-bit integer. Each bit in the trail
represents a level on the tree. Each bit in the trail has the following meanings:
bit = 0. The level on the current subtree contains unvisited nodes. They
might be on either the left or the right branches.
bit = 1. All nodes in the current level of the subtree have been visited.
The initial value of trail is 1 << firstbithigh(nodeNum) .
The firstbithigh function is an intrinsic DirectX function available in
Shader Model 5. It returns the location of the first bit set starting from the
highest-order bit and working downwards.
The output of the firstbithigh function returns the depth of the current
If a function similar to firstbithigh is not available, the following formula
n )&( n +1) ,
where n is nodeNum and & is the bitwise AND operator.
(( n +1)
nodeNum is the last hit node. It is initially set to 1 (the root).