# Jittered grid vs Poisson disc

from Red Blob Games
26 Jul 2018

I wanted to compare Poisson Disc with jittered grids. These are some notes I made; I didn't finish studying this topic before I got distracted by something else. I want to return to this someday.

The Poisson disc values come from the poisson-disk-sampling[2] javascript library. There's also a poisson-disk[3] library that's far smaller, but it uses a non-standard license, so I didn't use that. And now there's fast-2d-poisson-disk-sampling[4], faster and smaller than poisson-disk-sampling. Since the Poisson disc algorithm (2007) there are some algorithmic improvements[5] from 2019–2021 worth a look.

The jittered grids start with either a square or hexagon grid, and then add random jitter to each point. For the square grid I add random values to x and y. For the hex grid I tried both adding to x,y (a random point in a square) and also adding in polar coordinates (a random point in a circle[6]). Still to implement: random point in a hexagon. Compared to blue noise from Poisson disc, jittered grids tend to have some clumps and gaps. However, it's really fast and easy!

## Poisson disk#

The poisson-disk-sampling and fast-2d-poisson-disk libraries allows tuning the quality vs performance. The higher the `tries` parameter, the more evenly spaced the points, but the longer it takes. Reducing the value from the default of 30 down to 5 allows it to run 2–4X faster. I do not recommend using values of 4 or lower[8], as it seems to become unstable.

For a lot of my projects, the uneven spacing is better.

## More#

Fil's overview[9] is the first thing to check out

There are a whole bunch of other techniques, including latinized grids, wang tiles, penrose tiles, polyominoes, sobol/halton sequences, … One day I should write more of this up. Also watch this video[10] (read the paper for details). Also see The Nebraska Problem[11], Casey Muratori's exploration of the point placement problem. And https://twitter.com/Atrix256/status/1060906456189267969

https://github.com/kchapelier/jittered-hexagonal-grid-sampling implements hexagonal jitter inside a hexagon grid

TODO: investigate https://github.com/dcoeurjo/LowDiscBlueNoise , https://blog.demofox.org/2018/08/12/not-all-blue-noise-is-created-equal/

http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/

TODO: show how the precomputed blue noise can be combined with a perlin noise threshold to make variable density points

TODO: investigate Martin's http://extremelearning.com.au/an-improved-version-of-bridsons-algorithm-n-for-poisson-disc-sampling/ and also Jacob Rus's improvement (https://observablehq.com/@jrus/bridson-fork/2 ??)

TODO: for a sphere, look at https://observablehq.com/@jrus/stereorandom (but these aren't blue noise I think)

Email me , or tweet @redblobgames, or comment: