Pixar Technical Memo 13-01
Correlated Multi-Jittered Sampling
Andrew Kensler
March 5, 2013
We present a new technique for generating sets of stratified samples on the
unit square. Though based on jittering, this method is competitive with low-
discrepancy quasi-Monte Carlo sequences while avoiding some of the struc-
tured artifacts to which they are prone. An efficient implementation is pro-
vided that allows repeatable, random access to the samples from any set
without the need for precomputation or storage. Further, these samples can
be either ordered (for tracing coherent ray bundles) or shuffled (for combin-
ing without correlation).
Introduction
Imagesynthesistechniques requiring MonteCarlointegrationfrequentlyneed
to generate uniformly distributed samples within the unit hypercube. The
ideal sample generation method will maximize the variance reduction as the
numberofsamples increases. Stratication via jitteringisonesimple, tractable, R. L. Cook. Stochastic sampling in computer
graphics. ACM Transactions on Graphics,
5(1):51–72, January 1986.
well known and well understood technique for generating samples, though
there are other methods.
Of these, low-discrepancy quasi-Monte Carlo (QMC) sequences such as
Sobol’s (0,2) sequence and the Larcher-Pillichshammer sequence have be- I. M. Sobol’. On the distribution of points in
a cube and the approximate evaluation of inte-
grals. USSR Computational Mathematics and
Mathematical Physics, 7(4):86–112, 1967.
G. Larcher and F. Pillichshammer. Walsh se-
ries analysis of the L
-discrepancy of symmetri-
sized point sets. Monatshee für Mathematik,
132:1–18, April 2001.
come quite popular for their deterministic generation and improved variance
reduction versus jitter. See Kollig and Keller for an overview. Many QMC
T. Kollig and A. Keller. Ecient multidimen-
sional sampling. Computer Graphics Forum,
21(3):557–563, September 2002.
sampling methods also oer easy random access to shued sets of samples.
This makes it easy to “pad” or combine together samples from several decor-
related lower-dimensional distributions into a single higher-dimensional sam-
ple (e.g., combining image samples, lens samples, material samples, and light
samples) whereas the equivalent shuing of jittered samples typically requires
enumerating the full set rst. Unfortunately, QMC methods can also beprone
to structured artifacts.
Therefore we seek an alternative that combines the robust foundation of
jittered sampling with the benets of QMC. Our new approach is based on
three main contributions: rst, a modication to Chiu et al’s multi-jittered
sampling that greatly improves the convergence rate. Second, a way to gener- K. Chiu, P. Shirley, and C. Wang. Multi-jittered
sampling. In Graphics Gems IV, chapter V.4,
pages 370–374. Academic Press, May 1994.
ate patterns with arbitrary sample counts (including prime numbers) without
noticeable gaps or clumps. Finally, we provide an implementation that builds
a pseudorandom permutation function out of a reversable hash. This allows
us to compute any arbitrary sample directly from its index and a pattern index.
Multi-Jittered Sampling
In 2D, jittered sampling straties a set of N samples by dividing the unit square
into equal area cells using an m × n grid (where N = mn and m ≈ n) and
randomly positioning a single sample within each cell. This reduces clump-
ing since samples can only clump near the cell boundaries; no more than four
samples can ever clump near a given location.
1