泊松圆盘采样算法在大规模植被散布中消除人工规则感在开放世界游戏的大自然场景中树木、灌木与岩石的分布遵循着严密的生态规律同种乔木由于树冠采光与根系吸水范围的竞争树干之间会自然保持一个最小间距而自然界又不存在像果园一样整齐划一的阵列网格。如果使用伪随机白噪声直接生成植被坐标会出现大片区域光秃秃而局部又有多棵树重叠插在一起的“团聚与空洞”现象如果使用规则网格加随机抖动远处视线又会暴露出明显的网格条纹。泊松圆盘采样Poisson Disk Sampling, PDS能够在二维平面或三维地形上生成具有**蓝噪声Blue Noise**频谱特性的紧凑无序点集任意两点之间的欧几里得距离均不小于给定的最小排斥半径 $r$同时点集分布高度均匀致密完美还原出真实的自然散布生态。[白噪声 White Noise] [规则网格加抖动 Jitter Grid] [泊松圆盘采样 Blue Noise] • •• •• • • • • • • • • ••• • • • • • • • • • • • • • • • • • • (严重重叠与空洞) (条带感强/死板人工矩阵) (自然均匀/最小间距保证)Bridson 算法原理从 $O(N^2)$ 到 $O(N)$早期朴素的泊松圆盘采用“飞镖投掷法Dart Throwing”每次随机生成一个新坐标遍历此前已生成的所有点进行距离检测时间复杂度高达 $O(N^2)$在生成数万棵植被时极其缓慢。Robert Bridson 提出的线性时间算法通过维护一个“活动列表Active List”与“空间背景网格Background Grid”实现了 $O(N)$ 的高效采样背景网格加速将采样区域划分为网格单元单元尺寸设为 $CellSize \frac{r}{\sqrt{2}}$在二维平面下。此尺寸保证每个网格内最多只能容纳一个采样点。环形候选采样从活动列表中随机取出一个点 $\vec{P}$在以 $\vec{P}$ 为圆心、内径为 $r$、外径为 $2r$ 的圆环内随机生成 $k$ 个候选点通常 $k 30$。邻域快速排斥检测对于每个候选点只需检查其所在的网格以及周围 $5 \times 5$ 的相邻网格判断是否存在距离小于 $r$ 的点。若通过检测则将该候选点存入网格并加入活动列表若尝试 $k$ 次均失败则将点 $\vec{P}$ 移出活动列表。变半径泊松圆盘采样实现在实际地形散布中低洼湿润平原的树木密度大$r$ 较小而陡峭山坡或干燥高地的树木稀疏甚至演变为低矮灌木$r$ 较大。因此需要根据地表密度贴图Density Map或坡度动态计算局部半径 $r(x, y)$。using System.Collections.Generic; using Unity.Mathematics; using UnityEngine; public class PoissonDiskSampler { private readonly float _width; private readonly float _height; private readonly float _minRadius; private readonly float _maxRadius; private readonly int _k; // 候选点采样次数 (推荐 30) private float _cellSize; private int _gridWidth; private int _gridHeight; private int[,] _grid; private ListVector2 _points; private Listint _activeList; public PoissonDiskSampler(float width, float height, float minRadius, float maxRadius, int k 30) { _width width; _height height; _minRadius minRadius; _maxRadius maxRadius; _k k; // 以最小可能半径构建加速网格保证单元格互斥性 _cellSize _minRadius / Mathf.Sqrt(2f); _gridWidth Mathf.CeilToInt(width / _cellSize); _gridHeight Mathf.CeilToInt(height / _cellSize); _grid new int[_gridWidth, _gridHeight]; for (int x 0; x _gridWidth; x) for (int y 0; y _gridHeight; y) _grid[x, y] -1; _points new ListVector2(); _activeList new Listint(); } public ListVector2 GeneratePoints(Texture2D densityMap null) { // 1. 在区域内随机生成初始种子点 Vector2 firstPoint new Vector2(UnityEngine.Random.Range(0, _width), UnityEngine.Random.Range(0, _height)); AddPoint(firstPoint); // 2. 迭代活动列表 while (_activeList.Count 0) { int activeIndex UnityEngine.Random.Range(0, _activeList.Count); int pointIndex _activeList[activeIndex]; Vector2 basePoint _points[pointIndex]; // 依据密度贴图获取局部动态半径 float currentRadius GetLocalRadius(basePoint, densityMap); bool foundCandidate false; for (int i 0; i _k; i) { // 在 [r, 2r] 圆环范围内随机生成候选点 float angle UnityEngine.Random.value * Mathf.PI * 2f; float dist UnityEngine.Random.Range(currentRadius, currentRadius * 2f); Vector2 candidate basePoint new Vector2(Mathf.Cos(angle), Mathf.Sin(angle)) * dist; if (IsValidCandidate(candidate, currentRadius, densityMap)) { AddPoint(candidate); foundCandidate true; break; } } // 若 k 次尝试均未找到合法点该点周围已饱和移出活动列表 if (!foundCandidate) { _activeList[activeIndex] _activeList[_activeList.Count - 1]; _activeList.RemoveAt(_activeList.Count - 1); } } return _points; } private bool IsValidCandidate(Vector2 pt, float localRadius, Texture2D densityMap) { if (pt.x 0 || pt.x _width || pt.y 0 || pt.y _height) return false; int gx Mathf.FloorToInt(pt.x / _cellSize); int gy Mathf.FloorToInt(pt.y / _cellSize); // 检查周围邻域网格单元 int searchRadius Mathf.CeilToInt(localRadius / _cellSize); int minX Mathf.Max(0, gx - searchRadius); int maxX Mathf.Min(_gridWidth - 1, gx searchRadius); int minY Mathf.Max(0, gy - searchRadius); int maxY Mathf.Min(_gridHeight - 1, gy searchRadius); for (int x minX; x maxX; x) { for (int y minY; y maxY; y) { int neighborIdx _grid[x, y]; if (neighborIdx 0) { Vector2 neighborPt _points[neighborIdx]; float neighborRadius GetLocalRadius(neighborPt, densityMap); float requiredDist Mathf.Max(localRadius, neighborRadius); if ((neighborPt - pt).sqrMagnitude requiredDist * requiredDist) { return false; } } } } return true; } private void AddPoint(Vector2 pt) { int index _points.Count; _points.Add(pt); _activeList.Add(index); int gx Mathf.FloorToInt(pt.x / _cellSize); int gy Mathf.FloorToInt(pt.y / _cellSize); _grid[gx, gy] index; } private float GetLocalRadius(Vector2 pt, Texture2D densityMap) { if (densityMap null) return _minRadius; float u Mathf.Clamp01(pt.x / _width); float v Mathf.Clamp01(pt.y / _height); float density densityMap.GetPixelBilinear(u, v).r; // 0: 最稀疏, 1: 最致密 return Mathf.Lerp(_maxRadius, _minRadius, density); } }渲染管线对接GPU Instancing 批量绘制通过泊松圆盘生成的数万个散布点在烘焙或加载阶段与地形高度图Heightmap进行双线性插值采样求得 $Y$ 轴高程并计算地表法线得到三维旋转四元数。随后将所有矩阵数据打包送入 GPU StructuredBuffer配合Graphics.RenderMeshIndirect或Graphics.DrawMeshInstancedIndirect仅需 1 个 Draw Call 即可在屏幕上渲染数十万棵形态自然、彼此间隙均匀的高拟真森林。