A survey of algorithms for construction of optimal Heterogeneous Bounding Volume Hierarchies

In this paper we describe algorithms for automatic ob-ject hierarchy construction. We also describe a set of properties that hierarchies must possess to be consid-ered optimal. Based on knowledge from existing algo-rithms we develop and evaluate a Branch and Bound construction algorithm that searches for good hierar-chies, but due to computation time, not the globally optimal hierarchy. The algorithm is designed to con-struct hierarchies used for collision detection. This is controlled by a heuristic- and cost function. The hierarchy data structure built by the algorithm is the Approximating Hybrid Bounding Volume Hierarchy. It has nodes with varying branching factors, multiple bounding geometry types and approximating geome-tries in the leaf nodes