Bounding volume hierarchy
Encyclopedia
A bounding volume hierarchy (BVH) is a tree structure
on a set of geometric objects. All geometric objects are wrapped in bounding volume
s that form the leaf nodes of the tree. 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.
Although wrapping objects in bounding volumes and performing collision tests on them before testing the object geometry itself simplifies the tests and can result in significant performance improvements, the same number of pairwise tests between bounding volumes are still being performed. By arranging the bounding volumes into a bounding volume hierarchy, the time complexity can be reduced to logarithmic in the number of tests performed. With such a hierarchy in place, during collision testing, children do not have to be examined if their parent volumes are not intersected.
. The axis-aligned minimum bounding box for a given set of data objects is easy to compute, needs only few bytes of storage, and robust intersection tests are easy to implement and extremely fast.
There are several desired properties for a BVH that should be taken into consideration when designing one for a specific application:
In terms of the structure of BVH, we have to decide what degree (the number of children) and height to use in the tree representing the BVH. A tree of a higher degree will be of smaller height, minimizing root-to-leaf traversal time. In addition, the larger the degree, the fewer internal nodes are needed to form the tree. But at the same time, more work has to be expended at each visited node to check its children for overlap. The opposite holds for a low-degree tree: although the tree will be of greater height, less work is spent at each node. Looking at actual usage, it appears binary trees (degree = 2) are by far the most common hierarchical representation. An important reason is that binary trees are easier to build and, to some extent, to represent and traverse than other trees.
Tree structure
A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the...
on a set of geometric objects. All geometric objects are wrapped in bounding volume
Bounding volume
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex...
s that form the leaf nodes of the tree. 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.
Although wrapping objects in bounding volumes and performing collision tests on them before testing the object geometry itself simplifies the tests and can result in significant performance improvements, the same number of pairwise tests between bounding volumes are still being performed. By arranging the bounding volumes into a bounding volume hierarchy, the time complexity can be reduced to logarithmic in the number of tests performed. With such a hierarchy in place, during collision testing, children do not have to be examined if their parent volumes are not intersected.
BVH design issues
The choice of bounding volume is determined by a trade-off between two objectives. On the one hand, we would like to use bounding volumes that have a very simple shape. Thus, we need only a few bytes to store them, and intersection tests and distance computations are simple and fast. On the other hand, we would like to have bounding volumes that fit the corresponding data objects very tightly. One of the most commonly used bounding volumes is an axis-aligned minimum bounding boxMinimum bounding box
The minimum or smallest bounding or enclosing box for a point set in N dimensions is the box with the smallest measure within which all the points lie...
. The axis-aligned minimum bounding box for a given set of data objects is easy to compute, needs only few bytes of storage, and robust intersection tests are easy to implement and extremely fast.
There are several desired properties for a BVH that should be taken into consideration when designing one for a specific application:
- The nodes contained in any given sub-tree should be near each other. The lower down the tree, the nearer the nodes should be to each other.
- Each node in the BVH should be of minimum volume.
- The sum of all bounding volumes should be minimal.
- Greater attention should be paid to nodes near the root of the BVH. Pruning a node near the root of the tree removes more objects from further consideration.
- The volume of overlap of sibling nodes should be minimal.
- The BVH should be balanced with respect to both its node structure and its content. Balancing allows as much of the BVH as possible to be pruned whenever a branch is not traversed into.
In terms of the structure of BVH, we have to decide what degree (the number of children) and height to use in the tree representing the BVH. A tree of a higher degree will be of smaller height, minimizing root-to-leaf traversal time. In addition, the larger the degree, the fewer internal nodes are needed to form the tree. But at the same time, more work has to be expended at each visited node to check its children for overlap. The opposite holds for a low-degree tree: although the tree will be of greater height, less work is spent at each node. Looking at actual usage, it appears binary trees (degree = 2) are by far the most common hierarchical representation. An important reason is that binary trees are easier to build and, to some extent, to represent and traverse than other trees.
BVH construction
There are three primary categories of tree construction methods: top-down, bottom-up, and insertion methods. Top-down methods proceed by partitioning the input set into two (or more) subsets, bounding them in the chosen bounding volume, then keep partitioning (and bounding) recursively until each subset consists of only a single primitive (leaf nodes are reached). Top-down methods are easy to implement, fast to construct and by far the most popular, but do not result in the best possible trees in general. Bottom-up methods start with the input set as the leaves of the tree and then group two (or more) of them to form a new (internal) node, proceed in the same manner until everything has been grouped under a single node (the root of the tree). Bottom-up methods are more difficult to implement, but likely to produce better trees in general. Both top-down and bottom-up methods are considered off-line methods as they both require all primitives to be available before construction starts. Insertion methods build the tree by inserting one object at a time, starting from an empty tree. The insertion location should be chosen that causes the tree to grow as little as possible according to a cost metric. Insertion methods are considered on-line methods since they do not require all primitives to be available before construction starts and thus allow updates to be performed at runtime.See also
- Binary space partitioningBinary space partitioningIn computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...
, octreeOctreeAn octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
, k-d tree - R-treeR-treeR-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both research and real-world applications...
, R+-tree, R*-tree and X-treeX-treeIn computer science, an X-tree is an index tree structure based on the R-tree used for storing data in many dimensions. It differs from R-trees, R+-trees and R*-trees because it emphasizes prevention of overlap in the bounding boxes, which increasingly becomes a problem in high dimensions... - M-treeM-treeM-trees are tree data structures that are similar to R-trees and B-trees. It is constructed using a metric and relies on the triangle inequality for efficient range and k-NN queries....