Making low discrepancy sequence noise textures, not LDS sample positions

Question

When making sampling locations, there is a lot of information out there on how to do white noise sampling, uniform sampling, uniform+jittered sampling, low discrepancy sequence sampling (eg halton) and blue noise sampling (eg mitchell's best candidate algorithm Mitchell's Best Candidate Algorithm).

For instance these, where each point is a sample location in a 2d quad. (source: https://blog.demofox.org/2017/05/29/when-random-numbers-are-too-random-low-discrepancy-sequences/)

White Noise:

Uniform:

Uniform + Jitter:

Halton (2,3):

Blue Noise:

While those are good for sampling (a 2d quad in this case), here is a blue noise texture which is useful for dithering or stippling (src: http://momentsingraphics.de/?p=127)

Similarly, here is a white noise (random) one:

I've been trying to figure out in this case (a dither / stippling noise texture), if there is an equivalent to uniform sampling, uniform + jitter, or low discrepancy, and if so, what those textures might look like.

One obvious difference between the first set of the textures and the second is that the first textures take a single scalar value as input (an index) and give a 2d vector as output (a location on the 2d quad). The second set of textures takes an (x,y) 2d vector location as input, and gives out a scalar value as output.

It almost looks though like in the blue noise case that maybe you could start with the blue noise sample points, and then color every other pixel based on it's distance from the closest sample point, and that you might come up with the same image. If that's correct, could you do the same for the other flavors of sample distributions to make the other noise textures? It seems like white noise (random) wouldn't work for this though, so that doesn't seem correct.

Lastly, Jorge Jiminez has some "Interleaved Gradient Noise" that looks sort of blue noise-ish but kind of not... so seems a bit low discrepancy sequence. (http://www.iryoku.com/next-generation-post-processing-in-call-of-duty-advanced-warfare and also an image and the math mentioned here https://bartwronski.com/2016/10/30/dithering-part-three-real-world-2d-quantization-dithering/)

It makes me wonder if something about that noise shows the secret on how to generalize (low discrepancy) sample points to 2d?

Does anyone know whether there is a way to translate these sample concepts to noise textures for dithering and stippling?

Answer 1

In theory, it is possible to stuff every sample distribution into a texture to "pre-bake" it for fast access. The question is whether any of the results might be useful. For blue noise, this makes a lot of sense, as blue noise distributions have global influence and are hard to evaluate at runtime. Uniform random sampling, on the other hand, is so simple precisely because it is not global, but has no influence whatsoever from neighboring samples. So the best you can achieve, as you noticed yourself, is writing uncorrelated white noise to the texture, which gains you very little.

I think the key property of the blue noise textures that you failed to mention is that they are progressive. If you take, for example, Blue Noise Masks, Forced Random Dithering, or Relaxation Dart Throwing to generate a matrix/texture, you will not get grayscale values, but unique, ascending integer values corresponding to the order of insertion of the samples/texels. This means that you can also re-arrange such textures to a 1D list of width * height elements, where each element is a 2D position within the matrix. I.e., the first element of this list will be the (x, y) of the first sample inserted into the texture upon creation. The second element will be the (x2, y2) of the second sample, which will be quite far away from the first one, because the blue noise texture algorithms try to maximize distances between similar values.

The list representation is nothing but a sequence accomplishing what 2D low-discrepancy sequences do: giving you a 2D sample position (albeit discrete and in a grid) for a scalar index. You do not lose any information while converting. So applying the reverse conversion to low-discrepancy sequences, it should be possible to write their element indices into a texture for fast lookup. What I don't know is how fast this will degenerate, because sooner or later higher values will end up at the same discretized locations as previously written ones. Low-discrepancy sequences guarantee spatial uniformity on average, but if you want to fill an n² texture and create exactly n² samples, I bet that you will get some of these overlaps while also having some holes. These conflicts can, by design, not occur in blue noise textures, but here you would have to find a strategy. Just discarding the higher values? I don't know how this influences the distribution properties. I assume that results vary between different low-discrepancy sequences. I have only ever worked with Halton and Hammersley, which don't seem like the best fit in this case. Maybe something based on a grid/lattice would help you to reduce/eliminate the overlaps. Not my field of expertise, unfortunately.

This is the key problem, that low-discrepancy sequences (at least the ones I know) and in general sampling distributions used in computer graphics output nD values in the continuous domain rather than in a discrete grid. The reason blue noise textures work so well is because the discretization is already part of the generation. What you want is a permutation of n² integer values such that the result has special properties. Maximizing distances between similar values would be blue noise. Having no correlation between values would be white noise. And some other magic property could be pink noise, green noise, or a perfect interleaved gradient noise as in your provided picture. Would this be a reasonable approach, to understand your problem as the problem of permuting given values? Instead of continuous sampling? Maybe it simplifies the solution.

Another point to consider for dithering and related effects is that blue noise textures can usually be tiled seemlessly because the sample domain is taken to be toroidal. You will lose this feature unless you find a way to make your low-discrepancy sequence toroidal, which I think is pretty tough, but would be a great scientific contribution!

Answer 2

The missing link between sample locations and the greyscale noise textures is "ordered dithering".

Ordered dithering is a list of pixel locations with a "rank" (order) for each pixel. If you have a white background and want to add two black dots, you add them at the locations for the two pixels rank 0 and rank 1.

Choosing how to rank the order of the pixels to turn on can vary dramatically with different results. For instance, a bayer matrix is a specific ordering of the points, and blue noise sample points are as well. White noise is just shuffling the points so that they have a random ordering.

How we get from this "ordered dithering" (stippling) to the greyscale color noise images is that we divide each point's rank by the number of points to get a value from 0 to 1, and use that as the points greyscale color.

That gives you the greyscale noise textures.

The problem with converting the concept of "uniform sampling" to this is coming up with a definition of what uniform samples in 2d would look like. Would it just be in scanline order of the pixels? Would vertical stripes be any more or less uniform sampled? Maybe uniform sampling would consist of a course grid followed by a finer grid, and a finer grid, and a finer grid, until all pixels were filled in? It seems open to debate and interpretation. That question would need to be solved before you could assign ranks to the pixels.

The problem with converting the concept of "low discrepancy sequences" to this is figuring out how to do a low discrepancy sequence in 2d on a discretized grid where samples are only chosen for places that do not yet already have a sample. I'm betting there are some LDS's that fit this or could be made to fit this but many don't.