Poisson-Disk Sampling

DEFINITION

no two samples closer than r
candidates ring an active sample: r ≤ d < 2r
k failures retire the sample

NOTES

Random but never crowded: every sample keeps its neighbours at least r away, which is the "blue noise" the eye reads as even texture with no pattern. The photoreceptors of the monkey retina are packed this way, and renderers sample this way to trade aliasing for quiet noise. Cook proved why it works; Bridson found the linear-time construction this plate runs — grow outward from one seed, ringing each sample with candidates until it retires.

PROVENANCE

Origin

R. Bridson, "Fast Poisson Disk Sampling in Arbitrary Dimensions", SIGGRAPH sketches, 2007; R. L. Cook, "Stochastic Sampling in Computer Graphics", ACM Transactions on Graphics 5(1), 1986

Standing

Public domain — published algorithms, implemented from the papers

Constants

The gap is the whole definition; tries below ~10 leave visible holes

Source

doi:10.1145/1278780.1278807

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 55 · POISSON-DISK SAMPLING — Robert Bridson, 2007 · dart throwing after Robert L. Cook, 1986
//   no two samples closer than r
//   candidates ring an active sample: r ≤ d < 2r
//   k failures retire the sample
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=poisson

float p_gap   = 22 + chf('gap_tweak');        // r — minimum gap · live 14 .. 40
float p_tries = 30 + chf('tries_tweak');      // k — candidates · live 5 .. 30

// The plate's own colour: FORMA's LATTICES accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.4185 + 0.4549 * cos(6.28318530718 * (t + 0.05)),
    0.1389 + 0.151 * cos(6.28318530718 * (t + 0.1)));
}

// Bridson's fast Poisson-disk sampling run until every active sample has
// retired: candidates ring an active sample between r and 2r, a background
// grid of cell r/√2 makes the clearance test constant-time, and k failures
// retire the sample — the plate's own construction on the plate's own seed,
// so every cook grows the same blue noise from the same first dart. One
// point per sample, coloured by acceptance order, which is growth order.
// Domain is the plate's 560-unit reference canvas, where the gap constant
// is already in scale. The plate's faint underlay, its HILITE head and the
// exclusion-disk cursor are the reveal's devices, not the sampling, and are
// not ported.
float W = 560.0, H = 560.0, m = 8.0;

float r = p_gap;
int k = int(rint(p_tries));
float cell = r / sqrt(2.0);
int gw = max(1, int(ceil(W / cell))), gh = max(1, int(ceil(H / cell)));
int grid[];
resize(grid, gw * gh);
for (int i = 0; i < gw * gh; i++) grid[i] = -1;

int rc = 613;                     // the plate's own seed, counted upward
float ptx[], pty[];
int active[];

// the first dart, in the plate's own central window
float sx = W * (0.3 + 0.4 * random(rc));  rc++;
float sy = H * (0.3 + 0.4 * random(rc));  rc++;
grid[int(sy / cell) * gw + int(sx / cell)] = 0;
push(ptx, sx);  push(pty, sy);  push(active, 0);

while (len(active) > 0){
    int ai = int(random(rc) * len(active));  rc++;
    if (ai >= len(active)) ai = len(active) - 1;
    float qx = ptx[active[ai]], qy = pty[active[ai]];
    int placed = 0;
    for (int a = 0; a < k; a++){
        float ang = random(rc) * M_PI * 2.0;  rc++;
        float rad = r * (1.0 + random(rc));  rc++;
        float x = qx + rad * cos(ang), y = qy + rad * sin(ang);
        if (x < m || y < m || x > W - m || y > H - m) continue;
        // clearance against the 5×5 neighbourhood — one sample per cell at most
        int gx = int(x / cell), gy = int(y / cell), clear = 1;
        for (int dy = -2; dy <= 2 && clear; dy++){
            for (int dx = -2; dx <= 2; dx++){
                int cxx = gx + dx, cyy = gy + dy;
                if (cxx < 0 || cyy < 0 || cxx >= gw || cyy >= gh) continue;
                int i = grid[cyy * gw + cxx];
                if (i >= 0){
                    float ddx = ptx[i] - x, ddy = pty[i] - y;
                    if (sqrt(ddx * ddx + ddy * ddy) < r){ clear = 0;  break; }
                }
            }
        }
        if (!clear) continue;
        grid[gy * gw + gx] = len(ptx);
        push(active, len(ptx));
        push(ptx, x);  push(pty, y);
        placed = 1;
        break;
    }
    if (!placed) removeindex(active, ai);
}

int N = len(ptx);
for (int i = 0; i < N; i++){
    // canvas y runs down; negated about centre so growth spreads as the plate shows it
    int pt = addpoint(0, set(ptx[i] - W / 2.0, (H / 2.0) - pty[i], 0.0));
    setpointattrib(0, "Cd", pt, forma_ramp(0.84 + 0.2 * float(i) / float(N)));
    setpointattrib(0, "Alpha", pt, 0.85);
}

AFTER EFFECTS · DECLINED

Points, not a path: a blue-noise sample is the spacing between dots, and joining them in any order draws a figure the sampling never made.