A spatial data structure for fast Poisson-disk sample generation
Daniel Dunbar, Greg Humphreys · ACM Transactions on Graphics · 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.