Understanding Poisson Disk Sampling

In 2024, a group of nine mathematicians produced a staggering, nearly 1,000-page proof regarding the geometric Langlands conjecture. It stands as a peak of pure mathematics—a work so complex that I've accepted I will likely never grasp the proof, or even the initial statements being proved.

Conversely, in 2007, Robert Bridson released a mere one-page paper. Despite its brevity, it has garnered nearly 1,000 citations and can be fully comprehended in under ten minutes. This paper solves a ubiquitous challenge in simulations and computer graphics: how to distribute objects randomly without them clustering too closely.

The Problem: Randomness vs. Order

Imagine you are procedurally generating a forest. If you use basic random sampling to place your trees, you encounter an immediate issue: trees will overlap some trees will be placed directly on top of one another.

To fix this, we need a way to enforce a minimum distance between any two points. A set of points that satisfies this constraint is known as a Poisson disk distribution.

Why not just use rejection sampling?

A naive approach would be to "throw darts" at the map and reject any point that falls within the minimum distance $r$ of an existing point. However, this is inefficient because:

1. Without a specialized data structure, checking collisions takes linear time.
2. As the space fills up, the rejection rate rapidly approaches 100%.

---

Bridson’s Algorithm

To solve this efficiently, Bridson proposed an algorithm that works in $d$-dimensional space with a desired minimum distance $r$.

1. The Setup

First, partition the space into a grid where each cell has a side length of: $\text{cell size} = \frac{r}{\sqrt{d}}$ This specific size ensures that each grid cell can contain at most one point.

2. The Process

The algorithm maintains a list called active.

3. Sampling the Annulus

To find a new point, we sample an annulus (a ring) centered at $p$ with an inner radius $r$ and an outer radius $2r$. To do this uniformly:

1. Generate a random unit vector $\vec{v} \in \mathbb{R}^d$.
2. Pick a value $x$ uniformly from the interval $[ \frac{1}{2^d}, 1 )$.
3. The final sample point is calculated as: $2rx^{1/d} \cdot \vec{v}$

Note: In 2D, picking $\vec{v}$ is as simple as choosing an angle $\theta \in [0, 2\pi)$. In higher dimensions, you can normalize a vector composed of samples from a normal distribution.

---

Enhancing the Algorithm

There are two primary ways to reduce the number of iterations needed to fill the space. While the first is specific to 2D, the second is more general.

The "Parental" Optimization (2D)

When the algorithm generates a point $q$ from a parent point $p$, we gain useful information. When we later sample the annulus around $q$, there is a specific "cone" of angles that we can ignore because any point in that region would inevitably be too close to $p$.

The Geometry of the Forbidden Cone: The cone is centered at angle $\alpha$ with a total width of $2\beta$:

$\alpha = \operatorname{atan2}(p_y - q_y, p_x - q_x)$ $\beta = \min\left(\arccos\frac{|p-q|^2+3r^2}{4r \cdot |p-q|}, \arccos\frac{|p-q|}{2r}\right)$

The $\min$ function is critical here. Depending on the distance between $p$ and $q$, the boundary of the forbidden zone is determined by either the inner or outer circle of the annulus. The transition occurs when the distance between points crosses $\sqrt{3} \cdot r$.

Implementation Steps:

• Store the parent of every generated point.
• Calculate $\alpha$ and $\beta$ for the current point $q$ relative to its parent $p$.
• Generate the sample angle $\theta$ only from the range outside the $[\alpha - \beta, \alpha + \beta]$ window.

Performance Comparison

(Based on trials with $\ell = 100$ and $r = 1$)

Final Considerations

While the parental optimization is powerful in 2D, its utility in higher dimensions is limited:

• Storage: It would require storing more contact vectors.
• Diminishing Returns: The volume of the intersection between an annulus and a sphere becomes proportionally smaller as dimensions increase.

One could theoretically store "children" as well as "parents" to prune even more of the annulus, but this would increase memory overhead and slow down the selection of $\theta$.