Abstract: We introduce three new families of stochastic algorithms to generate progressive 2D sample point sequences. This opens a general framework that researchers and practitioners may find useful when developing future sample sequences. Our best sequences have the same low sampling error as the best known sequence (a particular randomization of the Sobol' (0,2) sequence). The sample points are generated using a simple, diagonally alternating strategy that progressively fills in holes in increasingly fine stratifications. The sequences are progressive (hierarchical): any prefix is well distributed, making them suitable for incremental rendering and adaptive sampling. The first sample family is only jittered in 2D; we call it progressive jittered. It is nearly identical to existing sample sequences. The second family is multi-jittered: the samples are stratified in both 1D and 2D; we call it progressive multi-jittered. The third family is stratified in all elementary intervals in base 2, hence we call it progressive multi-jittered (0,2). We compare sampling error and convergence of our sequences with uniform random, best candidates, randomized quasi-random sequences (Halton and Sobol'), Ahmed's ART sequences, and Perrier's LDBN sequences. We test the sequences on function integration and in two settings that are typical for computer graphics: pixel sampling and area light sampling. Within this new framework we present variations that generate visually pleasing samples with blue noise spectra, and well-stratified interleaved multi-class samples; we also suggest possible future variations.

Published in: Computer Graphics Forum (Proceedings of the Eurographics Symposium on Rendering 2018), volume 37, number 4, pages 21-33. Eurographics / John Wiley & Sons, July 2018. (Karlsruhe, Germany, July 2-4.)

One-line summary: An assessment of existing progressive sample sequences, and new stochastic alternatives to randomized quasi-random sample sequences; with our progressive multi-jittered samples, we can also target blue noise and other properties.

Download paper here: paper.pdf.

Supplemental material: pmj_suppl.pdf.

Slides: pmj_slides.pdf.

Implementations: There are several implementations available on github. Here are the ones I know about:
- by Adrien Hamers and David Coeurjolly (in C++): github;
- by Simon Brown (in Rust): github;
- by Andrew Helmer (in C++): github.

Follow-up work (2019): Matt Pharr has developed a faster method to generate progressive multi-jittered samples. He uses a suitable data structure to keep track of available strata instead of our rather brute-force candidate sample generation and rejection. See his nice paper: Efficient generation of points that satisfy two-dimensional elementary intervals, Journal of Computer Graphics Tools, volume 8, number 1, pages 56-68, 2019.

Update Dec 2020: I frequently get asked about the Owen-scrambled Sobol sequence we compared against in the paper. Brent Burley from WDAS had kindly made his elegant and efficient hash-based implementation of Owen scrambling available to us, but it had not been published at the time. Good news: Brent's paper describing his elegant algorithm is now published in Journal of Graphics Tools !

More follow-up work (June 2021): We have a new, simpler, and much faster implementation of progressive multi-jittered sample sequences. We could call them "pmj02++", I guess. They are also generalized to higher dimensions. The paper and code is here: EGSR 2021 paper.

Back to Per's publication page.