Poisson-Disk Sampling: Random Points That Refuse to Clump

Why pure random placement looks wrong

Scatter n points uniformly at random over a square and the result rarely looks like what people mean by "random" — instead it shows visible clumps where several points landed close together by chance, and equally visible empty gaps where none landed at all. That clustering is a real statistical property of uniform sampling, not a bug, but it is exactly what you do not want when scattering trees over terrain, placing stars in a skybox, or choosing sample positions for anti-aliasing. Poisson-disk sampling fixes this with one extra rule: no two points may be closer than a minimum distance r.

Bridson's algorithm: grow the pattern from an active front

Robert Bridson's 2007 paper "Fast Poisson Disk Sampling in Arbitrary Dimensions" solves this in expected O(n) time — a huge improvement over the naive approach of throwing random darts and rejecting the ones that are too close, which slows to a crawl as the pattern fills up. The trick is to only generate candidates near existing points, rather than blindly across the whole domain:

grid cell size = r / sqrt(2)            // guarantees at most 1 sample per cell

place one initial random point; add it to samples and to the active list

while active list is not empty:
    pick a random point p from the active list
    repeat k times (k ≈ 30):
        candidate = random point in the annulus [r, 2r] around p
        if candidate is >= r from every sample in nearby grid cells:
            accept candidate: add to samples and to active list
            (try another candidate from the SAME p next time too)
    if none of the k candidates were accepted:
        remove p from the active list      // p is "surrounded", stop trying

The background grid, sized so each cell can hold at most one accepted sample, is what makes the distance check fast: checking whether a candidate is far enough from every existing point only requires looking at a small, constant number of neighbouring grid cells, never the whole point set. Each accepted point does a bounded amount of work — generate up to k candidates, check a handful of grid cells per candidate — so the total cost scales linearly with the number of points placed, not quadratically.

Blue noise: what makes the result look right

Analyse the spatial frequency spectrum of a Poisson-disk pattern and it has almost no energy at low frequencies — no large clusters and no large gaps — while still being irregular at high frequencies, unlike a rigid grid. That spectral shape is called blue noise, by analogy with light: blue light sits at the high-frequency end of the visible spectrum, just as blue noise concentrates its energy at high spatial frequencies. The human visual system is particularly sensitive to low-frequency clustering, which is exactly what pure uniform random sampling produces and blue noise avoids — a big part of why blue-noise dithering looks smoother than ordinary random dithering at the same point density.

Where this shows up

Procedural content tools use Poisson-disk sampling to scatter vegetation, rocks and props over terrain without the telltale clumps of naive randomness. Rendering engines use it to place samples for anti-aliasing, soft shadows and ambient occlusion, since blue-noise-distributed samples converge to the correct answer with less visible noise than the same number of purely random samples. Stippling and half-toning software use it directly to render smooth gradients as dots, and mesh generators use variants of it to seed initial point sets before Delaunay triangulation, because well-spaced seed points produce better-shaped triangles.

Frequently asked questions

Try it live

Everything above runs in your browser — open Poisson-Disk Sampling and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.