Error-Diffusion Dithering

DEFINITION

quantise each pixel; pass the error on
ε → 7⁄16 →,  3⁄16 ↙,  5⁄16 ↓,  1⁄16 ↘

NOTES

Where Bayer consults a fixed matrix, Floyd and Steinberg carry the rounding error to pixels not yet visited, so the mistakes cancel instead of accumulating. The result keeps detail ordered dithering loses — and it is inherently sequential: each pixel depends on every pixel before it, which is why this plate has no shader tab. The pair of dither plates is the whole parallel-versus-serial trade, drawn — and plate 131 adds the third route: the same error carried along a Hilbert curve instead of the raster, so the diffusion follows locality rather than scan order.

PROVENANCE

Origin

R. W. Floyd & L. Steinberg, "An Adaptive Algorithm for Spatial Greyscale", Proceedings of the Society for Information Display 17(2), 1976

Standing

Public domain — a quantisation algorithm from a published paper

Constants

The grid is locked: it sets both the dot size and the cost

HOUDINI · VEX

The same published mathematics as a Detail Wrangle body. Paste it into a Wrangle with Run Over set to Detail; every constant is the published value plus a tweak channel, so Create Spare Parameters gives a slider that starts where the paper does.

// FORMA — PL. 52 · ERROR-DIFFUSION DITHERING — Robert W. Floyd & Louis Steinberg, 1976
//   quantise each pixel; pass the error on
//   ε → 7⁄16 →,  3⁄16 ↙,  5⁄16 ↓,  1⁄16 ↘
// Paste into a Detail Wrangle (Run Over: Detail), no inputs needed.
// Written from the published mathematics, not adapted from any code.
// Constants arrive at their published values. Press the node's Create
// Spare Parameters button and every tweak becomes a slider — starting
// at 0, the published figure, and moving in the constant's own units.
// https://forma-gen.com/#plate=errordiff

float p_grid = 100 + chf('grid_tweak');     // grid · live 60 .. 140
float p_lv   = 2 + chf('lv_tweak');         // tone levels · live 2 .. 4

// The plate's own colour: FORMA's COLOUR accent as a cosine ramp,
// brightest near t = 0 and t = 1, near-black around t = 0.5.
vector forma_ramp(float t){
  return set(
    0.46 + 0.5 * cos(6.28318530718 * (t + 0)),
    0.2002 + 0.2176 * cos(6.28318530718 * (t + 0.05)),
    0.3896 + 0.4235 * cos(6.28318530718 * (t + 0.1)));
}

// Floyd–Steinberg, the serial half of the atlas's dither pair: quantise
// each cell in scan order and push the rounding error onto the neighbours
// the scan has not reached — 7/16 right, 3/16 down-left, 5/16 down, 1/16
// down-right, the 1976 split exactly. Inherently sequential, which is why
// the plate has no shader tab and why this cook is a single ordered loop.
// One point per non-black cell, the plate's own tone-scaled ramp as Cd and
// the tone itself as Alpha.
//
// The source the plate dithers is a sine grating that rotates on the clock
// through the plate's own phase; a cook has neither, so the grating is
// frozen at a fixed oblique angle — 30°, so both diffusion axes participate
// — with the roll at zero. A staging decision on the record, as ripple's
// rain is: the mathematics is the diffusion, not the test card under it.
float ang = M_PI / 6.0;

int n = int(rint(p_grid));
int h = n;                        // the square cloth of a square card
int L = int(rint(p_lv));

float img[];
resize(img, n * h);
float co = cos(ang), si = sin(ang);
for (int y = 0; y < h; y++){
    for (int x = 0; x < n; x++){
        float u = float(x) / float(n), v = float(y) / float(h);
        img[y * n + x] = 0.5 + 0.5 * sin(6.283 * 1.5 * (u * co + v * si));
    }
}

// the one ordered pass that is the whole algorithm
for (int y = 0; y < h; y++){
    for (int x = 0; x < n; x++){
        int i = y * n + x;
        float q = rint(img[i] * float(L - 1)) / float(L - 1);
        q = min(1.0, max(0.0, q));
        float err = img[i] - q;
        if (x + 1 < n) img[i + 1] += err * 7.0 / 16.0;
        if (y + 1 < h){
            if (x > 0) img[i + n - 1] += err * 3.0 / 16.0;
            img[i + n] += err * 5.0 / 16.0;
            if (x + 1 < n) img[i + n + 1] += err * 1.0 / 16.0;
        }
        if (q <= 0.0) continue;   // the ground is the ink, not a point
        // canvas y runs down; negated so the grating leans as the plate shows it
        int pt = addpoint(0, set(float(x - n / 2), float(h / 2 - y), 0.0));
        setpointattrib(0, "Cd", pt, forma_ramp(0.86 + 0.2 * q) * q);
        setpointattrib(0, "Alpha", pt, q);
    }
}