푸아송 디스크 샘플링

Poisson-disk sampling

점들을 완전히 무작위로 흩뿌리지 않고, 서로 최소 거리 이상 떨어지도록 고르게 분포시키는 샘플링 방법.

다른 이름: 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);

Math.random()으로 점을 그냥 흩뿌리면 우연히 여러 점이 몰려 뭉친 자리와 휑하게 빈 자리가 함께 생깁니다. 푸아송 디스크 샘플링은 "새 점은 기존의 어떤 점과도 반지름 r 이내로 가까워질 수 없다"는 제약 하나를 추가해서, 뭉침 없이 고르게 흩어지면서도 완전히 규칙적인 격자는 아닌 자연스러운 분포를 만듭니다. 이런 분포를 주파수 관점에서 블루 노이즈라고도 부릅니다.

이 데모는 Robert Bridson이 2007년 발표한 알고리즘을 씁니다. 이미 확정된 점 하나를 골라 그 주변 반지름 r~2r 사이에서 후보를 몇 개 뽑고, 기존 점들과 너무 가깝지 않은 후보가 있으면 확정 목록에 추가하는 과정을 반복합니다. 매번 모든 점과 거리를 비교하면 느려지므로, 실제로는 칸 크기를 r/√2로 맞춘 격자에 점을 등록해두고 주변 칸만 검사해서 빠르게 만듭니다.

별이 흩뿌려진 배경, 자연스러운 점묘 텍스처, 오브젝트를 겹치지 않게 배치하는 절차적 배치(나무·풀 심기 등)에 씁니다.

언제 쓰나

겹치지 않게 오브젝트를 흩뿌려야 할 때(별, 나무, 점묘), 완전 무작위보다 고른 텍스처가 필요할 때. 반지름 r을 줄이면 점이 촘촘해지지만 계산량이 늘어납니다.