Question Using IJobParallelFor to populate a bunch of NativeLists in parallel?

Hi Unity Forum,

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<Vector2>.

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<Vector2> which I can merge once the job is finished.


But the following would not work because you cannot create nested NativeContainers.

Code (CSharp):

1. public struct ArrayOfListsJob : IJobParallelFor
2. {
3.     public NativeArray<NativeList<Vector2>> arrayOfLists;
4.     public void Execute(int index)
5.     {
6.         var list = arrayOfLists[index];
7.         list.Add(some vector2);
8.         list.Add(some vector2);
9.         list.Add(some vector2);
10.         ...
11.         list.Add(some vector2);
12.     }
13. }

Alternative 1:

Flatten the results into a single NativeArray<Vector2> 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<Vector2>, and in the main thread wait for all jobs to finish and combine the results.

Code (CSharp):

1.  
2. private void Start()
3. {
4.         int n = 16;
5.  
6.         NativeList<Vector2>[] arrayOfLists = new NativeList<Vector2>[n];
7.         JobHandle[] jobHandles = new JobHandle[n];
8.  
9.         // Schedule a bunch of jobs and allocate one NativeList for each job.
10.         for (int i = 0; i < n; i++)
11.         {
12.             NativeList<Vector2> list = new NativeList<Vector2>(Allocator.TempJob);
13.             arrayOfLists[i] = list;
14.  
15.             var job = new ListJob() { list = list };
16.             jobHandles[i] = job.Schedule();
17.         }
18.  
19.         // Wait for all jobs to finish
20.         for (int i = 0; i < n; i++)
21.         {
22.             jobHandles[i].Complete();
23.         }
24.  
25.         // Combine results and discard native containers.
26.         var results = new List<Vector2>();
27.         for (int i = 0; i < n; i++)
28.         {
29.             for (int j = 0; j < arrayOfLists[i].Length; j++)
30.             {
31.                 results.Add(arrayOfLists[i][j]);
32.             }
33.             arrayOfLists[i].Dispose();
34.         }
35. }

I am wandering if there is a preferred way to do something like this? Are there any hidden issues with the seconds solution?

Thanks!.

 

A few tips:
1) You can create a NativeArray<JobHandle> and JobHandle.Complete() which takes a NativeArray<JobHandle> exists and is faster.
2) Does results have to be a List? Could an array work? Could a NativeList or NativeArray work? Does it just need to be enumerable?
3) 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.

 

Thank you! This is good to know.

Oh yeah a List is unnecessary for "results". I think I will end up using a regular C# array to write to "terrainData.treeInstances".

I did not know this existed but it sounds promising. I will check it out.

Thanks a bunch!

 

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).

 

If it's not too much trouble would you mind sharing your code for this? I cannot seem to find any good examples on how to use NativeStream.

Thanks!

 

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.

This was based on Sebastian Lague's (https://github.com/SebLague/Poisson-Disc-Sampling) and Basudev Patel's (https://medium.com/@1basudevpatel/faster-poisson-sampling-a76cb9a99825) tutorials.

Code:

Spoiler: Job

Code (CSharp):

1. [BurstCompile]
2. public struct PoissonDiscJob : IJob
3. {
4.     public Random random;
5.  
6.     public float radius;
7.     public float sqrRadius;
8.  
9.     public float2 regionOrigin;
10.  
11.     public float2 regionSize;
12.  
13.     public int maxIter;
14.  
15.     /// <summary>
16.     /// List of valid points
17.     /// </summary>
18.     public NativeList<float2> points;
19.  
20.     /// <summary>
21.     /// List of points to use as spawn positions for new points.
22.     /// </summary>
23.     private NativeList<float2> activePoints;
24.  
25.     /// <summary>
26.     /// Flattened array representing all cells.
27.     /// Each cells stores the 1-based index of the point in the "points" list.
28.     /// 0 represents empty cell.
29.     /// </summary>
30.     [DeallocateOnJobCompletion]
31.     public NativeArray<int> grid;
32.    
33.     public int2 numCells;
34.  
35.     public float cellSize;
36.  
37.     public void Execute()
38.     {
39.         Sample();
40.     }
41.  
42.     private void Sample()
43.     {
44.         // The initial spawn point can be chosen randomly
45.         activePoints = new NativeList<float2>(numCells.x * numCells.y, Allocator.Temp)
46.         {
47.             regionOrigin + regionSize / 2
48.         };
49.  
50.         // For each spawn point, try to generate one valid point around it (distance [radius, 2*radius])
51.         // If such a point cannot be found, remove the spawn point.
52.         // Repeat until no spawn points are left.
53.         while (activePoints.Length > 0)
54.         {
55.             // On each iteration, choose a random spawn point.
56.             int iSpawnPoint = random.NextInt(activePoints.Length);
57.  
58.             float2 spawnCenter = activePoints[iSpawnPoint];
59.  
60.             bool foundValidPoint = false;
61.  
62.             // Limit the number of attempts to find a valid point
63.             for (int i = 0; i < maxIter; i++)
64.             {
65.                 float2 dir = random.NextFloat2Direction();
66.                 float2 point = spawnCenter + dir * random.NextFloat(radius, 2 * radius);
67.                 int2 cell = PointToCell(point, cellSize);
68.  
69.                 // Exit as soon as a valid point is found.
70.                 // The new point is added to the spawnPoints list.
71.                 if (IsValid(point, cell))
72.                 {
73.                     points.Add(point);
74.                     activePoints.Add(point);
75.                     grid[cell.x + cell.y * numCells.x] = points.Length;
76.                     foundValidPoint = true;
77.                     break;
78.                 }
79.             }
80.  
81.             // Remove the spawn point if no valid points were generated.
82.             if (!foundValidPoint)
83.                 activePoints.RemoveAt(iSpawnPoint);
84.         }
85.  
86.         activePoints.Dispose();
87.     }
88.  
89.     private int2 PointToCell(float2 point, float2 cellSize)
90.     {
91.         return (int2)((point - regionOrigin) / cellSize);
92.     }
93.  
94.     /// <summary>
95.     /// Check if a candidate point is valid.
96.     /// Must be inside the sampling region, and does not overlap with existing points.
97.     /// </summary>
98.     /// <param name="point"></param>
99.     /// <param name="cell"></param>
100.     /// <returns></returns>
101.     private bool IsValid(float2 point, int2 cell)
102.     {
103.         // Must be in sample region
104.         float2 localPoint = point - regionOrigin;
105.         if (localPoint.x < 0 || localPoint.x >= regionSize.x || localPoint.y < 0 || localPoint.y >= regionSize.y)
106.             return false;
107.        
108.         // Get the grid boundaries where there might be overlapping points.
109.         int xMin = math.max(0, cell.x - 2);
110.         int xMax = math.min(cell.x + 2, numCells.x - 1);
111.         int yMin = math.max(0, cell.y - 2);
112.         int yMax = math.min(cell.y + 2, numCells.y - 1);
113.  
114.         // Search the 5x5 grid for overlapping points.
115.         for (int x = xMin; x <= xMax; x++)
116.         {
117.             for (int y = yMin; y <= yMax; y++)
118.             {
119.                 int iPoint = grid[x + numCells.x * y] - 1;
120.                 if (iPoint >= 0)
121.                 {
122.                     if (math.lengthsq(point - points[iPoint]) < sqrRadius)
123.                         return false;
124.                 }
125.             }
126.         }
127.         return true;
128.     }
129. }

Spoiler: Scheduling Jobs

Code (CSharp):

1. public static class PoissonDisc
2. {
3.     /// <summary>
4.     ///
5.     /// </summary>
6.     /// <param name="radius"></param>
7.     /// <param name="region"></param>
8.     /// <param name="maxIterations"></param>
9.     /// <param name="seed"></param>
10.     /// <param name="subdivisions">Must be a power of two.</param>
11.     /// <returns></returns>
12.     public static float2[] Sample(float radius, Region region, int maxIterations = 30, uint seed = 1, int subdivisions = 4)
13.     {
14.         Debug.Assert(Mathf.IsPowerOfTwo(subdivisions), $"Subdivisions ({subdivisions}) must be a power of two.");
15.  
16.         float sqrRadius = radius * radius;
17.         float cellSize = radius / math.SQRT2;
18.  
19.         Region[] subregions = region.Subdivide(subdivisions, 4*cellSize);
20.         var jobHandles = new NativeArray<JobHandle>(subregions.Length, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
21.         var points = new NativeList<float2>[subregions.Length];
22.         var grid = new NativeArray<int>[subregions.Length];
23.         int numPoints = 0;
24.  
25.         for (int i = 0; i < subregions.Length; i++)
26.         {
27.             seed += (uint)i * 17;
28.             Region subregion = subregions[i];
29.             int2 numCells = (int2)math.ceil(new float2(subregions[0].w, subregions[0].h) / cellSize);
30.  
31.             points[i] = new NativeList<float2>(numCells.x * numCells.y, Allocator.TempJob);
32.             grid[i] = new NativeArray<int>(numCells.x * numCells.y, Allocator.TempJob, NativeArrayOptions.ClearMemory);
33.  
34.             var job = new PoissonDiscJob
35.             {
36.                 radius = radius,
37.                 sqrRadius = sqrRadius,
38.                 regionOrigin = subregion.origin,
39.                 regionSize = subregion.size,
40.                 cellSize = cellSize,
41.                 numCells = numCells,
42.                 maxIter = maxIterations,
43.  
44.                 points = points[i],
45.                 grid = grid[i],
46.                 random = new Random(seed),
47.             };
48.  
49.             jobHandles[i] = job.Schedule();
50.         }
51.  
52.         // Wait for all jobs to complete
53.         JobHandle.CompleteAll(jobHandles);
54.         jobHandles.Dispose();
55.  
56.         // If no subdivision
57.         float2[] results;
58.         if (subdivisions <= 1)
59.         {
60.             results = points[0].ToArray();
61.             points[0].Dispose();
62.             return results;
63.         }
64.  
65.         // If subdivisions, results need to be combined for a final pass
66.         for (int i = 0; i < subregions.Length; i++)
67.         {
68.             numPoints += points[i].Length;
69.         }
70.  
71.         // Combine points arrays
72.         var combinedPoints = new NativeList<float2>(numPoints, Allocator.TempJob);
73.         int iPoint = 0;
74.  
75.         for (int i = 0; i < subregions.Length; i++)
76.         {
77.             // Combine points
78.             combinedPoints.AddRangeNoResize(points[i]);
79.             iPoint += points[i].Length;
80.  
81.             points[i].Dispose();
82.         }
83.  
84.         // Regenerate grid
85.         NativeArray<int> combinedGrid = RegenerateGrid(combinedPoints, region, cellSize, out int2 numCellsCombined);
86.  
87.         // Final pass to fill in the gaps
88.         var finalJob = new PoissonDiscJob
89.         {
90.             radius = radius,
91.             sqrRadius = sqrRadius,
92.             regionOrigin = region.origin,
93.             regionSize = region.size,
94.             cellSize = cellSize,
95.             numCells = numCellsCombined,
96.             maxIter = maxIterations,
97.  
98.             points = combinedPoints,
99.             grid = combinedGrid,
100.             random = new Random(seed),
101.         };
102.  
103.         var jobHandle = finalJob.Schedule();
104.         jobHandle.Complete();
105.  
106.         results = combinedPoints.ToArray();
107.  
108.         combinedPoints.Dispose();
109.  
110.         return results;
111.     }
112.  
113.     private static NativeArray<int> RegenerateGrid(NativeList<float2> points, Region region, float cellSize, out int2 numCells)
114.     {
115.         numCells = (int2)math.ceil(region.size / cellSize);
116.  
117.         NativeArray<int> grid = new NativeArray<int>(numCells.x * numCells.y, Allocator.TempJob, NativeArrayOptions.ClearMemory);
118.  
119.         for (int i = 0; i < points.Length; i++)
120.         {
121.             float2 p = points[i];
122.             int2 cell = (int2)((p - (float2)region.origin) / cellSize);
123.             grid[cell.x + cell.y * numCells.x] = i + 1;
124.         }
125.  
126.         return grid;
127.     }
128. }

 

Its worth noting that for native containers instantiated inside jobs that

Temp

is indeed the recommended allocation type