@conference{9,
  keywords = {bounding interval hierarchy, multi-pivot, path tracing, ray tracing, spatial indexing},
  author = {Andrej Bukošek and Andrej Brodnik},
  title = {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 = {2014},
  journal = {PICACSA},
  month = {06/2014},
  publisher = {University of Ljubljana, Faculty of Computer and Information Science},
  address = {Ljubljana},
  language = {eng},
}