Scattering objects across a game world, whether trees in a forest or rocks on a mountainside, is one of the most common tasks in game development. A random number generator creates ugly distributions: visible clusters where objects land too close together and conspicuous voids where nothing appears. Poisson disk sampling solves this by ensuring no two points sit closer than a minimum distance, producing the irregular-but-even spacing found in tree canopies and retinal cells.
The Problem with Pure Randomness
Consider placing 200 trees across a meadow using uniform random coordinates. You might expect an even spread, but randomness does not work that way. A uniform random distribution creates noticeable clumps where several objects land near each other, alongside conspicuous voids where nothing appears at all.
This happens because each sample is independent. The random number generator has no knowledge of previously placed points, so the probability of two landing close together is higher than intuition expects, much like the birthday paradox in probability theory.
We are quick to notice clumps and gaps in a random distribution and read them as artificial, even though they are statistically inevitable. A truly random distribution looks less random to us than a controlled one.
What Is Poisson Disk Sampling?
A Poisson disk distribution satisfies one constraint: every pair of sample points must be separated by at least a minimum distance $r$. Beyond that, points are as random as possible. The result is called blue noise, a distribution whose frequency spectrum lacks low-frequency content, meaning no large-scale patterns, clumps, or voids.
The name comes from its connection to the Poisson point process in probability theory, filtered through a minimum-distance disk exclusion zone around each sample. Think of each point as surrounded by an invisible disk of radius $r$: no other point may land within that disk.
$$P(\text{accept sample } \mathbf{x}) = \begin{cases} 1 & \text{if } \|\mathbf{x} - \mathbf{s}_i\| \geq r \text{ for all existing samples } \mathbf{s}_i \\ 0 & \text{otherwise} \end{cases}$$
The result matches patterns found throughout nature: the arrangement of cone cells in the retina, the spacing of trees competing for sunlight and water.
Bridson's Algorithm
The challenge with Poisson disk sampling is efficiency. Checking every new candidate against all existing samples runs in $O(n^2)$ time, which becomes prohibitively slow for large point sets. In 2007, Robert Bridson published an $O(n)$ algorithm using a background grid to accelerate distance checks. His paper, Fast Poisson Disk Sampling in Arbitrary Dimensions, fits on a single page and is still the most widely used approach.
The Background Grid
The key insight is a spatial acceleration grid with cell size:
$$c = \frac{r}{\sqrt{d}}$$
where $r$ is the minimum distance and $d$ is the number of dimensions (2 for a 2D plane, 3 for volumetric sampling). For 2D, the cell size is $r / \sqrt{2} \approx 0.707r$.
This cell size guarantees that each grid cell contains at most one sample point. The diagonal equals $r$, so two samples in the same cell would violate the minimum distance constraint. When checking a new candidate, you only need to examine a small fixed-size neighborhood of cells, regardless of total sample count. This reduces each proximity check from $O(n)$ to $O(1)$.
The Active List
The algorithm maintains an active list, a set of samples that can still spawn new neighbors. Each active sample gets $k$ attempts (typically 30) to produce a valid neighbor. If all attempts fail, the sample is removed from the active list. When the list is empty, the domain is maximally filled.
Step-by-Step Process
Here is Bridson's algorithm in detail:
Step 1: Initialize the grid. Create a background grid with cell size $c = r/\sqrt{2}$. All cells start empty (marked with $-1$).
Step 2: Place the seed sample. Pick an initial random point within the sampling domain. Record it in the grid and add it to the active list.
Step 3: Iterate. While the active list is not empty:
- Pick a random sample $\mathbf{s}$ from the active list.
- Generate up to $k$ candidate points uniformly distributed in the annular region between distance $r$ and $2r$ from $\mathbf{s}$.
- For each candidate, check the grid neighborhood. If no existing sample is closer than $r$, accept the candidate: add it to the output, record it in the grid, and push it onto the active list.
- If none of the $k$ candidates are valid, remove $\mathbf{s}$ from the active list. It is surrounded and cannot produce more children.
Sampling the Annulus
Generating candidates within the annulus $[r, 2r]$ is straightforward. In 2D, we sample a random angle $\theta$ and a random distance $d$:
$$\theta = 2\pi \cdot \text{rand}()$$
$$d = r + r \cdot \text{rand}()$$
$$\mathbf{x}_{\text{new}} = \mathbf{s} + (d \cos\theta, \; d \sin\theta)$$
Strictly speaking, this biases toward the inner ring since smaller radii cover less area. For uniform annular sampling, use $d = \sqrt{\text{rand}() \cdot 3r^2 + r^2}$ instead. In practice, the simpler version produces visually indistinguishable results for object placement.
Neighbor Checking
For a candidate at grid coordinates $(g_i, g_j)$, we check a $5 \times 5$ neighborhood of cells centered on that position:
$$\text{for each } (c_i, c_j) \text{ where } |c_i - g_i| \leq 2 \text{ and } |c_j - g_j| \leq 2$$
If a cell contains a sample $\mathbf{s}_k$, compute the squared Euclidean distance $\|\mathbf{x}_{\text{new}} - \mathbf{s}_k\|^2$ and reject the candidate if it is less than $r^2$. Since each cell contains at most one sample, this examines at most 25 cells, a constant cost regardless of total sample count.
Implementation
Here is a JavaScript implementation of Bridson's algorithm for 2D sampling:
function poissonDiskSampling(width, height, minDist, maxAttempts = 30) {
const cellSize = minDist / Math.SQRT2;
const gridW = Math.ceil(width / cellSize);
const gridH = Math.ceil(height / cellSize);
const grid = new Array(gridW * gridH).fill(-1);
const samples = [];
const active = [];
// Seed sample at center
addSample(width / 2, height / 2);
while (active.length > 0) {
const idx = Math.floor(Math.random() * active.length);
const parent = samples[active[idx]];
let found = false;
for (let attempt = 0; attempt < maxAttempts; attempt++) {
const angle = Math.random() * Math.PI * 2;
const dist = minDist + Math.random() * minDist;
const cx = parent.x + dist * Math.cos(angle);
const cy = parent.y + dist * Math.sin(angle);
if (cx < 0 || cx >= width || cy < 0 || cy >= height) continue;
if (!isValid(cx, cy)) continue;
addSample(cx, cy);
found = true;
break;
}
if (!found) active.splice(idx, 1);
}
return samples;
function addSample(x, y) {
const i = Math.floor(x / cellSize);
const j = Math.floor(y / cellSize);
grid[j * gridW + i] = samples.length;
samples.push({ x, y });
active.push(samples.length - 1);
}
function isValid(x, y) {
const gi = Math.floor(x / cellSize);
const gj = Math.floor(y / cellSize);
for (let di = -2; di <= 2; di++) {
for (let dj = -2; dj <= 2; dj++) {
const ci = gi + di, cj = gj + dj;
if (ci < 0 || ci >= gridW || cj < 0 || cj >= gridH) continue;
const sIdx = grid[cj * gridW + ci];
if (sIdx === -1) continue;
const dx = samples[sIdx].x - x;
const dy = samples[sIdx].y - y;
if (dx * dx + dy * dy < minDist * minDist) return false;
}
}
return true;
}
}Adapting this to a game engine is straightforward. Here is the same algorithm in C# for Unity:
// Unity / C# sketch — same algorithm, typed for Vector2
List<Vector2> PoissonDisk(float width, float height, float r, int k = 30) {
float cell = r / Mathf.Sqrt(2f);
int gw = Mathf.CeilToInt(width / cell);
int gh = Mathf.CeilToInt(height / cell);
int[] grid = new int[gw * gh];
System.Array.Fill(grid, -1);
var samples = new List<Vector2>();
var active = new List<int>();
void Add(Vector2 p) {
int i = (int)(p.x / cell), j = (int)(p.y / cell);
grid[j * gw + i] = samples.Count;
samples.Add(p);
active.Add(samples.Count - 1);
}
Add(new Vector2(width / 2, height / 2));
while (active.Count > 0) {
int ri = Random.Range(0, active.Count);
Vector2 parent = samples[active[ri]];
bool found = false;
for (int n = 0; n < k; n++) {
float angle = Random.value * Mathf.PI * 2;
float dist = r + Random.value * r;
Vector2 cand = parent + new Vector2(
dist * Mathf.Cos(angle), dist * Mathf.Sin(angle));
if (cand.x < 0 || cand.x >= width ||
cand.y < 0 || cand.y >= height) continue;
if (!IsValid(cand, grid, samples, gw, gh, cell, r)) continue;
Add(cand);
found = true;
break;
}
if (!found) active.RemoveAt(ri);
}
return samples;
}Real-World Game Applications
Poisson disk sampling appears throughout the game industry, often behind the scenes in tools and world-building pipelines:
Procedural Object Placement
The most widespread use is scattering objects across terrain: vegetation, rocks, buildings, debris. Games like No Man's Sky and The Witcher 3 use Poisson-like distributions to place environmental details that look hand-crafted despite being procedurally generated. Weighted variants allow denser placement in some regions, like more trees near rivers, while maintaining the no-overlap guarantee.
Texture and Material Sampling
Blue noise distributions show up in dithering, anti-aliasing, and texture synthesis. Modern rendering engines use Poisson disk patterns for shadow map filtering, ambient occlusion, and screen-space reflections. Blue noise distributes error more evenly than white noise, producing perceptually smoother results with fewer samples.
Level Generation
Roguelikes and dungeon crawlers use Poisson disk sampling to place rooms, treasure, and spawn points. The minimum spacing guarantee prevents rooms from overlapping or items from stacking, common failure modes with pure random placement. Enter the Gungeon and many roguelike generators use this technique for room seed placement.
Audio and Effects
Open-world games use Poisson distributions to space out ambient audio sources, like bird calls or water drips, so sounds spread evenly without obvious repetition or dead zones. The same logic applies to particle emitters, light probes, and reflection captures.
NPC and Enemy Spawning
Strategy games and open-world RPGs use Poisson disk sampling to distribute NPC spawn points, resource nodes, and points of interest across large maps. The even spacing means players encounter content at a consistent pace rather than hitting clusters followed by long stretches of nothing.
Variations and Extensions
Variable-Density Sampling
Instead of a constant minimum distance $r$, you can use a function $r(\mathbf{x})$ that varies across the domain. This lets you create denser distributions in some areas and sparser ones in others, useful for placing more trees in a valley and fewer on a ridge. Set the grid cell size based on the smallest value of $r$, and check the local $r$ value at each candidate position.
Multi-Class Sampling
When placing multiple types of objects (oaks, pines, bushes), each class can have its own minimum distance, and inter-class distances can differ from intra-class ones. A pine might need 3 meters from other pines but only 1.5 meters from bushes. Large objects enforce wide spacing while small ones fill the gaps.
3D and Higher Dimensions
Bridson's algorithm generalizes to arbitrary dimensions by setting the grid cell size to $r / \sqrt{d}$ and expanding the neighbor check accordingly. In 3D, this works for volumetric effects like particle clouds, star fields, or ore deposits inside a procedural asteroid.
Surface Sampling
Poisson disk sampling extends to arbitrary mesh surfaces using geodesic distances instead of Euclidean distances, letting you distribute points evenly across curved 3D surfaces. This is useful for placing foliage on terrain or generating stippling effects for non-photorealistic rendering.
Performance Considerations
Bridson's algorithm runs in $O(n)$ time where $n$ is the number of generated samples. Each sample requires a constant number of grid lookups and distance comparisons. The parameter $k$ (maximum attempts per active sample) controls the trade-off between speed and fill density. Higher $k$ values produce slightly more tightly packed distributions at the cost of more computation, but values beyond 30 rarely improve results.
For real-time applications where the sampling domain changes frequently, you can precompute Poisson disk distributions and store them as lookup tables, transforming and tiling them at runtime. Many game engines use this approach for particle emission patterns and decal placement.
Poisson disk sampling is simple to implement and immediately useful. Once you start looking for it, you will see it everywhere, from trees in an open-world game to noise patterns in a film grain shader. It produces distributions that satisfy mathematical constraints while matching how humans perceive natural spacing.
Comments