Tree rotations for improving bounding volume hierarchies

Current top-down algorithms for constructing bounding volume hierarchies (BVHs) using the surface area heuristic (SAH) rely on an estimate of the cost of the potential subtrees to determine how to partition the primitives. After a tree has been fully built, however, the true cost value at each node can be computed. We present two related algorithms that use this information to reduce the treepsilas total cost through a series of local adjustments (tree rotations) to its structure. The first algorithm uses a fast and simple hill climbing method and the second uses simulated annealing to obtain greater improvements by avoiding local minima. Both algorithms are easy to add to existing BVH implementations and are suitable for preprocessing static geometry for interactive ray tracing.