If you asked someone to place points randomly in a square, most would probably say "just use a random number generator." But mathematicians and computer graphics researchers have long known that uniform randomness has a flaw: it creates clustering. Some areas get lots of points, others get none. For many applications, Poisson disk sampling is better: points are random but evenly distributed.
The Problem with Uniform Randomness
When you use a random number generator, you get true randomness - but that randomness includes clustering. Points tend to bunch together in some areas and leave gaps in others. This is statistically inevitable.
For certain applications - stippling, dithering, procedural generation - clustering is undesirable. You want random placement without the clustering.
Poisson Disk Sampling: The Solution
Poisson disk sampling (also called blue noise sampling) generates random points with a constraint: no two points can be closer than a minimum distance.
The result looks random (no grid pattern, no repetition) but is more evenly distributed than uniform randomness. The visual effect is natural-looking without clustering.
Bridson's Algorithm
In 2007, Robert Bridson published an efficient algorithm for generating Poisson disk samples. Before Bridson, generating Poisson disks was computationally expensive. His algorithm made it practical.
The basic idea:
- Start with a random point
- Repeatedly sample points in a ring around existing points
- If a new point is far enough from all others, accept it
- Otherwise, discard and try another random position
Blue Noise vs White Noise
White noise has equal power at all frequencies (like static on a TV).
Blue noise has more power at high frequencies, less at low frequencies. This means clustering is minimized - the noise is "whiter" at larger scales while remaining random at small scales.
Poisson disk sampling generates blue noise, which is why it's also called blue noise sampling.
Applications
Poisson disk sampling is used in:
- Stippling art: Creating stippled versions of photographs with even dot distribution
- Procedural terrain: Placing trees, rocks, or other objects naturally
- Dithering: Blue noise dithering produces less visible patterns than ordered dithering
- Sampling: Graphics rendering uses Poisson disk sampling for anti-aliasing
- Game design: Enemy placement, resource distribution, level generation
The Visual Difference
If you stipple a photograph using uniform randomness, you'll see clumps - areas with more dots, areas with fewer. Using Poisson disk sampling, the dots are more evenly spread, making the image look cleaner and more natural.
The effect is subtle but important. It's the difference between "this was randomly generated" and "this looks intentionally designed."
Modern Extensions
Researchers have since developed variations:
- Weighted Poisson disk sampling: Allow varying minimum distances based on location
- Adaptive sampling: Denser sampling in complex regions, sparser in simple ones
- Multi-class sampling: Generate multiple sets of points with different constraints
Ready to try it? Open GlitchArt Studio and experiment with this effect.