“Matrix row-column sampling for the many-light problem” by Hasan, Pellacini and Bala

Rendering complex scenes with indirect illumination, high dynamic range environment lighting, and many direct light sources remains a challenging problem. Prior work has shown that all these effects can be approximated by many point lights. This paper presents a scalable solution to the many-light problem suitable for a GPU implementation. We view the problem as a large matrix of sample-light interactions; the ideal final image is the sum of the matrix columns. We propose an algorithm for approximating this sum by sampling entire rows and columns of the matrix on the GPU using shadow mapping. The key observation is that the inherent structure of the transfer matrix can be revealed by sampling just a small number of rows and columns. Our prototype implementation can compute the light transfer within a few seconds for scenes with indirect and environment illumination, area lights, complex geometry and arbitrary shaders. We believe this approach can be very useful for rapid previewing in applications like cinematic and architectural lighting design.

1. Agarwal, S., Ramamoorthi, R., Belongie, S., and Jensen, H. W. 2003. Structured importance sampling of environment maps. ACM Transactions on Graphics 22, 3 (July), 605–612. Google ScholarDigital Library
2. Bala, K., Walter, B. J., and Greenberg, D. P. 2003. Combining edges and points for interactive high-quality rendering. ACM Transactions on Graphics 22, 3 (July), 631–640. Google ScholarDigital Library
3. Ben-Artzi, A., Overbeck, R., and Ramamoorthi, R. 2006. Real-time brdf editing in complex lighting. ACM Transactions on Graphics 25, 3 (July), 945–954. Google ScholarDigital Library
4. Carr, N. A., Hall, J. D., and Hart, J. C. 2003. Gpu algorithms for radiosity and subsurface scattering. In Graphics Hardware 2003, 51–59. Google ScholarDigital Library
5. Christensen, P. H., Lischinski, D., Stollnitz, E. J., and Salesin, D. H. 1997. Clustering for glossy global illumination. ACM Transactions on Graphics 16, 1, 3–33. Google ScholarDigital Library
6. Dachsbacher, C., and Stamminger, M. 2005. Reflective shadow maps. In S13D ’05: Proceedings of the 2005 symposium on Interactive 3D graphics and games, 203–231. Google ScholarDigital Library
7. Dachsbacher, C., and Stamminger, M. 2006. Splatting of indirect illumination. In 2006 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. Google ScholarDigital Library
8. Drineas, P., Mahoney, M. W., and Muthukrishnan, S. 2006. Subspace sampling and relative-error matrix approximation: Column-row-based methods. In Algorithms – ESA 2006, 304–314. Google ScholarDigital Library
9. Fernandez, S., Bala, K., and Greenberg, D. P. 2002. Local illumination environments for direct lighting acceleration. In Rendering Techniques 2002: 13th Eurographics Workshop on Rendering, 7–14. Google ScholarDigital Library
10. Gautron, P., Krivánek, J., Bouatouch, K., and Pattanaik, S. 2005. Radiance cache splatting: A gpu-friendly global illumination algorithm. In Rendering Techniques, 55–64. Google ScholarCross Ref
11. Gautron, P., Bouatouch, K., and Pattanaik, S. 2006. Temporal radiance caching. In SIGGRAPH 2006 Sketches. Google ScholarDigital Library
12. Goreinov, S. A., Tyrtyshnikov, E. E., and Zamarashkin, N. 1997. A theory of pseudoskeleton approximations. Linear Algebra and its Applications 261.Google Scholar
13. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. In SIGGRAPH 91, 197–206. Google ScholarDigital Library
14. Hašan, M., Pellacini, F., and Bala, K. 2006. Direct-to-indirect transfer for cinematic relighting. ACM Transactions on Graphics 25, 3 (July), 1089–1097. Google ScholarDigital Library
15. Jensen, H. W. 2001. Realistic image synthesis using photon mapping. A. K. Peters, Ltd., Natick, MA, USA. Google ScholarDigital Library
16. Keller, A. 1997. Instant radiosity. In Proceedings of SIGGRAPH 97, Computer Graphics Proceedings, Annual Conference Series, 49–56. Google ScholarDigital Library
17. Křivánek, J., Bouatouch, K., Pattanaik, S. N., and Žára, J. 2006. Making radiance and irradiance caching practical: Adaptive caching and neighbor clamping. In Eurographics Symposium on Rendering. Google ScholarCross Ref
18. Ng, R., Ramamoorthi, R., and Hanrahan, P. 2004. Triple product wavelet integrals for all-frequency relighting. ACM Transactions on Graphics (July). Google ScholarDigital Library
19. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. ACM Transactions on Graphics 23, 3, 488–495. Google ScholarDigital Library
20. Paquette, E., Poulin, P., and Drettakis, G. 1998. A light hierarchy for fast rendering of scenes with many lights. Computer Graphics Forum 17, 3, 63–74.Google ScholarCross Ref
21. Purcell, T. J., Donner, C., Cammarano, M., Jensen, H. W., and Hanrahan, P. 2003. Photon mapping on programmable graphics hardware. In Sypmosium on Graphics Hardware 2003. Google ScholarDigital Library
22. Scheel, A., Stamminger, M., and Seidel, H.-P. 2001. Thrifty final gather radiosity. Proceedings of the 12th Eurographics Workshop on Rendering. Google ScholarDigital Library
23. Scheel, A., Stamminger, M., and Seidel, H. 2002. Grid based final gather for radiosity on complex clustered scenes. Computer Graphics Forum, 21(3).Google Scholar
24. Schulman, L. J. 1999. Clustering for edge-cost minimization. Electronic Colloquium on Computational Complexity (ECCC) 6, 035.Google Scholar
25. Shirley, P., Wang, C., and Zimmerman, K. 1996. Monte carlo techniques for direct lighting calculations. ACM Transactions on Graphics 15, 1 (Jan.), 1–36. Google ScholarDigital Library
26. Sloan, P.-P., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. ACM Transactions on Graphics 21, 3 (July), 527–536. Google ScholarDigital Library
27. Smits, B. E., Arvo, J. R., and Salesin, D. H. 1992. An importance-driven radiosity algorithm. In SIGGRAPH 92, 273–282. Google ScholarDigital Library
28. Tole, P., Pellacini, F., Walter, B., and Greenberg, D. P. 2002. Interactive global illumination in dynamic scenes. ACM Transactions on Graphics 21, 3 (July), 537–546. Google ScholarDigital Library
29. Vempala, S. 2004. The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.Google Scholar
30. Wald, I., Benthin, C., and Slusallek, P. 2003. Interactive global illumination in complex and highly occluded environments. In 14th Eurographics Workshop on Rendering, 74–81. Google ScholarDigital Library
31. Walter, B., Drettakis, G., and Parker, S. 1999. Interactive rendering using the render cache. In Eurographics Rendering Workshop 1999. Google ScholarCross Ref
32. Walter, B., Fernandez, S., Arbree, A., Bala, K., Donikian, M., and Greenberg, D. P. 2005. Lightcuts: a scalable approach to illumination. ACM Transactions on Graphics 24, 3 (Aug.), 1098–1107. Google ScholarDigital Library
33. Walter, B., Arbree, A., Bala, K., and Greenberg, D. P. 2006. Multidimensional lightcuts. ACM Transactions on Graphics 25, 3 (July), 1081–1088. Google ScholarDigital Library
34. Ward, G., and Simmons, M. 1999. The holodeck ray cache: An interactive rendering system for global illumination in non-diffuse environments. ACM Transactions on Graphics 18, 4 (Oct.), 361–368. Google ScholarDigital Library
35. Ward, G. J., Rubinstein, F. M., and Clear, R. D. 1988. A ray tracing solution for diffuse interreflection. In Proceedings of ACM SIGGRAPH 88, 85–92. Google ScholarDigital Library
36. Ward, G. 1994. Adaptive shadow testing for ray tracing. In Proceedings of the Second Eurographics Workshop on Rendering, 11–20.Google ScholarCross Ref