泊松圆盘抽样生成均匀随机点
最编程
2024-05-31 17:49:10
...
当需要生成随机点且要求随机点自然均匀的分布，用泊松圆盘采样就比较适合。
但该方法与统计学上的泊松关联不大，这个只相当于点在面积上服从泊松分布，
而实现这个结果有很多做法。
最终效果：
圆形为含半径的点，圆形的中心代表生成点
B站有一个不错教程：
https://www.bilibili.com/video/BV1KV411x7LM
该教程做法如下：
- 传入生成区域Bounds，传入生成点半径，用点的半径和Bounds生成网格，存二维数组
- 网格内小方格的生成点无论在什么位置，只要不超出当前方格，遍历周围3x3方格区域即可遍历所有可能相交点
- 先在Bounds中心生成一个点，再在这个点周围半径x2且任意角度处随机生成一个新的点，检查是否与其它圆相交且在Bounds内，若无法生成则继续随机重复该步骤，重复直到上限。
- 将生成好的新点加入List，将旧点移出List，重新在List中随机一个点继续上述操作。
- 直到随机不出新的点，算法结束。
可能是视频较为模糊的缘故，修复了一些小问题后，代码如下：
public static class PossonDiscSampling { public static List<Vector3> GeneratePoints(float radius, Vector2 sampleRegionSize, int numSamplesBeforeRejection = 32) { bool IsValid(Vector3 candidate, Vector2 sampleRegionSize, float cellSize, float radius, List<Vector3> points, int[,] grid) { if (candidate.x - radius >= 0f && candidate.x + radius < sampleRegionSize.x && candidate.z - radius >= 0f && candidate.z + radius < sampleRegionSize.y) { int cellX = Mathf.RoundToInt(candidate.x / cellSize); int cellZ = Mathf.RoundToInt(candidate.z / cellSize); int searchStartX = Mathf.Max(0, cellX - 3); int searchEndX = Mathf.Min(cellX + 3, grid.GetLength(0) - 1); int searchStartZ = Mathf.Max(0, cellZ - 3); int searchEndZ = Mathf.Min(cellZ + 3, grid.GetLength(1) - 1); //如果要检测其它格子内的球，需要遍历周围6个格子 for (int x = searchStartX; x <= searchEndX; x++) { for (int z = searchStartZ; z <= searchEndZ; z++) { int pointIndex = grid[x, z] - 1;//存长度不存索引，取的时-1,0就变成了-1，不用初始化数组了 if (pointIndex != -1) { float dst = (candidate - points[pointIndex]).magnitude; if (dst < radius * 2f) { return false; } } } } return true; } return false; } float cellSize = radius / Mathf.Sqrt(2); int[,] grid = new int[Mathf.CeilToInt(sampleRegionSize.x / cellSize), Mathf.CeilToInt(sampleRegionSize.y / cellSize)]; List<Vector3> points = new List<Vector3>(); List<Vector3> spawnPoints = new List<Vector3>(); spawnPoints.Add(new Vector3(sampleRegionSize.x / 2f, 0f, sampleRegionSize.y / 2f)); while (spawnPoints.Count > 0) { int spawnIndex = Random.Range(0, spawnPoints.Count); Vector3 spawnCenter = spawnPoints[spawnIndex]; bool candidateAccepted = false; for (int i = 0; i < numSamplesBeforeRejection; i++) { float angle = Random.value * Mathf.PI * 2f; Vector3 dir = new Vector3(Mathf.Sin(angle), 0f, Mathf.Cos(angle)); Vector3 candidate = spawnCenter + dir * 2f * radius; if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid)) { points.Add(candidate); spawnPoints.Add(candidate); grid[Mathf.RoundToInt(candidate.x / cellSize), Mathf.RoundToInt(candidate.z / cellSize)] = points.Count; candidateAccepted = true; break; } } if (!candidateAccepted) { spawnPoints.RemoveAt(spawnIndex); } } return points; } }
测试代码如下：
using System.Collections; using System.Collections.Generic; using UnityEngine; public class Test : MonoBehaviour { public float radius = 0.3f; public Vector2 sampleRegionSize = new Vector2(3f, 3f); private List<Vector3> mPoints; private void OnEnable() { mPoints = PossonDiscSampling.GeneratePoints(radius, sampleRegionSize); } private void OnDrawGizmos() { if (mPoints == null) return; float cellSize = radius / Mathf.Sqrt(2); Color cacheColor = Gizmos.color; Gizmos.color = new Color(0.5f, 0.5f, 0.5f, 0.5f); for (float x = 0; x < sampleRegionSize.x; x += cellSize) { for (float z = 0; z < sampleRegionSize.y; z += cellSize) { Gizmos.DrawWireCube(new Vector3(x, 0f, z), new Vector3(cellSize, 0f, cellSize)); } }//生成对应采样点的调试方格 Gizmos.color = cacheColor; for (int i = 0; i < mPoints.Count; i++) { Vector3 vector = mPoints[i]; Gizmos.DrawWireSphere(vector, radius); int x = Mathf.FloorToInt(vector.x / cellSize); int z = Mathf.FloorToInt(vector.z / cellSize); Gizmos.DrawWireCube(new Vector3(x, 0f, z), new Vector3(cellSize, 0f, cellSize)); //生成当前点所属方格 } } }
对于该做法还可以做如下应用层面的扩展：
1.扩展到3D空间，一些鸟的移动轨迹可以直接用这个做路点寻路
2.在模型UV上生成好这些点，然后通过WS拿到非平面上的世界空间位置
3.可以基于这个做三角剖分(https://www.cnblogs.com/hont/p/15310157.html)
原文地址：https://www.cnblogs.com/hont/p/16412338.html
上一篇： 滨松摄像蟒蛇
推荐阅读