Jittered grid vs Poisson disc

from Red Blob Games
26 Jul 2018

I wanted to compare Poisson Disc with jittered grids.

Poisson disc
d={{ds1.toFixed(1)}}
Square grid with square jitter
d={{dr.toFixed(1)}}
Hexagonal grid with round jitter
d={{ds2.toFixed(1)}}
Hexagonal grid with square jitter
Hexagonal grid
Square grid
Precomputed blue noise from here
threshold={{threshold}}/255
channel={{channelName}}
Blue noise slices
slice={{slice}}
channel={{channelName}}

The Poisson disc values come from the poisson-disk-sampling javascript library.

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). 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, 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.

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 (read the paper for details). Also see The Nebraska Problem, Casey Muratori's exploration of the point placement problem. And https://twitter.com/Atrix256/status/1060906456189267969

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

Email me at , or tweet to @redblobgames, or post a public comment: