Bounding interval hierarchy
A bounding interval hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance (or real-time) ray tracing and may be especially useful for dynamic scenes.
The BIH itself is, however, not new. It has been presented earlier under the name of SKD-Trees [1], presented by Ooi et al., and BoxTrees [2], independently invented by Zachmann.
Overview
Bounding interval hierarchies (BIH) exhibit many of the properties of both bounding volume hierarchies (BVH) and kd-trees. Whereas the construction and storage of BIH is similar to that of BVH, the traversal of a BIH resembles that of kd-trees. Furthermore, BIH are also binary trees like kd-trees (and in fact their superset, BSP trees). Finally, BIH are axis-aligned as are its ancestors. Although a more general non-axis-aligned implementation of the BIH should be possible (similar to the BSP-tree, which uses unaligned planes), it would almost certainly be less desirable due to decreased numerical stability and an increase in the complexity of ray traversal.
It is also possible to just use the BIH datastructure for the construction phase but traverse the tree in a way a traditional axis aligned bounding box hierarchy does. This enables some simple speed up optimizations for large ray bundles [3] while keeping memory/cache usage low.
Some general attributes of bounding interval hierarchies (and techniques related to BIH) as described by [4] are:
- Very fast construction times
- Low memory footprint
- Simple and fast traversal
- Very simple construction and traversal algorithms
- High numerical precision during construction and traversal
- Flatter tree structure (decreased tree depth) compared to kd-trees
Operations
Construction
To construct any space partitioning structure some form of heuristic is commonly used. For this the surface area heuristic, commonly used with many partitioning schemes, is a possible candidate. Another simple heuristic is the "global" heuristic described by [4] which only requires an axis-aligned bounding box, rather than the full set of primitives, making it much more suitable for fast construction.
Ray traversal
The traversal phase closely resembles a kd-tree traversal: One has to distinguish 4 simple cases, where the ray
- just intersects the left child
- just intersects the right child
- intersects both children
- intersects none of both (the only case not possible in a kd traversal)
For the third case, depending on the ray direction (negative or positive) of the component (x,y or z) equalling the split axis of the current node, the traversal continues first with the left (positive direction) or the right (negative direction) child and the other one is pushed onto a stack.
Traversal continues until a leaf node is found. After intersecting the objects in the leaf, the next element is popped from the stack. If the stack is empty, the nearest intersection of all pierced leafs is returned.
Properties
Numerical Stability
All operations during the hierarchy construction/sorting of the triangles are min/max-operations and comparisons. Thus no triangle clipping has to be done as it is the case with kd-trees and which can become a problem for triangles that just slightly intersect a node. Even if the kd implementation is carefully written, numerical errors can result in a non-detected intersection and thus rendering errors (holes in the geometry) due to the missed ray-object intersection.
See also
References
Papers
- ^ Nam, Beomseok; Sussman, Alan. A comparative study of spatial indexing techniques for multidimensional scientific datasets
- ^ Zachmann, Gabriel. Minimal Hierarchical Collision Detection
- ^ Wald, Ingo; Boulos, Solomon; Shirley, Peter (2007). Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies
- ^ a b Wächter, Carsten; Keller, Alexander (2006). Instant Ray Tracing: The Bounding Interval Hierarchy