This blog doesn’t get enough attention, so I’m going to get something up for the day. This is my Unreal Engine implementation of a Poisson Disc Sampling Algorithm. The purpose of this is to generate evenly placed points in the world, allowing us to avoid overlapping positions.
This was done in part from the excellent work done by Martin Roberts: Over Here
Which itself was done on top of Jason Davies work: Here
Along with Robert Bridson’s work: Here
This algorithm quickly became one of my favorites, and I tend to find uses for it in most of my projects, so I wanted to share it with other creators out in the world.
Maybe I’ll post more of these on my personal Twitter: @OccultGameDev
If you follow me there and cyberbully me, I can try and post more of these when I find the time.
Header:
//////////////////////////////////////////////////////////////////////////////
// Returns a Series of 2D Local Space Locations Evenly Spaced from one another to avoid unpleasant clumping
// of locations. You can use these 2D Locations by adding a Worldspace Center Location, and finding a navigable
// point on the NavMesh.
//
// This was Written by Nick Crosgrove, 2022
// Based in Part on https://observablehq.com/@techsparx/an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2
// This Poisson Disk Sampler Algorithm is Released as a CC-BY License
// Commercial Usage is Fine, but Attribution is Required.
// The full Text of the license can be found here: https://creativecommons.org/licenses/by/4.0/legalcode
//////////////////////////////////////////////////////////////////////////////
UFUNCTION(BlueprintCallable, Category = "OccultUtilities|PoissonDiscSampler")
static TArray<FVector2D> GeneratePoissonDiscSamples(const int Width, const int Height, const float ExclusionRadius, const int Iterations, UPARAM(ref) FRandomStream& RandomStream);
//////////////////////////////////////////////////////////////////////////////
static void Internal_IteratePoissonDiscSamples(const int Width, const int Height, const float ExclusionRadius, FRandomStream& RandomStream, TArray<FVector2D>& FinalSamplesArray);
//////////////////////////////////////////////////////////////////////////////
static FORCEINLINE bool IsPointInsideBox(FVector2D const& Point, const float MinX, const float MaxX, const float MinY, const float MaxY)
{
return ((Point.X > MinX) && (Point.X < MaxX) && (Point.Y > MinY) && (Point.Y < MaxY));
}Implementation:
//////////////////////////////////////////////////////////////////////////////
// Returns a Series of 2D Local Space Locations Evenly Spaced from one another to avoid unpleasant clumping
// of locations. You can use these 2D Locations by adding a Worldspace Center Location, and finding a navigable
// point on the NavMesh.
//
// This was Written by Nick Crosgrove, 2022
// Based in Part on https://observablehq.com/@techsparx/an-improvement-on-bridsons-algorithm-for-poisson-disc-samp/2
// This Poisson Disk Sampler Algorithm is Released as a CC-BY License
// Commercial Usage is Fine, but Attribution is Required.
// The full Text of the license can be found here: https://creativecommons.org/licenses/by/4.0/legalcode
//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// static
TArray<FVector2D> UOccultUtilities::GeneratePoissonDiscSamples(const int Width, const int Height, const float ExclusionRadius, const int Iterations, UPARAM(ref) FRandomStream& RandomStream)
{
// Create Return
TArray<FVector2D> FinalSamples;
// First Sample is completely random
FinalSamples.Add(FVector2D(RandomStream.GetFraction() * Width, RandomStream.GetFraction() * Height));
// Iterate
for (int i = 0; i < Iterations; i++)
{
Internal_IteratePoissonDiscSamples(Width, Height, ExclusionRadius, RandomStream, FinalSamples);
}
// Correct Skew
const float HalfWidth = Width * 0.5f;
const float HalfHeight = Height * 0.5f;
for (FVector2D& ValidEntry : FinalSamples)
{
ValidEntry.X -= HalfWidth;
ValidEntry.Y -= HalfHeight;
}
return FinalSamples;
}
//////////////////////////////////////////////////////////////////////////////
// static
void UOccultUtilities::Internal_IteratePoissonDiscSamples(const int Width, const int Height, const float ExclusionRadius, FRandomStream& RandomStream, TArray<FVector2D>& FinalSamplesArray)
{
// Set Essential Values for the Sampler
const int k = 24; // Maximum Attempts before Rejecting this Sample
const float radius2 = ExclusionRadius * ExclusionRadius;
const float cellSize = ExclusionRadius * 0.707107f; // (1/SQRT(2) = 0.707107f)
// Reserve a contiguous location in memory
const int gridWidth = FMath::CeilToInt(Width / cellSize);
const int gridHeight = FMath::CeilToInt(Height / cellSize);
const int sampleSize = gridWidth * gridHeight;
// Create a "Queue" which will expand and contract as we use it.
TArray<FVector2D> SamplesQueue;
for (FVector2D const& sample : FinalSamplesArray)
{
SamplesQueue.Add(sample);
}
while (SamplesQueue.Num() > 0)
{
// Random Sample
int index = RandomStream.RandRange(0, SamplesQueue.Num() - 1);
FVector2D sample = SamplesQueue[index];
// Try to find a candidate within K attempts
for (int j = 0; j < k; ++j)
{
const float Angle = 2.0f * PI * RandomStream.GetFraction();
const float RandomRadius = (RandomStream.GetFraction() * radius2) + ExclusionRadius;
FVector2D Point = FVector2D(sample.X + (RandomRadius * FMath::Cos(Angle)), sample.Y + (RandomRadius * FMath::Sin(Angle)));
// Reject if we fall outside the box
if (false == IsPointInsideBox(Point, 0, Width, 0, Height))
{
continue;
}
// Reject if we are too close to a previous entry
bool hasFailedDistanceCheck = false;
for (FVector2D const& ValidEntry : FinalSamplesArray)
{
const float dx = ValidEntry.X - Point.X;
const float dy = ValidEntry.Y - Point.Y;
if (((dx * dx) + (dy * dy)) < radius2)
{
hasFailedDistanceCheck = true;
break;
}
}
if (true == hasFailedDistanceCheck)
{
continue;
}
// Add the Point
FinalSamplesArray.Add(Point);
continue;
}
// We've exhausted our checks at this sample, so we remove it.
SamplesQueue.RemoveAt(index);
}
}