Variance and convergence analysis of Monte Carlo line and segment sampling

1Dartmouth College

In Computer Graphics Forum (Proceedings of EGSR), 2017

We analyze the impact of line sample orientation on variance and convergence rate. Line samples on the light source are generated parallel to the edge above pixel A. Consequently, the regions below the left side of the triangle occluder see a step function (shown for Pixel A in second column) and benefit only from dimensionality reduction. The other two sides of the occluder benefit from both dimensionality reduction and smoothing of the integrand (shown for Pixel B in the second column).


Recently researchers have started employing Monte Carlo-like line sample estimators in rendering, demonstrating dramatic reductions in variance (visible noise) for effects such as soft shadows, defocus blur, and participating media. Unfortunately, there is currently no formal theoretical framework to predict and analyze Monte Carlo variance using line and segment samples which have inherently anisotropic Fourier power spectra. In this work, we propose a theoretical formulation for lines and finite-length segment samples in the frequency domain that allows analyzing their anisotropic power spectra using previous isotropic variance and convergence tools. Our analysis shows that judiciously oriented line samples not only reduce the dimensionality but also pre-filter C0 discontinuities, resulting in further improvement in variance and convergence rates. Our theoretical insights also explain how finite-length segment samples impact variance and convergence rates only by pre-filtering discontinuities. We further extend our analysis to consider (uncorrelated) multi-directional line (segment) sampling, showing that such schemes can increase variance compared to unidirectional sampling. We validate our theoretical results with a set of experiments including direct lighting, ambient occlusion, and volumetric caustics using points, lines, and segment samples.



Gurprit Singh, Bailey Miller, Wojciech Jarosz. Variance and convergence analysis of Monte Carlo line and segment sampling. Computer Graphics Forum (Proceedings of EGSR), 36(4), June 2017.
    author    = {Singh, Gurprit and Miller, Bailey and Jarosz, Wojciech},
    title     = {Variance and convergence analysis of {{Monte}} {{Carlo}} Line and Segment Sampling},
    journal   = {Computer Graphics Forum (Proceedings of EGSR)},
    year      = {2017},
    volume    = {36},
    number    = {4},
    month     = jun,
    doi       = {10/gfzncj},
    publisher = {The Eurographics Association},
    keywords  = {stochastic sampling, signal processing, Fourier transform, Power spectrum}
© 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