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.

Poisson disc
Square grid with square jitter
Hexagonal grid with round jitter
Hexagonal grid with square jitter
Hexagonal grid
Square grid
Precomputed blue noise from here[1]
Blue noise slices

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!

From what I've read, the best blue noise comes from Poisson disc or from Lloyd relaxation. Both can be slow. So I was considering precomputing the points and loading it in as a data file. So I also was looking to see if anyone had generated something already. The precomputed blue noise on this page is from Christoph Peters[7], CC0 license. If I understand right, each channel is independent, and they should all be tileable, so you can randomly choose a channel/image for each tile to avoid repetitive patterns. One nice feature is that it's progressive so you can change the threshold to increase the density, and you can do that independently in different areas. Although any one texture is tileable, different textures don't fit together nicely. I have four columns, two rows here, and as you play with the parameters you'll see there are clumps and gaps at the seam boundaries. So it's mostly useful if you can cover your map with a single texture (such as the 1024x1024 one that's included in the download, probably compressible down to 25k). I think that'll cover many of my projects. The blue noise slices are from the same data, but look at slice…slice+6. You can see that every slice gives you blue noise, so that means if you don't need progressive noise, there a lot of slices of blue noise embedded in that image.

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.


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/

TODO: read https://graphics.cs.kuleuven.be/publications/LD08CMGPD/LD08CMGPD_paper.pdf


TODO: read https://observablehq.com/@jobleonard/fast-pmj02-sequences and https://observablehq.com/@jobleonard/pseudo-blue-noise

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: