Hybrid Kd-trees for Photon Mapping and Accelerating Ray Tracing

Abstract

Acceleration data structures such as kd-trees, which partition geometric primitives, aim to reduce the ray traversal cost, which is crucial for the rendering performance. Photon maps such as kd-trees, which partition photons, aim to reduce the cost of performing k-nearest neighbor queries, which is crucial for the performance of the photon mapping light transport algorithm (Jensen 1996, 2001) and its variants. We introduce three hybrid kd-trees, which partition both geometric primitives and photons, aiming to fundamentally reduce the combined cost of the ray traversal and k-nearest neighbor queries:

• The Hybrid Additive Photon Map (HAPM) adds the photons to the kd-tree acceleration data structure and therefore uses the partitioning of the geometric primitives to partition the photons.
• The Hybrid Swapping Photon Map (HSPM) generalizes the idea behind the HAPM by constructing a hybrid kd-tree for the set of geometric primitives and photons as a whole, using our novel Hybrid Heuristic (HH) build heuristic, which takes both the cost of the ray traversal and k-nearest neighbor queries into account and connects both of these costs. Indeed, a k-nearest neighbor query can only originate from the hit point resulting from the intersection of a ray against a geometric primitive.
• The Hybrid Connected Photon Map (HCPM) maintains a separate kd-tree acceleration data structure and a separate kd-tree photon map, each constructed using an optimal build heuristic for the associated contained data, and connects these kd-trees using ropes.

Our HH encapsulates both the Ray Termination Surface Area Heuristic (RTSAH) for constructing kd-tree acceleration data structures and the Voxel Volume Heuristic (Wald et al. 2004) for constructing kd-tree photon maps. The de-facto standard for constructing kd-tree acceleration data structures, the Surface Area Heuristic (SAH) (MacDonald & Booth 1990), does not take ray termination into account, but assumes instead that rays never hit any geometric primitive and can thus not be used in the HH.

The RTSAH (Ize et al. 2011) is a cost metric originally used for determining the traversal order of the voxels for occlusion rays, taking ray termination into account. We adapt this RTSAH to construct kd-tree acceleration data structures. Our build procedures, based on the orthogonal projected and average projected surface areas of the geometric primitives onto the splitting plane, have the same overall time complexity and consider the same finite set of candidate splitting planes as the SAH. By taking ray termination into account, we favor cutting off child voxels which are not or hardly visible to each other. This results in fundamentally different and more qualitative kd-trees compared to the SAH. We achieve reductions in intersection tests up to 47% for primary rays and up to 41% for shadow rays (when traversing the voxels in order) compared to the SAH.

The HAPM and HSPM generally result in significant increases of the total rendering time compared to the use of a non-hybrid photon map. First of all, the geometric primitives (non-point data) and photons (point data) work against each other with regard to the granularity of the kd-tree. Second, tracing a ray and performing a k-nearest neighbor query are two fundamentally different operations. This impacts both the traversal of the hybrid kd-trees and the data required to evaluate the cost functions. Only the HCPM achieves reductions in total rendering time up to 1%.

Based on our results and arguments, we conclude that geometric primitives and photons can neither be reconciled with each other in kd-trees, nor in the other most common acceleration data structures (e.g. regular grids, BVHs, BSPs, octrees, etc.), with the goal of fundamentally reducing the combined cost of the ray traversal and k-nearest neighbor queries as opposed to the use of two separate data structures.