Understanding Bridson's Algorithm for Efficient Poisson Disk Sampling

The Problem with Random Placement

In computer graphics and simulations, a common challenge is placing objects randomly while ensuring they maintain a minimum distance from each other. Simple random sampling often leads to objects overlapping, such as trees in a procedurally generated forest appearing on top of one another. This necessitates a method to enforce a minimum separation between any two points.

Introducing Poisson Disk Distribution

A distribution of points that adheres to a minimum distance rule is known as a Poisson disk distribution. A naive approach, like rejection sampling, involves randomly placing points and discarding those that fall too close to existing ones. However, this method quickly becomes inefficient, especially as the number of points grows, due to the linear time complexity of collision checks and a high rejection rate.

Bridson's Efficient Algorithm

Robert Bridson's 2007 algorithm offers an efficient solution for generating Poisson disk samples. The algorithm operates by partitioning the space into a grid, where each cell can hold at most one point. It initializes an 'active' list with a single random point.

The core of the algorithm involves iteratively selecting a point from the 'active' list, then attempting to sample new points within an annulus (a ring-shaped region) around it. If a valid new point is found, it is added to the 'active' list. If no valid point is found after a set number of attempts (Bridson suggests 30), the original point is removed from the 'active' list. This process continues until the 'active' list is empty, yielding a Poisson disk distribution.

Sampling the Annulus

To uniformly sample the annulus, the algorithm generates a random unit vector and a random number within a specific interval. The final sample is then calculated using these values. In two dimensions, selecting a unit vector is equivalent to choosing a random angle, while in higher dimensions, it involves normalizing a vector with components sampled randomly.