Fourier Analysis of Correlated Monte Carlo Importance Sampling


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. This non-trivial exercise also provides exciting insight into the effects of importance sampling on the convergence rate of estimators because of the introduction or removal of discontinuities. Specifically, we demonstrate that the convergence of multiple importance sampling (MIS) is determined by the strategy that converges slowest. We propose two simple and practical approaches to limit the impact of discontinuities on the convergence rate of estimators: The first one involves mirroring the integrand to cancel out the effect of boundary discontinuities. This is followed by two novel mirror sampling techniques for MC estimation in this mirrored domain. The second approach improves direct illumination light sampling by smoothing out discontinuities within the domain at the cost of introducing a small amount of bias. Our approaches are simple, practical and can be easily incorporated in production renderers.

Computer Graphics Forum

Caption: 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 homogenization or Cranley-Patterson rotation [CP76] (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).

      author = {Gurprit Singh and Kartic Subr and David Coeurjolly and Victor Ostromoukhov and Wojciech Jarosz},
      doi = {10.1111/cgf.13613},
      journal = {Computer Graphics Forum},
      number = {4},
      title = {Fourier Analysis of Correlated Monte Carlo Importance Sampling},
      volume = {37},
      year = {2019}