“Variance analysis for Monte Carlo integration” by Pilleboue, Singh, Coeurjolly, Kazhdan and Ostromoukhov

  • ©Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov




    Variance analysis for Monte Carlo integration



    We propose a new spectral analysis of the variance in Monte Carlo integration, expressed in terms of the power spectra of the sampling pattern and the integrand involved. We build our framework in the Euclidean space using Fourier tools and on the sphere using spherical harmonics. We further provide a theoretical background that explains how our spherical framework can be extended to the hemispherical domain. We use our framework to estimate the variance convergence rate of different state-of-the-art sampling patterns in both the Euclidean and spherical domains, as the number of samples increases. Furthermore, we formulate design principles for constructing sampling methods that can be tailored according to available resources. We validate our theoretical framework by performing numerical integration over several integrands sampled using different sampling patterns.


    1. Arvo, J. 1995. Stratified sampling of spherical triangles. In Proc. SIGGRAPH ’95, ACM, 437–438. Google ScholarDigital Library
    2. Arvo, J. 2001. Stratified sampling of 2-manifolds. SIGGRAPH 2001 Course Notes 29, 2.Google Scholar
    3. Balzer, M., Schlömer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Trans. on Graphics 28, 3, 86:1–8. Google ScholarDigital Library
    4. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel Poisson disk sampling with spectrum analysis on surfaces. In Proc. SIGGRAPH Asia ’10, ACM, 166:1–166:10. Google ScholarDigital Library
    5. Brandolini, L., Colzani, L., and Torlaschi, A. 2001. Mean square decay of Fourier transforms in euclidean and non euclidean spaces. Tohoku Math. J. (2) 53, 3, 467–478.Google Scholar
    6. Brauchart, J., Saff, E., Sloan, I., and Womersley, R. 2014. QMC designs: optimal order Quasi Monte Carlo integration schemes on the sphere. Mathematics of Computation.Google Scholar
    7. Bridson, R. 2007. Fast Poisson disk sampling in arbitrary dimensions. In Proc. SIGGRAPH ’07 Sketches, ACM, Proc. SIGGRAPH ’07. Google ScholarDigital Library
    8. Choirat, C., and Seri, R. 2013. Computational aspects of cuifreeden statistics for equidistribution on the sphere. Mathematics of Computation 82, 284, 2137–2156.Google Scholar
    9. Cline, D., Jeschke, S., White, K., Razdan, A., and Wonka, P. 2009. Dart throwing on surfaces. In Proc. EGSR ’09, Eurographics Association, 1217–1226. Google ScholarDigital Library
    10. Cohen, M., Shade, J., Hiller, S., and Deussen, O. 2003. Wang tiles for image and texture generation. ACM Trans. on Graphics 22, 3, 287–294. Google ScholarDigital Library
    11. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. Google ScholarDigital Library
    12. Crow, F. C. 1977. The aliasing problem in computer-generated shaded images. Commun. ACM 20, 11, 799–805. Google ScholarDigital Library
    13. Cui, J., and Freeden, W. 1997. Equidistribution on the sphere. SIAM Scientific Computing 18, 2, 595–609. Google ScholarDigital Library
    14. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. Proc. SIGGRAPH Asia ’12 31, 171:1–171:10. Google ScholarDigital Library
    15. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In Proc. SIGGRAPH ’85, ACM, 69–78. Google ScholarDigital Library
    16. Dunbar, D., and Humphreys, G. 2006. A spatial data structure for fast Poisson-disk sample generation. In Proc. SIGGRAPH ’06, ACM, 503–508. Google ScholarDigital Library
    17. Durand, F. 2011. A frequency analysis of Monte-Carlo and other numerical integration schemes. MIT CSAIL Technical report TR-2011-052.Google Scholar
    18. Gabrielli, A., and Torquato, S. 2004. Voronoi and void statistics for superhomogeneous point processes. Physical Review E 70, 4, 041105.Google ScholarCross Ref
    19. Gamito, M. N., and Maddock, S. C. 2009. Accurate multidimensional Poisson-disk sampling. ACM Trans. on Graphics 29, 1, 8. Google ScholarDigital Library
    20. Górski, K. M., Hivon, E., Banday, A. J., Wandelt, B. D., Hansen, F. K., Reinecke, M., and Bartelmann, M. 2005. Healpix: A framework for high-resolution discretization and fast analysis of data distributed on the sphere. The Astrophysical Journal 622, 2, 759.Google ScholarCross Ref
    21. Groemer, H. 1996. Geometric Applications of Fourier Series and Spherical Harmonics. Cambridge University Press. Cambridge Books Online.Google Scholar
    22. Hansen, J.-P., and McDonald, I. R. 1990. Theory of simple liquids. Elsevier.Google Scholar
    23. Heck, D., Schlömer, T., and Deussen, O. 2013. Blue noise sampling with controlled aliasing. ACM Trans. on Graphics 32, 3, 25:1–25:12. Google ScholarDigital Library
    24. Hesse, K., Sloan, I., and Womersley, R. 2010. Numerical integration on the sphere. In Handbook of Geomathematics, W. Freeden, M. Nashed, and T. Sonar, Eds. Springer Berlin Heidelberg, 1185–1219.Google Scholar
    25. Jarosz, W., Carr, N. A., and Jensen, H. W. 2009. Importance sampling spherical harmonics. Computer Graphics Forum (Proceedings of Eurographics) 28, 2 (Apr.), 577–586.Google ScholarCross Ref
    26. Kautz, J., Sloan, P.-P., and Snyder, J. 2002. Fast, arbitrary brdf shading for low-frequency lighting using spherical harmonics. In Proc. of the 13th Eurographics Workshop on Rendering, Eurographics Association, 291–296. Google ScholarDigital Library
    27. Kazhdan, M. 2007. An approximate and efficient method for optimal rotation alignment of 3d models. IEEE Trans. Pattern Anal. Mach. Intell. 29, 7, 1221–1229. Google ScholarDigital Library
    28. Keller, A., Premoze, S., and Raab, M. 2012. Advanced (quasi) Monte Carlo methods for image synthesis. In SIGGRAPH ’12 Courses, ACM, New York, USA, 21:1–21:46. Google ScholarDigital Library
    29. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive wang tiles for real-time blue noise. ACM Trans. on Graphics 25, 3, 509–518. Google ScholarDigital Library
    30. Lemieux, C. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer.Google Scholar
    31. Li, H., Wei, L.-Y., Sander, P. V., and Fu, C.-W. 2010. Anisotropic blue noise sampling. In Proc. SIGGRAPH Asia ’10, ACM, 167:1–167:12. Google ScholarDigital Library
    32. Marques, R., Bouville, C., Ribardire, M., Santos, L. P., and Bouatouch, K. 2013. Spherical Fibonacci point sets for illumination integrals. Computer Graphics Forum 32, 8, 134–143.Google ScholarCross Ref
    33. McEwen, J., and Wiaux, Y. 2011. A novel sampling theorem on the sphere. Signal Processing, IEEE Trans. on 59, 12, 5876–5887. Google ScholarDigital Library
    34. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In Proc. SIGGRAPH ’87, 65–72. Google ScholarDigital Library
    35. Mitchell, D. 1991. Spectrally optimal sampling for distributed ray tracing. In Proc. SIGGRAPH ’91, vol. 25, 157–164. Google ScholarDigital Library
    36. Mitchell, D. P. 1996. Consequences of stratified sampling in graphics. In Proc. SIGGRAPH ’96, ACM, 277–280. Google ScholarDigital Library
    37. Niederreiter, H. 1992. Random Number Generation and Quasi-Monte-Carlo Methods. SIAM. Google ScholarDigital Library
    38. Ostromoukhov, V. 2007. Sampling with polyominoes. In ACM Trans. on Graphics, vol. 26, 78. Google ScholarDigital Library
    39. Öztireli, A. C., and Gross, M. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6, 174:1–174:6. Google ScholarDigital Library
    40. Peyrot, J.-L., Payan, F., and Antonini, M. 2013. Feature-preserving direct blue noise sampling for surface meshes. In Eurographics 2013, 4 pages.Google Scholar
    41. Ramamoorthi, R., and Hanrahan, P. 2001. A signal-processing framework for inverse rendering. In Proc. SIGGRAPH ’01, ACM, 117–128. Google ScholarDigital Library
    42. Ramamoorthi, R., Anderson, J., Meyer, M., and Nowrouzezahrai, D. 2012. A theory of monte carlo visibility sampling. ACM Trans. on Graphics 31, 5, 121:1–121:16. Google ScholarDigital Library
    43. Schlömer, T., Heck, D., and Deussen, O. 2011. Farthest-point optimized point sets with maximized minimum distance. In Proc. Symp. High Performance Graphics ’11, ACM, 135–142. Google ScholarDigital Library
    44. Shirley, P. 1991. Discrepancy as a quality measure for sample distributions. In Proc. Eurographics ’91, 183–194.Google Scholar
    45. 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 ’02, ACM, 527–536. Google ScholarDigital Library
    46. Subr, K., and Kautz, J. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. on Graphics 32, 4, 128:1–128:12. Google ScholarDigital Library
    47. Subr, K., Nowrouzezahrai, D., Jarosz, W., Kautz, J., and Mitchell, K. 2014. Error analysis of estimators that use combinations of stochastic sampling strategies for direct illumination. Computer Graphics Forum (Proceedings of EGSR) 33, 4 (June), 93102. Google ScholarDigital Library
    48. Torquato, S., Uche, O., and Stillinger, F. 2006. Random sequential addition of hard spheres in high euclidean dimensions. Physical Review E 74, 6, 061308.Google ScholarCross Ref
    49. Ulichney, R. 1987. Digital Halftoning. MIT Press. Google ScholarDigital Library
    50. Ureña, C., Fajardo, M., and King, A. 2013. An area-preserving parametrization for spherical rectangles. Computer Graphics Forum 32, 4, 59–66. Google ScholarDigital Library
    51. Wachtel, F., Pilleboue, A., Coeurjolly, D., Breeden, K., Singh, G., Cathelin, G., de Goes, F., Desbrun, M., and Ostromoukhov, V. 2014. Fast tile-based adaptive sampling with user-specified Fourier spectra. ACM Trans. on Graphics 33, 4, 56:1–56:11. Google ScholarDigital Library
    52. Wieczorek, M. A., and Simons, F. J. 2005. Localized spectral analysis on the sphere. Geophysical Journal International 162, 3, 655–675.Google ScholarCross Ref
    53. Xu, Y., Hu, R., Gotsman, C., and Liu, L. 2012. Blue noise sampling of surfaces. Computers & Graphics 36, 4, 232–240. Google ScholarDigital Library
    54. Zhou, Y., Huang, H., Wei, L.-Y., and Wang, R. 2012. Point sampling with general noise spectrum. ACM Transactions on Graphics (TOG) 31, 4, 76. Google ScholarDigital Library

ACM Digital Library Publication: