A bounding interval hierarchy (BIH) is a partitioning data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

 similar to that of bounding volume hierarchies

Bounding volume hierarchy

A bounding volume hierarchy is a tree structure on a set of geometric objects. 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 within larger bounding volumes...

 or kd-tree

Kd-tree

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...

s. 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 , presented by Ooi et al., and BoxTrees , independently invented by Zachmann.

Overview

Bounding interval hierarchies (BIH) exhibit many of the properties of both bounding volume hierarchies

Bounding volume hierarchy

A bounding volume hierarchy is a tree structure on a set of geometric objects. 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 within larger bounding volumes...

 (BVH) and kd-tree

Kd-tree

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...

s. Whereas the construction and storage of BIH is comparable to that of BVH, the traversal of BIH resemble that of kd-tree

Kd-tree

In computer science, a k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key...

s. Furthermore, BIH are also binary tree

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...

s just 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.

The key feature of the BIH is the storage of 2 planes per node (as opposed to 1 for the kd tree and 6 for an axis aligned bounding box hierarchy), which allows for overlapping children (just like a BVH), but at the same time featuring an order on the children along one dimension/axis (as it is the case for kd trees).

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

Cache

In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...

 usage low.

Some general attributes of bounding interval hierarchies (and techniques related to BIH) as described by 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

Construction

To construct any space partitioning

Space partitioning

In mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions...

 structure some form of heuristic

Heuristic

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...

 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:

• calculate the scene bounding box
• use a heuristic to choose one axis and a split plane candidate perpendicular to this axis
• sort the objects to the left or right child (exclusively) depending on the bounding box of the object (note that objects intersecting the split plane may either be sorted by its overlap with the child volumes or any other heuristic)
• calculate the maximum bounding value of all objects on the left and the minimum bounding value of those on the right for that axis (can be combined with previous step for some heuristics)
• store these 2 values along with 2 bits encoding the split axis in a new node
• continue with step 2 for the children

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 (results in a leftist tree which is often unfortunate for ray tracing though)
• Global heuristic: pick the split plane based on a global criterion, in the form of a regular grid (avoids unnecessary splits and keeps node volumes as cubic as possible)
• Surface area heuristic: calculate the surface area and amount of objects for both children, over the set of all possible split plane candidates, then choose the one with the lowest costs (claimed to be optimal, though the cost function poses unusual demands to proof the formula, which can not be fulfilled in real life. also an exceptionally slow heuristic to evaluate)

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

Stack (data structure)

In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the 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.

It is also possible to add a 5th 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 off empty 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

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.

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 (one and four planes per node were already proposed in and then properly evaluated in ) to achieve better object separation.