BibTex
@inproceedings{Steinhurst:2005:,
author = {Steinhurst, Joshua and Coombe, Greg and Lastra, Anselmo},
title = {Reordering for cache conscious photon mapping},
booktitle = {Proceedings of Graphics Interface 2005},
series = {GI 2005},
year = {2005},
issn = {0713-5424},
isbn = {1-56881-265-5},
location = {Victoria, British Columbia, Canada},
pages = {97--104},
numpages = {8},
publisher = {Canadian Human-Computer Communications Society},
address = {School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada},
}
Abstract
Photon mapping is a global illumination algorithm for generating and visualizing a sparse representation of the incident radiance on surfaces. Photon mapping places an enormous burden on the memory hierarchy. A 512x512 image using the standard kd-tree data structure requires more than 196GB of raw bandwidth to access the photon map. This bandwidth is a major obstacle to our long term goal of designing hardware capable of real time photon mapping.This paper investigates two approaches for reducing the required bandwidth: 1) reordering the kNN searches; and 2) cache conscious data structures. Using a Hilbert curve reordering, we demonstrate an approximate lower bound of 15MB of bandwidth. This improvement of four orders of magnitude requires a prohibitive amount of intermediate storage. We then demonstrate two more cost-effective algorithms that reduce the bandwidth by one order of magnitude to 24GB with IMB of storage. We explain why the choice of data structure can not, by itself, achieve this reduction. Irradiance caching, a popular technique that reduces the number of required kNN searches, receives the same proportional benefit as the higher quality photon gathers.