Sketch · 2026-07-10
Poisson disc sampling, by Bridson.
Fill a rectangle with points so that every pair keeps at least distance r apart, and pack them as tightly as that constraint allows. Naive rejection sampling gets slower with every added point. Bridson's 2007 algorithm stays linear by only ever probing near a small frontier of recent samples.
Why bother
Uniformly random points clump. Half a hundred throws leave big gaps and dense knots, because two throws that fall near each other have no rule stopping them. In graphics that clumping shows up as noise; in placement it shows up as ugly overlap.
A Poisson disc distribution keeps a minimum distance r between every pair. The resulting spectrum is flat above one frequency and empty below it, which is what graphics people call blue noise. It is what sunflower seeds do, roughly, and what photoreceptors do in a healthy retina.
The algorithm
A background grid of cell size r/√2 backs the whole thing. That cell is small enough that no cell can hold two samples at once, so each cell stores at most one point index. Two points inside distance r of each other must live in a five by five block of cells around the query, so every neighbour check reads twenty-five cells and no more.
Seed a single sample in the middle. Push it onto an active list. Then loop: pick a random active point, throw k candidates into the annulus between r and 2r around it, and test each candidate against those twenty-five cells. Accept the first that passes, adding it to samples and to active. If all k miss, the active point is used up and gets removed. The loop ends when active is empty.
The knobs
r sets the minimum distance and therefore the density: halving r quadruples the sample count. k caps the effort spent per active point; Bridson used k = 30 and later work has shown that anything above about ten is enough to stay close to a maximal packing on a plane. Lowering k leaves visible holes where the frontier gave up early.
The accept rate readout is the running ratio of accepted candidates to attempted candidates. Early on it stays near one: the field is empty and almost every throw lands in free space. Near the end it drops toward zero and the front collapses.
Sources
Bridson, R., Fast Poisson Disk Sampling in Arbitrary Dimensions, ACM SIGGRAPH 2007 Sketches. Cook, R.L., Stochastic Sampling in Computer Graphics, ACM Transactions on Graphics 5 (1986), 51-72. Lagae, A. and Dutré, P., A Comparison of Methods for Generating Poisson Disk Distributions, Computer Graphics Forum 27 (2008), 114-129.