Poisson Disk Sampling
This post offers a deep dive into Poisson Disk Sampling, a clever algorithm for placing objects randomly but without overlap, crucial for procedural generation in graphics. It dissects Robert Bridson's seminal 2007 method, showcasing elegant mathematical optimizations that significantly enhance its efficiency. Hacker News readers will appreciate the detailed technical explanations, practical improvements, and exploration of alternatives for this fundamental computer graphics technique.
The Lowdown
The article introduces Poisson Disk Sampling, a technique vital for computer graphics and simulations to place elements randomly while maintaining a minimum separation distance between them. It contrasts this practical, widely-cited algorithm with complex theoretical mathematics, highlighting its accessibility and utility. The core problem, as exemplified by placing trees in a forest without overlap, is addressed by avoiding naive rejection sampling, which quickly becomes inefficient.
Bridson's algorithm, published in 2007, offers an efficient solution:
- It partitions space into a grid of specific side length to ensure at most one point per cell.
- It initializes an 'active' list with a single random point.
- While the 'active' list is not empty, it repeatedly selects a point 'p', samples an annulus (a ring shape) around it for new potential points, and adds valid, collision-free points to the active list using the grid for speed. If 'k' attempts fail for 'p', it's removed.
The author then presents two significant improvements:
- Parental Optimization: For 2D, this modification stores the 'parent' of each new point. When sampling the annulus of a point, it avoids angular ranges where new points would be too close to the parent, leading to fewer iterations. The mathematics behind determining these forbidden angles are detailed.
- Distance CDF Adjustment: This improvement involves manipulating the cumulative distribution function (CDF) for sampling the distance of new points within the annulus using a parameter 'c'. By adjusting 'c', one can balance the density of points with the perception of randomness. Negative 'c' values push points closer to the minimum distance 'r', increasing density, but can introduce artifacts if pushed too far.
The article also touches upon advanced applications and alternatives. It demonstrates how varying the minimum distance 'r' dynamically, based on image brightness, can create a 'stippling' effect. It briefly mentions parallel algorithms like PixelPie for real-time applications. Finally, it introduces Scott A. Mitchell's 2022 algorithm, which achieves maximality, uniformity, and determinism without rejection sampling, offering a performant alternative to Bridson's method, albeit with higher complexity.