CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Poisson-Disk Sampling Patterns in O(N log N) Time

Thouis R. Jones


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.


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

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)