Game Development Reference

In-Depth Information

some disadvantages since empty nodes must be stored (yet are never visited) in

order to satisfy the arithmetic operations that relate the nodes in the heap. On

the other hand, the memory footprint of the SLBVH is lower than other stackless

approaches [Popov et al. 07] since no extra information is stored in the tree; at the

same time, SLBVH has more advantages than similar BVH algorithms [Laine 10]

using a bit trail.

Besides the common properties of a heap, the SLBVH possesses the following

characteristics:

•

The root node is at position
i
= 1. The node at position
i
= 0 is invalid.

In this way, the arithmetic operations to traverse the tree are simpler.

•

The first right ancestor of node
n
is found by removing all the least signifi-

cant bits that are 0 in the binary notation of
n
.

•

The binary notation of an auxiliary 32-bit integer (the “trail”) can be used

to substitute the stack (commonly used to store the visited nodes during

ray traversal). Each bit represents one level in the tree. A 0 means that

the level still has unvisited nodes, while a 1 means that all nodes in that

level have already been visited.

The tree uses a breadth-first scheme. A depth-first construction scheme was

also considered, but the traversal formula becomes more complex and an extra

variable is needed to keep track of which side of the subtree is being traversed.

1.4.1 Construction

The size of each node is 32 bytes. Six 32-bit floats are stored per node repre-

senting an axis-aligned bounding box (AABB), two 32-bit integers storing the

number of primitives (
PrimCount
), and a primitive offset (
PrimPos
). Additionally,

PrimCount
stores the split axis and whether the node is leaf or internal, as shown

in Figure 1.2. The axis is stored on the two least-significant bits of
PrimCount
,

and the node flag (leaf = 1, internal = 0) is stored on its third least-significant

bit. Two bits are enough to store the axis and the flag, but this would increase

the number of comparisons when traversing the structure.

32

3

2

0

Number of Primitives

Axis

Is Leaf?

Figure 1.2.
Binary breakdown of the
PrimCount
variable. The two least-significant bits

are used to store the axis:
x
= 00,
y
= 01, and
z
= 10. The third least-significant bit is

used to mark a node as leaf. The rest of the bits store the number of primitives in that

node.

Search Nedrilad ::

Custom Search