Efficient Generation of Poisson-Disk Sampling Patterns

Thouis R. Jones
MIT CSAIL

This paper appears in issue Volume 11, Number 2.
An electronic version of this article is available.

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 present a simple and efficient randomized algorithm for generating true Poisson-disk sampling patterns in a square domain, given a minimum radius $R$ between samples. The algorithm runs in O(N log N) time for a pattern of N points. The method is based on the Voronoi diagram. Source code is available online.

Author Information

Thouis R. Jones, 32-D458, MIT, Cambridge, MA 02139 thouis@gmail.com

Source Code

This code requires GTS (http://gts.sourceforge.net) to build.

Usage:
fast_delaunay num_pts exclusion_radius > point_list.txt

This will insert points into the [0-1]x[0-1] square, separated by at least exclusion_radius from each other, until either num_pts points have been added, or there is no more free space to insert a point.

BibTeX Entry

@article{Jones05,
  author = "Thouis R. Jones",
  title = "Efficient Generation of Poisson-Disk Sampling Patterns",
  journal = "journal of graphics, gpu, and game tools",
  volume = "11",
  number = "2",
  pages = "27-36",
  year = "2006",
}