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.
channel={{channelName}}
channel={{channelName}}
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.
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/
TODO: read https://graphics.cs.kuleuven.be/publications/LD08CMGPD/LD08CMGPD_paper.pdf
http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/
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)
TODO: for hex/square/voronoi, what if we apply jitter to the vertices instead of the center points? related: my corner cutting post[12] where I non-randomly moved vertices