Ray tracing acceleration structure : GPU based KD-tree using SAH heuristic

Abstract

Ray tracing is a very widely used rendering technique in many applications in the movie industry,

architecture and media industry. The reason why ray tracing is so popular is because it can produce the

most realistic and most accurate images compared to other rendering techniques due to its straight

forward nature of emulating light. However computational costs prevent it from being widely used in

interactive applications.

Much research has been done to help accelerate the ray tracing process and one of the most popular data

structures being used is the KD-Tree. However KD-Tree construction is also a computationally expensive

task thus holding it back from being used in interactive applications in which the scenes contain

animations and require the tree to be rebuilt in every frame.

With the advance of multi-purpose graphics hardware with its massive parallelism it is now possible to

accelerate the ray tracing process further to improve the performance greatly from traditional CPU based

approaches. The GPU construction stage also benefits greatly from the computing power of modern

graphics hardware and thus it is now possible to construct KD-Tree in real time.

In this final year project we try to implement such an approach by making a n early full GPU based ray

tracer using KD-Tree as the acceleration structure. The whole KD-Tree construction algorithm is also

implemented to try to take advantage of the GPU as much as possible using the CUDA framework

running on NVIDIA graphics cards.

Due to time constraints our GPU ray tracer is quite simple and does not support animation, however the

code is functional and reasonably stable. Further optimizations can be made to improve the performance

and more features can be implemented in future projects.