Efficient Computation of Blue Noise Point Sets through Importance Sampling
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
2011 The Author(s). 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 nave 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.
