Object partitioning considered harmful: Space subdivision for BVHs

Stefan Popov, Iliyan Georgiev, Rossen Dimov, Philipp Slusallek
ACM Conference on High Performance Graphics (HPG) 2009

Left: An extreme case where the centroids of all objects in a node coincide. While KD tree construction a) will be able to partition the set, classic BVH construction b) will have to create a leaf node, even though it would be more optimal to create two children nested in each other. Right: Our hybrid BVH construction algorithm c) can perform spatial splits similarly to KD tree construction. A triangle is split by clipping it to the child AABBs.

Abstract

A major factor for the efficiency of ray tracing is the use of good acceleration structures. Recently, bounding volume hierarchies (BVHs) have become the preferred acceleration structures, due to their competitive performance and greater flexibility compared to KD trees. In this paper, we present a study on algorithms for the construction of optimal BVHs.

Due to the exponential nature of the problem, constructing optimal BVHs for ray tracing remains an open topic. By exploiting the linearity of the surface area heuristic (SAH), we develop an algorithm that can find optimal splits in polynomial time. We further generalize this algorithm and show that every SAH-based KD tree or BVH construction algorithm is a special case of the generic algorithm.

Based on a number of experiments with the generic algorithm, we conclude that the assumption of non-terminating rays in the surface area cost model becomes a major obstacle for using the full potential of BVHs. We also observe that enforcing space partitioning helps to overcome this limitation. Finally, we develop a simple space partitioning algorithm for building efficient BVHs.

Downloads and links

BibTeX reference

@inproceedings{Popov:2009:SpatialBVH,
  author = {Popov, Stefan and Georgiev, Iliyan and Dimov, Rossen and Slusallek, Philipp},
  title = {Object partitioning considered harmful: space subdivision for BVHs},
  booktitle = {HPG '09: Proceedings of the 1st ACM conference on High Performance Graphics},
  year = {2009},
  isbn = {978-1-60558-603-8},
  pages = {15--22},
  location = {New Orleans, Louisiana},
  doi = {http://doi.acm.org/10.1145/1572769.1572772},
  publisher = {ACM},
  address = {New York, NY, USA},
}