Integration with Stochastic Point Processes

Abstract

We present a novel comprehensive approach for studying error in integral estimation with point distributions based on point process statistics. We derive exact formulae for bias and variance of integral estimates in terms of the spatial or spectral characteristics of integrands and first- and-second order product density measures of general point patterns. The formulae allow us to study and design sampling schemes adapted to different classes of integrands by analyzing the effect of sampling density, weighting, and correlations among point locations separately. We then focus on non-adaptive correlated stratified sampling patterns and specialize the formulae to derive closed-form and easy-to-analyze expressions of bias and variance for various stratified sampling strategies. Based on these expressions, we perform a theoretical error analysis for integrands involving the discontinuous visibility function. We show that significant reductions in error can be obtained by considering alternative sampling strategies instead of the commonly used random jittering or low discrepancy patterns. Our theoretical results agree with and extend various previous results, provide a unified analytic treatment of point patterns, and lead to novel insights. We validate the results with extensive experiments on benchmark integrands as well as real scenes with soft shadows.

References

1. Kristof Beets and Dave Barron. 2000. Super-sampling anti-aliasing analyzed. Beyond3D (2000), 1--22.
2. Laurent Belcour, Cyril Soler, Kartic Subr, Nicolas Holzschuch, and Fredo Durand. 2013. 5D covariance tracing for efficient defocus and motion blur. ACM Trans. Graph. 32, 3, Article 31 (July 2013), 18 pages. DOI:http://dx.doi.org/10.1145/2487228.2487239
3. John Bowers, Rui Wang, Li-Yi Wei, and David Maletz. 2010. Parallel poisson disk sampling with spectrum analysis on surfaces. ACM Trans. Graph. 29, Article 166 (December 2010), 10 pages. Issue 6. DOI:http://dx.doi.org/10.1145/1882261.1866188
4. Kenneth Chiu, Peter Shirley, and Changyaw Wang. 1994. Graphics Gems IV. Academic Press, San Diego, CA, 370--374.
5. Robert L. Cook. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1 (1986), 51--72. DOI:http://dx.doi.org/10.1145/7529.8927
6. Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, New York, NY.
7. Daniel Dunbar and Greg Humphreys. 2006. A spatial data structure for fast poisson-disk sample generation. ACM Trans. Graph. 25 (July 2006), 503--508. Issue 3. DOI:http://dx.doi.org/10.1145/1141911.1141915
8. Fredo Durand. 2011. A Frequency Analysis of Monte-Carlo and Other Numerical Integration Schemes. Technical Report MIT-CSAILTR-2011-052. CSAIL, MIT, MA.
9. Frédo Durand, Nicolas Holzschuch, Cyril Soler, Eric Chan, and François X. Sillion. 2005. A frequency analysis of light transport. ACM Trans. Graph. 24, 3 (July 2005), 1115--1126. DOI:http://dx.doi.org/10.1145/1073204.1073320
10. Mohamed S. Ebeida, Scott A. Mitchell, Anjul Patney, Andrew A. Davidson, and John D. Owens. 2012. A simple algorithm for maximal poisson-disk sampling in high dimensions. Comput. Graph. Forum 31, 2pt4 (2012), 785--794. DOI:http://dx.doi.org/10.1111/j.1467-8659.2012.03059.x
11. Kevin Egan, Frédo Durand, and Ravi Ramamoorthi. 2011a. Practical filtering for efficient ray-traced directional occlusion. ACM Trans. Graph. 30, 6, Article 180 (Dec. 2011), 10 pages. DOI:http://dx.doi.org/10.1145/2070781.2024214
12. Kevin Egan, Florian Hecht, Frédo Durand, and Ravi Ramamoorthi. 2011b. Frequency analysis and sheared filtering for shadow light fields of complex occluders. ACM Trans. Graph. 30, 2, Article 9 (April 2011), 13 pages. DOI:http://dx.doi.org/10.1145/1944846.1944849
13. 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. 28, 3, Article 93 (July 2009), 13 pages. DOI:http://dx.doi.org/10.1145/1531326.1531399
14. Raanan Fattal. 2011. Blue-noise point sampling using kernel density model. ACM Trans. Graph. 30, 4, Article 48 (July 2011), 12 pages. DOI:http://dx.doi.org/10.1145/2010324.1964943
15. Joseph Felsenstein. 1975. A pain in the torus: Some difficulties with models of isolation by distance. Am. Nat. 109, 967 (1975), 359--368.
16. Yongtao Guan. 2008. Variance estimation for statistics computed from inhomogeneous spatial point processes. J. Roy. Stat. Soc. Ser. B 70, 1 (2008), pp. 175--190. http://www.jstor.org/stable/20203817.
17. 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. 27, 3, Article 33 (Aug. 2008), 10 pages. DOI:http://dx.doi.org/10.1145/1360612.1360632
18. J. M. Hammersley and K. W. Morton. 1956. A new Monte Carlo technique: Antithetic variates. Math. Proc. Cambr. Philos. Soc. 52 (7 1956), 449--475. Issue 03. DOI:http://dx.doi.org/10.1017/S0305004100031455
19. Jon Hasselgren, Tomas Akenine-Mller, and Samuli Laine. 2005. A family of inexpensive sampling schemes. Comput. Graph. Forum 24, 4 (2005), 843--848. http://dblp.uni-trier.de/db/journals/cgf/cgf24.html#HasselgrenAL05.
20. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue noise sampling with controlled aliasing. ACM Trans. Graph. 32, 3, Article 25 (July 2013), 12 pages. DOI:http://dx.doi.org/10.1145/2487228.2487233
21. Janine Illian, Antti Penttinen, Helga Stoyan, and Dietrich Stoyan (Eds.). 2008. Statistical Analysis and Modelling of Spatial Point Patterns. John Wiley and Sons, New York, NY.
22. Alexander Keller, Simon Premoze, and Matthias Raab. 2012. Advanced (quasi) Monte Carlo methods for image synthesis. In ACM SIGGRAPH 2012 Courses (SIGGRAPH’12). ACM, New York, NY, Article 21, 46 pages. DOI:http://dx.doi.org/10.1145/2343483.2343502
23. Andrew Kensler. 2013. Correlated Multi-Jittered Sampling. Technical Report Pixar Technical Memo 13-01. Pixar.
24. David Kirk and James Arvo. 1991. Unbiased sampling techniques for image synthesis. SIGGRAPH Comput. Graph. 25, 4 (July 1991), 153--156. DOI:http://dx.doi.org/10.1145/127719.122735
25. Thomas Kollig and Alexander Keller. 2002. Efficient multidimensional sampling. Comput. Graph. Forum 21, 3 (2002), 557--563. http://dblp.uni-trier.de/db/journals/cgf/cgf21.html#KolligK02.
26. Ares Lagae and Philip Dutré. 2008. A comparison of methods for generating poisson disk distributions. Comput. Graph. Forum 27, 1 (March 2008), 114--129. DOI:http://dx.doi.org/10.1111/j.1467-8659.2007.01100.x
27. Soham Uday Mehta, Brandon Wang, and Ravi Ramamoorthi. 2012. Axis-aligned filtering for interactive sampled soft shadows. ACM Trans. Graph. 31, 6, Article 163 (Nov. 2012), 10 pages. DOI:http://dx.doi.org/10.1145/2366145.2366182
28. Soham Uday Mehta, Brandon Wang, Ravi Ramamoorthi, and Fredo Durand. 2013. Axis-aligned filtering for interactive physically-based diffuse indirect lighting. ACM Trans. Graph. 32, 4, Article 96 (July 2013), 12 pages. DOI:http://dx.doi.org/10.1145/2461912.2461947
29. Soham Uday Mehta, JiaXian Yao, Ravi Ramamoorthi, and Fredo Durand. 2014. Factored axis-aligned filtering for rendering multiple distribution effects. ACM Trans. Graph. 33, 4, Article 57 (July 2014), 12 pages. DOI:http://dx.doi.org/10.1145/2601097.2601113
30. Don P. Mitchell. 1987. Generating antialiased images at low sampling densities. SIGGRAPH Comput. Graph. 21, 4 (Aug. 1987), 65--72. DOI:http://dx.doi.org/10.1145/37402.37410
31. Don P. Mitchell. 1991. Spectrally optimal sampling for distribution ray tracing. SIGGRAPH Comput. Graph. 25, 4 (July 1991), 157--164. DOI:http://dx.doi.org/10.1145/127719.122736
32. Don P. Mitchell. 1996. Consequences of stratified sampling in graphics. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’96). ACM, New York, NY, 277--280. DOI:http://dx.doi.org/10.1145/237170.237265
33. Jesper Møller and Rasmus Plenge Waagepetersen. 2004. Statistical Inference and Simulation for Spatial Point Processes. Chapman & Hall/CRC, Boca Raton, FL. http://opac.inria.fr/record==b1128354.
34. H. Niederreiter. 1992. Quasi-Monte Carlo Methods. John Wiley & Sons, New York, NY.
35. Ryan S. Overbeck, Craig Donner, and Ravi Ramamoorthi. 2009. Adaptive wavelet rendering. ACM Trans. Graph. 28, 5, Article 140 (Dec. 2009), 12 pages. DOI:http://dx.doi.org/10.1145/1618452.1618486
36. Art B. Owen. 2008. Local antithetic sampling with scrambled nets. Ann. Stat. 36 (2008), 2319--2343. Issue 2008. DOI:http://dx.doi.org/10.1214/07-AOS548
37. Art B. Owen. 2013. Monte Carlo Theory, Methods and Examples. To be published. http://opac.inria.fr/record=b1128354.
38. A. Cengiz Öztireli and Markus Gross. 2012. Analysis and synthesis of point distributions based on pair correlation. ACM Trans. Graph. 31, 6, Article 170 (Nov. 2012), 10 pages. DOI:http://dx.doi.org/10.1145/2366145.2366189
39. Matt Pharr and Greg Humphreys. 2010. Physically Based Rendering, Second Edition: From Theory To Implementation (2nd ed.). Morgan Kaufmann, San Francisco, CA.
40. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance analysis for Monte Carlo integration. ACM Trans. Graph. 34, 4, Article 124 (July 2015), 14 pages. DOI:http://dx.doi.org/10.1145/2766930
41. Ravi Ramamoorthi, John Anderson, Mark Meyer, and Derek Nowrouzezahrai. 2012. A theory of Monte Carlo visibility sampling. ACM Trans. Graph. 31, 5, Article 121 (Sept. 2012), 16 pages. DOI:http://dx.doi.org/10.1145/2231816.2231819
42. Ravi Ramamoorthi and Pat Hanrahan. 2004. A signal-processing framework for reflection. ACM Trans. Graph. 23, 4 (Oct. 2004), 1004--1042. DOI:http://dx.doi.org/10.1145/1027411.1027416
43. Christian Schmaltz, Pascal Gwosdek, Andrs Bruhn, and Joachim Weickert. 2010. Electrostatic halftoning. Comput. Graph. Forum 29, 8 (2010), 2313--2327. DOI:http://dx.doi.org/10.1111/j.1467-8659.2010.01716.x
44. Peter Shirley. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics’91. Elsevier Science Publishers, Amsterdam, 183--194.
45. Cyril Soler, Kartic Subr, Frédo Durand, Nicolas Holzschuch, and François Sillion. 2009. Fourier depth of field. ACM Trans. Graph. 28, 2, Article 18 (May 2009), 12 pages. DOI:http://dx.doi.org/10.1145/1516522.1516529
46. Dietrich Stoyan and Helga Stoyan. 1994. Fractals, Random Shapes, and Point Fields : Methods of Geometrical Statistics. Wiley, New York, NY.
47. Kartic Subr and Jan Kautz. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graph. 32, 4, Article 128 (July 2013), 12 pages. DOI:http://dx.doi.org/10.1145/2461912.2462013
48. 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. Comput. Graph. Forum 33, 4 (2014), 93--102. DOI:http://dx.doi.org/10.1111/cgf.12416
49. Li-Yi Wei. 2008. Parallel poisson disk sampling. ACM Trans. Graph. 27, Article 20 (August 2008), 9 pages. Issue 3. DOI:http://dx.doi.org/10.1145/1360612.1360619
50. Li-Yi Wei. 2010. Multi-class blue noise sampling. ACM Trans. Graph. 29, 4, Article 79 (July 2010), 8 pages. DOI:http://dx.doi.org/10.1145/1778765.1778816
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. DOI:http://dx.doi.org/10.1145/2010324.1964945
52. Turner Whitted. 1980. An improved illumination model for shaded display. Commun. ACM 23, 6 (June 1980), 343--349. DOI:http://dx.doi.org/10.1145/358876.358882

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Numerical differentiation

    • Quadrature