Efficiency of k-d Tree Ray-Traversal Algorithms

K-d tree is attracting an increasing interest in recent decades for raytracing[1] due to its advantages in generating detailed images based on natural physical behaviors, flexibility, and ease of coding. However, the processing and rendering of real image have to be done in a real-time fashion. Such a requirement poses challenge to presentation and layout of global scenes because ray-scenes processing can be extremely time-consuming. The author utilizes a k-d tree as this kind of spatial data structure to accelerate the ray-scene processing. The author also combines "Spatial Median split" and SAH as splitting methods for k-d tree. This paper also proposes an implementation of breadth-first layout tree which can reduce cache misses and memory consumption, compares five different k-d tree traversal algorithms and analyzes experimental result.