[Unity] Poisson Disk Sampling

Poisson Disk Sampling 소개

알고리즘을 사용하여 특정 영역에서 지정된 반지름 내에 겹치지 않는 점을 생성하는 것을 말합니다.

아래 영상을 참고하여 알아볼 것이다.

https://www.youtube.com/watch?v=7WcmyxyFO7o 

주요 기능

위 영상에서 쓰인 코드는 2개로 첫번째는 실제로 배치될 위치를 계산하는 코드다.

각 후보 위치는 주어진 반지름 내에서 무작위로 생성되고, IsValid 메서드를 사용하여 다른 점과 충돌하지 않는지 확인한다. 후보 위치가 통과할 경우 위치 목록에 추가하고 격자 배열에 해당 위치를 표시한다. 그렇지 않은 경우, 후보 위치는 제거한다.
spawnPoints 리스트가 비어질 때까지 반복하며 최종적으로 사용될 위치가 들어가있는 points 리스트가 반환된다. 이러한 점은 지정된 반지름 내에서 서로 겹치지 않는 Poisson Disk 샘플을 나타냅니다

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class PoissonDiscSampling {

	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);
			Vector2 spawnCentre = spawnPoints[spawnIndex];
			bool candidateAccepted = false;

			for (int i = 0; i < numSamplesBeforeRejection; i++)
			{
				float angle = Random.value * Mathf.PI * 2;
				Vector2 dir = new Vector2(Mathf.Sin(angle), Mathf.Cos(angle));
				Vector2 candidate = spawnCentre + dir * 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)] = 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;
						if (sqrDst < radius*radius) {
							return false;
						}
					}
				}
			}
			return true;
		}
		return false;
	}
}

 

 

2번째 코드는 첫번째 코드를 사용하여 사용자에게 보여줄 수 있도록 가시화하는 코드다.

 

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);
			}
		}
	}
}

 

 

사용 예시

이걸 활용하여 지형에 꽃, 나무, 풀, 등을 겹치지 않게 생성시키는 것이 가능 할 것 같아 적용시켜보았다.

 

1. 터레인을 이용하여 지형 생성

 

2. 유튜브에 소개된 코드를 이용하여 생성된 각 포인트에서 지형을 향해 레이캐스트를 사용해서 배치될 오브젝트를 위치시켜주기 위한 간단한 코드 작성

public class Test : MonoBehaviour {

	public float radius = 1;
	public Vector2 regionSize = Vector2.one;
	public int rejectionSamples = 30;
	public float displayRadius =1;

	List<Vector2> points;

	public GameObject g_Rock;

	private void Start()
	{
		points = PoissonDiscSampling.GeneratePoints(radius, regionSize, rejectionSamples);

		if (points != null)
		{
			foreach (Vector2 point in points)
			{
				Vector3 rayStartPoint = new Vector3(point.x, 100f, point.y); 
				Vector3 rayDirection = Vector3.down;

				Ray ray = new Ray(rayStartPoint, rayDirection);

				RaycastHit hitInfo;
				if (Physics.Raycast(ray, out hitInfo, Mathf.Infinity, LayerMask.GetMask("ground")))
				{
					Vector3 hitPoint = hitInfo.point; 
					Instantiate(g_Rock, hitPoint, Quaternion.identity);
				}
			}
		}
	}
}

 

3. 결과