Efficient Computation of Blue Noise Point Sets through Importance Sampling

Abstract

Dart-throwing can generate ideal Poisson-disk distributions with excellent blue noise properties, but is very computationally expensive if a maximal point set is desired. In this paper, we observe that the Poisson-disk sampling problem can be posed in terms of importance sampling by representing the available space to be sampled as a probability density function (pdf). This allows us to develop an efficient algorithm for the generation of maximal Poisson-disk distributions with quality similar to naïve dart-throwing but without rejection of samples. In our algorithm, we first position samples in one dimension based on its marginal cumulative distribution function (cdf). We then throw samples in the other dimension only in the regions which are available for sampling. After each 2D sample is placed, we update the cdf and data structures to keep track of the available regions. In addition to uniform sampling, our method is able to perform variable-density sampling with small modifications. Finally, we also propose a new min-conflict metric for variable-density sampling which results in better adaptation of samples to the underlying importance field.