Cascaded Sobol' Sampling


Rendering quality is largely influenced by the samplers used in Monte Carlo integration. Important factors include sample uniformity (e.g., low discrepancy) in the high-dimensional integration domain, sample uniformity in lower-dimensional projections, and lack of dominant structures that could result in aliasing artifacts. A widely used and successful construction is the Sobol’ sequence that guarantees good high-dimensional uniformity and consequently results in faster convergence of quasi-Monte Carlo integration. We show that this sequence exhibits low uniformity and dominant structures in low-dimensional projections. These structures impair quality in the context of rendering, as they precisely occur in the 2-dimensional projections used for sampling light sources, reflectance functions, or the camera lens or sensor. We propose a new cascaded construction, which, despite dropping the sequential aspect of Sobol’ samples, produces point sets exhibiting provably perfect dyadic partitioning (and therefore, excellent uniformity) in consecutive 2-dimensional projections, while preserving good high-dimensional uniformity. By optimizing the initialization parameters and performing Owen scrambling at finer levels of binary representations, we further improve over Sobol’s integration convergence rate. Our method does not incur any overhead as compared to the generation of the Sobol’ sequence, is compatible with Owen scrambling and can be used in rendering applications.

ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), 40(6), pp. 274:1–274:13
fast forward 5min talk 12 min talk

Caption: Cascaded Sobol’ Point Sets. For quasi-Monte Carlo integration problems, low discrepancy samplers, such as the Sobol’ sequence with Owen scrambling [Owen 1998; Sobol’ 1967], are widely used thanks to their ease of generating high-dimensional point sets. While being low discrepancy in high dimension, some projections may exhibit strong uniformity defects (illustrated here by consecutive 2-dimensional projections of an 11-dimensional point set in the first row). We propose a sampling strategy with perfect (0,m,2)−net properties (second row) for consecutive pairs of dimensions and optimized low discrepancy in high dimension, reducing errors in Monte Carlo rendering. The third row shows L2-discrepancies of first 10 consecutive 2-dimensional projections; (see paper Figure 7 for s-dimensional discrepancies).

  author =       {Loïs Paulin and David Coeurjolly and Jean-Claude
                  Iehl and Nicolas Bonneel and Alexander Keller and
                  Victor Ostromoukhov},
  title =        {Cascaded Sobol' Sampling},
  journal =      tog_siggraphasia,
  year =         2021,
  month =        dec,
  volume = 40,
  number = 6,
  pages = {274:1--274:13}