Here is the wikipedia page on ordered dither, as used here:
http://en.wikipedia.org/wiki/Ordered_dithering
Here is an 8x8 dither table like we use here, from that wikipedia page:
Note that it contains 64 values, from 1 to 64. In order to simplify the comparison into a simple subtract, giving the threshold result in the sign bit, I subtracted one from these dither table values giving 0 to 63. Technically, an ordered dither really gives an extra value when you take zero into account (hence the 1/65 shown to the left of the image), and I prefer to skip a value in the center of the range so I can still have pure black and pure white area fills. In my case, I handle this with the contrast and brightness values to center and stretch the range for best image quality (which can result in more or less bright and dark areas than in the input image, to be adjusted for best eink compatibility as I did for the default values).
In this code the dither threshold values are used to determine whether an output pixel will be pure black or pure white. In my 256-color to 16-color dither code as used in the newtrix demo, the threshold values are used to determine when to increment a 16-bit output to the next brighter value to give the appearance of 256 different shades of gray and to prevent "
Mach banding" in gradients such as are common in a cloudy sky image.
As I mentioned previously, the important things about a dither table are that it contains a single instance of each value in the supported range (0-63 in my case) and that these values are evenly distributed through the table so that an particular grayscale value will consist of evenly distributed black and white pixels in the output image, in a ratio that gives an average value equal to the value of that pixel in the input image.
You can think of a dither table as an 8x8 texture image that can be tiled to fill the framebuffer. In fact, modern video graphics cards have shaders that can do dithering by using just such a dithered texture image, corresponding exactly with our dither table.
As you can see in the code snippets posted earlier in this thread, I have code that contains a real dither table, and code that computes the table values as-needed where needed using a logical formula.
I tested other dither methods, and I decided that a simple ordered dither like this looks the best for video on the kindle eink displays. One of the demos in newtrix also does a spatio-temporal random dither, which has some interesting artifacts causing severe "ringing" that appear as a trail behind moving objects that oscillates between too bright and too dark while it fades, with tail length depending on kindle model and boot mode. Ordered dither is more appealing and more consistent across all the eink kindle models, IMHO.