Tiny MCU 3D Renderer Part 2: Dithering

Dithering is an important post processing technique for color quantization, and is especially useful for smoothing gradients with a low precision color space. I got ahead of myself a little bit on the 3D renderer development, and decided to research and experiment with various dithering algorithms. The most popular algorithm is arguably Floyd-Steinberg, which is based upon error diffusion. I used this algorithm back in 2009 for an image processing side-project.

It's safe to say I've learned a bit more about dithering in the last 8 years. Most obviously that Floyd-Steinberg is not ideal for animations because error diffusion will cause an avalanche of artifacts over the temporal domain. A noisy animation could be nice - even artistic - if the noise was evenly distributed. Avoiding the grainy look may be a better option, however. To that end, Bayer's ordered dithering algorithm is commonly used. Unfortunately, the apparent pattern may be too distracting. Various deterministic noise functions are also useful (e.g. pink noise or blue noise ... definitely not white noise).

My first dithering attempt was simple: I would draw a smooth gradient from black to white, using only 2 stops: black at 0.0 and white at 1.0. It was immediately clear that I needed some gamma correction, because my gradient was far too bright overall (when compared to a linear gradient without dithering). Everything I know about gamma, I learned from this article; highly recommended read. This was the first decent dithered gradient I created, using 2 stops:

You'll have to stand pretty far away from the image, and maybe squint a bit to see how the gradient tones line up (note that gamma correction was performed with γ = 1.8, which looks correct on macOS and Windows 10). Not bad for two shades! Close up though, the pattern is a little too strong. It will look better when applied to an image with lower frequency components; the linear gradient is the same pattern of pixels repeated vertically. If applied to the head model, the dithering would probably look rather nice (TBD). But we can always do better!

The second attempt was a gradient using 3 stops. This one stumped me for an extra day because I was only gamma-correcting the input; not the output. I was able to get away with this on the 2-stop gradient because pure black and pure white are identical on both sides of the gamma transformation. The mid-tone on the 3-stop gradient needed to be gamma corrected, and suddenly it all fell into place:

The smoothness in this screenshot is definitely an improvement over the first attempt. It doesn't have enough gradient stops, though. So I had to take it one more level to a 4-stop gradient. The plan now is to stick with 4-stop gradients. I'll need the best dithering algorithm possible to make good use of so few shades. My research lead me to Interleaved Gradient Noise, which may be exactly what I have been looking for. I made a few tweaks to the algorithm, so it produces a less patterned texture. This is what it looks like with a 4-stop gradient, compared to the linear gradient and 4-stop Bayer gradient:

The Bayer gradient in this screenshot looks almost identical to the 3-stop variation above, but the interleaved gradient is just all over the place! This noise algorithm works by creating a spiral pattern (described in some detail in Jorge Jimenez's presentation). That fact becomes pretty apparent if you play with the magic numbers a bit. My additions to the algorithm were: a minor adjustment to the magic number, and swapping the x and y parameters when x is even:

magic.z = 53.4

if x & 1 == 0 then swap x and y

What I like about this method is that it's deterministic (works great with animations), adds enough randomness to hide cycles and patterns without going overboard (like white noise), and it's super fast (just a handful of arithmetic operations). I reckon applying the interleaved gradient over the head model would look far superior to Bayer (also TBD). Truthfully, I won't actually know what's better until I get around to adding post-processing steps to the renderer.

Now that my curiosity is satisfied, I can get back to working on the renderer again. In addition to texture mapping and perspective projection, I'd also like to have Gouraud shading or Phong shading (depending on compute). It will greatly improve the appearance of lighting on the mesh, specifically by creating smooth gradients (!) which can be dithered down to four shades. 😋