Real-time KD-tree construction on graphics hardware

Kun Zhou, Qiming Hou, Rui Wang, Baining Guo
Zhejiang University and Microsoft Research Asia
ACM Trans. Graph., Vol. 27, No. 5. (2008), pp. 1-11.


   title={Real-time kd-tree construction on graphics hardware},

   author={Zhou, K. and Hou, Q. and Wang, R. and Guo, B.},

   booktitle={ACM SIGGRAPH Asia 2008 papers},





Download Download (PDF)   View View   Source Source   



We present an algorithm for constructing kd-trees on GPUs. This algorithm achieves real-time performance by exploiting the GPU’s streaming architecture at all stages of kd-tree construction. Unlike previous parallel kd-tree algorithms, our method builds tree nodes completely in BFS (breadth-first search) order. We also develop a special strategy for large nodes at upper tree levels so as to further exploit the fine-grained parallelism of GPUs. For these nodes, we parallelize the computation over all geometric primitives instead of nodes at each level. Finally, in order to maintain kd-tree quality, we introduce novel schemes for fast evaluation of node split costs.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: