Fast Insertion-Based Optimization of Bounding Volume Hierarchies

• Published in: Computer graphics forum 2013-02, Vol.32 (1), p.85-100
• Main Authors: Bittner, Jiří, Hapala, Michal, Havran, Vlastimil
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; BVH; Computer graphics; Construction costs; Cost engineering; Heuristic; Hierarchies; I.3.7[Computer Graphics]: Three-Dimensional Graphics and Realism-Ray Tracing; Image processing systems; Insertion; Optimization; Optimization algorithms; ray tracing; Studies; Surface area; surface area heuristics
• ISSN: 0167-7055; 1467-8659
• DOI: 10.1111/cgf.12000

We present an algorithm for fast optimization of bounding volume hierarchies (BVH) for efficient ray tracing. We perform selective updates of the hierarchy driven by the cost model derived from the surface area heuristic. In each step, the algorithm updates a fraction of the hierarchy nodes to minimize the overall hierarchy cost. The updates are realized by simple operations on the tree nodes: removal, search and insertion. Our method can quickly reduce the cost of the hierarchy constructed by the traditional techniques, such as the surface area heuristic. We evaluate the properties of the proposed method on fourteen test scenes of different complexity including individual objects and architectural scenes. The results show that our method can improve a BVH initially constructed with the surface area heuristic by up to 27% and a BVH constructed with the spatial median split by up to 88%. We present an algorithm for fast optimization of bounding volume hierarchies (BVH) for efficient ray tracing. We perform selective updates of the hierarchy driven by the cost model derived from the surface area heuristic. In each step the algorithm updates a fraction of the hierarchy nodes in order to minimize the overall hierarchy cost. The updates are realized by simple operations on the tree nodes: removal, search, and insertion. Our method can quickly reduce the cost of the hierarchy constructed by the traditional techniques such as the surface area heuristic. We evaluate the properties of the proposed method on fourteen test scenes of different complexity including individual objects and architectural scenes. The results show that our method can improve a BVH initially constructed with the surface area heuristic by up to 27% and a BVH constructed with the spatial median split by up to 88%.