🔘 Poisson-Disk Sampling

Poisson-disk sampling generates a set of random points in space such that every pair of points is separated by at least a minimum distance r, while still looking irregular and organic rather than grid-like. It sits between fully random scattering (which clumps) and a regular grid (which looks artificial), and is the standard way to produce "blue noise" point distributions.

Start with one random seed point and add it to an "active list". Repeatedly pick a random point from the active list and try up to k random candidates in the annulus between r and 2r around it. The first candidate that is at least r away from every existing point is accepted and added to both the point set and the active list; if none of the k tries succeed, the parent point is removed from the active list. The process ends when the active list is empty.

Checking a new candidate against every existing point would take O(n) time per candidate, making the whole algorithm O(n²). Bridson's key trick is a background grid with cell size r/√2, chosen so each cell can hold at most one accepted point. A candidate only needs to check its own cell and the surrounding neighbourhood (a small fixed number of cells), so each check runs in O(1), and the entire algorithm runs in O(n) time for n output points.

Blue noise describes a point distribution whose power spectrum has little energy at low spatial frequencies — meaning there are no large clusters or large empty gaps, only fine-scale, evenly distributed variation. This property is visually important because the human eye is highly sensitive to low-frequency patterns like clumps or moiré artefacts. That is why blue noise sampling is the standard technique for stippling, dithering, anti-aliasing, and procedurally scattering objects such as trees, rocks or grass in a natural-looking way.

Instead of using one fixed radius r everywhere, the local minimum distance can be looked up from a density map: a small radius is used in dense regions (allowing points to sit closer together) and a larger radius in sparse regions (spreading points further apart). The neighbour check then uses the larger of the candidate's and each existing point's radius, so the packing stays consistent everywhere. This produces smoothly varying point density while keeping the same no-overlap guarantee everywhere, which is exactly what the Paint density map tool lets you sculpt by hand.