∿ Generative art

Poisson-disk sampling

푸아송 디스크 샘플링

A way to scatter points that keeps every pair at least some minimum distance apart, instead of purely random placement.

Also known as: Bridson’s algorithmBlue noise sampling

···

js

const c = document.createElement('canvas');
document.body.appendChild(c);
c.style.width = '100%'; c.style.height = '100%';
const ctx = c.getContext('2d');
const cs = getComputedStyle(document.documentElement);
const ACCENT = cs.getPropertyValue('--accent').trim() || '#5b5bf7';
let w, h, pts = [], revealed = 0, genStart = 0;
function resize() {
  const dpr = Math.min(devicePixelRatio || 1, 2);
  w = innerWidth; h = innerHeight;
  c.width = w * dpr; c.height = h * dpr;
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  generate();
}
function generate() {
  const r = 13, k = 20, cell = r / Math.SQRT2;
  const gw = Math.ceil(w / cell), gh = Math.ceil(h / cell);
  const grid = new Int32Array(gw * gh).fill(-1);
  pts = []; const active = [];
  const gi = (x, y) => Math.floor(y / cell) * gw + Math.floor(x / cell);
  function farEnough(x, y) {
    const gx = Math.floor(x / cell), gy = Math.floor(y / cell);
    for (let j = Math.max(0, gy - 2); j <= Math.min(gh - 1, gy + 2); j++)
      for (let i = Math.max(0, gx - 2); i <= Math.min(gw - 1, gx + 2); i++) {
        const idx = grid[j * gw + i];
        if (idx >= 0) { const p = pts[idx]; if (Math.hypot(p[0] - x, p[1] - y) < r) return false; }
      }
    return true;
  }
  const x0 = Math.random() * w, y0 = Math.random() * h;
  pts.push([x0, y0]); active.push(0); grid[gi(x0, y0)] = 0;
  // 상한은 안전장치일 뿐 — active 리스트가 스스로 소진될 때까지(=캔버스 전체가 찰 때까지) 돈다
  while (active.length && pts.length < 20000) {
    const ai = Math.floor(Math.random() * active.length);
    const [ax, ay] = pts[active[ai]];
    let found = false;
    for (let i = 0; i < k; i++) {
      const ang = Math.random() * Math.PI * 2, rad = r * (1 + Math.random());
      const nx = ax + Math.cos(ang) * rad, ny = ay + Math.sin(ang) * rad;
      if (nx < 0 || nx >= w || ny < 0 || ny >= h || !farEnough(nx, ny)) continue;
      pts.push([nx, ny]); grid[gi(nx, ny)] = pts.length - 1; active.push(pts.length - 1); found = true; break;
    }
    if (!found) active.splice(ai, 1);
  }
  revealed = 0;
  genStart = 0;
}
addEventListener('resize', resize);
resize();

function draw() {
  ctx.fillStyle = '#0d0d12'; ctx.fillRect(0, 0, w, h);
  ctx.fillStyle = ACCENT;
  for (let i = 0; i < revealed; i++) { ctx.beginPath(); ctx.arc(pts[i][0], pts[i][1], 2.4, 0, 7); ctx.fill(); }
}
// 점 개수와 무관하게 항상 같은 시간 안에 다 드러나도록 경과 시간 비율로 reveal 한다
const REVEAL_MS = 800, HOLD_MS = 2200;
draw();
(function loop(t) {
  if (!genStart) genStart = t;
  const elapsed = t - genStart;
  revealed = Math.min(pts.length, Math.floor(pts.length * Math.min(1, elapsed / REVEAL_MS)));
  if (elapsed > REVEAL_MS + HOLD_MS) generate();
  draw();
  requestAnimationFrame(loop);
})(0);

Scatter points with plain Math.random() and you get both accidental clumps and empty gaps. Poisson-disk sampling adds one constraint — no new point may land within radius r of any existing point — which spreads points evenly without clumping, while still avoiding a perfectly regular grid. In frequency terms, this kind of distribution is called blue noise.

This demo uses the algorithm Robert Bridson published in 2007: pick an already-confirmed point, generate a few candidates at a distance between r and 2r from it, and if a candidate isn't too close to any existing point, confirm it too. Checking every existing point on every candidate would be slow, so in practice points are registered into a grid sized r/√2 per cell, and only nearby cells get checked.

Use it for scattered-star backgrounds, natural-looking stipple textures, and procedural placement that must avoid overlap — scattering trees or grass, for instance.

When to use

Use it whenever objects must scatter without overlap (stars, trees, stipple textures) and pure randomness looks too clumpy. Shrinking r densifies the points at the cost of more computation.