Game Development Reference

In-Depth Information

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.

1.4.2 Traversal

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

node.

•

If a function similar to
firstbithigh
is not available, the following formula

canbeusedinstead:

n
+1

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).

Search Nedrilad ::

Custom Search