Efficient ray tracing algorithms exploiting kd-trees on a GPU

This work focuses on parallel algorithms for building and traversing k-d trees to accelerate ray tracing, mainly for dynamic scenes. It provides an introduction to k-d trees as well as GPU architectures. It also provides an overview and analysis of existing solutions for building k-d trees in parallel, for building k-d trees for dynamic scenes, and for traversing k-d trees on the GPU. A game engine-like framework is designed and implemented to provide a basis for implementing the ray tracing related algorithms. An algorithm design and implementation for building k-d trees on the GPU using binning and exploiting a task pool is presented, with detailed description of all its steps. An algorithm design for merging k-d trees on the CPU and GPU is also presented. Nine algorithms are implemented in total: two CPU single-threaded k-d tree building algorithms using exact and approximate split selection, one GPU k-d tree building algorithm using binning, one CPU k-d tree merging algorithm and four traversal algorithms designed for the GPU, in addition to the traditional stack-based traversal algorithm. The implemented algorithms are tested on ten static and five dynamic scenes, with tables for each scene presenting the final results.