Multi-pivot Bounding Interval Hierarchy

<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>