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