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

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,

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,

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.

×

Search Nedrilad ::

Custom Search