Multi-pivot Bounding Interval Hierarchy

TitleMulti-pivot Bounding Interval Hierarchy
Publication TypeConference Paper
Year of Publication2014
AuthorsBukošek, A., and A. Brodnik
Conference NamePICACSA
Date Published06/2014
PublisherFRI
Keywordsbounding interval hierarchy, multi-pivot, path tracing, ray tracing, spatial indexing
Abstract

This paper introduces a potentially faster way of constructing the bounding interval hierarchy (BIH).  The BIH is a spatial indexing structure used to accelerate ray tracing; the algorithm for its construction resembles quicksort.  Recent improvements to the quicksort algorithm have shown that using two or three pivots instead of one gives better performance due to better cache utilisation.  We apply these findings to the construction of the BIH by extending it to use two or three pivots.  We provide a methodology for measuring the performance of BIH construction and rendering, and outline an empirical evaluation and comparison of our modifications versus the original BIH algorithm using the described methodology.