Multi-pivot Bounding Interval Hierarchy

Abstract
<p>This paper introduces a potentially faster way of constructing the bounding interval hierarchy (BIH).&nbsp; The BIH is a spatial indexing structure used to accelerate ray tracing; the algorithm for its construction resembles quicksort.&nbsp; 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.&nbsp; We apply these findings to the construction of the BIH by extending it to use two or three pivots.&nbsp; 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.</p>
Year of Publication
2014
Secondary Title
PICACSA
Date Published
06/2014
Publication Language
eng
Publisher
University of Ljubljana, Faculty of Computer and Information Science
Place Published
Ljubljana
Citation Key
142