Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees

Ganestam, Per LU ; Barringer, Rasmus LU ; Doggett, Michael LU orcid and Akenine-Möller, Tomas LU (2015) In Journal of Computer Graphics Techniques 4(3). p.23-42
Abstract
We present an algorithm, called Bonsai, for rapidly building bounding volume hierarchies for ray tracing. Our method starts by computing midpoints of the triangle bounding boxes and then performs a rough hierarchical top-down split using the midpoints, creating triangle groups with tight bounding boxes. For each triangle group, a mini tree is built using an improved sweep SAH method. Once all mini trees have been built, we use them as leaves when building the top tree of the bounding volume hierarchy. We also introduce a novel and inexpensive optimization technique, called mini-tree pruning, that can be used to detect and improve poorly built parts of the tree. We achieve a little better than 100% in ray-tracing performance compared to a... (More)
We present an algorithm, called Bonsai, for rapidly building bounding volume hierarchies for ray tracing. Our method starts by computing midpoints of the triangle bounding boxes and then performs a rough hierarchical top-down split using the midpoints, creating triangle groups with tight bounding boxes. For each triangle group, a mini tree is built using an improved sweep SAH method. Once all mini trees have been built, we use them as leaves when building the top tree of the bounding volume hierarchy. We also introduce a novel and inexpensive optimization technique, called mini-tree pruning, that can be used to detect and improve poorly built parts of the tree. We achieve a little better than 100% in ray-tracing performance compared to a "ground truth" greedy top-down sweep SAH method, and our build times are the lowest we have seen with comparable tree quality. (Less)
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Journal of Computer Graphics Techniques
volume
4
issue
3
pages
23 - 42
publisher
Williams College
ISSN
2331-7418
language
English
LU publication?
yes
id
3adb99fb-266b-4ae2-bdf9-7f0d66fee8f3 (old id 8593622)
alternative location
http://jcgt.org/published/0004/03/02/
date added to LUP
2016-04-04 13:40:58
date last changed
2021-05-05 21:47:05
@article{3adb99fb-266b-4ae2-bdf9-7f0d66fee8f3,
  abstract     = {{We present an algorithm, called Bonsai, for rapidly building bounding volume hierarchies for ray tracing. Our method starts by computing midpoints of the triangle bounding boxes and then performs a rough hierarchical top-down split using the midpoints, creating triangle groups with tight bounding boxes. For each triangle group, a mini tree is built using an improved sweep SAH method. Once all mini trees have been built, we use them as leaves when building the top tree of the bounding volume hierarchy. We also introduce a novel and inexpensive optimization technique, called mini-tree pruning, that can be used to detect and improve poorly built parts of the tree. We achieve a little better than 100% in ray-tracing performance compared to a "ground truth" greedy top-down sweep SAH method, and our build times are the lowest we have seen with comparable tree quality.}},
  author       = {{Ganestam, Per and Barringer, Rasmus and Doggett, Michael and Akenine-Möller, Tomas}},
  issn         = {{2331-7418}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{23--42}},
  publisher    = {{Williams College}},
  series       = {{Journal of Computer Graphics Techniques}},
  title        = {{Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees}},
  url          = {{https://lup.lub.lu.se/search/files/6179951/8593625.pdf}},
  volume       = {{4}},
  year         = {{2015}},
}