Wait, What?
Random points can be too random for graphics.
Uniform independent random sampling produces clumps and empty gaps. That is mathematically normal, but visually it often looks wrong when you are placing trees, particles, samples, sensors, stipples or procedural objects. Poisson-disk sampling imposes a minimum distance between samples so points stay irregular without collapsing into a rigid grid. Robert Bridson’s 2007 algorithm makes this practical by combining an active list with a background acceleration grid.
The result is a compact algorithm with a rich learning path: probability, geometry, spatial hashing, rejection sampling, complexity analysis, blue-noise intuition, random-number quality and multidimensional engineering.
Quick Answer
Learn Bridson through white noise versus blue-noise intuition → minimum-distance invariant → background grid cell size → initial sample → active list → annulus candidate generation → neighbour rejection → retirement → proof of bounded local checks → O(N) analysis → reproducibility and high-dimensional limits.
1. Start with the sampling contract
Given a bounded domain and minimum separation radius r, generate points so that no accepted pair is closer than r. Bridson’s method does not promise the mathematically densest possible packing, nor does it generate a deterministic lattice. It is a stochastic method designed to produce well-spaced samples efficiently.
This is distinct from ordinary random sampling, quasi-Monte Carlo sequences, clustering, nearest-neighbour search and the existing Alias Method. The canonical job here is blue-noise-style spatial sampling with a hard local exclusion radius.
2. See why dart throwing is slow
The naïve method repeatedly throws a random candidate into the entire domain and accepts it if it is at least r away from all prior samples. Early on, many candidates work. Later, most of the domain lies inside exclusion zones, so rejection becomes expensive. If each candidate is compared with every prior point, neighbour checking is also costly.
Bridson attacks both problems. It generates candidates only near existing frontier samples, and it uses a grid so each candidate checks only a bounded neighbourhood.
3. The background grid is the first key idea
In d dimensions, choose a grid cell side length no greater than:
cell_size = r / sqrt(d)The diagonal of such a cell is at most r, so two valid Poisson-disk samples cannot occupy the same cell. Therefore each grid cell needs to store at most one sample index. A new candidate can be validated by looking only at nearby cells that might contain samples within distance r.
This is the algorithm’s local-search accelerator. The grid is not the output pattern; it is an internal indexing structure that turns a global proximity question into a bounded local one.
4. The active list is the second key idea
Accepted samples are not all equally useful forever. A newly accepted point may have empty space around it where more samples can fit. Bridson therefore maintains an active list of samples that may still spawn valid neighbours.
The algorithm begins with one random seed sample. While the active list is non-empty, choose an active point and try up to k candidates around it. If a valid candidate is found, accept it and add it to the active list. If all k attempts fail, retire the active point.
5. Why candidates come from an annulus
A candidate must be at least r away from its parent sample or it would be rejected immediately. Bridson therefore samples candidates from the spherical annulus between radii r and 2r around an active sample.
In 2D, do not sample the radius uniformly from [r,2r] if you want uniform area density in the annulus. Area grows with radius. A correct method samples a random angle and chooses radius using the square root of a uniformly sampled squared radius. In d dimensions, the corresponding radial transform uses the dth root.
This distinction is an excellent professional lesson: uniform random parameters do not always produce a uniform geometric distribution.
6. Conceptual pseudocode
samples = [random_point_in_domain()]
active = [0]
insert samples[0] into background grid
while active is not empty:
i = choose_random_active_index()
base = samples[active[i]]
accepted = false
repeat up to k times:
candidate = random_point_in_annulus(base, r, 2*r)
if candidate is inside domain
and no nearby grid sample is closer than r:
samples.append(candidate)
insert candidate into grid
active.append(index_of(candidate))
accepted = true
break
if not accepted:
remove active[i]
return samples7. Work a tiny 2D example
Use a 10×10 square with r = 2. Draw the background grid with cell width r/√2. Place one seed at approximately (5,5). Generate several candidate points in the annulus from radius 2 to 4. For each candidate, mark its grid cell and inspect only nearby occupied cells. Accept one, put it on the active list, and continue.
Do this by hand for five accepted points. The aim is not to finish the domain. The aim is to make three invariants visible: accepted pairs respect the radius; each grid cell stores at most one accepted point; every active sample is either eventually productive or retired after k failures.
8. Why Bridson can be O(N)
In the original sketch, Step 2 executes exactly 2N − 1 times to produce N samples: each iteration either adds one new sample to the active list or removes one active sample. With constant k and a bounded number of nearby grid cells to inspect, each iteration performs constant expected work with respect to N. That gives O(N) generation time for fixed dimension and fixed candidate budget.
Teach the assumptions. If dimension grows, the neighbourhood size and memory requirements become difficult. Current SciPy documentation explicitly warns that Poisson-disk sampling is more suitable for low dimensions and that small radii in high-dimensional spaces can require enormous sample counts.
9. What k really controls
Bridson suggests a small constant such as k = 30. Larger k gives each active point more chances to discover remaining space, often producing denser fill at greater cost. Smaller k is faster but retires frontier points earlier and may leave more holes.
Therefore k is a quality–work trade-off, not a theorem that 30 is universally optimal. Production systems should sweep it against the actual domain, dimensionality and downstream quality metric.
10. Blue noise is more than “points not touching”
The minimum-distance rule suppresses low-frequency clumping and produces visually even but non-periodic sample patterns often associated with blue-noise spectra. This is valuable in rendering and procedural content because it avoids both the obvious regularity of a lattice and the large clusters of independent white-noise samples.
But do not use “blue noise” as a vague compliment. If spectral quality matters, measure the power spectrum, radial distribution or task-specific sampling error rather than judging only by eye.
11. Randomness quality and reproducibility
There are two different requirements that students often mix together:
- Reproducible simulation: use a documented pseudorandom generator and store the seed/state.
- Security-sensitive randomness: use a cryptographically appropriate generator; ordinary simulation PRNGs are not automatically suitable.
The Poisson-disk algorithm needs random choices, but its spatial guarantee comes from geometric rejection, not from cryptographic unpredictability.
12. Boundaries and irregular domains
For a rectangle or box, reject candidates outside the bounds. For masks, polygons, surfaces or obstacle-filled spaces, candidate validity gains another predicate. Keep that predicate separate from the minimum-distance test so failures are diagnosable.
Periodic/toroidal domains require wrapped distance checks. Surface sampling requires a notion of distance appropriate to the surface; ordinary Euclidean distance in embedding space may be wrong if geodesic separation matters.
13. Production data structures
Dense background arrays are ideal for bounded low-dimensional domains. Large sparse worlds may prefer hashed grid cells. Memory layout matters when millions of cells are empty. On accelerators, parallel candidate generation introduces conflict resolution: two threads may propose valid points that are too close to each other if checked against stale state.
That is where the learning progression reaches professional engineering. The algorithmic invariant is unchanged, but concurrency changes how acceptance is synchronized.
14. Current implementation reality
SciPy’s current scipy.stats.qmc.PoissonDisk implementation exposes the dimension, radius, candidate count, RNG and domain bounds. It also offers optional post-processing, while warning that such optimization does not necessarily preserve every property of the original sample. This is a useful distinction: generation and post-processing have different contracts.
15. How to learn it efficiently
Use a visual Predict–Run–Investigate–Modify–Make sequence. Predict whether each drawn candidate will be accepted. Run the neighbour check. Investigate which background-grid cells were consulted. Modify r or k. Finally build the sampler from scratch. This aligns with PRIMM, which begins programming instruction by reading and tracing working code before independent construction.
Label subgoals explicitly: Generate frontier candidate → Map to grid → Enumerate possible conflicting cells → Reject or accept → Update frontier → Retire exhausted source. Subgoal-labelled worked-example research in programming education reports improved problem-solving outcomes, and faded worked examples can reduce support as learners become more capable.
Common failure states
- Sampling candidates from the whole domain rather than near active points.
- Using a grid cell larger than the one-sample-per-cell bound allows.
- Checking only the candidate’s own grid cell instead of all cells that could contain a point within
r. - Sampling annulus radius uniformly and unintentionally biasing candidate density toward the inner region.
- Removing an active sample after the first failed candidate rather than after its full candidate budget.
- Assuming
k = 30is universally optimal. - Calling the result “uniform random points” without stating the minimum-distance constraint.
- Using high-dimensional Poisson-disk sampling without understanding explosive memory/sample requirements.
- Post-processing points and assuming the hard separation invariant still holds without rechecking it.
Practice ladder
- Beginner: classify candidate points as valid/invalid around five existing samples.
- Foundation: build a 2D sampler with a simple background array.
- Intermediate: derive correct annulus sampling and verify the minimum pairwise distance automatically.
- Advanced: compare
r,k, white noise, jittered grids and Poisson-disk patterns using density and spectral diagnostics. - Professional: implement sparse-domain or parallel variants, validate invariants under concurrency, and profile memory/cache behaviour as dimensionality and domain size grow.
Learning Hall boundary
This article owns Bridson-style Poisson-disk sampling with an active list and background grid. It does not replace generic random sampling, quasi-Monte Carlo, nearest-neighbour search, clustering, spatial hashing as a general data-structure topic, or cryptographic random-number generation.
Evidence and further reading
- Robert Bridson, “Fast Poisson Disk Sampling in Arbitrary Dimensions,” SIGGRAPH 2007. The paper gives the background-grid rule, active-list algorithm and O(N) analysis.
- SciPy PoissonDisk documentation for a current implementation surface, current RNG API and dimensionality warnings.
- For teaching, see subgoal-labelled worked examples and research on worked examples/metacognitive scaffolding in novice programming.
Professional rule: you understand Bridson when you can derive the grid-cell bound, explain why local neighbour checks suffice, generate annulus candidates without geometric bias, and verify the minimum-distance invariant independently of the implementation.
