TY - CONF
KW - bounding interval hierarchy
KW - multi-pivot
KW - path tracing
KW - ray tracing
KW - spatial indexing
AU - Andrej Bukošek
AU - Andrej Brodnik
AB - <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>

CY - Ljubljana
LA - eng
N2 - <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>

PB - University of Ljubljana, Faculty of Computer and Information Science
PY - 2014
T2 - PICACSA
TI - Multi-pivot Bounding Interval Hierarchy
ER -