A spatial data structure for fast Poisson-disk sample generation

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.