“A constructive theory of sampling for image synthesis using reproducing Kernel bases” by Lessig, Desbrun and Fiume

  • ©Christian Lessig, Mathieu Desbrun, and Eugene Fiume




    A constructive theory of sampling for image synthesis using reproducing Kernel bases

Session/Category Title: Sampling & Spectra




    Sampling a scene by tracing rays and reconstructing an image from such pointwise samples is fundamental to computer graphics. To improve the efficacy of these computations, we propose an alternative theory of sampling. In contrast to traditional formulations for image synthesis, which appeal to nonconstructive Dirac deltas, our theory employs constructive reproducing kernels for the correspondence between continuous functions and pointwise samples. Conceptually, this allows us to obtain a common mathematical formulation of almost all existing numerical techniques for image synthesis. Practically, it enables novel sampling based numerical techniques designed for light transport that provide considerably improved performance per sample. We exemplify the practical benefits of our formulation with three applications: pointwise transport of color spectra, projection of the light energy density into spherical harmonics, and approximation of the shading equation from a photon map. Experimental results verify the utility of our sampling formulation, with lower numerical error rates and enhanced visual quality compared to existing techniques.


    1. Aronszajn, N. 1950. Theory of Reproducing Kernels. Transactions of the American Mathematical Society 68, 3, 337–404.Google ScholarCross Ref
    2. Arvo, J., Torrance, K., and Smits, B. 1994. A Framework for the Analysis of Error in Global Illumination Algorithms. In SIGGRAPH ’94: Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, ACM, New York, NY, USA, 75–84. Google ScholarDigital Library
    3. Arvo, J. 1995. Analytic Methods for Simulated Light Transport. Ph.d. thesis, Yale University. Google ScholarDigital Library
    4. Arvo, J. 1995. The Role of Functional Analysis in Global Illumination. In Rendering Techniques ’95, P. M. Hanrahan and W. Purgathofer, Eds. Springer-Verlag, New York, 115–126. Google ScholarDigital Library
    5. Basu, K., and Owen, A. B. 2014. Low discrepancy constructions in the triangle.Google Scholar
    6. Bungartz, H.-J., and Griebel, M. 2004. Sparse Grids. Acta Numerica 13 (May), 147–269.Google ScholarCross Ref
    7. Christensen, P. H., Stollnitz, E. J., Salesin, D., and DeRose, T. 1996. Global Illumination of Glossy Environments Using Wavelets and Importance. ACM Trans. Graph. 15, 37–71. Google ScholarDigital Library
    8. Christensen, P. H., Lischinski, D., Stollnitz, E. J., and Salesin, D. H. 1997. Clustering for Glossy Global Illumination. ACM Transactions on Graphics (TOG) 16, 1. Google ScholarDigital Library
    9. Clarberg, P., Jarosz, W., Akenine-Möller, T., and Jensen, H. W. 2005. Wavelet Importance Sampling: Efficiently Evaluating Products of Complex Functions. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2005) 24, 3. Google ScholarDigital Library
    10. Cook, R. L., Porter, T., and Carpenter, L. 1984. Distributed Ray Tracing. ACM SIGGRAPH Computer Graphics 18, 3. Google ScholarDigital Library
    11. Cook, R. L. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 51–72. Google ScholarDigital Library
    12. Daubechies, I. 1992. Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Google Scholar
    13. De Witt, T., Lessig, C., and Fiume, E. 2012. Fluid Simulation Using Laplacian Eigenfunctions. ACM Transactions on Graphics 31, 1 (Jan.), 1–11. Google ScholarDigital Library
    14. Dick, J., and Pillichshammer, F. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press. Google ScholarDigital Library
    15. Donoho, D., and Stodden, V. 2004. Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts? In Advances in Neural Information Processing Systems 16, MIT Press, Cambridge, MA, S. Thrun, L. Saul, and B. Schölkopf, Eds.Google Scholar
    16. Donoho, D. L. 2000. High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality. In Mathematical Challenges of the 21st Century, American Mathematical Society, Los Angeles, CA, USA.Google Scholar
    17. Galerkin, B. G. 1915. On Electrical Circuits for the Approximate Solution of the Laplace Equation. Vestnik Inzh. 19, 897–908.Google Scholar
    18. Goral, C. M., Torrance, K. E., Greenberg, C. P., and Battaile, B. 1984. Modeling the Interaction of Light between Diffuse Surfaces. SIGGRAPH Comput. Graph. 18, 213–222. Google ScholarDigital Library
    19. Gortler, S. J., Schröder, P., Cohen, M. F., and Hanrahan, P. 1993. Wavelet Radiosity. In Computer Graphics Proceedings, Annual Conference Series, 1993 (ACM SIGGRAPH ’93 Proceedings), 221–230. Google ScholarDigital Library
    20. Greger, G., Shirley, P., Hubbard, P. M., and Greenberg, D. P. 1998. The Irradiance Volume. IEEE Computer Graphics and Applications 18, 2, 32–43. Google ScholarDigital Library
    21. Heckbert, P., and Winget, J. M. 1991. Finite Element Methods for Global Illumination. Technical Report UCB/CSD 91/643, University of California at Berkeley, Berkeley, CA. Google ScholarDigital Library
    22. Jarosz, W., Carr, N. A., and Jensen, H. W. 2009. Importance Sampling Spherical Harmonics. Computer Graphics Forum 28, 2, 577–586. Google ScholarDigital Library
    23. Jensen, H. W., and Christensen, N. J. 1995. Photon Maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects. Computers & Graphics 19, 2, 215–224.Google ScholarCross Ref
    24. Jensen, H. W. 1995. Importance Driven Path Tracing using the Photon Map. In Rendering Techniques ’95, Springer-Verlag, P. Hanrahan and W. Purgathofer, Eds., 326–335. Google ScholarDigital Library
    25. Jensen, H. W. 2001. Realistic Image Synthesis using Photon Mapping. A. K. Peters, Ltd., Natick, MA, USA. Google ScholarDigital Library
    26. Kajiya, J. T., and von Herzen, B. P. 1984. Ray Tracing Volume Densities. International Conference on Computer Graphics and Interactive Techniques 18, 3. Google ScholarDigital Library
    27. Kajiya, J. T. 1986. The Rendering Equation. ACM SIGGRAPH Computer Graphics 20, 4. Google ScholarDigital Library
    28. Keller, A. 2006. Myths of Computer Graphics. Springer, 217–243.Google Scholar
    29. Lehtinen, J. 2007. A Framework for Precomputed and Captured Light Transport. ACM Trans. Graph. 26, 13. Google ScholarDigital Library
    30. Lessig, C., and Fiume, E. 2010. On the Effective Dimension of Light Transport. Computer Graphics Forum 29, 4 (Aug.), 1399–1403. Google ScholarDigital Library
    31. Lessig, C., de Witt, T., and Fiume, E. 2012. Efficient and Accurate Rotation of Finite Spherical Harmonics Expansions. Journal of Computational Physics 231, 2 (Jan.), 243–250. Google ScholarDigital Library
    32. Lessig, C. 2012. Modern Foundations of Light Transport Simulation. Ph.d. thesis, University of Toronto, Toronto. Google ScholarDigital Library
    33. Mahajan, D., Tseng, Y.-T., and Ramamoorthi, R. 2008. An Analysis of the In-Out BRDF Factorization for View-Dependent Relighting. Comput. Graph. Forum (Proceedings of EGSR) 27, 1137–1145. Google ScholarDigital Library
    34. Mallat, S. G. 2009. A Wavelet Tour of Signal Processing: The Sparse Way, third ed. Academic Press. Google ScholarDigital Library
    35. Mitchell, D. P. 1987. Generating Antialiased Images at Low Sampling Densities. In SIGGRAPH ’87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 65–72. Google ScholarDigital Library
    36. Mitchell, D. P. 1991. Spectrally Optimal Sampling for Distribution Ray Tracing. SIGGRAPH Comput. Graph. 25, 157–164. Google ScholarDigital Library
    37. Nashed, M. Z., and Walter, G. 1991. General Sampling Theorems for Functions in Reproducing Kernel Hilbert Spaces. Mathematics of Control, Signals, and Systems 4, 4, 363–390.Google ScholarCross Ref
    38. Nehab, D., and Hoppe, H. 2014. A Fresh Look at Generalized Sampling. Foundations and Trends in Computer Graphics and Vision 8, 1, 1–84. Google ScholarDigital Library
    39. Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, PA, USA. Google Scholar
    40. Nishita, T., and Nakamae, E. 1984. Calculation of Interreflections and its Representation Method. In 1984 Annual Conference of the Japanese Illumination Engineering Society, vol. 63.Google Scholar
    41. Novak, E., and Woźniakowski, H. 2010. Tractability of Multivariate Problems: Standard Information for Functionals, vol. II of EMS Tracts in Mathematics. European Mathematical Society Publishing House.Google Scholar
    42. Peercy, M. S. 1993. Linear Color Representations for Full Speed Spectral Rendering. In SIGGRAPH ’93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 191–198. Google ScholarDigital Library
    43. Petrov, G. I. 1940. Application of the Method of Galerkin to a Problem Involving the Stationary Flow of a Viscous Fluid. Prikl. Matem. Mekh. 4, 3.Google Scholar
    44. Pharr, M., and Humphreys, G. 2010. Physically Based Rendering: From Theory to Implementation, second ed. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google ScholarDigital Library
    45. Pinchon, D., and Hoggan, P. E. 2007. Rotation Matrices for Real Spherical Harmonics: General Rotations of Atomic Orbitals in Space-Fixed Axes. Journal of Physics A: Mathematical and Theoretical 40, 1597–1610.Google ScholarCross Ref
    46. Saff, E., and Kuijlaars, A. 1997. Distributing many points on a sphere. The Mathematical Intelligencer 19, 1, 5–11.Google ScholarCross Ref
    47. Schröder, P., Gortler, S. J., Cohen, M. F., and Hanrahan, P. 1993. Wavelet Projections for Radiosity. In Fourth Eurographics Workshop on Rendering, 105–114.Google Scholar
    48. Shirley, P., Wade, B., Hubbard, P. M., Zareski, D., Walter, B., and Greenberg, D. P. 1995. Global Illumination via Density-Estimation. In Proceedings of 6th Workshop on Rendering, Springer, 219–230.Google Scholar
    49. Shirley, P. 1991. Discrepancy as a Quality Measure for Sample Distributions. In Proceedings of Eurographics 1991.Google Scholar
    50. Sillion, F., Arvo, J., Westin, S., and Greenberg, D. P. 1991. A Global Illumination Solution for General Reflectance Distributions. In Proceedings of ACM SIGGRAPH 1991, ACM Press, New York, NY, USA, 187–196. Google ScholarDigital Library
    51. Simons, F. J. 2010. Slepian Functions and Their Use in Signal Estimation and Spectral Analysis. In Handbook of Geomathematics, W. Freeden, Z. M. Nashed, and T. Sonar, Eds.Google Scholar
    52. Sloan, P.-P., Kautz, J., and Snyder, J. 2002. Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low-Frequency Lighting Environments. In Proceedings of ACM SIGGRAPH 2002, ACM Press, New York, NY, USA, 527–536. Google ScholarDigital Library
    53. Traub, J. F., and Werschulz, A. G. 1999. Complexity and Information. Cambridge University Press, New York, NY, USA. Google ScholarDigital Library
    54. Trenogin, V. A. 2002. Galerkin Method. In Encyclopedia of Mathematics, M. Hazewinkel, Ed. Kluwer Academic Publishers.Google Scholar
    55. Veach, E., and Guibas, L. J. 1997. Metropolis Light Transport. In SIGGRAPH ’97: Proceedings of the 24th annual conference on computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 65–76. Google ScholarDigital Library
    56. Veach, E. 1997. Robust Monte Carlo Methods for Light Transport Simulation. Ph.d. thesis, Stanford University. Google ScholarDigital Library
    57. Walter, B., Hubbard, P. M., Shirley, P., and Greenberg, D. P. 1997. Global Illumination using Local Linear Density Estimation. ACM Trans. Graph. 16, 217–259. Google ScholarDigital Library
    58. Westin, S. H., Arvo, J., and Torrance, K. E. 1992. Predicting Reflectance Functions from Complex Surfaces. In Proceedings of ACM SIGGRAPH 1992, ACM Press, New York, NY, USA, 255–264. Google ScholarDigital Library
    59. Zatz, H. R. 1993. Galerkin Radiosity: A Higher Order Solution Method for Global Illumination. In SIGGRAPH ’93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA. Google ScholarDigital Library
    60. Zhu, C., Byrd, R. H., Lu, P., and Nocedal, J. 1997. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Math. Soft. (TOMS) 23, 4. Google ScholarDigital Library

ACM Digital Library Publication: