3

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 Lucas arts 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.

AForge Dithering

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: enter image description here

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"

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

You can download my full program source here (it does some other cool dithering stuff that does work.)

Download full C# source and binary

  • 1
    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 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 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 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 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 at 17:37
6

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.

  • 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 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. – Stephen Kitt Jan 10 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 at 16:45
  • @Tommy I'd see that as an algorithmic way to calculate the two colour numbers - the same coule be archieved by using a look up table I guess. – Raffzahn Jan 10 at 16:55
  • 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 at 17:05
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 :)

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.