stochastic-dithering

An experimental shader inspired by Runevision's Surface-Stable Fractal Dithering system, which attempts to keep the dithering dots circular and evenly spaced, even when the surface is viewed at a steep angle.

The approach I'm using for this is... rather complex, but I'll try to explain it here.

The shader starts by performing the standard Unity lighting calculations, because I work in Unity and those are available to me. But that isn't essential to this technique; it'd work just fine with any other lighting model.

Then, it uses the grayscale value returned from the lighting calculations and a "dot radius" configured as a material property (essentially a shader uniform, if I'm not mistaken) to calculate a minimum distance (in screen-pixels) between the dots that it will draw.

Then, it assigns a random number (which I'll call the "Rank") to every possible pair of (u, v) coordinates on the UV map of the object being rendered.

Then it considers a circle in screenspace around the current pixel with radius equal to that minimum distance between dots from earlier, projects that circle onto the object using its UV map, and then searches in that roughly-elliptical region in UV space for the point with the highest Rank.

The resulting point (if one is found) is a candidate to be the center of a dot.

The shader then runs the same project-and-search algorithm again, but with the circle centered on this candidate point and with a somewhat larger search radius. If the same point comes back out, then the shader will draw a dot there. If the second search returns a different point, then that means another, higher-Ranked dot's "area of influence" overlaps the candidate dot, which would cut a bite out of the candidate dot. I only want to draw dots if they will be complete circles, so if this check predicts that the original candidate dot will end up looking like a crescent moon, the shader will reject the candidate and not draw a dot there at all.

If the candidate is not rejected, then the shader colors the pixel based on its distance on the candidate- white if the distance is less than the configured dot radius, and black otherwise.

Then, if the original grayscale value was >50%, the shader inverts the colors: in light areas, the dots are drawn black on a white background.

And that's about the gist of it. For a history of how I came up with this algorithm and some insight as to how my "find the point with the highest Rank among all those whose UV coordinates project onto this circle in screen space" algorithm works, see my discussion with Runevision over on their repository.

Future Work

(I may or may not ever get around to implementing any of this; but I have released this code into the public domain. If any of this strikes your fancy, feel free to fork my repo and try implementing it yourself. I'd love to see your results!)

• My current code takes the maximum of the (red, green, blue) channels returned by the standard Unity lighting calculations as a grayscale value, and then does all of the crazy dithering stuff based on that. It would be very simple to extrnd this to dither the red, green, and blue channels independently.
• It may be possible to get this to look at bit nicer by doing more with the gradient of the grayscale value from the lighting calculations. Currently, I'm just using it to antialias the boundary between the white-on-black and black-on-white regions; but it could potentially also be used to skew the search regions to extend farther into areas where the dots should be farther apart. This could potentially improve the look of this shader in areas where the grayscale value changes rapidly, e.g. the edges of shadows.
• The code to find the highest-Ranked point within a given area could be optimized significantly. Currently, it searches in axis-aligned square regions in UV space, without much regard to the shape of the ellipse that the screen-space circle projects onto. I'm already calculating the corners of a parallelogram that more tightly bounds the ellipse. My could could be made more efficient by using Bresenham's line algorithm to search only inside that parallelogram, without wasting time searching time searching in the corners of an axis-aligned square around it.
• There's got to be some way to allow the dots to get more tightly packed than my current code allows, or even some way to allow them to overlap. I have no idea how to do that within my current framework, though.
  • This would be very easy to do by reducing the dot radius to 1-2 pixels, rendering to a frame buffer, and then using something like the Jump Flood algorithm to expand these small dots to the desired size. This would allow dots to overlap without artifacts caused by anti-aliasing at the perimeter of the higher-Rank dot, and it may even allow using some kind of smooth-min function to meld overlapping dots into peanut shapes, which I think would look pretty nice.
    I haven't done that here, partly because I didn't want to bother with allocating that extra frame buffer and implemeting Jump Flood, and partly because I thought implementing this effect without those things would be an interesting challenge.
• I also considered trying to come up with some kind of wavy fractal boundary between the white-on-black and black-on-white regions, but I quickly decided that would be out of scope for this exercise. I'm not sure how to do it while also maintaining all the same constraints as the dots algorithm (i.e. the features should stay pinned to their UV coordinates and the smallest features drawn should maintain roughly the same shape and size in screen space, all regardless of how close or far away or from what angle the surface is viewed). But if I could figure out (and I'll keep thinking about it), that'd be another quite passable solution to surface-stable dithering all on its own. I wouldn't need the dots at all at that point.