GoKawiilOn Poisson Disk Sampling
In 2024, a team of nine mathematicians released a monstrous, nearly 1,000 page proof of the geometric Langlands conjecture. It is a crowning achievement in pure mathematics, and I have accepted that I will never understand even the statements that they proved, much less the proof itself.
On the total opposite end of the spectrum, in 2007, Robert Bridson published a one page paper that has nearly 1,000 citations and takes less than 10 minutes to fully understand. It presents a simple solution to a problem that commonly arises in computer graphics and simulations: placing things randomly, but not too close together.
Say you’re trying to procedurally generate a forest and need a way to place the trees. The problem with plain random sampling is obvious:
Some of the trees would be on top of each other! What we need is the ability to set a minimum distance between any two trees. A distribution of trees that obeys this rule is called a Poisson disk distribution. We can try a naive rejection sampling approach where we throw random darts and reject any point that falls within that minimum distance of any other point, but without a more clever data structure, it takes linear time to check collisions for each sample and the rejection rate quickly approaches one. Bridson’s algorithm gives us an efficient way to do this.
Bridson’s Algorithm
Suppose the desired minimum distance between points is r r r and we are working in a d d d-dimensional space. Bridson’s algorithm goes as follows:
Partition the space into a grid of side length r d \frac{r}{\sqrt{d}} d r . This guarantees that each grid cell can have at most one point inside it. Initialize a list active to have one random point chosen uniformly from the space. While active is non-empty: Select an element p p p from active uniformly at random. Uniformly sample the annulus centered at p p p of inner radius r r r and outer radius 2 r 2r 2 r at most k k k times. If a valid Poisson disk sample is found, using the grid for efficient collision detection, add it to active and pick a new p p p . If no valid point is found within k k k attempts, remove p p p from active . Bridson recommends setting k = 30 k = 30 k = 30 .
The easiest way to uniformly sample the annulus is to generate a random unit vector v ⃗ ∈ R d \vec{v} \in \mathbb{R}^d v ∈Rd and a number x x x chosen uniformly from the interval [ 1 2 d , 1 ) \left[\frac{1}{2^d}, 1\right) [2d1,1), and then your final sample is 2 r x 1 / d ⋅ v ⃗ 2rx^{1/d}\cdot\vec{v} 2rx1/d⋅v . A few years ago, I made a video that explains why this works. In two dimensions, picking a unit vector is equivalent to picking an angle θ ∈ [ 0 , 2 π ) \theta \in [0, 2\pi) θ∈[0,2π). In higher dimensions, you can normalize a vector where each component is sampled from a normal distribution.
Improvements
... continue reading