“A constructive theory of sampling for image synthesis using reproducing Kernel bases” by Lessig, Desbrun and Fiume
Conference:
Type(s):
Title:
- A constructive theory of sampling for image synthesis using reproducing Kernel bases
Session/Category Title: Sampling & Spectra
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
