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

  • ©Jaakko Lehtinen, Matthias Zwicker, Emmanuel Turquin, Janne Kontkanen, Frédo Durand, François X. Sillion, and Timo Aila




    A meshless hierarchical representation for light transport



    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

ACM Digital Library Publication: