Progressive Multi-Jittered Sample Sequences

This is a C++ implementation of Progressive Multi-Jittered Sample Sequences (in 2D), based off two papers:

• Progressive Multi-Jittered Sample Sequences (2018) by Christensen, Kensler, and Kilpatrick
• Efficient Generation of Points that Satisfy Two-Dimensional Elementary Intervals (2019) by Matt Pharr

Much thanks to Per Christensen and Matt Pharr for help and encouragement with this implementation.

For a Rust version, see Simon Brown's implementation. Simon had a key insight on how to optimally pick subquadrants during sample generation, which improved the quality of the sequences generated by this code.

These sample sequences are really great for certain types of Monte Carlo integration problems, especially for use in computer graphics rendering. Here's one such sequence, with a subdividing grid to illustrate the most basic progressive stratification.

^{Generated with this Colab notebook}

Using the Sample Sequences for Rendering

See the Sample Usage Documentation. Also provided are some precomputed sample sequences in the sample_sequences directory, so you don't even need to run any of this code.

Using the Code (Building and Generating Your Own Samples)

To generate a set of samples you can build the generate_samples tool with make.

make release

And then run generate_samples.

./generate_samples --n=4096 --algorithm=pmj02 --out=$PWD/pmj02_samples.txt

See the Code Usage Documentation for more information on usage.

Sequence Properties and Convergence

The PMJ(0,2) or pmj02 sample sequence has the property that any prefix of the samples are stratified on every elementary base-2 2D elementary interval. For example, for 16 samples, these sequences are always stratified on the 16x1, 8x2, 4x4, 2x8, and 1x16 grids.

This yields extremely good convergence on test integrals, especially at powers of two for the PMJ(0,2) sequence. Note that both uniform random sampling and best-candidate sampling converge at a rate of approximately N^-.5. Refer to Christensen et al. for comparison against more sample sequences.

^{Generated with this Colab/Jupyter notebook}

The Progressive Multi-Jittered Sequence with Blue Noise, or pmjbn, doesn't have as good convergence as pmj02, but it does have very nice blue noise properties, while still having better convergence than best-candidate sampling. This animation shows how the samples are (mostly) distributed far away from each other at any given number of samples.

Licensing

Licensed under the MIT Open Source license. See the LICENSE file.