“Convergence analysis for anisotropic monte carlo sampling spectra” by Singh and Jarosz
Conference:
Type(s):
Title:
- Convergence analysis for anisotropic monte carlo sampling spectra
Session/Category Title: Random Sampling
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Traditional Monte Carlo (MC) integration methods use point samples to numerically approximate the underlying integral. This approximation introduces variance in the integrated result, and this error can depend critically on the sampling patterns used during integration. Most of the well-known samplers used for MC integration in graphics—e.g. jittered, Latin-hypercube (N-rooks), multijittered—are anisotropic in nature. However, there are currently no tools available to analyze the impact of such anisotropic samplers on the variance convergence behavior of Monte Carlo integration. In this work, we develop a Fourier-domain mathematical tool to analyze the variance, and subsequently the convergence rate, of Monte Carlo integration using any arbitrary (anisotropic) sampling power spectrum. We also validate and leverage our theoretical analysis, demonstrating that judicious alignment of anisotropic sampling and integrand spectra can improve variance and convergence rates in MC rendering, and that similar improvements can apply to (anisotropic) deterministic samplers.
References:
1. Abdalla G. M. Ahmed, Hui Huang, and Oliver Deussen. 2015. AA Patterns for Point Sets with Controlled Spectral Properties. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 34, 6, Article 212 (Oct. 2015), 8 pages. Google ScholarDigital Library
2. Abdalla G. M. Ahmed, Hélène Perrier, David Coeurjolly, Victor Ostromoukhov, Jianwei Guo, Dong-Ming Yan, Hui Huang, and Oliver Deussen. 2016. Low-discrepancy Blue Noise Sampling. ACM Trans. Graph. (Proc. SIGGRAPH) 35, 6, Article 247 (Nov. 2016), 13 pages. Google ScholarDigital Library
3. Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun. 2003. Anisotropic Polygonal Remeshing. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 22, 3 (July 2003), 9. Google ScholarDigital Library
4. Tom M. Apostol. 1974. Mathematical Analysis. Addison-Wesley Publishing Company.Google Scholar
5. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-Constrained Point Distributions: A Variant of Lloyd’s Method. ACM Trans. Graph. (Proc. SIGGRAPH) 28, 3 (2009).Google ScholarDigital Library
6. Laurent Belcour, Cyril Soler, Kartic Subr, Nicolas Holzschuch, and Fredo Durand. 2013. 5D Covariance Tracing for Efficient Defocus and Motion Blur. ACM Transactions on Graphics 32, 3, Article 31 (July 2013), 18 pages.Google ScholarDigital Library
7. Luca Brandolini, Leonardo Colzani, and Andrea Torlaschi. 2001. Mean square decay of Fourier transforms in Euclidean and non Euclidean spaces. Tohoku Math. J. (2) 53, 3 (2001). Google ScholarCross Ref
8. Luca Brandolini, Steve Hofmann, and Alex Iosevich. 2003. Sharp rate of average decay of the Fourier transform of a bounded set. Geometric & Functional Analysis GAFA 13, 4 (2003). Google ScholarCross Ref
9. Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Transactions on Graphics 5, 1 (Jan. 1986). Google ScholarDigital Library
10. Robert L. Cook, Thomas Porter, and Loren Carpenter. 1984. Distributed Ray Tracing. Computer Graphics (Proc. SIGGRAPH) 18, 3 (Jan. 1984). Google ScholarDigital Library
11. Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue Noise through Optimal Transport. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 31 (2012). Issue 6.Google Scholar
12. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing Through Stochastic Sampling. Computer Graphics (Proc. SIGGRAPH) (1985).Google Scholar
13. Mark A. Z. Dippé and Erling Henry Wold. 1992. Progress in Computer Graphics (Vol. 1). Ablex Publishing Corp., Norwood, NJ, USA, Chapter Stochastic Sampling: Theory and Application.Google Scholar
14. Frédo Durand. 2011. A frequency analysis of Monte-Carlo and other numerical integration schemes. Technical Report TR-2011–052. MIT CSAIL.Google Scholar
15. Frédo Durand, Nicolas Holzschuch, Cyril Soler, Eric Chan, and François X. Sillion. 2005. A Frequency Analysis of Light Transport. ACM Trans. Graph. (Proc. SIGGRAPH) 24, 3 (July 2005), 1115–1126. Google ScholarDigital Library
16. Kevin Egan, Frédo Durand, and Ravi Ramamoorthi. 2011. Practical Filtering for Efficient Ray-traced Directional Occlusion. ACM Trans. Graph. 30, 6, Article 180 (Dec. 2011), 10 pages. Google ScholarDigital Library
17. Kevin Egan, Yu-Ting Tseng, Nicolas Holzschuch, Frédo Durand, and Ravi Ramamoorthi. 2009. Frequency Analysis and Sheared Reconstruction for Rendering Motion Blur. ACM Trans. Graph. (Proc. SIGGRAPH) 28, 3, Article 93 (July 2009), 13 pages. Google ScholarDigital Library
18. Louis Feng, Ingrid Hotz, Bernd Hamann, and Kenneth I Joy. 2008. Anisotropic noise samples. Visualization and Computer Graphics, IEEE Transactions on 14, 2 (2008).Google Scholar
19. Andrea Gabrielli and Salvatore Torquato. 2004. Voronoi and void statistics for superhomogeneous point processes. Physical Review E 70, 4 (2004). Google ScholarCross Ref
20. Iliyan Georgiev and Marcos Fajardo. 2016. Blue-noise Dithered Sampling. In ACM SIGGRAPH 2016 Talks. ACM, New York, NY, USA, Article 35, 1 pages. Google ScholarDigital Library
21. Toshiya Hachisuka, Wojciech Jarosz, Richard Peter Weistroffer, Kevin Dale, Greg Humphreys, Matthias Zwicker, and Henrik Wann Jensen. 2008. Multidimensional Adaptive Sampling and Reconstruction for Ray Tracing. ACM Trans. Graph. (Proc. SIGGRAPH) 27, 3, Article 33 (Aug. 2008), 10 pages. Google ScholarDigital Library
22. John H. Halton. 1960. On the Efficiency of Certain Quasi-random Sequences of Points in Evaluating Multi-dimensional Integrals. Numer. Math. 2, 1 (Dec. 1960), 7.Google ScholarDigital Library
23. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue Noise Sampling with Controlled Aliasing. ACM Transactions on Graphics 32, 3 (2013). Google ScholarDigital Library
24. Janine Illian, P. Antti Penttinen, Helga Stoyan, and Dietrich Stoyan. 2008. Statistical Analysis and Modelling of Spatial Point Patterns. Wiley.Google Scholar
25. Howard .J. Keisler. 2012. Elementary Calculus: An Infinitesimal Approach. Dover Publications.Google Scholar
26. Andrew Kensler. 2013. Correlated multi-jittered sampling. (2013).Google Scholar
27. Ares Lagae and Philip Dutré. 2008. A Comparison of Methods for Generating Poisson Disk Distributions. Comp. Graph. Forum 27, 1 (2008).Google Scholar
28. Jaakko Lehtinen, Timo Aila, Jiawen Chen, Samuli Laine, and Frédo Durand. 2011. Temporal Light Field Reconstruction for Rendering Distribution Effects. ACM Trans. Graph. 30, 4, Article 55 (July 2011), 12 pages. Google ScholarDigital Library
29. Oscar AZ Leneman. 1966. Random sampling of random processes: Impulse processes. Information and Control 9, 4 (1966).Google Scholar
30. Bruno Lévy and Yang Liu. 2010. Lp Centroidal Voronoi Tessellation and Its Applications. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 29, 4, Article 119 (July 2010), 11 pages.Google Scholar
31. Hongwei Li, Li-Yi Wei, Pedro V. Sander, and Chi-Wing Fu. 2010. Anisotropic Blue Noise Sampling. ACM Trans. Graph. (Proc. SIGGRAPH Asia) 29, 6 (Dec. 2010). Google ScholarDigital Library
32. Soham Uday Mehta, Brandon Wang, and Ravi Ramamoorthi. 2012. Axis-aligned Filtering for Interactive Sampled Soft Shadows. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 6, Article 163 (Nov. 2012), 10 pages. Google ScholarDigital Library
33. Soham Uday Mehta, JiaXian Yao, Ravi Ramamoorthi, and Fredo Durand. 2014. Factored Axis-aligned Filtering for Rendering Multiple Distribution Effects. ACM Trans. Graph. (Proc. SIGGRAPH) 33, 4, Article 57 (July 2014), 12 pages. Google ScholarDigital Library
34. Don P. Mitchell. 1991. Spectrally Optimal Sampling for Distributed Ray Tracing. Computer Graphics (Proc. SIGGRAPH) 25, 4 (1991).Google Scholar
35. Don P. Mitchell. 1996. Consequences of Stratified Sampling in Graphics. In Annual Conference Series (Proc. SIGGRAPH). ACM. Google ScholarDigital Library
36. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Transactions on Graphics 35, 5, Article 160 (Aug. 2016), 16 pages.Google ScholarDigital Library
37. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory To Implementation (3rd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.Google Scholar
38. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance Analysis for Monte Carlo Integration. ACM Trans. Graph. (Proc. SIGGRAPH) 34, 4 (July 2015). Google ScholarDigital Library
39. Ravi Ramamoorthi, John Anderson, Mark Meyer, and Derek Nowrouzezahrai. 2012. A Theory of Monte Carlo Visibility Sampling. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 5 (2012).Google ScholarDigital Library
40. Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective Blue Noise Sampling. Comp. Graph. Forum (2016).Google Scholar
41. Peter .S. Shirley. 1991. Discrepancy as a Quality Measure for Sample Distributions. In Proc. Eurographics.Google Scholar
42. Ilya M. Sobol. 1967. On the distribution of points in a cube and the approximate evaluation of integrals. U. S. S. R. Comput. Math. and Math. Phys. 7, 4 (1967), 86 — 112. Google ScholarCross Ref
43. Cyril Soler, Kartic Subr, Frédo Durand, Nicolas Holzschuch, and François Sillion. 2009. Fourier Depth of Field. ACM Transactions on Graphics 28, 2, Article 18 (May 2009), 12 pages.Google ScholarDigital Library
44. Kartic Subr and Jan Kautz. 2013. Fourier Analysis of Stochastic Sampling Strategies for Assessing Bias and Variance in Integration. ACM Trans. Graph. (Proc. SIGGRAPH) 32, 4 (July 2013). Google ScholarDigital Library
45. Kartic Subr, Derek Nowrouzezahrai, Wojciech Jarosz, Jan Kautz, and Kenny Mitchell. 2014. Error analysis of estimators that use combinations of stochastic sampling strategies for direct illumination. Comp. Graph. Forum (Proc. EGSR) 33, 4 (June 2014). Google ScholarDigital Library
46. Kartic Subr, Gurprit Singh, and Wojciech Jarosz. 2016. Fourier Analysis of Numerical Integration in Monte Carlo Rendering: Theory and Practice. In ACM SIGGRAPH 2016 Courses. ACM, New York, NY, USA, Article 10, 40 pages.Google ScholarDigital Library
47. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google Scholar
48. Karthik Vaidyanathan, Jacob Munkberg, Petrik Clarberg, and Marco Salvi. 2015. Layered Light Field Reconstruction for Defocus Blur. ACM Transactions on Graphics 34, 2, Article 23 (March 2015), 12 pages.Google ScholarDigital Library
49. Florent Wachtel, Adrien Pilleboue, David Coeurjolly, Katherine Breeden, Gurprit Singh, Gaël Cathelin, Fernando de Goes, Mathieu Desbrun, and Victor Ostromoukhov. 2014. Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra. ACM Trans. Graph. (Proc. SIGGRAPH) 33, 4 (2014).Google ScholarDigital Library
50. Li-Yi Wei, Chia-Kai Liang, Graham Myhre, Colvin Pitts, and Kurt Akeley. 2015. Improving Light Field Camera Sample Design with Irregularity and Aberration. ACM Trans. Graph. (Proc. SIGGRAPH) 34, 4, Article 152 (July 2015), 11 pages. Google ScholarDigital Library
51. Li-Yi Wei and Rui Wang. 2011. Differential Domain Analysis for Non-uniform Sampling. ACM Trans. Graph. 30, 4, Article 50 (July 2011), 10 pages. Google ScholarDigital Library
52. Turner Whitted. 1980. An Improved Illumination Model for Shaded Display. Commun. ACM 23, 6 (June 1980), 343–349. Google ScholarDigital Library
53. Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4 (2012).Google ScholarDigital Library
54. Matthias Zwicker, Wojciech Jarosz, Jaakko Lehtinen, Bochang Moon, Ravi Ramamoorthi, Fabrice Rousselle, Pradeep Sen, Cyril Soler, and Sung-Eui Yoon. 2015. Recent Advances in Adaptive Sampling and Reconstruction for Monte Carlo Rendering. Comp. Graph. Forum (Proc. Eurographics) 34, 2 (May 2015), 667–681. Google ScholarDigital Library
