Efficient Stackless Hierarchy Traversal on GPUs with Backtracking in Constant Time

Binder, Nikolaus; Keller, Alexander

Efficient Stackless Hierarchy Traversal on GPUs with Backtracking in Constant Time

Files

041-050.pdf (6.23 MB)

Date

2016

Authors

Binder, Nikolaus
Keller, Alexander

Publisher

The Eurographics Association

Abstract

The fastest acceleration schemes for ray tracing rely on traversing a bounding volume hierarchy (BVH) for efficient culling and use backtracking, which in the worst case may expose cost proportional to the depth of the hierarchy in either time or state memory. We show that the next node in such a traversal actually can be determined in constant time and state memory. In fact, our newly proposed parallel software implementation requires only a few modifications of existing traversal methods and outperforms the fastest stack-based algorithms on GPUs. In addition, it reduces memory access during traversal, making it a very attractive building block for ray tracing hardware.

        @inproceedings{10.2312:hpg.20161191
,
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics
},
editor = {Ulf Assarsson and Warren Hunt
},
title = {{Efficient Stackless Hierarchy Traversal on GPUs with Backtracking in Constant Time
}},
author = {Binder, Nikolaus and 
Keller, Alexander
},
year = {2016
},
publisher = {The Eurographics Association
},
ISSN = {2079-8679
},
ISBN = {978-3-03868-008-6
},
DOI = {10.2312/hpg.20161191
}
}