Faster Poisson Disk Sampling
Two divide-and-conquer enhancements to Robert Bridson’s algorithm.
Background
A simple and reasonably fast algorithm for generating the Poisson Disk sampling pattern is Robert Bridson’s O(n) algorithm. Building on top of this, I will discuss two ways to use threads to speed-up the algorithm so we can generate more points in the same amount of time. Both approaches are simple to implement and quite fast with visually indistinguishable results.
Before going any further, I highly recommend checking out Robert Bridson’s algorithm to understand how that works. Here is an animation of the original algorithm in action:
All white and red points are samples that have been generated thus far. But the red points are part of the active list. The yellow border is the specified bounds.
Looking at the animated preview of the algorithm above one can think of using multiple threads to fill up separate areas. And that is exactly what the first approach does.
Approach 1 — Buckets
In this approach, we split the whole area into equal-sized buckets with their own hash-grid. We run the algorithm in each bucket on a separate thread. Points very close to the edges of each bucket may have to be checked for intersection against points in another bucket, and that would cause contention between threads. We can easily eliminate this contention by adding some padding to each bucket. And this is what we get:
Next, neighboring buckets and their hash-grids are merged into a new bucket. Note the gap due to the padding we added. We can fill this gap with more points. To do this we add samples close to the merged border to the new active-list (red points):
We then run the algorithm in each bucket again, merge buckets again, and generate again. We repeat these phases until we are left with only one area, which is the original area that we split:
Note again that in each step the buckets are filled on separate threads. So initially 4-by-4 = 16 buckets would be filled, and then 8, and then 4 and so on till we are left with only one. The last bucket is completed on the main thread. And this gives us a speedup of about 4 times as illustrated in the graph below:
Approach 2 — Tiles
A further speed-up can be achieved by pre-generating a few tiles that we stamp into the buckets in the first step. This speeds up the initial split-and-generate phase.
Once we stamp the tiles we just let the process run like the Bucket Approach, merge-generate, again and again.
The performance characteristics of this approach depend on a lot more factors now though. Like the size and number of unique tiles. When tile size is small a lot of time is spent merging them. But as tile sizes get larger, more time is spent in creating them. Some trial and error turns-up a tile-size of 32 and 4 unique tiles resulting in the best performance. And seems to hold for a total area of both 256-by-256 and 512-by-512 according to my experiments.
You can compare the final result of the two approaches in the image below. We can see that there is a difference in the number of points. And that’s to be expected since the initial seeding phase itself would have distributed the points in the buckets differently.
Now a performance comparison with the other two methods, the tiled approach is up to four times as fast as the Bucket approach:
Conclusion
The tiled approach seems pretty adequate for generating a lot of Poisson disk sampling points. On visual inspection, the tiled approach looks great. Some repetition can be noticed if we pay close attention. We can add some more randomness by rotating and/or flipping the tiles at the cost of slightly higher overhead in the stamping stage.
Additional Notes
This algorithm was written in C# to work with the Unity game engine. All illustrations were made from within the Unity game engine.
