A Spatial Data Structure for Fast Poisson-Disk Sample Generation


17,593 points, generated in 80 milliseconds

Daniel Dunbar
Greg Humphreys
University of Virginia

Proceedings of SIGGRAPH 2006

Abstract

Sampling distributions with blue noise characteristics are widely used in computer graphics. Although Poisson-disk distributions are known to have excellent blue noise characteristics, they are generally regarded as too computationally expensive to generate in real time. We present a new method for sampling by dart-throwing in O(N log N) time and introduce a novel and efficient variation for generating Poisson-disk distributions in O(N) time and space.

Paper

PDF (2MB)

Technical Report

CS-2006-08.pdf (626KB)

Movie

MPEG4 (125MB)

Source Code

PDSample-0.2.tar.gz