7

I am trying to write a program in C# that will re-create the type of dithering used in many of the old Sierra and LucasArts games. I have looked up many different dithering algorithms and none seem to be right. It is very simple. It should produce a grid of alternating colors to mimic 256 colors using only 16. Everything is in a square format.

I have been trying to use the AForge.NET AForge.Imaging.ColorReduction library and I can't get it quite right. I believe the class I want is: OrderedColorDithering. I've been using that and tweaking the ThresholdMatrix.

There is sort of a tool that does this inside of SCI Companion, but it's too limited for what I want to do.

Here is an example: Two versions of a screenshot of Sierra’s The Colonel’s Bequest, with the protagonist standing next to a statue in front of the mansion; the original, dithered version and in ScummVM’s undither mode.

I have implemented the code from ScummVM (this is snipped from inside x,y loop):

col = bmp.GetPixel(x, y);

int closeCol = FindNearestColor(VGACols, col);
if ((closeCol & 0xF0) > 0)
{
    closeCol ^= closeCol << 4;
    closeCol = (((x ^ y) & 1) > 0) ? closeCol >> 4 : closeCol & 0x0F;
}

if (closeCol < VGACols.Length)
    outBmp.SetPixel(x, y, VGACols[closeCol]);

Using this palette (VGA 256 color mode 13h):

VGACols[] = {
    "#000000", "#0000AA", "#00AA00", "#00AAAA", "#AA0000", "#AA00AA",
    "#AA5500", "#AAAAAA", "#555555", "#5555FF", "#55FF55", "#55FFFF",
    "#FF5555", "#FF55FF", "#FFFF55", "#FFFFFF", "#000000", "#101010",
    "#202020", "#353535", "#454545", "#555555", "#656565", "#757575",
    "#8A8A8A", "#9A9A9A", "#AAAAAA", "#BABABA", "#CACACA", "#DFDFDF",
    "#EFEFEF", "#FFFFFF", "#0000FF", "#4100FF", "#8200FF", "#BE00FF",
    "#FF00FF", "#FF00BE", "#FF0082", "#FF0041", "#FF0000", "#FF4100",
    "#FF8200", "#FFBE00", "#FFFF00", "#BEFF00", "#82FF00", "#41FF00",
    "#00FF00", "#00FF41", "#00FF82", "#00FFBE", "#00FFFF", "#00BEFF",
    "#0082FF", "#0041FF", "#8282FF", "#9E82FF", "#BE82FF", "#DF82FF",
    "#FF82FF", "#FF82DF", "#FF82BE", "#FF829E", "#FF8282", "#FF9E82",
    "#FFBE82", "#FFDF82", "#FFFF82", "#DFFF82", "#BEFF82", "#9EFF82",
    "#82FF82", "#82FF9E", "#82FFBE", "#82FFDF", "#82FFFF", "#82DFFF",
    "#82BEFF", "#829EFF", "#BABAFF", "#CABAFF", "#DFBAFF", "#EFBAFF",
    "#FFBAFF", "#FFBAEF", "#FFBADF", "#FFBACA", "#FFBABA", "#FFCABA",
    "#FFDFBA", "#FFEFBA", "#FFFFBA", "#EFFFBA", "#DFFFBA", "#CAFFBA",
    "#BAFFBA", "#BAFFCA", "#BAFFDF", "#BAFFEF", "#BAFFFF", "#BAEFFF",
    "#BADFFF", "#BACAFF", "#000071", "#1C0071", "#390071", "#550071",
    "#710071", "#710055", "#710039", "#71001C", "#710000", "#711C00",
    "#713900", "#715500", "#717100", "#557100", "#397100", "#1C7100",
    "#007100", "#00711C", "#007139", "#007155", "#007171", "#005571",
    "#003971", "#001C71", "#393971", "#453971", "#553971", "#613971",
    "#713971", "#713961", "#713955", "#713945", "#713939", "#714539",
    "#715539", "#716139", "#717139", "#617139", "#557139", "#457139",
    "#397139", "#397145", "#397155", "#397161", "#397171", "#396171",
    "#395571", "#394571", "#515171", "#595171", "#615171", "#695171",
    "#715171", "#715169", "#715161", "#715159", "#715151", "#715951",
    "#716151", "#716951", "#717151", "#697151", "#617151", "#597151",
    "#517151", "#517159", "#517161", "#517169", "#517171", "#516971",
    "#516171", "#515971", "#000041", "#100041", "#200041", "#310041",
    "#410041", "#410031", "#410020", "#410010", "#410000", "#411000",
    "#412000", "#413100", "#414100", "#314100", "#204100", "#104100",
    "#004100", "#004110", "#004120", "#004131", "#004141", "#003141",
    "#002041", "#001041", "#202041", "#282041", "#312041", "#392041",
    "#412041", "#412039", "#412031", "#412028", "#412020", "#412820",
    "#413120", "#413920", "#414120", "#394120", "#314120", "#284120",
    "#204120", "#204128", "#204131", "#204139", "#204141", "#203941",
    "#203141", "#202841", "#2D2D41", "#312D41", "#352D41", "#3D2D41",
    "#412D41", "#412D3D", "#412D35", "#412D31", "#412D2D", "#41312D",
    "#41352D", "#413D2D", "#41412D", "#3D412D", "#35412D", "#31412D",
    "#2D412D", "#2D4131", "#2D4135", "#2D413D", "#2D4141", "#2D3D41",
    "#2D3541", "#2D3141", "#000000", "#000000", "#000000", "#000000",
    "#000000", "#000000", "#000000", "#000000"
}

The dithering style looks correct; it just doesn't use the right colors. I've cross-referenced my palette and it does appear to be the correct 256 color palette. Any additional info would be appreciated.

11
  • 3
    Might to add information about the pictures shown? What hardware, are they examples of your work? Also, the question is the way it is formed rather borderline. You might want it to make more about the original games than modern development to keep it on topic.
    – Raffzahn
    Jan 10, 2019 at 9:51
  • 1
    If none else works you can try mine dithering by known color palete its very basic so it might create artifacts ...
    – Spektre
    Jan 10, 2019 at 10:24
  • Color QuickDraw on early-90s Macintosh did a nice job dithering images down to 16 colors. It's not a ready-to-go solution, and the source code might not be available, but perhaps that can point you in the right direction.
    – DrSheldon
    Jan 10, 2019 at 15:49
  • Maybe my arithmetic is askew, but I make it that there are around 10 billion billion billion of selecting a 16-colour palette from a potential set of 64 — that's 64!/48!. So picking the colour palette is probably the majority of the battle, especially considering how difficult it is to pin down a measure for similarity of colours to allow reasonable vector quantisation (or similar). compuphase.com/cmetric.htm takes a decent stab at similarity, at least.
    – Tommy
    Jan 10, 2019 at 17:26
  • @Tommy IIRC the default EGA/VGA palettes both 16 and 256 color was created for better dithering results ... the idea on pallete is to have each of the primary colors and possibly some shades to limit the number of pixel where the color need to bleed...
    – Spektre
    Jan 10, 2019 at 17:37

2 Answers 2

10

SCI games support dithering using any pair of EGA colours; each individual scene can use up to four palettes of forty colours (one at a time). When dithering, colours are alternated horizontally and vertically; this means that there are 120 unique dithered variants from a colour perspective, plus the sixteen base colours, but in some cases the order will be important so all 256 values can be useful.

The way these are encoded is as follows, at least as re-implemented in ScummVM:

  • the base colours are represented using their standard values, between 0 and 15 inclusive;
  • dithered colours, considered as a byte, are exclusive-ored with themselves shifted left by four; the alternating colours are respectively the lower nibble of the result shifted right by four, and the lower nibble of the result.

So for example, colour 215 results in alternating colours 10 and 7.

8
  • So they still take two screen pixel to represent one colour. But the palettes are not made up from a larger 256 colour, but created from what the base colours allow? So more of a reverse creation process when drawing the picture, right?
    – Raffzahn
    Jan 10, 2019 at 15:55
  • 3
    Right, they use two pixels for a single colour (or rather, the rendering algorithm determines which of the two colours is appropriate for a given pixel, so you can technically draw a single pixel with a dithered colour — but that’s hair-splitting and you wouldn’t do that when drawing the artwork). I get the impression from looking at presentations by the artists of the time, that they worked up from the constituent colours rather than down from a larger colour space (which would have been hard to work with anyway, at least on PCs before VGA), so yes, more of a reverse creation process. Jan 10, 2019 at 16:33
  • I've got to admit I'm confused by the inclusion of the XOR step; this is a digression since it's more like 'why did they do this' than 'what were they doing', but have you any idea what is achieved with that extra bit of processing? Is it something to do with using the same colour information more widely than merely in EGA mode?
    – Tommy
    Jan 10, 2019 at 16:45
  • 1
    @Raffzahn I think I'm still failing to comprehend an important element — I don't presently understand why you wouldn't just say that e.g. the stored colour resolution is 256 colours, in EGA mode 0xab will be output as 0xa next to 0xb in a chequerboard, in VGA colour 0xab will be a blend of EGA colours 0x and 0xb. I suspect you're somehow avoiding the reduction of VGA to 128 colours, hence the "in some cases the order will be important so all 256 values can be useful", but I don't see how storing as 0x(a^b)b rather than 0xab achieves that. Oh well. Not important to the real question.
    – Tommy
    Jan 10, 2019 at 17:05
  • 3
    @tommy I think the reason is so that first 16 values can represent the undithered colours, while still allowing the upper nibble colour to be colour 0 (black). In other words, 0x0*b* means undithered b while 0xbb means b dithered with colour 0.
    – user722
    Jan 16, 2019 at 1:41
1

Preface, this is not an authorative answer, just from rough memory.


As far as I remember, they used different techniques. For most parts it was a modified colour scheme:

  • All Rendering was based on pixel pairs
  • With basic colours they are just that colour
  • Diverging colours are made from one pixel of the (closest) base colour and on modifier
  • Modifiers where
    • The 'other' colour version (the bright for dim and vice versa)
    • Black
    • Dark Grey
    • Light Grey
    • White
  • Position of colour and modifier where swapped between lines

So basically this resulted in a bit less than 74 colours, not 256.

And of course, every background was manually modified to fit best :)

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .