next up previous
Next: Caching Objects Up: Optimizations for Bounding Volume Previous: Intersection Rays versus Shadow


Traversal Code

Figure 3: Three different representations for a tree. (a) Children pointers. (b) Left child, right sibling, parent pointers. (c) Array in depth-first order with skip pointers.
\includegraphics[width = 3in]{trees.ill}

Casting a ray against a bounding volume hierarchy requires traversing the hierarchy. If a ray hits a bounding volume, then the ray is checked against the children of the bounding volume. If the bounding volume is a leaf, then it has an object inside it, and the object is checked. This is done in depth-first order. Once bounding volume intersection tests are as fast as they can be, the next place for improvement is the traversal of the hierarchy. Traversal code for shadow rays will be used in the following discussion.

In 1991, Haines[7] published some techniques for better traversals. Several of these techniques used extra knowledge to mark bounding boxes as automatically hit and to change the order of traversal. In my experience these methods do not speed up the ray tracer and greatly increase the complexity of the code. This difference in experience may be due to changes in architecture over the last 8 years that make branches and memory accesses instead of floating point the bottleneck. It may also be due to faster bounding box tests. I have found that the best way to make the traversal fast is to make it as minimal as possible.

Figure 4: Traversal of bounding volume tree using left child, right sibling, parent structure.
\begin{figure}
\center
\begin{pseudocode}
\PCBegin{\PCFunction{TreeShadowTravers...
...
\PCEnd{if}
\PCEnd{while}
\PCEnd{while}
\PCEnd{}
\end{pseudocode}\end{figure}

The simplest traversal code is to use recursion to traverse the tree in depth-first order. Figure  3(a) shows a hierarchy of bounding boxes. Depth first traversal means that bounding box A is tested, then box B, then the boxes with primitives D, E, and F. The idea is to find an intersection as soon as possible by traveling down into the tree. The biggest problem with this is the function call overhead. The compiler maintains much more state information than we need here. We can eliminate much of this overhead by changing our representation of the tree. A representation that works well is to store the left-most child, the right sibling, and the parent for each node, as in Figure  3. Using this representation we can get rid of the recursion by following the appropriate pointers. If the ray intersects the bounding box, we get to its children by following the left-most child link. If the ray misses, we get to the next node by following the right sibling link. If the right sibling is empty, we move up until either there is a right sibling, or we get back up to the root, as shown in pseudocode in Figure 4.

This tree traversal also does too much work. Notice that when the traversal is at a leaf or when the ray misses a bounding volume, we compute the next node. The next node is always the same, there is no reason to be computing it for each traversal. We can pre-compute the node we go to when we skip this subtree and store this skip node in each node. This step eliminates all computation of traversal related data from the traversal. There are still intersection computations, but no extra computation for determining where to go. This is expressed in pseudocode in Figure 5

Figure 5: Traversal of bounding volume tree using left child, and skip pointers.
\begin{figure}
\center
\begin{pseudocode}
\PCBegin{\PCFunction{SkipTreeShadowTra...
...d{}
\PCEnd{while}
\PC \PCKey{return false}
\PCEnd{}
\end{pseudocode}\end{figure}

The final optimization is the recognition that we only need to do depth-first traversals on the tree once it is built. This observation lets us store the tree in an array in depth-first order as in Figure  3. If the bounding volume is intersected, the next node to try is the next node in the array. If the bounding volume is missed, the next node can be found through the skip mechanism. We have effectively thrown out all the information we don't need out of the tree, although it is still possible to reconstruct it. The traversal code can be seen in Figure 6.

The array traversal approach works significantly better than the previous one, and has a couple subtle advantages. The first is better memory usage. In addition to the bounding volume, this method requires only a pointer to a primitive and a pointer to the skip node. This is very minimal. Since the nodes are arranged in the order they will be accessed in, there is more memory coherency for large environments. The second advantage is that this method requires copying data from the original tree into an array. Since the original tree is going to be thrown out, it can be augmented with extra information. Depending upon how the tree is created, this extra information can more than double the cost of each node. Now there is no penalty for this information. Storing the extra information can reduce the time to build the tree and more importantly can result in better trees. The fastest bounding volume test is the one you don't have to do.

Figure 6: Traversal of bounding volume tree stored as an array in depth-first order.
\begin{figure}
\center
\begin{pseudocode}
\PCBegin{\PCFunction{ArrayShadowTraver...
...{}
\PCEnd{while}
\PC \PCKey{return false}
\PCEnd{}
\end{pseudocode}\end{figure}


next up previous
Next: Caching Objects Up: Optimizations for Bounding Volume Previous: Intersection Rays versus Shadow
Comments: Brian Smits
1999-02-19