Stackless KD-Tree Traversal for Ray Tracing on Graphics Hardware

Stefan Popov
Master Thesis
[bib] [pdf] [C++]



Recursive ray tracing is a simple and powerful technique for rendering high quality images. With the recent hardware and algorithmic advancements, it has become possible to run ray tracing at interactive frame rates. However, even the fastest ray tracers can only achieve a few frames per second on commodity hardware in the general case, mainly limited by the computational power of the latter.

GPUs on the other hand offer an order of a magnitude higher computational power, but have a very limited programming model. They are very fast at shading, but until now no good algorithm for ray-scene intersection has been published, that can exploit their full power.

In this thesis, we present a new ray-object intersection algorithm based on the recursive KD-tree traversal algorithm. It has the same performance characteristics as the CPU optimal one. It does not require a stack and is thus suitable for GPU implementations. Furthermore, it is a one-pass algorithm able to fully exploit the power of the GPU. We also present a ray tracer, built around this algorithm and running entirely on the GPU, that is an order of a magnitude faster than previous attempts for GPU ray tracing. It is also the first GPU ray tracer that can outperform the existing CPU ray tracers.