Interactive demo

Blue Noise

Purely random points form clumps and leave gaps. Blue noise points are still random, but keep a minimum distance from each other, like trees in a forest or cells in the retina. Robert Bridson's algorithm creates them in linear time.

Your browser does not support the HTML5 canvas tag.

Every step picks an active point (coral) and tries up to k random positions in the ring around it. Green is accepted, crosses were too close to another point.

Controls

Display

Points
–
Active points
–

Legend

  • Point
  • Active point (may still get neighbors)
  • Current point and rejected tries
  • Accepted new point

All noise types →

1. Tries around active points

  1. Start with one random point and mark it active.
  2. Pick a random active point and try up to k random positions in the ring between r and 2r around it.
  3. Keep the first position that is at least r away from every point, and mark it active.
  4. If all k tries fail, retire the point. Stop when no active point is left.

2. A grid for the neighbors

To test a position quickly, a background grid with cells of size r/√2 is used. Each cell holds at most one point, so only the 5 × 5 cells around a position need to be checked, no matter how many points there are.

3. Why “blue”

The spectrum of random points is flat, like white noise. Poisson disk points have almost no power at low frequencies, the dark disk in the middle of their spectrum, because they never clump. That is the mark of blue noise, and why it is used for sampling, dithering and stippling.

Credits