A Spatial Data Structure for Fast Poisson-Disk Sample Generation
ACM Transactions on Graphics (Proceedings of SIGGRAPH), August 2006
Daniel Dunbar, Greg Humphreys
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.