> The above thresholding matrix approach describes the Bayer family of ordered dithering algorithms. A number of other algorithms are also known; they generally involve changes in the threshold matrix, equivalent to the "noise" in general descriptions of dithering.
Basically, I'm leaning into "general descriptions of dithering" with my noise requirement, and the lack of noise in "ordered dithering" leads me to consider it not-quite-dithering.
The very first sentence of the general Dithering article [0] connects with my perspective as well:
> preventing large-scale patterns such as color banding
Aside: I probably misspoke with the word "halftone" earlier; apparently that's a specific thing as opposed to an umbrella term. I'm not sure there's a great word (other than "dither"...) for techniques to trade resolution for color.
The threshold map of ordered dithering is still a source of noise, it just happens to be carefully pre-baked so that (original image + noise)==output makes the output more legible than what you'd get from just mapping the original image pixels to the nearest available color.
The error diffusion is static and baked into the thresholds chosen, but it's still there and choosing the error diffusion properly still matters to getting a reasonable output.
The color Next machines only had 12 bit displays, 4 bits per channel, but with careful use of dithering it was often indistinguishable from a 24-bit display (so called "true color")
One standard point of view is that what introduces noise is quantization, in the sense that the quantized image has an unwanted difference from the desired image, and dithering consists of techniques to shape that noise. The Bayer-matrix ordered dithering algorithm presented here concentrates the noise at high frequencies where the eye is less sensitive to it, but it still retains some noise at lower frequencies, which is the banding you're commenting on.
Dave Long had the sharp observation earlier today that Bresenham-style line drawing is a form of dithering, where the signal being represented is the position of the pen rather than the brightness of the visual field. (I see that dreamcompiler made the same observation two days ago: https://news.ycombinator.com/item?id=45728962 but I don't know if Dave saw it there)
We had a good discussion of dithering here a couple of days ago, connected with a significantly more comprehensive article with a less fancy presentation: https://news.ycombinator.com/item?id=45728231
Bresenham is the equivalent of a sharp quantization, with no dithering. Using true 1D dithering for line drawing would instead result in a "wobbly" almost hand-drawn output.
I'm tempted to try the wobbly algorithm now to see what it looks like!
I agree that the lack of division is surprising and beneficial.
In color dithering A is the set of colors in the original image and B is a smaller set of colors. Often just pure black and pure white, but that doesn't have to be the case.
In Bresenham A is the relative x,y coordinates of the ideal next pixel in the line if the pixels were infinitely small (thus |A| = infinity), while B contains the relative x,y coordinates of the 3 pixels that are actually available: +1,0; 0,+1; and +1,+1 (with appropriate rotation for the other 3 quadrants).
An important feature of Bresenham's is that the error inherent in this assignment is carried forth into the decision made for the next pixel, such that the total error is diffused along the line and its average value stays close to zero. Such error diffusion is also a feature of the best color dithering algorithms, but not the one described in TFA -- ordered dithering -- because ordered dithering is not a very good algorithm and is not used much today except when its peculiar artifacts are desired.
And yes, Bresenham's original algorithm does set each pixel it chooses to pure black, but this has nothing to do with its error diffusion mechanism. Bresenham's with grayscale is also a thing and it results in even better line approximations, but it's usually referred to as antialiased Bresenham.
Here[0] is a good summary of dithering/noise to reduce color banding. Interestingly, for my game[1] I found that Valve's animated dithering technique (which uses variation over time in lieu of a fixed noise pattern) worked best, as the other techniques described there altered the perceived lightness of the resulting image.
[0]: https://blog.frost.kiwi/GLSL-noise-and-radial-gradient/
[1]: A multiplayer Noita-like (more at https://slowrush.dev), where the radiance-cascades-powered lighting tends to cause obvious banding patterns on really dark backgrounds.
The halftone technique demonstrated here takes a palette of 2 colors and increases it to something on the order of 20 apparent colors, but even with 20 there are extremely obvious bands.
That banding can be virtually eliminated by having way more colors (say, 256 if grayscale, 256^3 if RGB) or it can be virtually eliminated via dithering. I suspect the "error diffusion" technique (which is teased at the end of this demo) does what I'm talking about.
Noise is the key to dithering, and I don't see any noise in this demo. Everything is deterministic.
But the presentation is spectacular!