Graphics Reference
In-Depth Information
Chapter
6
Bounding Volume
Hierarchies
Wrapping objects in bounding volumes and performing tests on the bounding
volumes before testing the object geometry itself can result in significant perfor-
mance improvements. However, although the tests themselves have been simplified,
the same number of pairwise tests are still being performed. The asymptotic time
complexity remains the same and the use of bounding volumes improves the situa-
tion by a constant factor. By arranging the bounding volumes into a tree hierarchy
called a
bounding volume hierarchy
(BVH), the time complexity can be reduced to
logarithmic in the number of tests performed.
The original set of bounding volumes forms the leaf nodes of the tree that is this
bounding volume hierarchy. These nodes are then grouped as small sets and enclosed
within larger bounding volumes. These, in turn, are also grouped and enclosed within
other larger bounding volumes in a recursive fashion, eventually resulting in a tree
structure with a single bounding volume at the top of the tree. Figure 6.1 shows a
small AABB hierarchy constructed from five objects.
With a hierarchy in place, during collision testing children do not have to be exam-
ined if their parent volume is not intersected. The same bounding volume hierarchies
are also used, for instance, in scene graphs and ray tracing and for view-frustum
culling.
Comparing bounding volume hierarchies with spatial partitioning schemes (see
Chapter 7), the main differences are that two or more volumes in a BVH can cover the
same space and objects are generally only inserted in a single volume. In contrast, in
a spatial partitioning scheme the partitions are disjoint and objects contained in the
spatial partitioning are typically allowed to be represented in two or more partitions.
It is important to note that the bounding volume of a parent node does not neces-
sarily need to enclose the bounding volumes of its child nodes. Although it is often
easier to construct hierarchies in which this parent-child property holds true, the
parent bounding volume needs to enclose only the object primitives contained in the
subtrees of its children.
235
