Sample Elimination for Poisson Disk Sample Sets

Given an input set of samples, sample elimination selects a subset with Poisson disk property: 15K input samples, and 5K selected samples from this input.

Abstract

We describe sample elimination for generating Poisson disk sample sets with a desired size. We introduce a greedy sample elimination algorithm that assigns a weight to each sample in a given set and eliminates the ones with greater weights in order to pick a subset of a desired size with Poisson disk property without having to specify a Poisson disk radius. This new algorithm is simple, computationally efficient, and it can work in any sampling domain, producing sample sets with more pronounced blue noise characteristics than dart throwing. Most importantly, it allows unbiased progressive (adaptive) sampling and it scales better to high dimensions than previous methods. However, it cannot guarantee maximal coverage. We provide a statistical analysis of our algorithm in 2D and higher dimensions as well as results from our tests with different example applications.

Images

Random vs. Poisson Disk hair placement: (left) 100K strands randomly placed on a bunny, and (right) 100K strands selected from 300K samples using Weighted Sample Elimination.

A sequence of tree leaves placed on the surfaces of the branches using weighted sample elimination.

16-64spp Unordered

16-64spp Ordered

64spp

An example sample set generated using Weighted Sample Elimination used in a ray tracer. (middle) the progressive sampling orders the samples in the set, such that introducing these samples one by one produces subsets with blue noise characteristics. () if the samples are not ordered, these subsets do not have blue noise characteristics that leads to undesired adaptive sampling decisions. () comparison to 64 samples per pixel.