Bridson's Poisson Disk Sampling: Faster, Denser, and Still Random

Poisson disk sampling is the workhorse behind procedural forests, stippling, and blue-noise textures. Bridson's 2007 one-page algorithm remains the go-to, but it's not optimal. Two tweaks — one that skips wasted angular samples, another that biases the sampling radius — can cut iterations dramatically and pack points tighter without sacrificing the randomness that makes the output look natural.

Bridson's Algorithm in a Nutshell

The goal: place points randomly in a space such that no two are closer than a minimum distance r. Naive rejection sampling degrades quickly as the space fills. Bridson's trick is to keep an active list of points that might still accept new neighbors. For each active point, sample the annulus between r and 2r up to k times, using a background grid to check collisions in constant time. If a valid point is found, add it to the active list; otherwise, retire the current point. The recommended k=30 balances success rate against wasted attempts.

Optimization 1: Skip the Parent's Shadow

When a new point q is spawned from p, the annulus around q that faces p is partially invalid — any point there would be too close to p. By storing the parent of each point, you can compute the angular cone of invalid directions and sample only the valid range. The cone's half-angle is given by a min of two arccos terms, depending on whether the inner or outer circle bounds it. This simple bookkeeping cuts the number of iterations needed to fill a region, as the author's experiments show.

Optimization 2: Bias the Radius

Instead of sampling the annulus uniformly, you can skew the distance distribution toward the outer edge. The CDF of the distance is proportional to x^d in d dimensions, but you can replace the exponent d with a tunable constant c. Negative values of c push points farther from the parent, which packs more points into the space. The author found empirically that c = -1.4 - 17/sqrt(k) works well for k between 15 and 40, producing densities close to the theoretical maximum for random sequential adsorption. But beware: too negative and the output becomes visibly patterned, with strings and gaps that ruin the randomness.

Stippling and Parallel Variants

Poisson disk sampling isn't limited to constant r. By making r a function of position, you can stipple images — darker areas get denser points. The author also highlights PixelPie, a GPU-parallel algorithm that enables real-time stippling, and mentions a 2022 deterministic method by Scott Mitchell that deserves more attention.

Key Takeaways

• Bridson's algorithm is efficient but leaves room for optimization.
• Storing the parent point lets you skip invalid angular ranges, cutting iterations.
• Biasing the sampling radius with a negative exponent increases point density.
• Extreme bias destroys randomness, so tune carefully.
• GPU-parallel variants like PixelPie enable real-time applications.