4. The Dither Algorithm

The actual dither algorithm itself. There's some great places to learn about dither, including the blog post I linked at the top of this document. These are good places to get a thorough overview of the topic, not here.

Dithering is a matter of taking each pixel and approximating it to the nearest color. If a pixel is kinda light, make it white. If it's kinda dark, make it black. For our filter, these two colors are referred to as light and dark.

Two dimensional dither works by taking the error (how much it snapped to the color), and distributing it to the surrounding pixels, in a process known as error diffusion. How this error is divied up and distrubuted determines the diffusion algorithm.

Atkinson dithering works by taking the error, dividing it by 8, and then distributing that value amongst 6 surrounding pixels: two pixels down, two pixels forward, one pixel down to the left, and one pixel down to the right. It helps to draw a picture (the blog post I used had an excellent one).

The full error does not get distributed. Apparently, this sort of technique is known to provide a "reduced color bleed", reducing speckling artifacts, but causing contiguous light/dark regions to be more pronounced.

And that's it in a nutshell. To implement the error distribution, three row buffers were used: the first row is used to store errors for the current row, the second for the next row, the third for the row after that. At the end of every row, the row buffers rotate up in position, causing the first row to be the new third row. While in in the first row, the buffer gets zero'd out as it goes left-to-right, causing it to be fully re-initialized by the time the rotation happens.

static void atkinson_dither(monolith_framebuffer *f,
                            int xpos, int ypos,
                            int w, int h,
                            monolith_pixel light,
                            monolith_pixel dark)
{
    int x, y;
    int *mem;
    int *rows[3];
    int rowpos;
    int *err[3];

    mem = malloc(3 * w * sizeof(int));
    rowpos = 0;

    rows[0] = &mem[0];
    rows[1] = &mem[w];
    rows[2] = &mem[w*2];

    err[0] = rows[rowpos];
    err[1] = rows[(rowpos + 1) % 3];
    err[2] = rows[(rowpos + 2) % 3];

    for (x = 0; x < 3 * w; x++) mem[x] = 0;

    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            monolith_pixel p;
            monolith_pixel *out;
            int gray;
            int s;
            int e;
            e = 0;

            s = 0;
            monolith_gfx_pixel_get(f, x + xpos, y + ypos, &p);
            gray = pixel2grayscale(&p) + err[0][x];

            /* clear error */
            err[0][x] = 0;

            s = (gray > 127);

            if (s) {
                out = &light;
                e = gray - 255;
            } else {
                out = &dark;
                e = gray;
            }


            /* divide error by 8 */
            e >>= 3;

            if ((x + 2) < w) {
                err[0][x + 2] += e;

                /* also do x + 1 */
                err[0][x + 1] += e;
                err[1][x + 1] += e;
            } else if ((x + 1) < w) {
                err[0][x + 1] += e;
                err[1][x + 1] += e;
            }

            /* x + 1 distribution */
            if (x > 0) {
                err[1][x - 1] += e;
            }

            err[1][x] += e;
            err[2][x] += e;

            monolith_gfx_pixel_set(f, x + xpos, y + ypos, *out);

            /* shift rows circularly */
            rowpos = (rowpos + 1) % 3;
            err[0] = rows[rowpos];
            err[1] = rows[(rowpos + 1) % 3];
            err[2] = rows[(rowpos + 2) % 3];
        }
    }

    free(mem);
}

---

prev | home | next