Геометриялық нысандарды ұйымдастыру: Шекаралық көлем иерархиясы

Graphics structure

A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, which form the leaf nodes of the tree, are wrapped in bounding volumes. 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. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing. 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 (the number of tests performed) can be reduced to logarithmic in the number of objects. With such a hierarchy in place, during collision testing, children volumes do not have to be examined if their parent volumes are not intersected (for example, if the bounding volumes of two bumper cars do not intersect, the bounding volumes of the bumpers themselves would not have to be checked for collision).

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. Some recent studies indicate that in low dimensional space, the construction speed can be largely improved (which matches or outperforms the top down approaches) by sorting objects using space filling curve and applying approximate clustering based on this sequential order. 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.

BVHs are often used in ray tracing to eliminate potential intersection candidates within a scene by omitting geometric objects located in bounding volumes which are not intersected by the current ray. Additionally, as common performance optimization, when only closest intersection of the ray is of interest, as the ray tracing traversal algorithm is descending nodes, and multiple child nodes are intersecting the ray, traversal algorithm will consider the closer volume first, and if it finds intersection there, which is definitively closer than any possible intersection in second (or other) volume (i. e. volumes are non overlapping), it can safely ignore the second volume. Similar optimizations during BVH traversal can be employed when descending into child volumes of the second volume, to restrict further search space and thus reduce traversal time. Additionally, many specialized methods were developed for BVHs, especially ones based on AABB (axis aligned bounding boxes), such as parallel building, SIMD accelerated traversal, good split heuristics (SAH surface area heuristic is often used in ray tracing), wide trees (4 ary and 16 ary trees provide some performance benefits, both in build and query performance for practical scenes), and quick structure update (in real time applications objects might be moving or deforming spatially relatively slowly or be still, and same BVH can be updated to be still valid without doing a full rebuild from scratch). BVHs also naturally support inserting and removing objects without full rebuild, but with resulting BVH having usually worse query performance compared to full rebuild. To solve these problems (as well as quick structure update being sub optimal), the new BVH could be built asynchronously in parallel or synchronously, after sufficient change is detected (leaf overlap is big, number of insertions and removals crossed the threshold, and other more refined heuristics). BVHs can also be combined with scene graph methods, and geometry instancing, to reduce memory usage, improve structure update and full rebuild performance, as well as guide better object or primitive splitting.