Review: Kd-tree Traversal Algorithms for Ray Tracing

M. Hapala, V. Havran
Faculty of Electrical Engineering, Czech Technical University in Prague, Czech Republic
Computer Graphics Forum, Volume 30, Issue 1, pages 199-213, 2011


   author={Hapala, M. and Havran, V.},

   title={Review: Kd-tree Traversal Algorithms for Ray Tracing},

   journal={Computer Graphics Forum},



   publisher={Blackwell Publishing Ltd},





   keywords={I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Ray Tracing},



Download Download (PDF)   View View   Source Source   



In this paper we review the traversal algorithms for kd-trees for ray tracing. Ordinary traversal algorithms such as sequential, recursive, and those with neighbour-links have different limitations, which led to several new developments within the last decade. We describe algorithms exploiting ray coherence and algorithms designed with specific hardware architecture limitations such as memory latency and consumption in mind. We also discuss the robustness of traversal algorithms as one issue that has been neglected in previous research.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: