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

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