A Bounding Volume Hierarchy (BVH) is a tree structure on a set of geometric objects like a 3D configurator. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed in larger sets. These in turn are also grouped recursively and included in other larger boundary volumes, resulting in a tree structure with a single boundary volume at the top of the tree. Volume boundary hierarchies are used to efficiently support multiple operations on sets of geometric objects, such as collision detection and raytracing.

What is a Bounding Volume Hierarchy?

Although wrapping objects in bounding volumes and performing collision tests before testing the object geometry itself can simplify the tests and lead to significant performance improvements, the same number of paired tests are still performed between bounding volumes. By arranging the bounding volumes in a bounding volume hierarchy, the time complexity in the number of objects can be reduced to logarithmic. If such a hierarchy exists, collision testing does not require subordinate volumes to be examined if their parent volumes are not cut.

BVH design themes.

The choice of bound volume is determined by a compromise between two targets. On the one hand, we want to use boundary bands that have a very simple shape. So we only need a few bytes to store them. In addition, cut tests and distance calculations are simple and fast. On the other hand, we would like to have bounding volumes that fit very closely to the corresponding data objects. One of the most commonly used bounding volumes is an axially parallel minimum bounding frame. The axis-oriented minimum boundary box for a given set of data objects is easy to calculate, requires only a few bytes of memory, robust cut tests are easy to implement, and extremely fast.

There are several desired properties for a BVH that should be considered when designing for a particular application.

  • The nodes contained in a particular subtree should be close together. The further down the tree, the closer the nodes should be to each other.
  • Each node in the BVH should have a minimum volume.
  • The sum of all limiting volumes should be minimal.
  • More attention should be paid to the node near the root of the BVH.
  • If you prune a node near the root of the tree, more objects will be removed from further consideration.
  • The overlap volume of the sibling nodes should be minimal.
  • The BVH should be balanced both in its node structure and in its contents. When balancing, as much of the BVH as possible can be cut if a branch is not crossed.

With regard to the structure of the BVH, it must be decided to what extent (number of children) and in what size the tree representing the BVH should be used. A tree of small degree will be of larger height. This increases the traversal time from root to leaf. On the other hand, each node visited requires less work to check its children for overlaps. The opposite is true for a high-grade tree: although the tree has a lower height, more work is required at each node. In practice, binary trees (grade = 2) are by far the most common. One of the main reasons is that binary trees are easier to create.

Erhöhen Sie Ihr Verkaufsvolumen.

Mit unseren 3D-Konfiguratoren erreichen Sie mehr kommerziellen Erfolg auf Website..

Jetzt beraten lassen

Structure.

There are three main categories of tree building methods: top-down, bottom-up, and insert methods.

Top-down methods go so far as to partition the input set into two (or more) subsets, limit them in the selected boundary volume, and then partition them recursively until each subset consists of only a single primitive (leaf nodes are reached). Top-down methods are easy to implement, quick to construct, and by far the most popular, but do not lead to the best possible trees in general.

Bottom-up methods start with the input record as leaves of the tree and then group two of them into a new (internal) node, proceeding in the same way until everything is grouped under a single node. Bottom-up methods are more difficult to implement, but are generally likely to produce better trees. Some recent studies suggest that the construction speed in low-dimensional space can be significantly improved (equal to or superior to the top-down approaches) by sorting objects by the space fill curve and approximately bundling them based on this sequential order.

Both top-down and bottom-up methods are considered offline because they both require all primitives to be available before construction begins. Insert methods build the tree by inserting one object after another, starting with an empty tree. The insertion position should be chosen so that the tree grows as little as possible after a cost key figure. Insertion methods are considered to be online methods because they do not require all primitives to be available before construction begins and therefore updates can be performed at runtime.

Use.

BVHs are often used in ray tracing to eliminate potential intersection candidates within a scene by omitting geometric objects in limited volumes that are not intersected by the current beam.

I hope that we can offer them a first introduction to this topic. If you have any comments or questions on this topic, please feel free to contact our experts via our forum.

Thank you very much for your visit.