Bounding interval hierarchy

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[4] 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 number 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)

The traversal phase closely resembles a kd-tree traversal: One has to distinguish four simple cases, where the ray

• just intersects the left child
• just intersects the right child
• intersects both children
• intersects neither child (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 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 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

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.