Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing

Kirill Garanzha, Charles Loop
Keldysh Institute of Applied Mathematics, Russian Academy of Sciences
Computer Graphics Forum, Vol. 29, No. 2., pp. 289-298


   title={Fast Ray Sorting and Breadth-First Packet Traversal for GPU Ray Tracing},

   author={Garanzha, K. and Loop, C.},

   booktitle={Computer Graphics Forum},






   organization={Wiley Online Library}


Download Download (PDF)   View View   Source Source   



We present a novel approach to ray tracing execution on commodity graphics hardware using CUDA. We decompose a standard ray tracing algorithm into several data-parallel stages that are mapped efficiently to the massively parallel architecture of modern GPUs. These stages include: ray sorting into coherent packets, creation of frustums for packets, breadth-first frustum traversal through a bounding volume hierarchy for the scene, and localized ray-primitive intersections. We utilize the well known parallel primitives scan and segmented scan in order to process irregular data structures, to remove the need for a stack, and to minimize branch divergence in all stages. Our ray sorting stage is based on applying hash values to individual rays, ray stream compression, sorting and decompression. Our breadth-first BVH traversal is based on parallel frustum-bounding box intersection tests and parallel scan per each BVH level. We demonstrate our algorithm with area light sources to get a soft shadow effect and show that our concept is reasonable for GPU implementation. For the same data sets and ray-primitive intersection routines our pipeline is ~3x faster than an optimized standard depth first ray tracing implemented in one kernel.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: