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.

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[5]). 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[6], 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[7] (read the paper for details). Also see The Nebraska Problem[8], 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/

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

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

Email me , or tweet @redblobgames, or comment: