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.