I am attempting to implement Poisson disc sampling using the Jobs system. The original single thread algorithm returns a variable number of points as a List.
So I figured in order to run this in parallel, I would split the world into many smaller regions, use an IJobParallelFor to process each region independently, each generating a NativeList which I can merge once the job is finished.
But the following would not work because you cannot create nested NativeContainers.
public struct ArrayOfListsJob : IJobParallelFor
{
public NativeArray<NativeList<Vector2>> arrayOfLists;
public void Execute(int index)
{
var list = arrayOfLists[index];
list.Add(some vector2);
list.Add(some vector2);
list.Add(some vector2);
...
list.Add(some vector2);
}
}
Alternative 1:
Flatten the results into a single NativeArray and have threads writing to different parts of the array. I have not tried this yet, since this would involve setting a hard limit to how many points can be generated by the algorithm.
Alternative 2:
Schedule an IJob for each region, where each job would have its own NativeList, and in the main thread wait for all jobs to finish and combine the results.
private void Start()
{
int n = 16;
NativeList<Vector2>[] arrayOfLists = new NativeList<Vector2>[n];
JobHandle[] jobHandles = new JobHandle[n];
// Schedule a bunch of jobs and allocate one NativeList for each job.
for (int i = 0; i < n; i++)
{
NativeList<Vector2> list = new NativeList<Vector2>(Allocator.TempJob);
arrayOfLists[i] = list;
var job = new ListJob() { list = list };
jobHandles[i] = job.Schedule();
}
// Wait for all jobs to finish
for (int i = 0; i < n; i++)
{
jobHandles[i].Complete();
}
// Combine results and discard native containers.
var results = new List<Vector2>();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < arrayOfLists[i].Length; j++)
{
results.Add(arrayOfLists[i][j]);
}
arrayOfLists[i].Dispose();
}
}
I am wandering if there is a preferred way to do something like this? Are there any hidden issues with the seconds solution?
You can create a NativeArray and JobHandle.Complete() which takes a NativeArray exists and is faster.
Does results have to be a List? Could an array work? Could a NativeList or NativeArray work? Does it just need to be enumerable?
You may consider using NativeStream instead, which allows you to create and populate multiple streams in an IJobParallelFor using a single container and has a useful method for converting that data into a NativeArray.
For Poisson Disc Sampling you need read-write access of the region’s samples to calculate the sample distances right?
I have made a working parallel poisson disc sampling before with IJobParallelFor and I’m using NativeStream to write the final result in a parallel way. However I allocate a new NativeList<float2> inside the jobs for local checking, i.e. measuring distance between samples within one region. So every time I made a new sample, I add the sample to the local list and write to the stream at the same time.
Oh yeah, since the local list is only used within one job and I use stream to write, I allocate the list inside the job with Temp allocation. I don’t know if it’s only my machine but using Temp allocation is significantly faster than TempJob when a reallocation happens (which happens quite often in a growing NativeList like in this scenario).
Here’s what I’ve come up with so far in case anyone finds this helpful. A rectagular region is subdivided into smaller ones and a job is scheduled for each subregion. Each job generates results as a NativeList<float2> which are then combined. A final pass is done over the whole region to fill in the gaps between subregions.
[BurstCompile]
public struct PoissonDiscJob : IJob
{
public Random random;
public float radius;
public float sqrRadius;
public float2 regionOrigin;
public float2 regionSize;
public int maxIter;
/// <summary>
/// List of valid points
/// </summary>
public NativeList<float2> points;
/// <summary>
/// List of points to use as spawn positions for new points.
/// </summary>
private NativeList<float2> activePoints;
/// <summary>
/// Flattened array representing all cells.
/// Each cells stores the 1-based index of the point in the "points" list.
/// 0 represents empty cell.
/// </summary>
[DeallocateOnJobCompletion]
public NativeArray<int> grid;
public int2 numCells;
public float cellSize;
public void Execute()
{
Sample();
}
private void Sample()
{
// The initial spawn point can be chosen randomly
activePoints = new NativeList<float2>(numCells.x * numCells.y, Allocator.Temp)
{
regionOrigin + regionSize / 2
};
// For each spawn point, try to generate one valid point around it (distance [radius, 2*radius])
// If such a point cannot be found, remove the spawn point.
// Repeat until no spawn points are left.
while (activePoints.Length > 0)
{
// On each iteration, choose a random spawn point.
int iSpawnPoint = random.NextInt(activePoints.Length);
float2 spawnCenter = activePoints[iSpawnPoint];
bool foundValidPoint = false;
// Limit the number of attempts to find a valid point
for (int i = 0; i < maxIter; i++)
{
float2 dir = random.NextFloat2Direction();
float2 point = spawnCenter + dir * random.NextFloat(radius, 2 * radius);
int2 cell = PointToCell(point, cellSize);
// Exit as soon as a valid point is found.
// The new point is added to the spawnPoints list.
if (IsValid(point, cell))
{
points.Add(point);
activePoints.Add(point);
grid[cell.x + cell.y * numCells.x] = points.Length;
foundValidPoint = true;
break;
}
}
// Remove the spawn point if no valid points were generated.
if (!foundValidPoint)
activePoints.RemoveAt(iSpawnPoint);
}
activePoints.Dispose();
}
private int2 PointToCell(float2 point, float2 cellSize)
{
return (int2)((point - regionOrigin) / cellSize);
}
/// <summary>
/// Check if a candidate point is valid.
/// Must be inside the sampling region, and does not overlap with existing points.
/// </summary>
/// <param name="point"></param>
/// <param name="cell"></param>
/// <returns></returns>
private bool IsValid(float2 point, int2 cell)
{
// Must be in sample region
float2 localPoint = point - regionOrigin;
if (localPoint.x < 0 || localPoint.x >= regionSize.x || localPoint.y < 0 || localPoint.y >= regionSize.y)
return false;
// Get the grid boundaries where there might be overlapping points.
int xMin = math.max(0, cell.x - 2);
int xMax = math.min(cell.x + 2, numCells.x - 1);
int yMin = math.max(0, cell.y - 2);
int yMax = math.min(cell.y + 2, numCells.y - 1);
// Search the 5x5 grid for overlapping points.
for (int x = xMin; x <= xMax; x++)
{
for (int y = yMin; y <= yMax; y++)
{
int iPoint = grid[x + numCells.x * y] - 1;
if (iPoint >= 0)
{
if (math.lengthsq(point - points[iPoint]) < sqrRadius)
return false;
}
}
}
return true;
}
}
Scheduling Jobs
public static class PoissonDisc
{
/// <summary>
///
/// </summary>
/// <param name="radius"></param>
/// <param name="region"></param>
/// <param name="maxIterations"></param>
/// <param name="seed"></param>
/// <param name="subdivisions">Must be a power of two.</param>
/// <returns></returns>
public static float2[] Sample(float radius, Region region, int maxIterations = 30, uint seed = 1, int subdivisions = 4)
{
Debug.Assert(Mathf.IsPowerOfTwo(subdivisions), $"Subdivisions ({subdivisions}) must be a power of two.");
float sqrRadius = radius * radius;
float cellSize = radius / math.SQRT2;
Region[] subregions = region.Subdivide(subdivisions, 4*cellSize);
var jobHandles = new NativeArray<JobHandle>(subregions.Length, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
var points = new NativeList<float2>[subregions.Length];
var grid = new NativeArray<int>[subregions.Length];
int numPoints = 0;
for (int i = 0; i < subregions.Length; i++)
{
seed += (uint)i * 17;
Region subregion = subregions[i];
int2 numCells = (int2)math.ceil(new float2(subregions[0].w, subregions[0].h) / cellSize);
points[i] = new NativeList<float2>(numCells.x * numCells.y, Allocator.TempJob);
grid[i] = new NativeArray<int>(numCells.x * numCells.y, Allocator.TempJob, NativeArrayOptions.ClearMemory);
var job = new PoissonDiscJob
{
radius = radius,
sqrRadius = sqrRadius,
regionOrigin = subregion.origin,
regionSize = subregion.size,
cellSize = cellSize,
numCells = numCells,
maxIter = maxIterations,
points = points[i],
grid = grid[i],
random = new Random(seed),
};
jobHandles[i] = job.Schedule();
}
// Wait for all jobs to complete
JobHandle.CompleteAll(jobHandles);
jobHandles.Dispose();
// If no subdivision
float2[] results;
if (subdivisions <= 1)
{
results = points[0].ToArray();
points[0].Dispose();
return results;
}
// If subdivisions, results need to be combined for a final pass
for (int i = 0; i < subregions.Length; i++)
{
numPoints += points[i].Length;
}
// Combine points arrays
var combinedPoints = new NativeList<float2>(numPoints, Allocator.TempJob);
int iPoint = 0;
for (int i = 0; i < subregions.Length; i++)
{
// Combine points
combinedPoints.AddRangeNoResize(points[i]);
iPoint += points[i].Length;
points[i].Dispose();
}
// Regenerate grid
NativeArray<int> combinedGrid = RegenerateGrid(combinedPoints, region, cellSize, out int2 numCellsCombined);
// Final pass to fill in the gaps
var finalJob = new PoissonDiscJob
{
radius = radius,
sqrRadius = sqrRadius,
regionOrigin = region.origin,
regionSize = region.size,
cellSize = cellSize,
numCells = numCellsCombined,
maxIter = maxIterations,
points = combinedPoints,
grid = combinedGrid,
random = new Random(seed),
};
var jobHandle = finalJob.Schedule();
jobHandle.Complete();
results = combinedPoints.ToArray();
combinedPoints.Dispose();
return results;
}
private static NativeArray<int> RegenerateGrid(NativeList<float2> points, Region region, float cellSize, out int2 numCells)
{
numCells = (int2)math.ceil(region.size / cellSize);
NativeArray<int> grid = new NativeArray<int>(numCells.x * numCells.y, Allocator.TempJob, NativeArrayOptions.ClearMemory);
for (int i = 0; i < points.Length; i++)
{
float2 p = points[i];
int2 cell = (int2)((p - (float2)region.origin) / cellSize);
grid[cell.x + cell.y * numCells.x] = i + 1;
}
return grid;
}
}