Bounding interval hierarchy

From Wikipedia, the free encyclopedia

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 (or real-time) ray tracing and may be especially useful for dynamic scenes.

1 Overview
2 Operations
- 2.1 Construction
- 2.2 Ray traversal
3 Properties
- 3.1 Numerical Stability
4 See also
5 References
- 5.1 Papers
- 5.2 Forums

[edit] 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.

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

[edit] Operations

[edit] 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 ^[1] which only requires an axis-aligned bounding box, rather than the full set of primitives, making it much more suitable for fast construction.