Research Projects

Sample Elimination
for Poisson Disk Sample Sets


Given an input set of samples, sample elimination selects a subset with Poisson disk property: (left) 15K input samples, and (right) 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.


An example sample set generated using Weighted Sample Elimination used in a ray tracer. 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.

Videos

Sample Elimination for Generating Poisson Disk Sample Sets, Eurographics 2015 paper video.

Publications

Cem Yuksel
Sample Elimination for Generating Poisson Disk Sample Sets
Computer Graphics Forum (Proceedings of EUROGRAPHICS 2015), 34, 2, 2015
Paper - 12.6MB
Publisher's Page
Youtube Video
BibTeX
The definitive version is available at http://diglib.eg.org/ and http://onlinelibrary.wiley.com/.

Related Links

An implementation of the weighted sample elimination algorithm is in cyCodeBase. The related code release supports any sampling domain, including high dimensions.