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