공간 채워넣기 알고리즘

참고영상 : https://www.youtube.com/watch?v=7WcmyxyFO7o&t=3s&ab_channel=SebastianLague 

물체를 곂치지 않고 공간에 적절한 거리로 생성하기 위해 생각해낸 알고리즘인 것 같다

해당 알고리즘 코드는 유투브 채널에 더보기란에 Github 주소에 있다

 

PoissonDiscSampling.cs

 

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

public static class PoissonDiscSampling {

    // 주어진 반경 내에서 겹치지 않는 점을 생성하는 메서드

    // radius: 점 사이의 최소 거리 (원의 반지름)

    // sampleRegionSize: 점을 생성할 영역의 크기

    // numSamplesBeforeRejection: 동일한 위치에서 점을 생성하기 전에 시도할 최대 횟수

    public static List<Vector2> GeneratePoints(float radius, Vector2 sampleRegionSize, int numSamplesBeforeRejection = 30) {

        // 한 셀의 크기를 계산

        float cellSize = radius / Mathf.Sqrt(2);

        // 셀 그리드를 초기화

        int[,] grid = new int[Mathf.CeilToInt(sampleRegionSize.x / cellSize), Mathf.CeilToInt(sampleRegionSize.y / cellSize)];

        // 생성된 점을 저장할 리스트

        List<Vector2> points = new List<Vector2>();

        // 현재 검사 중인 위치를 저장할 리스트

        List<Vector2> spawnPoints = new List<Vector2>();

        // 초기 위치(영역 중앙)를 스폰 포인트로 추가

        spawnPoints.Add(sampleRegionSize / 2);

        // 스폰 포인트 리스트에 위치가 남아 있는 동안 반복

        while (spawnPoints.Count > 0) {

            // 무작위로 스폰 포인트 선택

            int spawnIndex = Random.Range(0, spawnPoints.Count); // 처음엔 0밖에 없어서 맨 첫 배열 불러움

            Vector2 spawnCentre = spawnPoints[spawnIndex];

            bool candidateAccepted = false;

            // 최대 numSamplesBeforeRejection 횟수만큼 후보 위치 생성 시도

            for (int i = 0; i < numSamplesBeforeRejection; i++) {

                // 임의의 방향과 거리로 후보 위치 생성

                float angle = Random.value * Mathf.PI * 2;

                Vector2 dir = new Vector2(Mathf.Sin(angle), Mathf.Cos(angle)); // x좌표 y좌표 핸덤으로 선택된 방향 (-1~1, -1~1)

                Vector2 candidate = spawnCentre + dir * Random.Range(radius, 2 * radius); // 지금 xy에서 랜덤으로 규칙에 멀어진 곳에 생성

                // 생성한 후보 위치가 유효한지 확인하고, 유효하면 리스트에 추가하고 그리드에 표시

                if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid)) {

                    points.Add(candidate);

                    spawnPoints.Add(candidate);

                    grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize)] = points.Count;

                    candidateAccepted = true;

                    break;

                }

            }

            // 후보 위치가 유효하지 않으면 스폰 포인트 리스트에서 제거

            if (!candidateAccepted) {

                spawnPoints.RemoveAt(spawnIndex);

            }

        }

        // 생성된 점의 리스트 반환

        return points;

    }

    // 주어진 위치가 유효한지 확인하는 메서드

    static bool IsValid(Vector2 candidate, Vector2 sampleRegionSize, float cellSize, float radius, List<Vector2> points, int[,] grid) {

        // 위치가 영역 내에 있는지 확인

        if (candidate.x >= 0 && candidate.x < sampleRegionSize.x && candidate.y >= 0 && candidate.y < sampleRegionSize.y) {

            // 위치를 그리드 셀로 변환

            int cellX = (int)(candidate.x / cellSize);

            int cellY = (int)(candidate.y / cellSize);

            // 검사할 주변 셀 범위 계산

            int searchStartX = Mathf.Max(0, cellX - 2);

            int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1);

            int searchStartY = Mathf.Max(0, cellY - 2);

            int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1);

            // 주변 셀을 검사하여 점들이 서로 겹치는지 확인

            for (int x = searchStartX; x <= searchEndX; x++) {

                for (int y = searchStartY; y <= searchEndY; y++) {

                    int pointIndex = grid[x, y] - 1;

                    if (pointIndex != -1) {

                        float sqrDst = (candidate - points[pointIndex]).sqrMagnitude;

                        // 점 사이의 거리가 최소 거리(radius)보다 작으면 유효하지 않음

                        if (sqrDst < radius * radius) {

                            return false;

                        }

                    }

                }

            }

            return true;

        }

        return false;

    }

}

해당 코드가 핵심인게 지름만큼 거리를 둬서 가상의 네모난 칸을 생성한다

가상의 네모난 칸을 지정한 크기만큼 생성해서 배열로 만들어 둔다

 

그리고 그 다음은 중앙에 첫 point지점으로 선택해 두고

해당 point에서 랜덤하게 회전하고 해당 위치에 둬도 되는지 확인한다

 -> 이 과정을 변수로 지정해둔 갯수rejectionSamples 만큼 반복한다

 

이 후 선택된 위치에 둘 수 있다면 spawnPoints에 추가한 뒤

spawnPoints가 없어질 때 까지 위 과정을 반복한다

 

 

Test.cs

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

public class Test : MonoBehaviour {

    public float radius = 1;

    public Vector2 regionSize = Vector2.one;

    public int rejectionSamples = 30;

    public float displayRadius =1;

    List<Vector2> points;

    void OnValidate() {

        points = PoissonDiscSampling.GeneratePoints(radius, regionSize, rejectionSamples);

    }

    void OnDrawGizmos() {

        Gizmos.DrawWireCube(regionSize/2,regionSize);

        if (points != null) {

            foreach (Vector2 point in points) {

                Gizmos.DrawSphere(point, displayRadius);

            }

        }

    }

}

해당 위치를 GeneratePoints 함수를 통해 받아와서 해당 위치에 원을 그리게 되는 것 까지가 구현되어 있다

 

하지만 코드상 2D로만 되어 있어서 3D로 만들면 어떨까 였다

 

일딴 오브젝트로 생성하기 위해 간단한 프리팹 하나를 생성해 주었다

 

이후 3D용으로 PoissonDiscSampling코드를 수정했다

PoissonDiscSampling3D.cs

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

public static class PoissonDiscSampling3D {

    // Poisson-Disc Sampling을 사용하여 3D 공간에서 점을 생성하는 메서드

    // radius: 점 사이의 최소 거리 (구의 반지름)

    // sampleRegionSize: 점을 생성할 공간의 크기

    // numSamplesBeforeRejection: 동일한 위치에서 점을 생성하기 전에 시도할 최대 횟수

    public static List<Vector3> GeneratePoints(float radius, Vector3 sampleRegionSize, int numSamplesBeforeRejection = 30) {

        // 한 셀의 크기를 계산

        float cellSize = radius / Mathf.Sqrt(3);

        // 셀 그리드를 초기화

        int[,,] grid = new int[

            Mathf.CeilToInt(sampleRegionSize.x / cellSize),

            Mathf.CeilToInt(sampleRegionSize.y / cellSize),

            Mathf.CeilToInt(sampleRegionSize.z / cellSize)

        ];

        // 생성된 점을 저장할 리스트

        List<Vector3> points = new List<Vector3>();

        // 현재 검사 중인 위치를 저장할 리스트

        List<Vector3> spawnPoints = new List<Vector3>();

        // 초기 위치(공간 중앙)를 스폰 포인트로 추가

        spawnPoints.Add(sampleRegionSize / 2);

        // 스폰 포인트 리스트에 위치가 남아 있는 동안 반복

        while (spawnPoints.Count > 0) {

            // 무작위로 스폰 포인트 선택

            int spawnIndex = Random.Range(0, spawnPoints.Count);

            Vector3 spawnCentre = spawnPoints[spawnIndex];

            bool candidateAccepted = false;

            // 최대 numSamplesBeforeRejection 횟수만큼 후보 위치 생성 시도

            for (int i = 0; i < numSamplesBeforeRejection; i++) {

                // 무작위 방향과 거리로 후보 위치 생성

                // float angleX = Random.value * Mathf.PI * 2;

                // float angleY = Random.value * Mathf.PI * 2;

                // // 두 각도를 사용하여 3D 방향 벡터 생성

                // Vector3 dir = new Vector3(

                //     Mathf.Sin(angleX) * Mathf.Cos(angleY),

                //     Mathf.Sin(angleX) * Mathf.Sin(angleY),

                //     Mathf.Cos(angleX)

                // );

                // Vector3 randomDirection = Random.onUnitSphere;

                Vector3 candidate = spawnCentre + Random.onUnitSphere * Random.Range(radius, 2 * radius);

                // 생성한 후보 위치가 유효한지 확인하고, 유효하면 리스트에 추가하고 그리드에 표시

                if (IsValid(candidate, sampleRegionSize, cellSize, radius, points, grid)) {

                    points.Add(candidate);

                    spawnPoints.Add(candidate);

                    grid[(int)(candidate.x / cellSize), (int)(candidate.y / cellSize), (int)(candidate.z / cellSize)] = points.Count;

                    candidateAccepted = true;

                    break;

                }

            }

            // 후보 위치가 유효하지 않으면 스폰 포인트 리스트에서 제거

            if (!candidateAccepted) {

                spawnPoints.RemoveAt(spawnIndex);

            }

        }

        // 생성된 점의 리스트 반환

        return points;

    }

    // 주어진 위치가 유효한지 확인하는 메서드

    static bool IsValid(Vector3 candidate, Vector3 sampleRegionSize, float cellSize, float radius, List<Vector3> points, int[,,] grid) {

        // 위치가 공간 내에 있는지 확인

        if (candidate.x >= 0 && candidate.x < sampleRegionSize.x &&

            candidate.y >= 0 && candidate.y < sampleRegionSize.y &&

            candidate.z >= 0 && candidate.z < sampleRegionSize.z) {

            // 위치를 그리드 셀로 변환

            int cellX = (int)(candidate.x / cellSize);

            int cellY = (int)(candidate.y / cellSize);

            int cellZ = (int)(candidate.z / cellSize);

            // 주변 셀 검사 범위 계산

            int searchStartX = Mathf.Max(0, cellX - 2);

            int searchEndX = Mathf.Min(cellX + 2, grid.GetLength(0) - 1);

            int searchStartY = Mathf.Max(0, cellY - 2);

            int searchEndY = Mathf.Min(cellY + 2, grid.GetLength(1) - 1);

            int searchStartZ = Mathf.Max(0, cellZ - 2);

            int searchEndZ = Mathf.Min(cellZ + 2, grid.GetLength(2) - 1);

            // 주변 셀을 검사하여 점들이 서로 겹치는지 확인

            for (int x = searchStartX; x <= searchEndX; x++) {

                for (int y = searchStartY; y <= searchEndY; y++) {

                    for (int z = searchStartZ; z <= searchEndZ; z++) {

                        int pointIndex = grid[x, y, z] - 1;

                        if (pointIndex != -1) {

                            float sqrDst = (candidate - points[pointIndex]).sqrMagnitude;

                            // 점 사이의 거리가 최소 거리(radius)보다 작으면 유효하지 않음

                            if (sqrDst < radius * radius) {

                                return false;

                            }

                        }

                    }

                }

            }

            return true;

        }

        return false;

    }

}

 

Test도 해당 위치에 프리팹을 생성하고 부모가 회전하면 다 회전할 수 있게 수정했다

Test.cs

using System.Collections;

using System.Collections.Generic;

using UnityEngine;

public class Test : MonoBehaviour {

    public float radius = 1;

    public Vector3 regionSize = Vector3.one;

    public int rejectionSamples = 30;

    List<Vector3> points;

    public GameObject m_prefab;

    private void Start()

    {

        points = PoissonDiscSampling3D.GeneratePoints(radius, regionSize, rejectionSamples);

        if (points != null)

        {

            foreach (Vector3 point in points)

            {

                Instantiate(m_prefab, point, Quaternion.identity).transform.SetParent(this.gameObject.transform);

            }

        }

    }

    void OnDrawGizmos() {

        Gizmos.DrawWireCube(regionSize/2,regionSize);

    }

}

 

큐브의 크기는 잘 보일 수 있도록 4로 해두었고

 

radius는 어떻게 할까 하다가 정사각형 안곂치게 5.7로 하였다

 

x, y, z는 많이 만들기 위해 100, 100 ,100으로 했고 RejectionSamples는 4만 해도 충분하지만 혹시 몰라 10으로 뒀다

 

 

 

 

정육면체로 만든 정육면체가 완성이 되었다

 

회전도 된다 몬가 되니까 몬가 신기하다