Unity|泊松盘采样算法_泊松圆盘采样方法

---

前言

基于Unity的泊松盘采样算法

一、介绍

泊松盘采样算法用于创建随机点坐标，以便每个点与所有其他点间隔指定的最小距离。会产生一组紧密排列且均匀的点。

应用：

• 生成类似《群星》中那样的银河系地图
• 在平面上均匀分布一些装饰物，如树木石块等

二、代码

using System.Collections.Generic;
using UnityEngine;

public class PoissonDiskSampling : MonoBehaviour
{
    /// <summary>
    /// 点之间的最小距离
    /// </summary>
    public float r = 1f;
    private float d;
    /// <summary>
    /// 采样数
    /// </summary>
    public int k = 30;
    /// <summary>
    /// 采样范围的宽度
    /// </summary>
    public float width = 20f;
    /// <summary>
    /// 采样范围的高度
    /// </summary>
    public float height = 16f;
    private int nx;
    private int ny;
    private int[,] occupied;
    private Vector2[,] occupiedCoord;
    private List<Vector2> activeList;
    /// <summary>
    /// 采样结果
    /// </summary>
    public List<Vector2> sampled;

    public int[,] relative = new int[,]
    {
        {-1, 2}, {0, 2}, {1, 2},
        {-2, 1}, {-1, 1}, {0, 1}, {1, 1}, {2, 1},
        {-2, 0}, {-1, 0}, {1, 0}, {2, 0},
        {-2, -1}, {-1, -1}, {0, -1}, {1, -1}, {2, -1},
        {-1, -2}, {0, -2}, {1, -2}
    };
    /// <summary>
    /// 开始采样
    /// </summary>
    public void Start()
    {
        d = r / Mathf.Sqrt(2);
        nx = Mathf.FloorToInt(width / d) + 1;
        ny = Mathf.FloorToInt(height / d) + 1;

        occupied = new int[ny, nx];
        occupiedCoord = new Vector2[ny, nx];
        activeList = new List<Vector2>();//激活集
        sampled = new List<Vector2>();//结果

        System.Random random = new();
        float x = (float)random.NextDouble() * width;
        float y = (float)random.NextDouble() * height;
        int idx_x = Mathf.FloorToInt(x / d);
        int idx_y = Mathf.FloorToInt(y / d);
        occupied[idx_y, idx_x] = 1;
        occupiedCoord[idx_y, idx_x] = new Vector2(x, y);
        activeList.Add(new Vector2(x, y));
        sampled.Add(new Vector2(x, y));//在列表里放置一个随机点作为起点

        int sampledIdx = 0;//采样次数
        while (activeList.Count > 0)
        {
            int idx = random.Next(activeList.Count);
            Vector2 refPoint = activeList[idx];

            float[] radius = new float[k];
            float[] theta = new float[k];

            for (int i = 0; i < k; i++)
            {
                radius[i] = ((float)random.NextDouble() + 1f) * r;
                theta[i] = (float)random.NextDouble() * 2f * Mathf.PI;
            }
            List<Vector2> candidate = new();//候选集
            for (int i = 0; i < k; i++)
            {
                float candidateX = radius[i] * Mathf.Cos(theta[i]) + refPoint.x;
                float candidateY = radius[i] * Mathf.Sin(theta[i]) + refPoint.y;
                candidate.Add(new Vector2(candidateX, candidateY));
            }
            bool flagOut = false;
            foreach (Vector2 candidatePoint in candidate)
            {
                float _x = candidatePoint.x;
                float _y = candidatePoint.y;
                if (_x < 0f || _x > width || _y < 0f || _y > height)
                    continue;
                bool flag = true;
                int idxX = Mathf.FloorToInt(_x / d);
                int idxY = Mathf.FloorToInt(_y / d);
                if (occupied[idxY, idxX] != 0)
                    continue;
                else
                {
                    for (int i = 0; i < relative.GetLength(0); i++)//检测与相邻单元格中点的距离是否过近
                    {
                        int candX = relative[i, 0] + idxX;
                        int candY = relative[i, 1] + idxY;
                        if (candX < 0 || candX >= nx || candY < 0 || candY >= ny)
                            continue;
                        if (occupied[candY, candX] == 1)
                        {
                            Vector2 coord = occupiedCoord[candY, candX];
                            if (Mathf.Pow(_x - coord.x, 2) + Mathf.Pow(_y - coord.y, 2) < Mathf.Pow(r, 2))
                            {
                                flag = false;
                                break;
                            }
                        }
                    }
                }
                if (flag)
                {
                    flagOut = true;
                    occupied[idxY, idxX] = 1;
                    occupiedCoord[idxY, idxX] = new Vector2(_x, _y);
                    sampled.Add(new Vector2(_x, _y));
                    activeList.Add(new Vector2(_x, _y));
                    sampledIdx++;
                    break;
                }
            }
            if (!flagOut)
            {
                activeList.RemoveAt(idx);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

图示

---

总结

这只是一种简单的泊松盘采样算法，在此基础上还可以使用灰度图来控制采样时点之间的距离，生成不同类型的星系，如悬臂星系、棒旋星系、纺锤形星系、圆盘星系。三维泊松盘采样只需设定采样范围的高度，将relative数组改为三维数组，在生成时考虑坐标与立方体网格中其他点的距离是否过近即可实现三维泊松盘（球）采样。