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