high performance computing on graphics processing units: hgpu.org

Photon mapping is a state of the art global illumination rendering algorithm. Photons are traced from the light sources in a first pass and their interactions with scene surfaces stored. A second pass reconstructs illumination by density estimation, reproducing a wide range of optical phenomena. This thesis addresses the question how photon mapping can be turned from an offline algorithm to one synthesizing images at interactive frame rates. An emerging trend in computer architecture is manycore computing. Performance increases no longer result from higher operating frequencies and instruction-level parallelism but from more processing cores working in parallel. Owing to this, photon mapping is investigated in the context of manycore computing, ensuring computations are efficiently distributed to highly parallel processing units. The specific platform employed is CUDA, utilizing commodity NVIDIA GPU hardware. Techniques enabling efficient parallel execution in CUDA are presented for each component of the photon mapping algorithm. We begin with a focus on the tracing of rays and photons through a scene. A new heuristic for constructing the spatial index that accelerates these operations is introduced and the resulting speedup demonstrated. Spatial index traversal is addressed next, investigating both its stackless and stack-based variants. The latter is found to be more efficient. We then show how to exploit hardware resources not used during traversal as explicitly managed caches, reducing bandwidth requirements. Our findings identify computational cost as a factor whose importance is understated by the CUDA documentation. Reducing bandwidth requirements does improve performance but the overheads of explicit cache management in many cases negate the benefits. Photon mapping uses k-th nearest neighbor density estimation, locating the k photon interactions nearest a query point to determine a smoothing kernel bandwidth for it. This costly operation is not efficiently possible on the CUDA platform. We therefore employ variable kernel density estimation instead, a priori choosing an individual bandwidth for each photon interaction. Our extension of the photon differentials framework efficiently computes bandwidths adaptive to the local interaction density from information tracked with each photon. We demonstrate image quality matching that obtained with k-th nearest neighbor density estimation. The final photon mapping component is the photon map, a spatial index over photon interactions that accelerates their retrieval. We show how to replace the kd-tree originally used with a bounding volume hierarchy (BVH). This simplifies density estimation and permits parallel construction via the linear BVH (LBVH) algorithm. We improve the efficiency of LBVH construction, illustrate the quality of the resulting photon maps relative to an expensive heuristic BVH construction and finally present benchmarks of the complete photon mapping algorithm running in CUDA. An extension to volumetric photon mapping for simulating light transport in participating media forms the final part of the thesis. Photon differentials are further extended to account for extinction and scattering. Volumetric photon mapping leads to more expensive density estimation. We therefore investigate additional improvements by rederiving the efficient beam radiance estimate method, correcting its physical units, and showing that packetization provides a large performance benefit.