Master’s thesis, Department of Computer Science, KU Leuven, June 2015
Hybrid Kd-trees for Photon Mapping and Accelerating Ray Tracing
Computer Graphics Research Group, Department of Computer Science, KU Leuven
Abstract
Acceleration data structures such as kd-trees, which partition geometric primitives, aim to reduce the ray traversal cost. Photon maps such as kd-trees, which partition photons, aim to reduce the cost of performing k-nearest neighbor queries. We introduce three hybrid kd-trees, which partition both geometric primitives and photons:
- The Hybrid Additive Photon Map (HAPM) adds photons to the kd-tree acceleration data structure, using the primitive partitioning to also partition photons.
- The Hybrid Swapping Photon Map (HSPM) constructs a hybrid kd-tree for the joint set of primitives and photons using our novel Hybrid Heuristic (HH) build cost metric.
- The Hybrid Connected Photon Map (HCPM) maintains separate kd-trees for primitives and photons, connected via ropes.
Our HH encapsulates both the RTSAH for acceleration data structures and the Voxel Volume Heuristic for photon maps. By taking ray termination into account we achieve intersection test reductions up to 47% for primary rays and 41% for shadow rays versus the SAH. The HAPM and HSPM generally increase total rendering time; only the HCPM achieves reductions of up to 1%.