Dithering

In February 1985 COMPUTE!’s Gazette explained to Commodore 64 owners how a new colour printer could print their screens. The Okimate 10 had a ribbon of only three colours, which it overstruck to make seven. To print the C64’s sixteen it used “a trick known as dithering”, Charles Brannon wrote. “Dithering places two colored dots side by side, rather than mixing them. From the right distance, a magenta dot next to a cyan dot looks like a fat purple dot. Television pictures work on a similar principle.”

That is the whole idea. A machine that can show only a few colours places dots of them close together, and the eye averages them into colours the machine cannot show. A checkerboard of black and white reads as grey; three dots of one colour to one of another reads as a shade between them, closer to the first. The rest is a matter of where to put the dots, and in the 1980s that was a choice between a fixed pattern, an algorithm that chased its own mistakes, and an artist’s hand.

Fast facts

• Principle: neighbouring dots of different colours blend in the eye into an in-between colour.
• Ordered dithering: compare each pixel with a fixed, repeating table of thresholds. Cheap, and it leaves a regular cross-hatched texture.
• Error diffusion: pick the nearest colour, then pass the difference on to the pixels not yet drawn. Smoother, but every pixel depends on the ones before it.
• Where it showed up: printer drivers, digitisers, paint programs’ fills, artists’ hand shading, and image converters.

Ordered dithering

An ordered dither uses a small square of thresholds, repeated across the picture like a tile. Hearn and Baker’s Computer Graphics sets out the rule. An n by n matrix holds the numbers 0 to n²−1. Scale the brightness of each pixel to the range 0 to n², look up the threshold for that pixel’s position, and turn the pixel on if the brightness is greater. The matrices most often used start from a 2×2 one and build larger ones from it:

2x2:        4x4:
0 2          0  8  2 10
3 1         12  4 14  6
             3 11  1  9
            15  7 13  5

Each 4×4 matrix is four copies of the 2×2 one scaled up, with the 2×2 pattern added on top, so the thresholds are spread as evenly as possible. In code, for a two-colour screen and a brightness from 0 to 16:

on = brightness > matrix[y mod 4][x mod 4]

A flat area of brightness 8 turns on exactly half the pixels in every 4×4 block, as a checkerboard; brightness 4 turns on a quarter, spaced evenly. Because the thresholds repeat, every area of the same brightness gets the same pattern, and a gradient comes out as a series of distinct textured bands. That regularity made ordered dithering easy to compute and easy to predict, which suited printers and screen dumps.

Error diffusion

Error diffusion takes the opposite approach. Work through the picture from left to right and top to bottom. For each pixel, choose the nearest colour the machine has, work out how far that was from the colour wanted, and add that error to the neighbours not yet drawn. A pixel that was rounded down makes its neighbours more likely to be rounded up, so the average comes out right.

The best-known weights are Floyd and Steinberg’s, published in 1976. Hearn and Baker give them as seven sixteenths of the error to the pixel on the right, three sixteenths below left, five sixteenths directly below and one sixteenth below right:

       X    7
  3    5    1      (sixteenths of the error)

The pattern this makes is irregular, so it hides the banding of an ordered dither, but it costs more: every pixel needs arithmetic, and a working copy of the image has to hold values above and below the displayable range. Commodore offered both in the Amiga’s printer settings. The Preferences program in Workbench 1.3 let users choose “Ordered”, “Halftone” or “F-S”, and the manual warned that Floyd–Steinberg “incurs an approximate 2:1 speed penalty when printing”.

By hand: the Amiga artists

Paint programs could dither automatically, and by 1988 reviewers expected them to. ACE counted the lack of “dithered fills and shading” as the greatest limitation of the Atari ST program Quantum Paint. But the artists who drew games often preferred to place the dots themselves. In Amiga Format’s “How to DPaint” feature in 1992, Bullfrog’s Paul McLaughlin warned that “you can create a picture using dithered fills, perspective, the works, but it will show”. Domark’s artists said “it is often better to dither and shade things by hand”, especially where contrast is high. Psygnosis’s Jeff Bramfitt complained that Deluxe Paint’s Gradient Fill had “only a random dithering option, no ordered method”, so a background filled with it could “look strange”.

The same feature treated dither as texture as well as colour: “varying the amount of dither can change how granular or rough a surface looks … More dither equals rougher, while less means smoother.”

How much an Amiga picture needed dithering depended on its mode. The Denise chip shows up to 32 colours in low resolution and 16 in high resolution, from a palette of 4,096. Extra Half-Brite doubles that to 64 with darker copies of the 32, and hold-and-modify can show all 4,096 at the cost of fringes where colours change sharply. A 16-colour game screen had to fake most of its shades.

The Commodore 64

The C64 has 16 fixed colours, and its bitmap modes ration them by area. Commodore’s Programmer’s Reference Guide gives the standard bitmap mode “a choice of 2 colors in each 8-dot by 8-dot section”, and the multicolour bitmap mode “up to four different colors in each 8 by 8 section”, one of them the background shared by the whole screen, at half the horizontal resolution. A dither can only mix the colours a cell already has.

Dithering reached C64 owners early through hardware. Besides the Okimate’s screen dump, Ahoy! reported in December 1985 a $39.95 video digitiser kit from Kinney Software that used “an alternate dot pattern technique (dithering)” to show six and eight levels of grey.

Error diffusion came to the machine itself with image converters. In 2000 Adrian Gonzalez described in C=Hacking how his renderer for Stephen Judd’s C64 JPEG decoder applied Floyd–Steinberg dithering, measuring each pixel’s error against a table of RGB values for the 16 colours. (His diagram swaps the three and the one sixteenth, a mirror image of the usual weights.) The hard part was the cell rule. Multicolour bitmap mode allows “up to 3 different colors out of the C64’s 16 colors plus one background color common to all cells”, which Gonzalez called “a very tough choice for displaying true color images”, so the renderer targets IFLI, the interlaced form of FLI, where “the IFLI image itself takes up half the c64’s memory!”

The ZX Spectrum

The Spectrum keeps colour for each 8×8 cell, not each pixel: one ink and one paper colour per cell, from eight colours with a brightness bit, fifteen distinct colours in all. A dither on the Spectrum is a pattern of ink and paper pixels inside a cell, so it can blend only those two colours, and a pattern that crosses into the next cell takes that cell’s colours instead. See Colour Clash.

See also

• Colour Clash
• Pixel Art
• Deluxe Paint
• Denise
• VIC-II
• Character Graphics