KD-Tree Raytracing (CPU Side)
Raytracing on the CPU is a slow and intense process, however, there’s a lot we can do to help it out when it comes to spatial partitioning. In dealing with static objects in a scene, one of the dominant spatial partitioning methods used is the KD-Tree. The KD-Tree is a spatial partitioning algorithm that splits up space using infinite half-planes, storing the split plane and axis on each branch of the tree. Though KD-Trees are typically used to store points and do nearest point queries, the KD-Tree implemented here stores triangles at the leaf node level and makes splits on the edges of triangles. In order to determine where to make the splits, the KD-Tree uses the Surface Area Heuristic (SAH). SAH was made with raytracing in mind, and is based loosely upon the entropy and occlusion of rays. Using SAH over doing a naïve split (like splitting half way in) yields a tremendous performance gain and allows for nearly realtime raytraced scenes, as can be seen below.