What algorithm did Microsoft use to dither colour in early versions of Windows?

Question

In the late 1980s to mid 1990s, most consumer-class video hardware was not capable of displaying greater than 16 colours at a time. To create the illusion of greater colour, software often "blended" solid colours by placing single pixels of two or more colours close together. On older CRT monitors from a distance, the dither pattern appeared as close to a solid colour as achievable. Note how patterns could either be 50-50 of two colours, or combinations of three or more solids:

I am creating a retro-themed game and am seeking to reproduce this same dithering appearance Microsoft used in early versions of Windows. However, I cannot find any information/documentation on the algorithm or method they used to achieve this unique look. My end goal is to create a function that accepts RGB components, a box area size, and N solid colours...and outputs a pattern creating a new dithered colour appearing as Windows 3.x would display it.

My question is, what algorithm did they use to combine Red, Green, and Blue components into these dithered patterns, all while assuming a base of N solid colours (in this case, the 16 standard VGA colours)?

Answer 1

Basically, Windows used the basic 16-color CGA palette, which included 4 shades of monochrome, and 12 basic colors (two each of red, green, blue, yellow, purple, and teal), which later formed the basis of the "web safe palette" that became popular during the early days of the Internet.

The algorithm used back then was known as the Bayer dithering technique, otherwise referred to as ordered dithering. The basic idea was to generate a grid of threshold values in a mathematical arrangement that favors nearly consistent values equal distances from each other, which is what produces the cross-hatch effect.

This article basically describes the pseudocode algorithm:

Threshold = COLOR(256/4, 256/4, 256/4); /* Estimated precision of the palette */
For each pixel, Input, in the original picture:
Factor  = ThresholdMatrix[xcoordinate % X][ycoordinate % Y];
Attempt = Input + Factor * Threshold
Color = FindClosestColorFrom(Palette, Attempt)
Draw pixel using Color

And they also included some example source code written in PHP:

<?php

/* Create a 8x8 threshold map */
$map = array_map(function($p) {
    $q = $p ^ ($p >> 3);
    return (
        (($p & 4) >> 2) | (($q & 4) >> 1) |
        (($p & 2) << 1) | (($q & 2) << 2) |
        (($p & 1) << 4) | (($q & 1) << 5)
    ) / 64.0;
}, range(0, 63));

/* Define palette */
$pal = [
    0x080000, 0x201A0B, 0x432817, 0x492910,  
    0x234309, 0x5D4F1E, 0x9C6B20, 0xA9220F,
    0x2B347C, 0x2B7409, 0xD0CA40, 0xE8A077,
    0x6A94AB, 0xD5C4B3, 0xFCE76E, 0xFCFAE2
];

/* Read input image */
$srcim = ImageCreateFromPng('scene.png');
$w = ImageSx($srcim);
$h = ImageSy($srcim);

/* Create paletted image */
$im = ImageCreate($w,$h);
foreach ($pal as $c)
    ImageColorAllocate($im, $c >> 16, ($c >> 8) & 0xFF, $c & 0xFF);

$thresholds = [256 / 4, 256 / 4, 256 / 4];

/* Render the paletted image by converting each input pixel using the threshold map. */
for($y = 0; $y < $h; ++$y) {
    for($x = 0; $x < $w; ++$x) {
        $map_value = $map[($x & 7) + (($y & 7) << 3)]; 
        $color = ImageColorsForIndex($srcim, ImageColorAt($srcim, $x,$y));
        $r = (int)($color['red']   + $map_value * $thresholds[0]);
        $g = (int)($color['green'] + $map_value * $thresholds[1]);
        $b = (int)($color['blue']  + $map_value * $thresholds[2]);
        /* Plot using the palette index with color that is closest to this value */     
        ImageSetPixel($im, $x,$y, ImageColorClosest($im, $r,$g,$b));
    }
}

ImagePng($im, 'scenebayer0.png');

Basically, the entire thing was dreamed up by Bayer, and this algorithm dominated the market during the 4-bit era of computer graphics.

You can read more about ordered dithering from DITHER.TXT, which basically explains different algorithms and sample implementations.

Note that your source images should be in full 256 color or better, and your palette should consist of these colors:

#000000 #808080
#800000 #FF0000
#008000 #00FF00
#808000 #FFFF00
#000080 #0000FF
#800080 #FF00FF
#008080 #00FFFF
#C0C0C0 #FFFFFF

Always dither from a full-color image, otherwise it'll probably look even worse than you intended. Dithering in realtime is trivial for modern systems, as even classic 33mhz systems that ran Windows had no trouble implementing the Bayer dithering pattern.

Answer 2

The other answers already mention that the algorithm is based on an 8×8 Bayer matrix. But that’s not the whole story.

Most how-to guides to colour Bayer dithering, like the one cited in @phyrfox’s answer will have you perturb the colour’s RGB coordinates⁰ uniformly by the amount specified in the dithering matrix’s cell (scaled to the precision of the target palette), and then rounded off to the nearest⁰ colour in the palette. But if you try it, you’ll notice that’s not what actually happens in Windows. Here’s an example with the colour whose coordinates appear in the screenshot in the question:

The actual full algorithm is a bit more involved. It can be found in the Windows 3.1 Device Developer’s Kit, in a file named dithers.asm (appearing there in several copies, with the source code of display drivers). Unfortunately, since it’s written in assembly, it’s a bit hard to follow (especially that it relies on some preconditions set up in routines located in other files), plus blithely copying Microsoft’s code could have you accused of copyright infringement.¹ The top of the file names the author as Günter Zieber and promises that the algorithm ‘will be commented and described in some detail in a few days’. However, tough luck trying to find this description in the DDK.

But indeed this promise was eventually fulfilled – although somewhere completely different. Searching for the author’s name reveals U.S. patent 5485558, also filed as in Canada as CA2064074A1 and in Europe as EP0484509A1. All those patents have expired in the last decade or sooner, so you should not be worried about getting sued for reading them.¹ The algorithm described is as follows:

0. The RGB coordinates⁰ of the source colour are permuted so that the property R ≥ G ≥ B holds. The original order of coordinates is then remembered for later.
1. The coordinates are scaled from the range [0, 256) into [0, 64] and further classified into one of four non-overlapping tetrahedra in RGB space, defined by points corresponding to select palette colours:
   • #000000, #800000, #808000, #808080
   • #800000, #808000, #808080, #ff0000
   • #808000, #808080, #ff0000, #ffff00
   • #808080, #ff0000, #ffff00, #ffffff
2. The RGB coordinates of the dithered colour are converted into scaled barycentric coordinates over the vertices of the tetrahedron chosen in the previous step. Those latter coordinates are then taken as weights/proportions in which the corresponding colours will be taken.
3. The bits of the RGBI values of chosen colours are shuffled back to agree with the original order of RGB coordinates of the source colour.
4. The list of chosen colours is sorted in order of increasing intensity. (This step doesn’t seem strictly necessary; I assume it is meant to prevent awkward discontinuities when colours transition from one equivalence class to another.)
5. Finally, a Bayer matrix is used to distribute the colours in an 8×8 pixel grid.

The US patent text even contains a C code sample (table 14), which is much more readable than assembly, and as US patent texts themselves are usually uncopyrighted, you should be able to plagiarise that one with impunity.¹ The input colour is passed as 8-bit numbers in the variables R, G and B, while the output is returned in the output array containing packed 4-bit IBGR values (1 = red, 2 = green, 4 = blue, 8 = intensity). Although to actually use the code you will have to apply some corrections:

• In the matrix multiplication code, the tempG and tempB variables should be swapped;
• The final row of the transformation matrix for subspace 3 should be { 1, 0, 1} and not { 1, 1, 1};
• The colors array in MakeColorCntTable should contain 3s where it has 2s;
• There are also a number of trivial issues like missing declarations, an omitted comma, and a logical operator spelt and instead of &&.²

Additionally, as mentioned by @Neil, Windows special-cases the otherwise-unused solid light-gray colour to be returned for #c0c0c0 instead of a cross-hatch pattern of dark gray (#808080) and white (#ffffff). The patent does not mention this at all and does not replicate the behaviour in the code sample. But otherwise, this is the exact same algorithm that appears in the DDK, and the one built-in Windows drivers use.

---

⁰ Those knowledgeable about colour reproduction should immediately ask: which RGB coordinates? If you want to know what does this even mean and why it matters, read up on gamma. I am telling you about this because I really hate you.

To clarify: although the # notation is usually understood as specifying colour coordinates in sRGB space, all colour specifications in this post should be understood to be in linear RGB space. This assumption is necessary to make the dithering algorithm gamma-correct.

¹ Probably. I’m just a language lawyer, not a regular lawyer.

² Also, it doesn’t quite adhere to current best practices of writing C, as it uses global variables to pass values between functions, and doesn’t declare them static. But fixing that is not necessary to make the code work at all.

Answer 3

As @phyrfox mentions, it is ordered dithering using a Bayer matrix.

I recently was trying to find a 16×16 Bayer matrix (256 discrete values) but all the ones I could find were 8×8 max, so I derived the algorithm. It's actually a pretty simple recursion: (Python)

def InitBayer(size, value=0, step=1):
    matrix = [[0 for _ in range(size)] for _ in range(size)]
    
    def recurse(x, y, size, value, step):
        if size == 1:
            matrix[x][y] = value
            return
        
        half = size // 2
        for (xd, yd) in ((0, 0), (half, half), (half, 0), (0, half)):
            recurse(x + xd, y + yd, half, value, step * 4)
            value += step
    
    recurse(0, 0, size, value, step)
    return matrix

PNG images for the threshold matrix are located here:

https://github.com/tromero/BayerMatrix

Answer 4

As I recall, the Windows code did have some special cases.

• If you asked for #C0C0C0 you would of course get solid #C0C0C0. This was a special case; if you asked for #BFBFBF then you would get a chequerboard dither using #808080 and #FFFFFF.
• The dither used an 8×8 matrix, so it would only approximate 18-bit colour.
• If all channels had a value of 128 or less then it would dither using a palette of the seven dark colours and #000000. (However, it was still only 18-bit colour, so it jumped two pixels at a time.)
• If at least one channel had a value greater than 128 then it would dither using a palette of the seven bright colours, plus #808080 and #000000.