– Faster Photon Mapping using the Voxel Volume Heuristic –

Photon mapping is one of the most important algorithms for computing global illumination. Especially for efficiently producing convincing caustics, there are no real alternatives to photon mapping. On the other hand, photon mapping is also quite costly: Each radiance lookup requires to find the k nearest neighbors in a kd-tree, which can be more costly than shooting several rays. Therefore, the nearest-neighbor queries often dominate the rendering time of a photon map based renderer.

In this paper, we present a method that reorganizes
– i.e. *un*balances – the kd-tree for
storing the photons in a way that allows for finding the k-nearest neighbors
much more efficiently, thereby accelerating the radiance estimates by a factor
of 1.2-3.4. Most importantly, our method still finds exactly the same
k-nearest-neighbors as the original method, *without* introducing any
approximations or loss of accuracy. The impact of our method is demonstrated
with several practical examples.

[pdf][bib] |
EG 2004 9 pages 1896 kb bibtex entry |