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


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.



Technical Report

CS-2006-08.pdf (626KB)


MPEG4 (125MB)

Source Code