Poisson disk sampling

Poisson disk sampling places points randomly while keeping every pair at least a minimum distance apart. Robert Bridson's paper describes the target as samples "where all samples are at least distance r apart for some user-supplied density parameter r" (Columbia) 2007). In environment art it gives scattered trees a natural, even spacing instead of random clumps and gaps. Blender's scatter node offers it beside plain random as its second method: "Distribute points randomly on the surface while taking a minimum distance into account" (Blender Manual: Distribute Points on Faces Node).

For the wider scattering workflow, see procedural placement and scattering, which shows random and Poisson results side by side.

#Clumping in pure random scatter

Uniform random points ignore each other, so some land almost on top of one another and others leave holes. Dev.Mag's article on the technique, written for game developers, sums up the two naive options, grid and random: "both these methods result in unsatisfying worlds: either too regular or too messy" (Dev.Mag: Poisson Disk Sampling). Real plants, rocks and even people in a crowd space themselves out. A minimum distance gives you an even but irregular spread, with no grid pattern for the eye to catch. Use it wherever things compete for space: trees, bushes, boulders, debris, crowd spawn points.

#Bridson's algorithm

The naive approach throws random darts and rejects any that land too close, checking each against every point already placed. Bridson's 2007 algorithm avoids that with a grid and runs in linear time (Columbia) 2007). It takes three inputs: the area, the minimum distance r, and a limit k on attempts, "typically" 30 (Columbia) 2007).

1. Make a background grid with cells of size r ÷ √n (r ÷ √2 in 2D), so that "each grid cell will contain at most one sample". Checking neighbours then only means looking at a few cells (Columbia) 2007).
2. Place a first point at random and add it to an "active list" (Columbia) 2007).
3. Grow from active points. Pick a random active point and try up to k candidates in the ring between radius r and 2r around it. Keep the first candidate that is at least r from every existing point and make it active. If all k fail, remove the point from the active list (Columbia) 2007).
4. Stop when the active list is empty.

"Each iteration of step 2 takes O(k) time, and since k is held constant ... the algorithm is linear" (Columbia) 2007).

#Variations

• Different radii per asset. You can run big trees with a large r first, then bushes with a smaller r that also respect the trees.
• Variable radius from a mask. Scaling r by a density map makes forests thin out towards a clearing. The Dev.Mag article describes feeding the algorithm "a greyscale image, which is used to modulate the minimum distance between points", and notes that Perlin noise as that image gives clusters that suit fields of plants (Dev.Mag: Poisson Disk Sampling). This addresses the main objection to Poisson (see below), because it combines natural clumping with a minimum distance.
• Inside the level editor. Dev.Mag calls object placement "the simplest way to use this algorithm in games" and suggests building it into level tools, so an artist picks a region and the models to fill it with (Dev.Mag: Poisson Disk Sampling). Blender's node and engine scatter tools now offer this as a standard feature.
• On surfaces as well as planes. Blender distributes on mesh faces, and its Density can be multiplied by a vertex attribute (Blender Manual: Distribute Points on Faces Node).
• Point elimination. Blender's Poisson mode generates points internally and removes those that break Distance Min; with Distance Min at its default of zero, "none of the internally generated points are removed" and it behaves like Random (Blender Manual: Distribute Points on Faces Node).

#Common mistakes

• Minimum distance too small to matter. If r is smaller than typical random spacing, Poisson looks random.
• One radius for every asset. A 10 m oak and a 1 m fern need different spacing.
• Changing the seed late. A new seed reshuffles every point (Blender Manual: Distribute Points on Faces Node), and hand-placed fixes stop lining up.

Related: procedural placement and scattering, foliage and vegetation, instancing, procedural modeling.

#Further reading and watching