Abstract

Poisson Disk sampling patterns are of interest to the graphics community because their blue-noise properties are desirable in sampling patterns for rendering, illumination, and other computations. Until now, such patterns could only be generated by slow methods with poor convergence, or could only be approximated by jittering individual samples or tiling sets of samples.

We have developed a simple and efficient (O(N log N)) randomized algorithm for generating true Poisson Disk sampling patterns of N points. The method is based on incremental construction of the Voronoi diagram and rejection sampling.

References:

[1] Thouis R. Jones. Poisson-Disk Sampling Patterns in O(N log N) Time. Submitted. 2005.