Poisson Disc Sampling for Unity3D

PoissonDiscSampler.cs

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

namespace Problematic.Toolkit {
	// https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf
	public static class PoissonDiscSampler {
		const int SAMPLE_LIMIT = 30;

		public static IEnumerable<Vector2> Sample<T> (QuadTree<T> quadTree, float minSeparation, System.Func<Vector2, T> CreateSample, System.Func<Vector2, QuadTree<T>, float, bool> IsCandidateValid) where T : IQuadTreeObject{
			var initialSample = new Vector2(
				Random.Range(quadTree.Bounds.xMin, quadTree.Bounds.xMax),
				Random.Range(quadTree.Bounds.yMin, quadTree.Bounds.yMax)
			);
			int initialIndex = 0;

			var samples = new List<Vector2>();
			samples.Add(initialSample);

			var activeSamples = new List<int>();
			activeSamples.Add(initialIndex);

			quadTree.Insert(CreateSample(initialSample));

			while (activeSamples.Count > 0) {
				int index = activeSamples.Sample();
				var center = samples[index];
				var found = false;

				for (int i = 0; i < SAMPLE_LIMIT; i++) {
					Vector2 candidate = GenerateCandidateAround(center, minSeparation);

					if (IsCandidateValid(candidate, quadTree, minSeparation)) {
						found = true;
						int newIndex = samples.Count;
						samples.Add(candidate);
						quadTree.Insert(CreateSample(candidate));
						activeSamples.Add(newIndex);

						break;
					}
				}

				if (!found) {
					activeSamples.Remove(index);
				}
			}

			return samples;
		}

		public static IEnumerable<Vector2> Sample<T> (QuadTree<T> quadTree, float minSeparation, System.Func<Vector2, T> CreateSample) where T : IQuadTreeObject {
			return Sample(quadTree, minSeparation, CreateSample, IsCandidateValid);
		}

		static Vector2 GenerateCandidateAround (Vector2 center, float minSeparation) {
			var sep2 = minSeparation * minSeparation;
			var k = (sep2 * sep2) - sep2;
			var a = Random.value * 2 * Mathf.PI;
			var r = Mathf.Sqrt(Random.value * k + sep2);

			return center + new Vector2(r * Mathf.Cos(a), r * Mathf.Sin(a));
		}

		public static bool IsCandidateValid<T> (Vector2 candidate, QuadTree<T> quadTree, float minSeparation) where T : IQuadTreeObject {
			if (!quadTree.ContainsLocation(candidate)) {
				return false;
			}

			var area = new Rect(0, 0, minSeparation * 4, minSeparation * 4);
			area.center = candidate;

			var nearby = quadTree.RetrieveObjectsInArea(area);

			foreach (var sample in nearby) {
				if ((sample.GetPosition() - candidate).sqrMagnitude < minSeparation * minSeparation) {
					return false;
				}
			}

			return true;
		}
	}
}