Reordering for cache conscious photon mapping

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.

REFERENCES

• 1: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173--189, 1972.
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: Per H. Christensen, Faster photon map global illumination, Journal of Graphics Tools, v.4 n.3, p.1-10, 1999
• 4: Per H. Christensen and Dana Batali. An irradiance atlas for global illumination in complex production scenes. In Proc. Eurographics Symposium on Rendering, pages 133--141, 2004.
• 5: Frank Dachille, IX , Arie Kaufman, GI-cube: an architecture for volumetric global illumination and rendering, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.119-128, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.348241]
• 6: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 7: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 8: V. Havran. Analysis of cache sensitive representations for binary space partitioning trees. Informatica, 23(3):203--210, May 2000.
• 9: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 10: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 11: Intel. Microburst Architecture. IA-32 Intel Architecture Software Developers Manual, 1:37--40, 2003.
• 12: Wojciech Jarosz, April 2004. http://renderedrealities.net/.
• 13: Henrik Wann Jensen, Realistic image synthesis using photon mapping, A. K. Peters, Ltd., Natick, MA, 2001
• 14: Yuanxin Liu and Jack Snoeyink. A notation for hilbert curves to support multidimensional spatial indexing. In preparation.
• 15: Vincent C. H. Ma , Michael D. McCool, Low latency photon mapping using block hashing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 16: Joel McCormack , Robert McNamara , Christopher Gianos , Larry Seiler , Norman P. Jouppi , Ken Correll, Neon: a single-chip 3D workstation graphics accelerator, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.123-132, August 31-September 01, 1998, Lisbon, Portugal [doi>10.1145/285305.285320]
• 17: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 18: NVIDIA. Ultra-high-end products, October 2004. http://nvidia.com/page/qfx_uhe.html.
• 19: Matt Pharr , Pat Hanrahan, Geometry caching for ray-tracing displacement maps, Proceedings of the eurographics workshop on Rendering techniques '96, p.31-ff., December 1996, Porto, Portugal
• 20: Matt Pharr , Greg Humphreys, Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 21: Matt Pharr , Craig Kolb , Reid Gershbein , Pat Hanrahan, Rendering complex scenes with memory-coherent ray tracing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.101-108, August 1997 [doi>10.1145/258734.258791]
• 22: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 23: E Reinhard and E W. Jansen. Rendering large scenes using parallel ray tracing. In First Eurographics Workshop on Parallel Graphics and Visualization, pages 67--80, 1996.
• 24: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 25: Jörg Schmittler , Ingo Wald , Philipp Slusallek, SaarCOR: a hardware architecture for ray tracing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 26: Ingo Wald, Johannes Guenther, and Philipp Slusallek. Balancing considered harmful - faster photon mapping using the voxel volume heuristic. In Proc. Eurographics, 2004.
• 27: Ingo Wald, Philipp Slusallek, Carsten Benthin, and Markus Wagner. Interactive rendering with coherent ray tracing. Computer Graphics Forum, 20(3):153--164, 2001.
• 28: Gregory J. Ward , Francis M. Rubinstein , Robert D. Clear, A ray tracing solution for diffuse interreflection, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.85-92, June 1988

INDEX TERMS

Keywords:
global illumination, graphics hardware