

Title  Efficient Maximal PoissonDisk Sampling
(Article) 
in  ACM Transactions on Graphics 
Author(s) 
Mohamed S. Ebeida, Anjul Patney, Scott A. Mitchell, Andrew Davidson, Patrick M. Knupp, John D. Owens 
Keyword(s)  Poisson disk, maximal, provable convergence, linear complexity, sampling, blue noise 
Year 
2011

Location  Vancouver, Canada 
Date  August 711, 2011 
Volume  30 
Number  4 
Download  
BibTeX  
Abstract 
We solve the problem of generating a uniform Poissondisk sampling that is both maximal and unbiased over bounded nonconvex domains. To our knowledge this is the first provably correct algorithm with time and space dependent only on the number of points produced. Our method has two phases, both based on classical dartthrowing. The first phase uses a background grid of square cells to rapidly create an unbiased, nearmaximal covering of the domain. The second phase completes the maximal covering by calculating the connected components of the remaining uncovered voids, and by using their geometry to efficiently place unbiased samples that cover them. The second phase converges quickly, overcoming a common difficulty in dartthrowing methods. The deterministic memory is O(n) and the expected running time is O(n log n), where n is the output size, the number of points in the final sample. Our serial implementation verifies that the log n dependence is minor, and nearly O(n) performance for both time and memory is achieved in practice. We also present a parallel implementation on GPUs to demonstrate the parallelfriendly nature of our method, which achieves 2.4x the performance of our serial version.
