Index going out of bounds for array in Poisson Disk Sampling when trying to convert from 3D to 1D

Thank you to anyone who responds.

I’m always getting an index out of bounds error while trying to implement Bridson’s Algorithm and I can’t figure out why. It’s always when Flatten3DArrayIndexTo1DIndex is being called. I don’t know how or why?

Is it because of how I’m rounding for my SampleCellDimensions? But I’m not sure why it would ever round under 0. I think with how I calculated the annulus, it shouldn’t give me a negative result, but I’m unsure about the math part. That calculation based on the annulus is what I get for Sample and CellSize will never be negative due to the radius and number of dimensions always being positive.

class FPoissonDiskSamplingTaskGraph
{
	/* ~~~~~~~~~~~
	Actual Task Code
	~~~~~~~~~~~ */

public:
	/** return the name of the task **/
	static const TCHAR* GetTaskName()
	{
		return TEXT("PoissonDiskSamplingGraphTask");
	}
	// Required
	FORCEINLINE static TStatId GetStatId()
	{
		RETURN_QUICK_DECLARE_CYCLE_STAT(FPoissonDiskSamplingGraphTask, STATGROUP_TaskGraphTasks);
	}
	/** return the thread for this task **/
	static ENamedThreads::Type GetDesiredThread()
	{
		return ENamedThreads::AnyBackgroundThreadNormalTask;
	}

	static ESubsequentsMode::Type GetSubsequentsMode()
	{
		return ESubsequentsMode::TrackSubsequents;
	}

	// Definition should be in .cpp file, CurrentThread should be a ENamedThreads::AnyBackgroundThreadNormalTask
	void DoTask(ENamedThreads::Type CurrentThread, const FGraphEventRef& MyCompletionGraphEvent)
	{
		/***************************************
		Please note you should not create, destroy, or modify UObjects here. Do those sort of things after all thread are completed.
		All calcs for making stuff can be done in the threads. But the actual making/modifying of the UObjects should be done in main game thread, which is AFTER all tasks have completed :)
		****************************************/
		FIntVector BackgroundGridQuadrantDimensions = FIntVector(120, 150, 100);
		int NumberOfGenerationAttempts = 30, Radius = 25;
		float CellSize = Radius/FMath::Sqrt(3);
		TSet<FVector> PreGeneratedQuadrants;

		BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfGenerationAttempts, Radius, CellSize, PreGeneratedQuadrants);

		for (FVector& Point : PreGeneratedQuadrants)
			UE_LOG(LogTemp, Display, TEXT("%s"), *Point.ToCompactString());
	}

private:
	// https://stats.stackexchange.com/questions/8021/how-to-generate-uniformly-distributed-points-in-the-3-d-unit-ball
	FVector CalculateSamplePointLocationFromSphericalAnnulus(FVector PointToBeAround, int Radius, const TArray<FVector>& ActiveGrid)
	{
		float ρ = FMath::RandRange((float)Radius, (float)2.0f * Radius), Cosθ = FMath::RandRange(0.0f, 1.0f), Φ = FMath::RandRange(0.0f, HALF_PI);

		FVector Sample = FVector(ρ * FMath::Sqrt(FMath::Pow(1 - Cosθ, 2)) * FMath::Cos(Φ), ρ * Cosθ, ρ * FMath::Sqrt(FMath::Pow(1 - Cosθ, 2)) * FMath::Sin(Φ)) + PointToBeAround;

		if (ActiveGrid.Contains(Sample))
			CalculateSamplePointLocationFromSphericalAnnulus(PointToBeAround, Radius, ActiveGrid);

		return Sample;
	}

	// ((X • Y • Z) - 1) = (X + WIDTH • (Y + DEPTH • Z)) → (119 + 120  • (149 + 150  • 99))
	int Flatten3DArrayIndexTo1DIndex(FIntVector ArrayIndex3D, FIntVector BackgroundGridDimensions)
	{
		int Result = ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z);

		UE_LOG(LogTemp, Display,
			TEXT("Flatten 3D Array Index To 1D Index: \n%s, %s\n%d + %d * (%d + %d * %d) = %d"),
			*ArrayIndex3D.ToString(), *BackgroundGridDimensions.ToString(), ArrayIndex3D.X, BackgroundGridDimensions.X, ArrayIndex3D.Y, BackgroundGridDimensions.Y, ArrayIndex3D.Z,
			Result);

		return Result;

		// return ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z);
	}

	int  SearchingForNeighbour(const TArray<FVector>& BackgroundGrid, int NeighbourIndex, FVector& Sample, int& Radius)
	{
		FVector Neighbour = BackgroundGrid[NeighbourIndex];

		return (Neighbour != FVector(-1.f) && FVector::Distance(Sample, Neighbour) > Radius);
	}

	uint8 DoesNeighbourExist(const TArray<FVector>& BackgroundGridQuadrant, const FIntVector& BackgroundGridQuadrantDimensions, FIntVector& MinPossibleNeighbourLeftOfSample, FIntVector& MaxPossibleNeighbourRightOfSample, FVector& Sample, int& SampleCellIndex, int& Radius, float& CellSize)
	{
		int
			MinNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MinPossibleNeighbourLeftOfSample, BackgroundGridQuadrantDimensions),
			MaxNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MaxPossibleNeighbourRightOfSample, BackgroundGridQuadrantDimensions),
			MinNeighbourSearchAmt = (SampleCellIndex - MinNeighbourIndex) - 1,
			MaxNeighbourSearchAmt = MaxNeighbourIndex - SampleCellIndex;

		for (int I = MinNeighbourIndex; I < SampleCellIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;

		for (int I = SampleCellIndex + 1; I < MaxNeighbourIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;
		return false;
	}

	void BridsonsAlgorithm(const FIntVector& BackgroundGridQuadrantDimensions, const int& NumberOfGenerationAttempts, int& Radius, float& CellSize, TSet<FVector>& PreGeneratedQuadrants)
	{
		double StartPlatformTimeSeconds = FPlatformTime::Seconds();

		int BackgroundGridQuadrantMaxIndex = BackgroundGridQuadrantDimensions.X * BackgroundGridQuadrantDimensions.Y * BackgroundGridQuadrantDimensions.Z;

		// Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r / √n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple ndimensional array of integers : the default −1 indicates no sample, a non - negative integer gives the index of the sample located in a cell.
		TArray<FVector> BackgroundGridQuadrant;
		BackgroundGridQuadrant.Init(FVector(-1.f), BackgroundGridQuadrantMaxIndex);

		// Step 1: Select the initial sample,  X₀, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list”(an array of sample indices) with this index(zero). 
		FVector X₀ = FVector(FMath::RandHelper(BackgroundGridQuadrantDimensions.X), FMath::RandHelper(BackgroundGridQuadrantDimensions.Y), FMath::RandHelper(BackgroundGridQuadrantDimensions.Z));

		FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));
		int ActiveGridMaxIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions);
		BackgroundGridQuadrant[ActiveGridMaxIndex] = X₀;

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		TSet<FVector> Points;

		// Step 2. While the active list is not empty
		while (ActiveGrid.Num() > 0) {
			// Again, this should be the NumberOfAttemptsBeforeRejection
			for (int I = 0; I < NumberOfGenerationAttempts; I++) {
				int Index = FMath::RandHelper(ActiveGridMaxIndex);

				// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. 				
				FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

				int  HasFoundNeighbour = false;

				// Không hẳn vì phát theo hình vành khăn, nên điểm có thể xa hơn bán kính.
				FIntVector
					SampleCellDimensions = FIntVector(FMath::RoundToInt(Sample.X / CellSize), FMath::RoundToInt(Sample.Y / CellSize), FMath::RoundToInt(Sample.Z / CellSize)),
					MaxPossibleNeighbourLeftOfSample = FIntVector(FMath::RoundToInt((Sample.X - Radius) / CellSize), FMath::RoundToInt((Sample.Y - Radius) / CellSize), FMath::RoundToInt((Sample.Z - Radius) / CellSize)),
					MaxPossibleNeighbourRightOfSample = FIntVector(FMath::RoundToInt((Sample.X + Radius) / CellSize), FMath::RoundToInt((Sample.Y + Radius) / CellSize), FMath::RoundToInt((Sample.Z + Radius) / CellSize));

				// Sample cell index somehow becomes negative? Overflow
				int SampleCellIndex = Flatten3DArrayIndexTo1DIndex(SampleCellDimensions, BackgroundGridQuadrantDimensions);

				UE_LOG(LogTemp, Display, 
					TEXT("Active Grid - Number of elements: %d\nIndex: %d\nXᵢ: %s\nSample: %s, Sample Cell Dimensions: %s"), 
					ActiveGrid.Num(), Index, *Xᵢ.ToCompactString(), *Sample.ToCompactString(), *SampleCellDimensions.ToString());

				if ((SampleCellIndex <= BackgroundGridQuadrantMaxIndex) && DoesNeighbourExist(BackgroundGridQuadrant, BackgroundGridQuadrantDimensions, MaxPossibleNeighbourLeftOfSample, MaxPossibleNeighbourRightOfSample, Sample, SampleCellIndex, Radius, CellSize))
				{
					HasFoundNeighbour = true;

					BackgroundGridQuadrant[SampleCellIndex] = Sample;
					ActiveGrid.AddUnique(Sample);

					Points.Add(Sample);

					UE_LOG(LogTemp, Display, TEXT("Poisson Disc Sampling sample location: %s"), *Sample.ToCompactString());

					return;
				}

				// If after k attempts no such point is found, instead remove i from the active list.
				if (!HasFoundNeighbour)
					ActiveGrid.RemoveAt(Index);
			}
		}

		if (Points.Num() <= 0)
			BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfGenerationAttempts, Radius, CellSize, PreGeneratedQuadrants);

		PreGeneratedQuadrants.Append(Points);

		double EndPlatformTimeSeconds = FPlatformTime::Seconds();
		UE_LOG(LogTemp, Display, TEXT("Bridson's Algorithm (UE4 C++): %f seconds."), EndPlatformTimeSeconds - StartPlatformTimeSeconds);
	}
};

[Edit]
Ok, nevermind. Sample could be less than 0. I fixed it so that when searching for neighbors, the dimensions of those neighbor cells will always be between 0 and the background grid dimension’s max index. But the question is now, how do I make Sample always more than 0.

class FPoissonDiskSamplingTaskGraph
{
	/* ~~~~~~~~~~~
	Actual Task Code
	~~~~~~~~~~~ */

public:
	/** return the name of the task **/
	static const TCHAR* GetTaskName()
	{
		return TEXT("PoissonDiskSamplingGraphTask");
	}
	// Required
	FORCEINLINE static TStatId GetStatId()
	{
		RETURN_QUICK_DECLARE_CYCLE_STAT(FPoissonDiskSamplingGraphTask, STATGROUP_TaskGraphTasks);
	}
	/** return the thread for this task **/
	static ENamedThreads::Type GetDesiredThread()
	{
		return ENamedThreads::AnyBackgroundThreadNormalTask;
	}

	static ESubsequentsMode::Type GetSubsequentsMode()
	{
		return ESubsequentsMode::TrackSubsequents;
	}

	// Definition should be in .cpp file, CurrentThread should be a ENamedThreads::AnyBackgroundThreadNormalTask
	void DoTask(ENamedThreads::Type CurrentThread, const FGraphEventRef& MyCompletionGraphEvent)
	{
		/***************************************
		Please note you should not create, destroy, or modify UObjects here. Do those sort of things after all thread are completed.
		All calcs for making stuff can be done in the threads. But the actual making/modifying of the UObjects should be done in main game thread, which is AFTER all tasks have completed :)
		****************************************/
		FIntVector BackgroundGridQuadrantDimensions = FIntVector(120, 150, 100);
		int NumberOfGenerationAttempts = 30, Radius = 25;
		float CellSize = Radius/FMath::Sqrt(3);
		TSet<FVector> PreGeneratedQuadrants;

		BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfGenerationAttempts, Radius, CellSize, PreGeneratedQuadrants);

		for (FVector& Point : PreGeneratedQuadrants)
			UE_LOG(LogTemp, Display, TEXT("\n\n\n%s"), *Point.ToCompactString());
	}

private:
	// https://stats.stackexchange.com/questions/8021/how-to-generate-uniformly-distributed-points-in-the-3-d-unit-ball
	FVector CalculateSamplePointLocationFromSphericalAnnulus(FVector PointToBeAround, int Radius, const TArray<FVector>& ActiveGrid)
	{
		float ρ = FMath::RandRange((float)Radius, (float)2.0f * Radius), Cosθ = FMath::RandRange(0.0f, 1.0f), Φ = FMath::RandRange(0.0f, HALF_PI);

		FVector Sample = FVector(ρ * FMath::Sqrt(FMath::Pow(1 - Cosθ, 2)) * FMath::Cos(Φ), ρ * Cosθ, ρ * FMath::Sqrt(FMath::Pow(1 - Cosθ, 2)) * FMath::Sin(Φ)) + PointToBeAround;

		if (ActiveGrid.Contains(Sample))
			CalculateSamplePointLocationFromSphericalAnnulus(PointToBeAround, Radius, ActiveGrid);

		return Sample;
	}

	// ((X • Y • Z) - 1) = (X + WIDTH • (Y + DEPTH • Z)) → (119 + 120  • (149 + 150  • 99))
	int Flatten3DArrayIndexTo1DIndex(FIntVector ArrayIndex3D, FIntVector BackgroundGridDimensions, const int& BackgroundGridQuadrantMaxIndex)
	{
		int Result = FMath::Clamp(ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z), 0, BackgroundGridQuadrantMaxIndex);

		UE_LOG(LogTemp, Display,
			TEXT("\n\n\nFlatten 3D Array Index To 1D Index: \n%s, %s\n%d + %d * (%d + %d * %d) = %d"),
			*ArrayIndex3D.ToString(), *BackgroundGridDimensions.ToString(), ArrayIndex3D.X, BackgroundGridDimensions.X, ArrayIndex3D.Y, BackgroundGridDimensions.Y, ArrayIndex3D.Z,
			Result);

		return Result;

		// return ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z);
	}

	int  SearchingForNeighbour(const TArray<FVector>& BackgroundGrid, int NeighbourIndex, FVector& Sample, int& Radius)
	{
		FVector Neighbour = BackgroundGrid[NeighbourIndex];

		return (Neighbour != FVector(-1.f) && FVector::Distance(Sample, Neighbour) > Radius);
	}

	uint8 DoesNeighbourExist(const TArray<FVector>& BackgroundGridQuadrant, const FIntVector& BackgroundGridQuadrantDimensions, const int& BackgroundGridQuadrantMaxIndex, FIntVector& MinPossibleNeighbourLeftOfSample, FIntVector& MaxPossibleNeighbourRightOfSample, FVector& Sample, int& SampleCellIndex, int& Radius, float& CellSize)
	{
		// The problem has to be MinPossibleNeighbourLeftOfSample, and MaxPossibleNeighbourRightOfSample
		int
			MinNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MinPossibleNeighbourLeftOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex),
			MaxNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MaxPossibleNeighbourRightOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex),
			MinNeighbourSearchAmt = SampleCellIndex - MinNeighbourIndex,
			MaxNeighbourSearchAmt = MaxNeighbourIndex - SampleCellIndex;

		UE_LOG(LogTemp, Display,
			TEXT("\n\n\nMin neighbour index: %d\nMax neighbour index: %d\nMin neighbour search amount: %d\nMax neighbour search amount: %d"),
			MinNeighbourIndex, MaxNeighbourIndex, MinNeighbourSearchAmt, MaxNeighbourSearchAmt);

		for (int I = MinNeighbourIndex; I < SampleCellIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;

		for (int I = SampleCellIndex + 1; I < MaxNeighbourIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;
		return false;
	}

	void BridsonsAlgorithm(const FIntVector& BackgroundGridQuadrantDimensions, const int& NumberOfGenerationAttempts, int& Radius, float& CellSize, TSet<FVector>& PreGeneratedQuadrants)
	{
		double StartPlatformTimeSeconds = FPlatformTime::Seconds();

		int BackgroundGridQuadrantMaxIndex = BackgroundGridQuadrantDimensions.X * BackgroundGridQuadrantDimensions.Y * BackgroundGridQuadrantDimensions.Z - 1;

		// Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r / √n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple ndimensional array of integers : the default −1 indicates no sample, a non - negative integer gives the index of the sample located in a cell.
		TArray<FVector> BackgroundGridQuadrant;
		BackgroundGridQuadrant.Init(FVector(-1.f), BackgroundGridQuadrantMaxIndex);

		// Step 1: Select the initial sample,  X₀, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list”(an array of sample indices) with this index(zero). 
		FVector X₀ = FVector(FMath::RandHelper(BackgroundGridQuadrantDimensions.X), FMath::RandHelper(BackgroundGridQuadrantDimensions.Y), FMath::RandHelper(BackgroundGridQuadrantDimensions.Z));


		FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));
		int ActiveGridMaxIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);
		BackgroundGridQuadrant[ActiveGridMaxIndex] = X₀;

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		TSet<FVector> Points;

		// Step 2. While the active list is not empty
		while (ActiveGrid.Num() > 0) {
			// Again, this should be the NumberOfAttemptsBeforeRejection
			for (int I = 0; I < NumberOfGenerationAttempts; I++) {
				int Index = FMath::RandHelper(ActiveGridMaxIndex);

				// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. This could actually end up just being where the player is.
				FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

				int  HasFoundNeighbour = false;

				// Không hẳn vì phát theo hình vành khăn, nên điểm có thể xa hơn bán kính.
				FIntVector
					SampleCellDimensions = FIntVector(FMath::RoundToInt(Sample.X / CellSize), FMath::RoundToInt(Sample.Y / CellSize), FMath::RoundToInt(Sample.Z / CellSize)),
					MaxPossibleNeighbourLeftOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z)),
					MaxPossibleNeighbourRightOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z));

				// Sample cell index somehow becomes negative? Overflow
				int SampleCellIndex = Flatten3DArrayIndexTo1DIndex(SampleCellDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);

				UE_LOG(LogTemp, Display, 
					TEXT("\n\n\nActive Grid - Number of elements: %d\nIndex: %d\nXᵢ: %s\nSample: %s, Sample Cell Dimensions: %s"), 
					ActiveGrid.Num(), Index, *Xᵢ.ToCompactString(), *Sample.ToCompactString(), *SampleCellDimensions.ToString());

				if ((SampleCellIndex <= BackgroundGridQuadrantMaxIndex) && DoesNeighbourExist(BackgroundGridQuadrant, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex, MaxPossibleNeighbourLeftOfSample, MaxPossibleNeighbourRightOfSample, Sample, SampleCellIndex, Radius, CellSize))
				{
					HasFoundNeighbour = true;

					BackgroundGridQuadrant[SampleCellIndex] = Sample;
					ActiveGrid.AddUnique(Sample);

					Points.Add(Sample);

					UE_LOG(LogTemp, Display, TEXT("\n\n\nPoisson Disc Sampling sample location: %s"), *Sample.ToCompactString());

					return;
				}

				// If after k attempts no such point is found, instead remove i from the active list.
				if (!HasFoundNeighbour)
					ActiveGrid.RemoveAt(Index);
			}
		}

		if (Points.Num() <= 0)
			BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfGenerationAttempts, Radius, CellSize, PreGeneratedQuadrants);

		PreGeneratedQuadrants.Append(Points);

		double EndPlatformTimeSeconds = FPlatformTime::Seconds();
		UE_LOG(LogTemp, Display, TEXT("Bridson's Algorithm (UE4 C++): %f seconds."), EndPlatformTimeSeconds - StartPlatformTimeSeconds);
	}
};

After some debugging your code is crashing here

FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

Your ActiveGrid has a length of 1 yet the index you are using to get it’s offset can be in the thousands (eg random 44834)

You need to either limit the index to the max count of ActiveGrid or you are missing some type of generation of it (higher TArray count) on the first pass.

This is triggering the out of bounds index exception because you are reaching well beyond the array count.

Thank you for responding. With the instructions of the paper:

Step 0. Initialize an n-dimensional background grid for storing
samples and accelerating spatial searches. We pick the cell size to
be bounded by r/√ n, so that each grid cell will contain at most
one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default −1 indicates no sample, a
non-negative integer gives the index of the sample located in a cell.
Step 1. Select the initial sample, x0, randomly chosen uniformly
from the domain. Insert it into the background grid, and initialize
the “active list” (an array of sample indices) with this index (zero).

Did I not do that correctly here then?

FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));
		int ActiveGridMaxIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);
		BackgroundGridQuadrant[ActiveGridMaxIndex] = X₀;

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		int Index = FMath::RandHelper(ActiveGridMaxIndex);

		// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. This could actually end up just being where the player is.
		FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

		// If the checks succeed
		ActiveGrid.AddUnique(Sample);

And sorry if I’m not understanding right away. Actually I think I see what you mean. Would I be using the ActiveGrid.Num() - 1 for the range?

The part where it crashes is during an iteration loop perhaps you mistranslated

	FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

instead of

FVector Xᵢ = FVector(ActiveGrid[I]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

You do not use the I iterator descriptor anywhere in the loop which is strange. I’d start looking there.

Alright, thank you. I’ll come back to this post soon. Unfortunately I don’t have much time today. I really appreciate your insight, and yea it makes a lot of sense now…I’m just trying to follow the instructions of the paper but I think I didn’t fully understand it or how to translate it.

Well I’m not getting any crashes after the switch to I

FVector Xᵢ = FVector(ActiveGrid[I]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

Log Readouts

LogTemp: Display: ActiveGridDimensions: 
 X: 6 
 Y: 5 
 Z: 1
LogTemp: Display: Flatten 3D Array Index To 1D Index: 
X=6 Y=5 Z=1, X=120 Y=150 Z=100
6 + 120 * (5 + 150 * 1) = 18606
LogTemp: Display: ActiveGridMaxIndex: 18606
LogTemp: Display: Flatten 3D Array Index To 1D Index: 
X=8 Y=5 Z=2, X=120 Y=150 Z=100
8 + 120 * (5 + 150 * 2) = 36608
LogTemp: Display: Active Grid - Number of elements: 1
Index: 12766
Xᵢ: V(X=90.00, Y=68.00, Z=11.00)
Sample: V(X=117.65, Y=70.85, Z=33.64), Sample Cell Dimensions: X=8 Y=5 Z=2
LogTemp: Display: Flatten 3D Array Index To 1D Index: 
X=6 Y=3 Z=1, X=120 Y=150 Z=100
6 + 120 * (3 + 150 * 1) = 18366
LogTemp: Display: Flatten 3D Array Index To 1D Index: 
X=10 Y=7 Z=4, X=120 Y=150 Z=100
10 + 120 * (7 + 150 * 4) = 72850
LogTemp: Display: Poisson Disc Sampling sample location: V(X=117.65, Y=70.85, Z=33.64)

Though it is a shot in the dark, you’ll have to check if the readouts match the whitepapers

If you need a random value from ActiveGrid then you need to add some safe guards to not trigger out of bounds


	void BridsonsAlgorithm(const FIntVector& BackgroundGridQuadrantDimensions, const int& NumberOfGenerationAttempts, int& Radius, float& CellSize, TSet<FVector>& PreGeneratedQuadrants)
	{
		double StartPlatformTimeSeconds = FPlatformTime::Seconds();

		int BackgroundGridQuadrantMaxIndex = BackgroundGridQuadrantDimensions.X * BackgroundGridQuadrantDimensions.Y * BackgroundGridQuadrantDimensions.Z;

		// Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r / √n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple ndimensional array of integers : the default −1 indicates no sample, a non - negative integer gives the index of the sample located in a cell.
		TArray<FVector> BackgroundGridQuadrant;
		BackgroundGridQuadrant.Init(FVector(-1.f), BackgroundGridQuadrantMaxIndex);

		// Step 1: Select the initial sample,  X₀, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list”(an array of sample indices) with this index(zero). 
		FVector X₀ = FVector(FMath::RandHelper(BackgroundGridQuadrantDimensions.X), FMath::RandHelper(BackgroundGridQuadrantDimensions.Y), FMath::RandHelper(BackgroundGridQuadrantDimensions.Z));

		FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));

		UE_LOG(LogTemp, 
			Display, TEXT("ActiveGridDimensions: \n X: %d \n Y: %d \n Z: %d\n"), 
			ActiveGridDimensions.X, ActiveGridDimensions.Y, ActiveGridDimensions.Z);
		


		int ActiveGridMaxIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions);

		UE_LOG(LogTemp,
			Display, TEXT("ActiveGridMaxIndex: %d"),
			ActiveGridMaxIndex);
		

		BackgroundGridQuadrant[ActiveGridMaxIndex] = X₀;


		

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		TSet<FVector> Points;

		// Step 2. While the active list is not empty
		while (ActiveGrid.Num() > 0) {
			if (ActiveGrid.Num() == 0) break;

			// Again, this should be the NumberOfAttemptsBeforeRejection
			for (int I = 0; I < NumberOfGenerationAttempts; I++) {
				int Index = FMath::RandHelper(ActiveGrid.Num());

				// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. 				
				FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

				int  HasFoundNeighbour = false;

				// Không hẳn vì phát theo hình vành khăn, nên điểm có thể xa hơn bán kính.
				FIntVector
					SampleCellDimensions = FIntVector(FMath::RoundToInt(Sample.X / CellSize), FMath::RoundToInt(Sample.Y / CellSize), FMath::RoundToInt(Sample.Z / CellSize)),
					MaxPossibleNeighbourLeftOfSample = FIntVector(FMath::RoundToInt((Sample.X - Radius) / CellSize), FMath::RoundToInt((Sample.Y - Radius) / CellSize), FMath::RoundToInt((Sample.Z - Radius) / CellSize)),
					MaxPossibleNeighbourRightOfSample = FIntVector(FMath::RoundToInt((Sample.X + Radius) / CellSize), FMath::RoundToInt((Sample.Y + Radius) / CellSize), FMath::RoundToInt((Sample.Z + Radius) / CellSize));

				// Sample cell index somehow becomes negative? Overflow
				int SampleCellIndex = Flatten3DArrayIndexTo1DIndex(SampleCellDimensions, BackgroundGridQuadrantDimensions);

				UE_LOG(LogTemp, Display,
					TEXT("Active Grid - Number of elements: %d\nIndex: %d\nXᵢ: %s\nSample: %s, Sample Cell Dimensions: %s"),
					ActiveGrid.Num(), Index, *Xᵢ.ToCompactString(), *Sample.ToCompactString(), *SampleCellDimensions.ToString());

				if ((SampleCellIndex <= BackgroundGridQuadrantMaxIndex) && DoesNeighbourExist(BackgroundGridQuadrant, BackgroundGridQuadrantDimensions, MaxPossibleNeighbourLeftOfSample, MaxPossibleNeighbourRightOfSample, Sample, SampleCellIndex, Radius, CellSize))
				{
					HasFoundNeighbour = true;

					BackgroundGridQuadrant[SampleCellIndex] = Sample;
					ActiveGrid.AddUnique(Sample);

					Points.Add(Sample);

					UE_LOG(LogTemp, Display, TEXT("Poisson Disc Sampling sample location: %s"), *Sample.ToCompactString());

					return;
				}

				// If after k attempts no such point is found, instead remove i from the active list.
				if (!HasFoundNeighbour) {
					if (ActiveGrid.IsValidIndex(Index)) { 
						ActiveGrid.RemoveAt(Index); 
					}
				}
			}
		}

		if (Points.Num() <= 0)
			BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfGenerationAttempts, Radius, CellSize, PreGeneratedQuadrants);

		PreGeneratedQuadrants.Append(Points);

		double EndPlatformTimeSeconds = FPlatformTime::Seconds();
		UE_LOG(LogTemp, Display, TEXT("Bridson's Algorithm (UE4 C++): %f seconds."), EndPlatformTimeSeconds - StartPlatformTimeSeconds);
	}
1 Like

I think I fixed it? You’re kind of right, the FMath::RandHelper should be ActiveGrid.Num()-1 because the index starts at 0. At least I’m pretty sure how that works, because I think at the very beginning you’re supposed to grab whatever the value Active Grid has at the very beginning and should be initialised at the 0 index. So it should be choosing randomly between 0 and 0 then eventually increasing the amount of indices in Active Grid from there.

I guess I’m just not sure about the spherical coordinates to Cartesian coordinates. But so far no negative values? Should I use absolute values in the math just to make sure? Actually I also realised I’d have to probably clamp Sample so it doesn’t go out of Background Grid. Or do something with the calculation so it sample can’t be bigger than the background grid dimensions? Not sure why I’m getting samples that are bigger than that at least on one axis.

Thank you for your help. I appreciate it.

class FPoissonDiskSamplingTaskGraph
{
	/* ~~~~~~~~~~~
	Actual Task Code
	~~~~~~~~~~~ */

public:
	/** return the name of the task **/
	static const TCHAR* GetTaskName()
	{
		return TEXT("PoissonDiskSamplingGraphTask");
	}
	// Required
	FORCEINLINE static TStatId GetStatId()
	{
		RETURN_QUICK_DECLARE_CYCLE_STAT(FPoissonDiskSamplingGraphTask, STATGROUP_TaskGraphTasks);
	}
	/** return the thread for this task **/
	static ENamedThreads::Type GetDesiredThread()
	{
		return ENamedThreads::AnyBackgroundThreadNormalTask;
	}

	static ESubsequentsMode::Type GetSubsequentsMode()
	{
		return ESubsequentsMode::TrackSubsequents;
	}

	// Definition should be in .cpp file, CurrentThread should be a ENamedThreads::AnyBackgroundThreadNormalTask
	void DoTask(ENamedThreads::Type CurrentThread, const FGraphEventRef& MyCompletionGraphEvent)
	{
		/***************************************
		Please note you should not create, destroy, or modify UObjects here. Do those sort of things after all thread are completed.
		All calcs for making stuff can be done in the threads. But the actual making/modifying of the UObjects should be done in main game thread, which is AFTER all tasks have completed :)
		****************************************/
		FIntVector BackgroundGridQuadrantDimensions = FIntVector(120, 150, 100);
		int NumberOfAttemptsBeforeRejection = 30, Radius = 25;
		TSet<FVector> PreGeneratedQuadrants;

		BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfAttemptsBeforeRejection, Radius, PreGeneratedQuadrants);

		for (FVector& Point : PreGeneratedQuadrants)
			UE_LOG(LogTemp, Display, TEXT("\n%s\n"), *Point.ToCompactString());
	}

private:
	// https://stats.stackexchange.com/questions/8021/how-to-generate-uniformly-distributed-points-in-the-3-d-unit-ball . If math is right, will always be positive number.
	FVector CalculateSamplePointLocationFromSphericalAnnulus(FVector PointToBeAround, int Radius, const TArray<FVector>& ActiveGrid)
	{
		float ρ = FMath::RandRange((float)Radius, (float)2.0f * Radius), Cosθ = FMath::RandRange(0.0f, 1.0f), Φ = FMath::RandRange(0.0f, HALF_PI);

		FVector Sample = FVector(ρ * FMath::Sqrt(FMath::Square(1 - Cosθ)) * FMath::Cos(Φ), ρ * Cosθ, ρ * FMath::Sqrt(FMath::Square(1 - Cosθ)) * FMath::Sin(Φ)) + PointToBeAround;

		if (ActiveGrid.Contains(Sample))
			CalculateSamplePointLocationFromSphericalAnnulus(PointToBeAround, Radius, ActiveGrid);

		return Sample;
	}

	// ((X • Y • Z) - 1) = (X + WIDTH • (Y + DEPTH • Z)) → (119 + 120  • (149 + 150  • 99))
	int Flatten3DArrayIndexTo1DIndex(FIntVector ArrayIndex3D, FIntVector BackgroundGridDimensions, const int& BackgroundGridQuadrantMaxIndex)
	{
		int Result = FMath::Clamp(ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z), 0, BackgroundGridQuadrantMaxIndex);

		UE_LOG(LogTemp, Display,
			TEXT("\nFlatten 3D Array Index To 1D Index: \n%s, %s\n%d + %d * (%d + %d * %d) = %d\n"),
			*ArrayIndex3D.ToString(), *BackgroundGridDimensions.ToString(), ArrayIndex3D.X, BackgroundGridDimensions.X, ArrayIndex3D.Y, BackgroundGridDimensions.Y, ArrayIndex3D.Z,
			Result);

		return Result;

		// return ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z);
	}

	int  SearchingForNeighbour(const TArray<FVector>& BackgroundGrid, int NeighbourIndex, FVector& Sample, int& Radius)
	{
		FVector Neighbour = BackgroundGrid[NeighbourIndex];

		return (Neighbour != FVector(-1.f) && FVector::Distance(Sample, Neighbour) > Radius);
	}

	uint8 DoesNeighbourExist(const TArray<FVector>& BackgroundGridQuadrant, const FIntVector& BackgroundGridQuadrantDimensions, const int& BackgroundGridQuadrantMaxIndex, FIntVector& MinPossibleNeighbourLeftOfSample, FIntVector& MaxPossibleNeighbourRightOfSample, FVector& Sample, int& SampleCellIndex, int& Radius, float& CellSize)
	{
		int
			MinNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MinPossibleNeighbourLeftOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex),
			MaxNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MaxPossibleNeighbourRightOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex),
			MinNeighbourSearchAmt = SampleCellIndex - MinNeighbourIndex,
			MaxNeighbourSearchAmt = MaxNeighbourIndex - SampleCellIndex;

		UE_LOG(LogTemp, Display,
			TEXT("\nMin neighbour index: %d\nMax neighbour index: %d\nMin neighbour search amount: %d\nMax neighbour search amount: %d\n"),
			MinNeighbourIndex, MaxNeighbourIndex, MinNeighbourSearchAmt, MaxNeighbourSearchAmt);

		for (int I = MinNeighbourIndex; I < SampleCellIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;

		for (int I = SampleCellIndex + 1; I <= MaxNeighbourIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;
		return false;
	}

	void BridsonsAlgorithm(const FIntVector& BackgroundGridQuadrantDimensions, const int& NumberOfAttemptsBeforeRejection, int& Radius, TSet<FVector>& PreGeneratedQuadrants, int MaxNumOfPoints = 200)
	{
		double StartPlatformTimeSeconds = FPlatformTime::Seconds();

		int BackgroundGridQuadrantMaxIndex = BackgroundGridQuadrantDimensions.X * BackgroundGridQuadrantDimensions.Y * BackgroundGridQuadrantDimensions.Z - 1;

		// Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r / √n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple ndimensional array of integers : the default −1 indicates no sample, a non - negative integer gives the index of the sample located in a cell.
		TArray<FVector> BackgroundGridQuadrant;
		BackgroundGridQuadrant.Init(FVector(-1.f), BackgroundGridQuadrantMaxIndex);

		float CellSize = Radius / FMath::Sqrt(3);

		// Step 1: Select the initial sample,  X₀, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list”(an array of sample indices) with this index(zero). 
		FVector X₀ = FVector(FMath::RandHelper(BackgroundGridQuadrantDimensions.X), FMath::RandHelper(BackgroundGridQuadrantDimensions.Y), FMath::RandHelper(BackgroundGridQuadrantDimensions.Z));

		FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));
		int ActiveGridIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);
		BackgroundGridQuadrant[ActiveGridIndex] = X₀;

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		TSet<FVector> Points;

		// Step 2. While the active list is not empty
		while (ActiveGrid.Num() > 0) {
			// Prevent running out of memory error. Possible for it to continue forever.
			if (Points.Num() == MaxNumOfPoints)
				break;

			// Again, this should be the NumberOfAttemptsBeforeRejection
			for (int I = 0; I < NumberOfAttemptsBeforeRejection; I++) {
				int Index = FMath::RandHelper(ActiveGrid.Num() - 1);

				// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. This could actually end up just being where the player is.
				FVector Xᵢ = FVector(ActiveGrid[Index]), Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid);

				uint8  HasFoundNeighbour = false;

				//Possible for neighbours to be out of bounds otherwise and will throw an index out of bounds error.
				FIntVector
					SampleCellDimensions = FIntVector(FMath::RoundToInt(Sample.X / CellSize), FMath::RoundToInt(Sample.Y / CellSize), FMath::RoundToInt(Sample.Z / CellSize)),
					MaxPossibleNeighbourLeftOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z)),
					MaxPossibleNeighbourRightOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z));

				int SampleCellIndex = Flatten3DArrayIndexTo1DIndex(SampleCellDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);

				UE_LOG(LogTemp, Display, 
					TEXT("\nActive Grid - Number of elements: %d\nIndex: %d\nXᵢ: %s\nSample: %s, Sample cell dimensions: %s\nSample cell index: %d"), 
					ActiveGrid.Num(), Index, *Xᵢ.ToCompactString(), *Sample.ToCompactString(), *SampleCellDimensions.ToString(), SampleCellIndex);

				if ((SampleCellIndex <= BackgroundGridQuadrantMaxIndex) && DoesNeighbourExist(BackgroundGridQuadrant, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex, MaxPossibleNeighbourLeftOfSample, MaxPossibleNeighbourRightOfSample, Sample, SampleCellIndex, Radius, CellSize))
				{
					HasFoundNeighbour = true;

					BackgroundGridQuadrant[SampleCellIndex] = Sample;
					ActiveGrid.AddUnique(Sample);

					Points.Add(Sample);

					UE_LOG(LogTemp, Display, TEXT("\nPoisson Disc Sampling sample location: %s\n"), *Sample.ToCompactString());

					break;
				}

				// If after k attempts no such point is found, instead remove i from the active list.
				if (!HasFoundNeighbour)
					ActiveGrid.RemoveAt(Index);
			}
		}

		// Possible to never generate any points.
		if (Points.Num() <= 0)
			BridsonsAlgorithm(BackgroundGridQuadrantDimensions, NumberOfAttemptsBeforeRejection, Radius, PreGeneratedQuadrants);

		PreGeneratedQuadrants.Append(Points);

		double EndPlatformTimeSeconds = FPlatformTime::Seconds();
		UE_LOG(LogTemp, Display, TEXT("\nBridson's Algorithm (UE4 C++): %f seconds.\n"), EndPlatformTimeSeconds - StartPlatformTimeSeconds);
	}
};
class FPoissonDiskSamplingTaskGraph
{
private:
	TSet<FVector> PreGeneratedQuadrant;

	/* ~~~~~~~~~~~
	Actual Task Code
	~~~~~~~~~~~ */

public:
	/** return the name of the task **/
	static const TCHAR* GetTaskName()
	{
		return TEXT("PoissonDiskSamplingGraphTask");
	}
	// Required
	FORCEINLINE static TStatId GetStatId()
	{
		RETURN_QUICK_DECLARE_CYCLE_STAT(FPoissonDiskSamplingGraphTask, STATGROUP_TaskGraphTasks);
	}
	/** return the thread for this task **/
	static ENamedThreads::Type GetDesiredThread()
	{
		return ENamedThreads::AnyBackgroundThreadNormalTask;
	}

	static ESubsequentsMode::Type GetSubsequentsMode()
	{
		return ESubsequentsMode::TrackSubsequents;
	}

	void DoTask(ENamedThreads::Type CurrentThread, const FGraphEventRef& MyCompletionGraphEvent)
	{
		FIntVector BackgroundGridQuadrantDimensions = FIntVector(120, 150, 100);
		int NumberOfAttemptsBeforeRejection = 30, Radius = 25, MaxNumOfPoints = 200;

		BridsonsAlgorithm(PreGeneratedQuadrant/*, BackgroundGridQuadrantDimensions, MaxNumOfPoints*/);

		if (bToggleLogTemp) {
			int I = 0;
			FString PointsList;

			for (FVector& Point : PreGeneratedQuadrant) {
				PointsList.Append(FString::Printf(TEXT("%d: %s\n"), I, *Point.ToCompactString()));
				I++;
			}

			UE_LOG(LogTemp, Display, TEXT("\n%s\n"), *PointsList);
		}
	}

private:
	uint8 bToggleLogTemp = false;

	// https://stats.stackexchange.com/questions/8021/how-to-generate-uniformly-distributed-points-in-the-3-d-unit-ball . If math is right, will always be positive number.
	FVector CalculateSamplePointLocationFromSphericalAnnulus(FVector PointToBeAround, int Radius, const TArray<FVector>& ActiveGrid, const FIntVector& BackgroundGridQuadrantDimensions)
	{
		float ρ = FMath::RandRange((float)Radius, (float)2.0f * Radius), Cosθ = FMath::RandRange(0.0f, 1.0f), Φ = FMath::RandRange(0.0f, HALF_PI);

		FVector Sample = FVector(ρ * FMath::Sqrt(FMath::Square(1 - Cosθ)) * FMath::Cos(Φ), ρ * Cosθ, ρ * FMath::Sqrt(FMath::Square(1 - Cosθ)) * FMath::Sin(Φ)) + PointToBeAround;

		if (bToggleLogTemp)
			UE_LOG(LogTemp, Display,
				TEXT("\nρ: %f\ncos(θ): %f\nΦ: %f\nSample: %s"),
				ρ, Cosθ, Φ, *Sample.ToString());

		if (ActiveGrid.Contains(Sample))
			return CalculateSamplePointLocationFromSphericalAnnulus(PointToBeAround, Radius, ActiveGrid, BackgroundGridQuadrantDimensions);

		return Sample;
	}

	// ((X • Y • Z) - 1) = (X + WIDTH • (Y + DEPTH • Z)) → (119 + 120  • (149 + 150  • 99))
	int Flatten3DArrayIndexTo1DIndex(FIntVector ArrayIndex3D, FIntVector BackgroundGridDimensions, const int& BackgroundGridQuadrantMaxIndex)
	{
		int Result = ArrayIndex3D.X + BackgroundGridDimensions.X * (ArrayIndex3D.Y + BackgroundGridDimensions.Y * ArrayIndex3D.Z);

		if (bToggleLogTemp)
			UE_LOG(LogTemp, Display,
				TEXT("\nFlatten 3D Array Index To 1D Index: \n%s, %s\n%d + %d * (%d + %d * %d) = %d\n"),
				*ArrayIndex3D.ToString(), *BackgroundGridDimensions.ToString(), ArrayIndex3D.X, BackgroundGridDimensions.X, ArrayIndex3D.Y, BackgroundGridDimensions.Y, ArrayIndex3D.Z,
				Result);

		return Result;
	}

	uint8 IsSampleValid(const FVector& Sample, const FIntVector& BackgroundGridDimensions)
	{
		return (Sample.X >= 0 && Sample.X < BackgroundGridDimensions.X) && (Sample.Y >= 0 && Sample.Y < BackgroundGridDimensions.Y) && (Sample.Z >= 0 && Sample.Z < BackgroundGridDimensions.Z);
	}

	uint8 SearchingForNeighbour(const TMap<uint32, FVector>& BackgroundGrid, int NeighbourIndex, FVector& Sample, const int& Radius)
	{
		if (!BackgroundGrid.Contains(NeighbourIndex))
			return false;

		return FVector::Distance(Sample, BackgroundGrid.FindRef(NeighbourIndex)) > Radius;
	}

	uint8 DoesNeighbourExist(const TMap<uint32, FVector>& BackgroundGridQuadrant, const FIntVector& BackgroundGridQuadrantDimensions, const int& BackgroundGridQuadrantMaxIndex, FIntVector& MinPossibleNeighbourLeftOfSample, FIntVector& MaxPossibleNeighbourRightOfSample, FVector& Sample, const int& SampleCellIndex, const int& Radius, const float& CellSize)
	{
		int
			MinNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MinPossibleNeighbourLeftOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex),
			MaxNeighbourIndex = Flatten3DArrayIndexTo1DIndex(MaxPossibleNeighbourRightOfSample, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);

		if (bToggleLogTemp)
			UE_LOG(LogTemp, Display,
				TEXT("\nMin neighbour index: %d\nMax neighbour index: %d\nMin neighbour search amount: %d\nMax neighbour search amount: %d\n"),
				MinNeighbourIndex, MaxNeighbourIndex, SampleCellIndex - MinNeighbourIndex, MaxNeighbourIndex - SampleCellIndex);

		for (int I = MinNeighbourIndex; I < SampleCellIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;

		for (int I = SampleCellIndex + 1; I <= MaxNeighbourIndex; I++)
			if (SearchingForNeighbour(BackgroundGridQuadrant, I, Sample, Radius))
				return true;
		return false;
	}

	void BridsonsAlgorithm(TSet<FVector>& PreGeneratedQuadrants, const FIntVector& BackgroundGridQuadrantDimensions = FIntVector(5000, 5000, 5000), const int& MaxNumOfPoints = 1000, const int& NumberOfAttemptsBeforeRejection = 30, const int& Radius = 25)
	{
		double StartPlatformTimeSeconds = FPlatformTime::Seconds();

		// Step 0. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r / √n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple ndimensional array of integers : the default −1 indicates no sample, a non - negative integer gives the index of the sample located in a cell.
		// Using an array gives the issue where too much is iniitialised past the max size of what TArray can hold.
		TMap<uint32, FVector> BackgroundGridQuadrant;
		
		// Can't exceed value an int can hold otherwise it'll loop back on itself and become negative. 10000 * 10000 * 10000 is way too big.
		int BackgroundGridQuadrantMaxIndex = BackgroundGridQuadrantDimensions.X * BackgroundGridQuadrantDimensions.Y * BackgroundGridQuadrantDimensions.Z - 1;

		float CellSize = Radius / FMath::Sqrt(3);

		// Step 1: Select the initial sample,  X₀, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list”(an array of sample indices) with this index(zero). 
		FVector X₀ = FVector(FMath::RandHelper(BackgroundGridQuadrantDimensions.X), FMath::RandHelper(BackgroundGridQuadrantDimensions.Y), FMath::RandHelper(BackgroundGridQuadrantDimensions.Z));

		FIntVector ActiveGridDimensions = FIntVector(FMath::RoundToInt(X₀.X / CellSize), FMath::RoundToInt(X₀.Y / CellSize), FMath::RoundToInt(X₀.Z / CellSize));
		int ActiveGridIndex = Flatten3DArrayIndexTo1DIndex(ActiveGridDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);
		BackgroundGridQuadrant.Emplace(ActiveGridIndex, X₀);

		TArray<FVector>ActiveGrid = TArray<FVector>{ X₀ };

		TSet<FVector> Points;

		// Step 2. While the active list is not empty. Why does it run even if ActiveGrid is empty.
		while (!ActiveGrid.IsEmpty()) {
			// Prevent running out of memory error. Possible for it to continue forever.
			if (Points.Num() >= MaxNumOfPoints)
				break;

			uint8 IsSampleAccepted = false;

			int Index = FMath::RandHelper(ActiveGrid.Num() - 1);
			FVector Xᵢ = FVector(ActiveGrid[Index]);

			for (int I = 0; I < NumberOfAttemptsBeforeRejection; I++) {
				// Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around Xᵢ. This could actually end up just being where the player is. Problem, ActiveGrid could be empty and it still continue.
				FVector Sample = CalculateSamplePointLocationFromSphericalAnnulus(Xᵢ, Radius, ActiveGrid, BackgroundGridQuadrantDimensions);

				if (!IsSampleValid(Sample, BackgroundGridQuadrantDimensions))
					continue;
				
				// Clamps the neighbours to make the check for neighbours faster. No point if you know the neighbours are too big or too small.
				FIntVector
					SampleCellDimensions = FIntVector(FMath::RoundToInt(Sample.X / CellSize), FMath::RoundToInt(Sample.Y / CellSize), FMath::RoundToInt(Sample.Z / CellSize)),
					MaxPossibleNeighbourLeftOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z - Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z)),
					MaxPossibleNeighbourRightOfSample = FIntVector(FMath::Clamp(FMath::RoundToInt((Sample.X + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.X), FMath::Clamp(FMath::RoundToInt((Sample.Y + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Y), FMath::Clamp(FMath::RoundToInt((Sample.Z + Radius) / CellSize), 0, BackgroundGridQuadrantDimensions.Z));

				int SampleCellIndex = Flatten3DArrayIndexTo1DIndex(SampleCellDimensions, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex);

				if (bToggleLogTemp)
					UE_LOG(LogTemp, Display,
						TEXT("\nActive Grid - Number of elements: %d\nIndex: %d\nXᵢ: %s\nSample: %s, Sample cell dimensions: %s\nSample cell index: %d"),
						ActiveGrid.Num(), Index, *Xᵢ.ToCompactString(), *Sample.ToCompactString(), *SampleCellDimensions.ToString(), SampleCellIndex);

				if (!DoesNeighbourExist(BackgroundGridQuadrant, BackgroundGridQuadrantDimensions, BackgroundGridQuadrantMaxIndex, MaxPossibleNeighbourLeftOfSample, MaxPossibleNeighbourRightOfSample, Sample, SampleCellIndex, Radius, CellSize))
					continue;

				IsSampleAccepted = true;

				BackgroundGridQuadrant.Emplace(SampleCellIndex, Sample);
				ActiveGrid.AddUnique(Sample);

				Points.Add(Sample);

				if (bToggleLogTemp)
					UE_LOG(LogTemp, Display, TEXT("\nPoisson Disc Sampling sample location: %s\n"), *Sample.ToCompactString());

				break;
			}

			// If after k attempts no such point is found, instead remove i from the active list.
			if (!IsSampleAccepted)
				ActiveGrid.RemoveAt(Index);
		}

		// Possible to never generate any points.
		if (Points.Num() <= 0)
			BridsonsAlgorithm(PreGeneratedQuadrants, BackgroundGridQuadrantDimensions, MaxNumOfPoints, NumberOfAttemptsBeforeRejection, Radius);

		PreGeneratedQuadrants.Append(Points);

		double EndPlatformTimeSeconds = FPlatformTime::Seconds();
		UE_LOG(LogTemp, Display, TEXT("\nBridson's Algorithm (UE4 C++): %f seconds.\n"), EndPlatformTimeSeconds - StartPlatformTimeSeconds);
	}
};

I’ve found a solution for my issue.
BackgroundGridQuadrant is no longer an array. The reason why I had an array in the first place is because in the research paper,

We pick the cell size to be bounded by r/√n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default −1 indicates no sample, a non-negative integer gives the index of the sample located in a cell.

however that caused two issues, I could’ve populated TArray so much that it would’ve exceeded the size. Seconds, I’d also have to check to make sure that the neighbour cells I’m checking for, MinNeighbourIndex and MaxNeighbourIndex isn’t too big or too small, causing the index out of bounds error.

Unless there is a different way of doing this, I do need to have indices though because I’m flattening an FVector into 1 value. If I had an FVector I’m pretty sure I’d have to do inner for loops to check for neighbours and I think that would’ve been slower. With maps though, I could still fulfill this check:

For each point in turn, check if it is within distance r of existing samples (using the background grid to only test nearby samples).

as long as the nearby sample exists, then it should be fine and that’s the point of the check. I wouldn’t be surprised if there’s a way to bypass using indices though, maybe bits like in bitboards but I’ve never used that before and don’t know.

Moving the code I did out of the NumberOfAttemptsBeforeRejection loop was meant to stop the fact that ActiveGrid could be empty, but the loop still ran and therefore created an index out of bounds issue.

What 3dRaven said was right, shouldn’t have used ActiveGridMaxIndex, but I still had other index going out of bounds issues.

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.