Procedural Generation Techniques – Poisson-Disc Sampling

If you’re a game developer, there’s a good chance that you’ve tried generating random or procedural terrain at least once before. You start with the ground, the grassy and rocky areas, and then begin to populate your world with trees, rocks and other decorative foliage.

At first, it might seem like a good idea to simply generate a random position within some boundaries and place your object level with your terrain at a given height. For most cases where not much detail is required this will usually suffice, however this approach will likely lead to objects overlapping as well as producing overpopulated and underpopulated areas as shown below:

Random distribution of points on a plane

If you imagine the points above represent your foliage, such as trees, it’s clear that using this method will produce an unrealistic distribution and sometimes place trees within each other. They don’t do that in nature.

This is where the Poisson-Disc sampling technique comes in. We’re aiming to maintain the pseudo-randomness of the points, but enforce some rules so that each point maintains a specified minimum and maximum distance away from another given point to give a nice even and organic-looking distribution, seen below:

Poisson-Disc distribution of points on a plane

There are several methods of implementation, such as Bridson’s Poisson-Disc or Mitchell’s best-candidate algorithm but they all essentially perform this same task.

It works by generating points in a radius around existing points, after checking that the distance requirements are met. You’ll need 2 lists, one to keep track of samples that are currently being generated and another for those that need processing. Then, create a grid such that each cell only contains at most 1 sampling point. If the points are going to be r distance from each other, the cell size should be r/2π.

For the first starting point, it doesn’t matter where this is, so you can generate this randomly or input the position manually. Place this first point inside the processing list, sample list and the grid. Then, while the processing list contains points, chose a random point from the processing list and generate up to k points within a sphere around it. The value for k can vary, however larger values will likely slow down generation time. Then, for each of the generated k points, check that there are no surrounding points that are too close, and if there are none, add the point to both lists and the grid.

Finally, remove the origin point from the processing list and return the output list as the sample points. Done! This algorithm can seem rather daunting at first, but it’s actually quite simple to implement and for more information on how to do so, check out the links below.

Further Reading:

https://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3

http://gregschlom.com/devlog/2014/06/29/Poisson-disc-sampling-Unity.html

http://devmag.org.za/2009/05/03/poisson-disk-sampling/