Fourier analysis of correlated Monte Carlo importance sampling

1Max-Planck Institute for Informatics, Saarbrücken, Germany 2University of Edinburgh, UK 3Université de Lyon, CNRS/LIRIS, France 4Dartmouth College, USA

In Computer Graphics Forum, 2019

Teaser
The convergence rate of Monte Carlo integration with correlated (jittered) samples depends on the importance function (light vs. BSDF). We analyze two Pixels P & Q directly illuminated by a square area light source in (a). Pixel P is fully visible from the light source, which results in a smooth integrand when performing light source surface area sampling (visualized in bottom-left b) and a convergence rate of O(N-2) (c: dot-dashed green curve, all plots are in log-log scale). C0 discontinuities in the integrand result in O(N-1.5) convergence, which can happen: when using Cranley-Patterson rotation (CPr, solid green curve) since it introduces boundary discontinuities; when the light source is partially occluded (Pixel Q); or when sampling the BSDF (in magenta) since this treats the boundary of the light as a C0 discontinuity even when the light is fully visible (visualized in the second column of b).

Abstract

Fourier analysis is gaining popularity in image synthesis as a tool for the analysis of error in Monte Carlo (MC) integration. Still, existing tools are only able to analyze convergence under simplifying assumptions (such as randomized shifts) which are not applied in practice during rendering. We reformulate the expressions for bias and variance of sampling-based integrators to unify non-uniform sample distributions (importance sampling) as well as correlations between samples while respecting finite sampling domains. Our unified formulation hints at fundamental limitations of Fourier-based tools in performing variance analysis for MC integration. At the same time, it reveals that, when combined with correlated sampling, importance sampling (IS) can impact convergence rate by introducing or inhibiting discontinuities in the integrand. We demonstrate that the convergence of multiple importance sampling (MIS) is determined by the strategy which converges slowest and propose several simple approaches to overcome this limitation. We show that smoothing light boundaries (as commonly done in production to reduce variance) can improve (M)IS convergence (at a cost of introducing a small amount of bias) since it removes C0 discontinuities within the integration domain. We also propose practical integrand- and sample-mirroring approaches which cancel the impact of boundary discontinuities on the convergence rate of estimators.

Downloads

Acknowledgements

We are grateful to all the anonymous reviewers for their constructive remarks, Tobias Ritschel for suggesting minor edits in Figure 7. This work was partially supported by the Fraunhofer and Max Planck cooperation program within the German pact for research and innovation (PFI) and NSF grant CNS-1205521. Kartic Subr was supported by a Royal Society University Research Fellowship and Wojciech Jarosz was partially supported by NSF grant IIS-181279.

Cite

Gurprit Singh, Kartic Subr, David Coeurjolly, Victor Ostromoukhov, Wojciech Jarosz. Fourier analysis of correlated Monte Carlo importance sampling. Computer Graphics Forum, 38(1), April 2019.
@article{singh19fourier,
    author = "Singh, Gurprit and Subr, Kartic and Coeurjolly, David and Ostromoukhov, Victor and Jarosz, Wojciech",
    title = "Fourier analysis of correlated {{Monte}} {{Carlo}} importance sampling",
    journal = "Computer Graphics Forum",
    volume = "38",
    number = "1",
    year = "2019",
    month = apr,
    doi = "10/gfznck",
    abstract = "Fourier analysis is gaining popularity in image synthesis as a tool for the analysis of error in Monte Carlo (MC) integration. Still, existing tools are only able to analyze convergence under simplifying assumptions (such as randomized shifts) which are not applied in practice during rendering. We reformulate the expressions for bias and variance of sampling-based integrators to unify non-uniform sample distributions (importance sampling) as well as correlations between samples while respecting finite sampling domains. Our unified formulation hints at fundamental limitations of Fourier-based tools in performing variance analysis for MC integration. At the same time, it reveals that, when combined with correlated sampling, importance sampling (IS) can impact convergence rate by introducing or inhibiting discontinuities in the integrand. We demonstrate that the convergence of multiple importance sampling (MIS) is determined by the strategy which converges slowest and propose several simple approaches to overcome this limitation. We show that smoothing light boundaries (as commonly done in production to reduce variance) can improve (M)IS convergence (at a cost of introducing a small amount of bias) since it removes C0 discontinuities within the integration domain. We also propose practical integrand- and sample-mirroring approaches which cancel the impact of boundary discontinuities on the convergence rate of estimators."
}
© The Author(s). This is the author's version of the work. It is posted here by permission of The Eurographics Association for your personal use. Not for redistribution. The definitive version is available at diglib.eg.org.