poisson.ts (3269B)
1 /** 2 * Poisson-disc sampling (Bridson), seeded. 3 * 4 * Blue-noise points: no two closer than `r`, none further than about 5 * `2r` from a neighbour, so the field reads as a cloud rather than as a 6 * grid or as static. Seeded so a given hero looks the same on every 7 * visit and every mount; the seed also keys the per-point randoms the 8 * shader uses for twinkle and arrival order. 9 */ 10 11 /** mulberry32 — small, fast, good enough for layout. */ 12 export function rng(seed: number) { 13 let a = seed >>> 0; 14 return () => { 15 a = (a + 0x6d2b79f5) >>> 0; 16 let t = a; 17 t = Math.imul(t ^ (t >>> 15), t | 1); 18 t ^= t + Math.imul(t ^ (t >>> 7), t | 61); 19 return ((t ^ (t >>> 14)) >>> 0) / 4294967296; 20 }; 21 } 22 23 export interface PoissonOptions { 24 /** Half-extents of the domain, centred on the origin. */ 25 halfW: number; 26 halfH: number; 27 /** Minimum spacing between points. */ 28 r: number; 29 seed?: number; 30 /** Candidates tried around each active point before it retires. */ 31 k?: number; 32 } 33 34 /** 35 * Points as a flat `[x0, y0, x1, y1, …]` array in the domain's units. 36 * Count is roughly `0.7 · area / r²`; `minDistFor` inverts that. 37 */ 38 export function poisson({ halfW, halfH, r, seed = 1, k = 30 }: PoissonOptions): Float32Array { 39 const rand = rng(seed); 40 const W = halfW * 2; 41 const H = halfH * 2; 42 const cell = r / Math.SQRT2; 43 const gw = Math.ceil(W / cell); 44 const gh = Math.ceil(H / cell); 45 const grid = new Int32Array(gw * gh).fill(-1); 46 const xs: number[] = []; 47 const ys: number[] = []; 48 const active: number[] = []; 49 const r2 = r * r; 50 51 const put = (x: number, y: number) => { 52 const i = xs.length; 53 xs.push(x); 54 ys.push(y); 55 grid[Math.floor((y + halfH) / cell) * gw + Math.floor((x + halfW) / cell)] = i; 56 active.push(i); 57 return i; 58 }; 59 60 const fits = (x: number, y: number) => { 61 if (x < -halfW || x >= halfW || y < -halfH || y >= halfH) return false; 62 const gx = Math.floor((x + halfW) / cell); 63 const gy = Math.floor((y + halfH) / cell); 64 for (let j = Math.max(0, gy - 2); j <= Math.min(gh - 1, gy + 2); j++) { 65 for (let i = Math.max(0, gx - 2); i <= Math.min(gw - 1, gx + 2); i++) { 66 const n = grid[j * gw + i]; 67 if (n < 0) continue; 68 const dx = xs[n] - x; 69 const dy = ys[n] - y; 70 if (dx * dx + dy * dy < r2) return false; 71 } 72 } 73 return true; 74 }; 75 76 put((rand() - 0.5) * W, (rand() - 0.5) * H); 77 78 while (active.length) { 79 const ai = Math.floor(rand() * active.length); 80 const p = active[ai]; 81 let placed = false; 82 for (let n = 0; n < k; n++) { 83 const a = rand() * Math.PI * 2; 84 const d = r * (1 + rand()); 85 const x = xs[p] + Math.cos(a) * d; 86 const y = ys[p] + Math.sin(a) * d; 87 if (fits(x, y)) { 88 put(x, y); 89 placed = true; 90 break; 91 } 92 } 93 if (!placed) { 94 active[ai] = active[active.length - 1]; 95 active.pop(); 96 } 97 } 98 99 const out = new Float32Array(xs.length * 2); 100 for (let i = 0; i < xs.length; i++) { 101 out[i * 2] = xs[i]; 102 out[i * 2 + 1] = ys[i]; 103 } 104 return out; 105 } 106 107 /** The spacing that lands about `count` points on a `w × h` domain. */ 108 export function minDistFor(count: number, w: number, h: number) { 109 return Math.sqrt((0.7 * w * h) / count); 110 }