“A meshless hierarchical representation for light transport” by Lehtinen, Zwicker, Turquin, Kontkanen, Durand, et al. …

We introduce a meshless hierarchical representation for solving light transport problems. Precomputed radiance transfer (PRT) and finite elements require a discrete representation of illumination over the scene. Non-hierarchical approaches such as per-vertex values are simple to implement, but lead to long precomputation. Hierarchical bases like wavelets lead to dramatic acceleration, but in their basic form they work well only on flat or smooth surfaces. We introduce a hierarchical function basis induced by scattered data approximation. It is decoupled from the geometric representation, allowing the hierarchical representation of illumination on complex objects. We present simple data structures and algorithms for constructing and evaluating the basis functions. Due to its hierarchical nature, our representation adapts to the complexity of the illumination, and can be queried at different scales. We demonstrate the power of the new basis in a novel precomputed direct-to-indirect light transport algorithm that greatly increases the complexity of scenes that can be handled by PRT approaches.

1. Arikan, O., Forsyth, D. A., and O’Brien, J. F. 2005. Fast and detailed approximate global illumination by irradiance decomposition. ACM Trans. Graph. 24, 3, 1108–1114. Google ScholarDigital Library
2. Arvo, J., Torrance, K., and Smits, B. 1994. A framework for the analysis of error in global illumination algorithms. In Proc. ACM SIGGRAPH 94, ACM Press, 75–84. Google ScholarDigital Library
3. Atkinson, K. 1997. The Numerical Solution of Integral Equations of the Second Kind. Cambridge University Press.Google Scholar
4. Bala, K., Walter, B. J., and Greenberg, D. P. 2003. Combining edges and points for interactive high-quality rendering. ACM Trans. Graph. 22, 3, 631–640. Google ScholarDigital Library
5. Belytschko, T., Krongauz, Y., Organ, D., Fleming, M., and Krysl, P. 1996. Meshless methods: An overview and recent developments. Comput. Methods Appl. Mech. Eng., 139, 3–48.Google ScholarCross Ref
6. Burt, P., and Adelson, E. 1983. The Laplacian pyramid as a compact image code. IEEE Trans. Comm. 31, 4, 532–540.Google ScholarCross Ref
7. Christensen, P. H., Stollnitz, E. J., Salesin, D. H., and DeRose, T. D. 1996. Global illumination of glossy environments using wavelets and importance. ACM Trans. Graph. 15, 1, 37–71. Google ScholarDigital Library
8. Desbrun, M., and Cani, M.-P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In Proc. Eurographics Workshop on Computer Animation and Simulation, 61–76. Google ScholarDigital Library
9. Dobashi, Y., Yamamoto, T., and Nishita, T. 2004. Radiosity for point-sampled geometry. In Proc. 12th Pacific Conference on Computer Graphics and Applications, 152–159. Google ScholarDigital Library
10. Fasshauer, G. E. 2002. Matrix-free multilevel moving least-squares methods. Approximation Theory X: Wavelets, Splines, and Applications, 271–281.Google Scholar
11. Floater, M., and Iske, A. 1996. Multistep scattered data interpolation using compactly supported radial basis functions. J. Comput. Applied Math. 73, 65–78. Google ScholarDigital Library
12. Gautron, P., Křivánek, J., Bouatouch, K., and Pattanaik, S. 2005. Radiance cache splatting: A GPU-friendly global illumination algorithm. In Proc. Eurographics Symposium on Rendering, 55–64. Google ScholarCross Ref
13. Gortler, S. J., Schröder, P., Cohen, M. F., and Hanrahan, P. 1993. Wavelet radiosity. In Proc. SIGGRAPH 93, 221–230. Google ScholarDigital Library
14. Green, P., Kautz, J., Matusik, W., and Durand, F. 2006. View-dependent precomputed light transport using nonlinear gaussian function approximations. In Proc. ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 7–14. Google ScholarDigital Library
15. Guennebaud, G., Barthe, L., and Paulin, M. 2004. Deferred Splatting. Comp. Graph. Forum 23, 3, 653–660.Google ScholarCross Ref
16. Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In Proc. ACM SIGMOD 84, 47–57. Google ScholarDigital Library
17. Hanrahan, P., Salzman, D., and Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. In Computer Graphics (Proc. SIGGRAPH 91), 197–206. Google ScholarDigital Library
18. Hašan, M., Pellacini, F., and Bala, K. 2006. Direct-to-indirect transfer for cinematic relighting. ACM Trans. Graph. 25, 3, 1089–1097. Google ScholarDigital Library
19. Hiu, L. H. 2006. Meshless local Petrov-Galerkin method for solving radiative transfer equation. Thermophysics and Heat Transfer 20, 1, 150–154.Google ScholarCross Ref
20. Holzschuch, N., Cuny, F., and Alonso, L. 2000. Wavelet radiosity on arbitrary planar surfaces. In Proc. Eurographics Workshop on Rendering, 161–172. Google ScholarDigital Library
21. Jensen, H. W. 1996. Global illumination using photon maps. In Proc. Eurographics Workshop on Rendering, 21–30. Google ScholarDigital Library
22. Kontkanen, J., Turquin, E., Holzschuch, N., and Sillion, F. X. 2006. Wavelet radiance transport for interactive indirect lighting. In Proc. Eurographics Symposium on Rendering 2006, 161–171. Google ScholarCross Ref
23. Kristensen, A. W., Akenine-Möller, T., and Jensen, H. W. 2005. Precomputed local radiance transfer for real-time lighting design. ACM Trans. Graph. 24, 3, 1208–1215. Google ScholarDigital Library
24. Křivánek, J., Gautron, P., Pattanaik, S., and Bouatouch, K. 2005. Radiance caching for efficient global illumination computation. IEEE Trans. Vis. Comput. Graph. 11, 5, 550–561. Google ScholarDigital Library
25. Lecot, G., Lévy, B., Alonso, L., and Paul, J.-C. 2005. Master-element vector irradiance for large tessellated models. In Proc. GRAPHITE 05. Google ScholarDigital Library
26. Lehtinen, J., Zwicker, M., Kontkanen, J., Turquin, E., Sillion, F. X., and Aila, T. 2007. Meshless finite elements for hierarchical global illumination. Tech. Rep. TML-B7, Helsinki University of Technology.Google Scholar
27. Lehtinen, J. 2007. A framework for precomputed and captured light transport. ACM Trans. Graph. 26, 4, 13:1–13:22. Google ScholarDigital Library
28. Liu, G. 2002. Mesh-free methods. CRC Press.Google Scholar
29. Mitchell, D. P. 1991. Spectrally optimal sampling for distributed ray tracing. In Computer Graphics (Proceedings of SIGGRAPH 91), vol. 25, 157–164. Google ScholarDigital Library
30. Müller, M., Charypar, D., and Gross, M. 2003. Particle-based fluid simulation for interactive applications. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 154–159. Google ScholarDigital Library
31. Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 141–151. Google ScholarDigital Library
32. Ng, R., Ramamoorthi, R., and Hanrahan, P. 2003. All-frequency shadows using non-linear wavelet lighting approximation. ACM Trans. Graph. 22, 3, 376–381. Google ScholarDigital Library
33. Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2005. 3D scattered data interpolation and approximation with multilevel compactly supported RBFs. Graph. Models 67, 3, 150–165. Google ScholarDigital Library
34. Pauly, M., Keiser, R., Adams, B., Dutré, P., Gross, M., and Guibas, L. J. 2005. Meshless animation of fracturing solids. ACM Trans. Graph. 24, 3, 957–964. Google ScholarDigital Library
35. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann. Google ScholarDigital Library
36. Reinhard, E., Stark, M., Shirley, P., and Ferwerda, J. 2002. Photographic tone reproduction for digital images. ACM Trans. Graph. 21, 3, 267–276. Google ScholarDigital Library
37. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proc. 23rd ACM national conference, 517–524. Google ScholarDigital Library
38. Sillion, F. X. 1995. A unified hierarchical algorithm for global illumination with scattering volumes and object clusters. IEEE Trans. Vis. Comput. Graph. 1, 3, 240–254. Google ScholarDigital Library
39. Sloan, P.-P., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. In Proc. SIGGRAPH 2002, 527–536. Google ScholarDigital Library
40. Sloan, P.-P., Hall, J., Hart, J., and Snyder, J. 2003. Clustered principal components for precomputed radiance transfer. ACM Trans. Graph. 22, 3, 382–391. Google ScholarDigital Library
41. Sloan, P.-P., Luna, B., and Snyder, J. 2005. Local, deformable precomputed radiance transfer. ACM Trans. Graph. 24, 3, 1216–1224. Google ScholarDigital Library
42. Sweldens, W. 1997. The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511–546. Google ScholarDigital Library
43. Tsai, Y.-T., and Shih, Z.-C. 2006. All-frequency precomputed radiance transfer using spherical radial basis functions and clustered tensor approximation. ACM Trans. Graph. 25, 3, 967–976. Google ScholarDigital Library
44. Walter, B., Fernandez, S., Arbree, A., Bala, K., Donikian, M., and Greenberg, D. P. 2005. Lightcuts: A scalable approach to illumination. ACM Trans. Graph. 24, 3, 1098–1107. Google ScholarDigital Library
45. Walter, B., Arbree, A., Bala, K., and Greenberg, D. P. 2006. Multidimensional lightcuts. ACM Trans. Graph. 25, 3, 1081–1088. Google ScholarDigital Library
46. Ward, G. J., Rubinstein, F. M., and Clear, R. D. 1988. A ray tracing solution for diffuse interreflection. In Computer Graphics (Proc. SIGGRAPH 88), vol. 22, 85–92. Google ScholarDigital Library
47. Willmott, A., Heckbert, P., and Garland, M. 1999. Face cluster radiosity. In Proc. Eurographics Workshop on Rendering. Google ScholarCross Ref