纯随机撒点 85.8% 聚团、Bridson 蓝噪声却把最小间距锁死在 30px：生成艺术落点的实测复盘-开发者社区

我见过太多生成艺术 / 程序化场景：草草for一圈Math.random()把几百个点撒到画布，肉眼一看全是问题——几颗挤成一坨，旁边又空出一块；可当有人提议“加个最少间距约束”时，第一反应是“会不会很慢、要引库”。这条“纯随机最省事”的直觉，恰恰是生成艺术里最容易被原谅、也最容易被低估的坑。

背景：为什么这件事值得写

生成艺术、程序化植被散布、星空 / 粒子落点、甚至蓝噪声抖动（dithering），底层的共同动作都是“在区域里撒点”。纯随机（Math.random()独立同分布）是写起来最短的那一行，但它有个反直觉的统计事实：每个点都与前面无关，于是一小撮点会“碰巧”落得很近，又有一片区域“碰巧”落空。人眼对低频聚团极敏感，所以纯随机成图常常显得“比真随机还假”。

更微妙的是代价认知：很多人以为“加个最小间距”就必须上第三方库、或退回到 O(n²) 的暴力拒绝采样。本次用 Node 22 在单线程上自己实现，把“聚团有多严重”和“修掉它要付多少时间”两件事实测出来，结论是 Bridson 蓝噪声几乎零额外成本。

解剖：Bridson 到底怎么运作

朴素拒绝采样的痛点是：每来一个候选，都要和全部已落点比距离，整体退化成 O(n²)。Bridson 2007 年的算法用两个结构把它压回 O(n)：

背景网格：格边长取r/√2（二维），保证每个格子至多落 1 个点；于是判定“新候选是否离谁太近”只需看周围 5×5 个格，是 O(1)。
活动列表（active list）：只保留“周围还能再长点”的父点；从它身上在环形[r, 2r]内试 k≈30 个候选，成功就入列，连续 k 次失败就把它移出列表。列表空了，区域就被填到最大。

图1：左为网格 + 活动点结构，每格至多 1 点；右为环形候选与距离判定，绿点≥r 接受、红点<r 拒绝，判定只查邻域而非全量。

实证：一次可复现的落点对比

我用固定种子（mulberry32(20260824)）在 1000×1000 区域、最小间距 r=30px 下，让三种策略生成同一密度（都落 695 个点）做公平对比，5 轮取中位。下面这段就是 Bridson 的核心，无第三方依赖：

function bridson(r, rnd, k = 30) { const cell = r / Math.SQRT2, cols = Math.floor(W / cell) + 1, rows = Math.floor(H / cell) + 1; const grid = new Int32Array(cols * rows).fill(-1), pts = [], active = []; const idx = (x, y) => Math.floor(x / cell) + Math.floor(y / cell) * cols; const seed = [rnd() * W, rnd() * H]; pts.push(seed); grid[idx(seed[0], seed[1])] = 0; active.push(0); while (active.length) { const ai = (rnd() * active.length) | 0, p = pts[active[ai]]; let found = false; for (let t = 0; t < k; t++) { const ang = rnd() * Math.PI * 2, rad = r * Math.sqrt(1 + 3 * rnd()); // 环 [r,2r] const cx = p[0] + Math.cos(ang) * rad, cy = p[1] + Math.sin(ang) * rad; if (cx < 0 || cx >= W || cy < 0 || cy >= H) continue; const gx = Math.floor(cx / cell), gy = Math.floor(cy / cell); let ok = true; for (let oy = -2; oy <= 2 && ok; oy++) for (let ox = -2; ox <= 2; ox++) { const gi = grid[gx + ox + (gy + oy) * cols]; if (gi !== -1) { const q = pts[gi], dx = q[0]-cx, dy = q[1]-cy; if (dx*dx+dy*dy < r*r) ok = false; } } if (ok) { pts.push([cx, cy]); grid[idx(cx, cy)] = pts.length - 1; active.push(pts.length - 1); found = true; break; } } if (!found) active.splice(ai, 1); } return pts; }

图2：左为Math.random()纯随机落位，红圈标出与邻居不足 30px 的“聚团”点；右为 Bridson 蓝噪声，任意两点间距 ≥30px，无大块空洞。

数据：聚团率与代价账

直接看测量值（1000×1000，r=30px，695 点，单线程 Node 22，5 轮取中位）：

纯随机：耗时 0.035ms，但85.8%的点最近邻不足 30px，最小最近邻仅1.24px，平均最近邻18.91px——恰好等于二维均匀随机的理论值1/√(πρ)（ρ=695/10⁶≈6.95e⁻⁴，理论 ≈18.9px），说明测量靠谱、聚团是分布本身的性质而非 bug。
Bridson 蓝噪声：耗时 2.06ms，把最小间距锁死在 30px，任意两点都不挨太近。
朴素拒绝采样：耗时 2.64ms、共 13932 次尝试才落 695 点（平均每点浪费 ≈20 次尝试），与 Bridson 同量级——但它是 O(n·尝试) 的，半径减半时拒绝率指数上升，耗时立刻爆炸。

图3：三者生成同样 695 点的中位耗时。Bridson 比纯随机慢约 70×（纯常数因子），远不是“指数级变慢”；朴素拒绝在低密度尚可，密度一高就退化。

一句话读数：修掉聚团的代价是纯随机的约 70× 常数开销（2ms 量级），而不是很多人怕的“不可接受”。真正该警惕的是朴素拒绝采样随密度退化的 O(n²) 风险，而不是 Bridson。

局限：哪些场景别上蓝噪声

你要的就是“野”：噪点粒子、闪电、破碎纹理，刻意需要成团与留白时，纯随机或带偏置的随机才对味；上蓝噪声反而显得“假均匀”。
密度很高 / r 很小：Bridson 仍 O(n)，但可接受点数上限由 r² 决定，r 太小会逼近网格容量；此时应改用best-candidate、低差异序列（Sobol/Halton）或分层采样。
需要严格可复现跨平台：坐标比较、浮点截断会让不同引擎落点有微小偏差，生产环境要锁定 PRNG 种子与 float64（本次已用固定种子复现）。
本次未逐半径实测：只取了 r=30px 一个密度点，r=15/60 的退化曲线留给读者按上面脚本自跑。