176

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:

Windows 3.1 Dithering Sample

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)?

15
  • 90
    This graphic makes my flat panel monitor flip out when I scroll. – hBy2Py Dec 8 '16 at 18:35
  • 19
    @hBy2Py My flat panel monitor flips out even when I'm not scrolling! – Thunderforge Dec 8 '16 at 19:52
  • 17
    Just reproducing the algorithm isn't quite enough - for real effect, you need to emulate the way the colours blended together on a CRT display too. Otherwise it's just ugly. The same is true for most CGA graphics, actually - they're mostly optimised for an NTSC display, exploiting the (many) flaws of the system to give vastly higher picture quality than would otherwise be possible (Yes, the "Never the same colour" display turns into "How did you do that with 4/16 colours?!"). – Luaan Dec 9 '16 at 14:18
  • 6
    @Luaan No, the original poster is talking about VGA level graphics, Windows 3.x doesn't support 16-colours on CGA cards.The VGA cards and monitors that were typically used with Windows 3.x didn't blend colours the way you describe. For that matter neither did actual CGA monitors, the ones that used the 9-pin digital CGA video connector. – user722 Dec 9 '16 at 19:05
  • 12
    The "flipping out" is because of LCD polarity inversion: every frame the polarity of each pixel is flipped to prevent burn-in damage. The cheaper the LCD circuitry the less likely the + and - voltages will properly match. See techmind.org/lcd for some test image patterns that demonstrate worst-case behaviour (major epilepsy alert). – Levi Dec 12 '16 at 6:20
169

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.

1
  • It would have been a good answer, if it were actually correct. This is not the algorithm Windows uses, and it’s obvious if you actually follow the advice in this answer. – user3840170 Mar 12 at 9:18
37

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

0
18

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.
5
  • 1
    Probably not coincidentally, 15-bit color is still an advanced display option in the Microsoft Remote Desktop connection Application. – Rowan Hawkins Dec 10 '16 at 21:00
  • 1
    There are 4 other specially cased colours on 256 colour mode, none of which are especially attractive. The matrix is 8x8, as can be seen in OP's screenshot. And lastly, the 50% shades are used in more cases than you suggest, e.g. #bf0000 is rendered as a mix of 50% and 100% red. – mm201 Jun 11 '18 at 21:01
  • 2
    @mm201 I actually managed to find the code I'd written over 20 years ago to reverse engineer the dither (this was before I knew about things like Bayer dithering). Should I ever understand again it I'll update my answer. – Neil Jun 11 '18 at 23:20
  • 1
    Mind if I ask how you found code from 20 years ago? Where was it stored for all these years? Surely it jumped around from medium to medium? – ecc Jun 13 '18 at 7:33
  • 3
    @ecc I would have originally written it during my lunch break at work on a Windows 3.1 PC. I then transferred it when it was replaced with a Windows 95 PC 20 years ago, and that PC had been knocking about the office for 20 years until we finally ditched it as part of an office move, but I copied that particular code from it because I thought it might help me refine this answer. – Neil Jun 13 '18 at 8:00
15

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 coordinates0 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 nearest0 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:

Worked example of Bayer dithering of #4db3ff (77, 179, 255) with the method described above, which results in a cross-hatch pattern of cyan (#00ffff) and light grey (#c0c0c0) in roughly 3:5 proportion, compared to how Windows actually dithers the colour, which combines 19× blue (#0000ff), 26× cyan (#00ffff) and 19× white (#ffffff).

The actual full algorithm is a bit more involved. The rough steps are:

  1. The RGB coordinates0 of the source colour are permuted so that the property R ≥ G ≥ B holds. The original order of coordinates is then remembered for later.
  2. 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, which are defined by points corresponding to select palette colours (#000000, #800000, #ff0000, #808000, #ffff00, #808080, #ffffff).
  3. 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.
  4. 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.
  5. 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.)
  6. Finally, a Bayer matrix is used to distribute the colours in an 8×8 pixel grid.

The complete algorithm 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.1 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.1 The US patent text even contains a C code sample (table 11), 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.1 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 &&.2

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.


0 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 gamma 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.

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

2 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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.