157

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

  • 80
    This graphic makes my flat panel monitor flip out when I scroll. – hBy2Py Dec 8 '16 at 18:35
  • 18
    @hBy2Py My flat panel monitor flips out even when I'm not scrolling! – Thunderforge Dec 8 '16 at 19:52
  • 13
    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
  • 3
    @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. – Ross Ridge Dec 9 '16 at 19:05
  • 10
    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
148

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 = Array(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 = Array(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.

  • 15
    Welcome to Retrocomputing! Great first post! – JAL Dec 8 '16 at 5:21
  • 2
    Incidentally the dithering is still there in modern windows. If you happen to have a low-color monitor and video card you can see it. – Joshua Dec 8 '16 at 17:22
  • 4
    The basic 16 colour palette comes from CGA. Most precisely, from the CGA text mode. EGA could generate 64 colours and VGA, 262144 colours. – mcleod_ideafix Dec 8 '16 at 21:10
  • 4
    @mcleod_ideafix both EGA, and VGA in full resolution mode (640x480), only supported 16 colors on the screen at the same time. – Random832 Dec 9 '16 at 4:49
  • 4
    The palette is adapted from CGA text mode, but is not identical to CGA text mode's palette. You still have light colors and dark colors, with different intensities, but the precise colors are different. @mcleod Also, phyrfox, you have the gray colors reversed in your palette listing. #808080 is the dark gray and should go in column #1 with the dark colors; #C0C0C0 is the light gray (silver) and should go in column #2 with the light colors. This corresponds to the exact ordering of the default 16-color palette that Windows uses. – Cody Gray Dec 9 '16 at 5:08
29

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

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

def InitBayer(x, y, size, value, step,
              matrix = [[]]):
    if matrix == [[]]:
        matrix = [[0 for i in range(size)]for i in range(size)]

    if (size == 1):
        matrix[y][x] = value
        return

    half = size/2

    #subdivide into quad tree and call recursively
    #pattern is TL, BR, TR, BL
    InitBayer(x,      y,      half, value+(step*0), step*4, matrix)
    InitBayer(x+half, y+half, half, value+(step*1), step*4, matrix)
    InitBayer(x+half, y,      half, value+(step*2), step*4, matrix)
    InitBayer(x,      y+half, half, value+(step*3), step*4, matrix)
    return matrix

PNG images for the threshold matrix are located here:

https://github.com/tromero/BayerMatrix

15

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 #80 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 of greater than #80 then it would dither using a palette of the seven bright colours, plus #808080 and #000000.
  • 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
  • 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
  • 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
  • 1
    @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

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.