Single-pass stratified importance resampling

EGSR 2022

Overview of our algorithm. Sorted 1D stratified samples are mapped onto a space-filling curve to produce stratified candidates on the unit hypercube. We resample these candidates along the curve proportionally to their associated weights using our on-the-fly bidirectional CDF sampling. Stratifying the resampling input 'u' yields stratified output integration samples 'x'.

Abstract

Resampling is the process of selecting from a set of candidate samples to achieve a distribution (approximately) proportional to a desired target. Recent work has revisited its application to Monte Carlo integration, yielding powerful and practical importance resampling methods. One drawback of these methods is that they cannot generate stratified samples. We propose a method to achieve efficient stratification. We first introduce a discrete sampling algorithm which yields the same result as conventional inverse CDF sampling but in a single pass over the candidates, without needing to store them, similarly to reservoir sampling. We order the candidates along a space-filling curve to ensure that stratified CDF sampling of candidate indices yields stratified samples in the integration domain. We showcase our method on various resampling-based rendering problems.

Downloads and links

Media

Talk video

BibTeX reference

@article{Ciklabakkal:2022:StratifiedResampling,
  author = {Ege Ciklabakkal and Adrien Gruson and Iliyan Georgiev and Derek Nowrouzezahrai and Toshiya Hachisuka},
  title = {Single-pass stratified importance resampling},
  journal = {Computer Graphics Forum (Proceedings of EGSR)},
  year = {2022},
  number = {4},
  volume = {41}
}