This article originally appeared in Dev.Mag Issue 21, released in March 2008

One way to populate large worlds with objects is to simply place objects on a grid, or randomly. While fast and easy to implement, both these methods result in unsatisfying worlds: either too regular or too messy. In this article we look at an alternative algorithm that returns a random set of points with nice properties:

• the points are tightly packed together; but
  
• no closer to each other than a specified minimum distance.

Figure 1 shows an example of such a set, which is called Poisson-disk sample set. For comparison, two other sample sets are also shown: a uniform random sample, and a jittered grid sample.

Poisson disk sampling has many applications in games:

• random object placement;
  
• sampling for graphics applications;
  
• procedural texture algorithms; and
  
• mesh algorithms.

In this article we will look mostly at object placement and briefly at texture generation.

Figure 1

Implementation

There are several algorithms for producing a Poisson disk sample set. The one presented here is easy to implement, and runs reasonably fast. It is also easy adapted for specific applications (described in the next section).

The basic idea is to generate points around existing points, and to check whether they can be added so that they don't disturb the minimum distance requirement. A grid is used to perform fast lookups of points. Two lists keep track of points that are being generated, and those that needs processing.

Here are the details:

1. A grid is created such that every cell will contain at most one sampling point. If points are at least distance r from each other, then the cell size must be r/√2.
   
2. The first point is randomly chosen, and put in the output list, processing list and grid.
   
3. Until the processing list is empty, do the following:
   
   1. Choose a random point from the processing list.
      
   2. For this point, generate up to k points, randomly selected from the annulus surrounding the point. You can choose k - a value of 30 gives good results. In general, larger values give tighter packings, but make the algorithm run slower. For every generated point:
      
      1. Use the grid to check for points that are too close to this point. See below for more detail.
         
      2. If there is none, add the point to the output list, processing list, and grid.
   3. Remove the point from the processing list.
4. Return the output list as the sample points.