Poisson Disk Sampling
Unity C# 版本:
using UnityEngine;
using System.Collections.Generic;
[System.Serializable]
public class PoissonDiscHelper
{
int _w;
int _h;
float _r;
[SerializeField]
public List<Vector2> Points = new List<Vector2>();
[SerializeField]
List<Vector2> CandidatePoints = new List<Vector2>();
public List<Vector2> Gen(int w, int h, float r)
{
_w = w;
_h = h;
_r = r;
Points.Clear();
CandidatePoints.Clear();
AddPointToMax();
return Points;
}
private void AddPointToMax()
{
int limit = 9999;
int idx = 0;
while ((Points.Count == 0 || CandidatePoints.Count > 0) && idx < limit)
{
AddPoint();
idx++;
}
}
private void AddPoint()
{
Vector2 newP;
if (Points.Count == 0)
{
System.Random r = new System.Random();
newP = new Vector2(r.Next(0, _w), r.Next(0, _h));
}
else
{
if (CandidatePoints.Count <= 0)
{
Debug.LogFormat("Total Done. Point Count: {0}", Points.Count);
return;
}
int rand = Random.Range(0, CandidatePoints.Count - 1);
newP = CandidatePoints[rand];
CandidatePoints.RemoveAt(rand);
}
Points.Add(newP);
int rayCount = 64;
for (int rayI = 0; rayI < rayCount; rayI++)
{
Vector3 dir3 = Rotate(new Vector3(0, 0, 1), Vector3.up, rayI * 360f / rayCount);
Vector2 dir = new Vector2(dir3.x, dir3.z);
Vector2 candiate = newP + (dir.normalized * _r);
if (candiate.x <= _r / 4 || candiate.y <= _r / 4)
{
continue;
}
if (candiate.x > _w - _r / 4 || candiate.y > _h - _r / 4)
{
continue;
}
CandidatePoints.Add(candiate);
}
foreach (Vector2 p in Points)
{
for (int i = CandidatePoints.Count - 1; i >= 0; i--)
{
Vector2 cp = CandidatePoints[i];
if (Vector2.Distance(cp, p) < _r - 0.001f)
{
CandidatePoints.RemoveAt(i);
}
}
}
}
private Vector3 Rotate(Vector3 source, Vector3 axis, float angle)
{
Quaternion q = Quaternion.AngleAxis(angle, axis);// 旋转系数
return q * source;// 返回目标点
}
}
其他可參考演算法:
Best Candidate Sampling
Lloyd's algorithm
