next up previous
Next: Optimizations for Bounding Volume Up: Efficiency Issues for Ray Previous: Compute Only What You

Overview of Bounding Volume Hierarchies

A bounding volume hierarchy is simply a tree of bounding volumes. The bounding volume at a given node encloses the bounding volumes of its children. The bounding volume of a leaf encloses a primitive. If a ray misses the bounding volume of a particular node, then the ray will miss all of its children, and the children can be skipped. The ray casting algorithm traverses this hierarchy, usually in depth first order, and determines if the ray intersects an object.

Figure 1: Building a bounding volume hierarchy recursively.
\begin{figure}
\center
\begin{pseudocode}
\PCBegin{BoundingVolume \PCFunction{Bu...
...,
end, axis)
\PC \PCKey{return} parent
\PCEnd{}
\end{pseudocode}\end{figure}

There are several ways of building bounding volume hierarchies [6,10]. The simplest way to build them is to take a list of bounding volumes containing the primitives and sort along an axis[8]. Split the list in half, put a bounding box around each half, and then recurse, cycling through the axes as you recurse. This is expressed in pseudocode in Figure 1. This method can be modified in many ways to produce better hierarchies. A better way to build the hierarchy is to try to minimize the cost functions described by Goldsmith and Salmon [6].


next up previous
Next: Optimizations for Bounding Volume Up: Efficiency Issues for Ray Previous: Compute Only What You
Comments: Brian Smits
1999-02-19