嗚嗚喔學習筆記: 10月 2021

搜尋此網誌

2021年10月7日 星期四

Poisson Disk Sampling - Unity - C#

Poisson Disk Sampling

創造一個自然 而且每個點之間距離均衡的演算法:


演算結果: 長寬 105x105 圓圈半徑:10

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


參考資料:

https://chih-sheng-huang821.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E9%9B%86%E7%BE%A4%E5%88%86%E6%9E%90-k-means-clustering-e608a7fe1b43