A bounding interval hierarchy is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance ray tracing and may be especially useful for dynamic scenes. The BIH was first presented under the name of SKD-Trees, presented by Ooi et al., and BoxTrees, independently invented by Zachmann.
Overview
Bounding interval hierarchies exhibit many of the properties of both bounding volume hierarchies and kd-trees. Whereas the construction and storage of BIH is comparable to that of BVH, the traversal of BIH resemble that of kd-trees. Furthermore, BIH are also binary trees just like kd-trees. Finally, BIH are axis-aligned as are its ancestors. Although a more general non-axis-aligned implementation of the BIH should be possible, it would almost certainly be less desirable due to decreased numerical stability and an increase in the complexity of ray traversal. The key feature of the BIH is the storage of 2 planes per node, which allows for overlapping children, but at the same time featuring an order on the children along one dimension/axis. It is also possible to just use the BIH data structure 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 while keeping memory/cache usage low. Some general attributes of bounding interval hierarchies as described by are:
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, more simplistic heuristic is the "global" heuristic described by which only requires an axis-aligned bounding box, rather than the full set of primitives, making it much more suitable for a fast construction. The general construction scheme for a BIH:
Potential heuristics for the split plane candidate search:
Classical: pick the longest axis and the middle of the node bounding box on that axis
Classical: pick the longest axis and a split plane through the median of the objects
Global heuristic: pick the split plane based on a global criterion, in the form of a regular grid
Surface area heuristic: calculate the surface area and number of objects for both children, over the set of all possible split plane candidates, then choose the one with the lowest costs
Ray traversal
The traversal phase closely resembles a kd-tree traversal: One has to distinguish four simple cases, where the ray
For the third case, depending on the ray direction of the component equalling the split axis of the current node, the traversal continues first with the left or the right child and the other one is pushed onto a stack for deferred potential traversal. Traversal continues until a leaf node is found. After intersecting the objects in the leaf, the next traversal element is popped from the stack. If the stack is empty, the nearest intersection of all pierced leaves is returned. If the popped element is entirely beyond the current nearest intersection, its traversal is skipped. It is also possible to add a fifth traversal case, but which also requires a slightly complicated construction phase. By swapping the meanings of the left and right plane of a node, it is possible to cut offempty space on both sides of a node. This requires an additional bit that must be stored in the node to detect this special case during traversal. Handling this case during the traversal phase is simple, as the ray
just intersects the only child of the current node or
intersects nothing
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 due to the missed ray-object intersection.
Extensions
Instead of using two planes per node to separate geometry, it is also possible to use any number of planes to create a n-ary BIH or use multiple planes in a standard binary BIH to achieve better object separation.
