I had spent quite a bit of time working on ways to get more colours out of the limited display system of the Atari ST/e platform. Good results were possible but the cost was nearly 100% CPU load, rendering the machine mostly incapable of doing anything else at the same time. Moving objects around the screen isn't really practical, leaving these high-colour techniques usable only for slideshows or perhaps point-and-click adventure games.
Often I had been asked if it would be possible to do something similar for use in games and I generally said no. But more recently I have been thinking about this question again. Partly because it's an interesting problem on its own, and partly because I noticed some odd things going on during tests while upgrading PCS5. In light of this, I have changed my mind and started figuring out a way to get some extra colours without the CPU load.
PCS makes use of a spread of techniques to increase perceived colour count.
- palette switching multiple times within a scanline
- palette switching between display fields
- bitmap switching between display fields
- colour averaging effects from field switching
- field interlace pattern to reduce field switch flicker
- special colour reduction/remapping methods which can compensate for colour error
Almost all of the CPU load is caused by the palette switching. If it were possible to somehow reduce the significance of the palette switching in favour of the other techniques, we'd be able to solve the CPU load problem. But that is quite a shift - the palette switching is generally responsible for all those extra colours...
While making improvements to PCS5 - specifically the field-error-diffusion system - I began to see some interesting side effects which I hadn't given enough attention. This system is responsible for lifting colour mapping errors from one field, and pushing them into the opposing field, in order that they properly 'average' to the intended colour. The most simplistic expectation is that the system will settle on two very nearby colours to simulate the intended colour. This diffusion process is repeated several times with varying influence, until a portion of the error settles into both fields at some 'global minima' for the entire image. Under normal circumstances, this is exactly what it does.
However, when the colour mapper gets under serious pressure - too many source colours and not enough palette switching to allocate them - interesting things begin to occur. The 'paired' colours from opposing fields responsible for simulating each pixel begin to diverge quite significantly. This seems reasonably obvious - but the interesting part is what happens as they diverge. The colours begin to pair more frequently with other, unrelated colours. This increases their statistical reuse in a nonlinear way, and permits the generation of many more colours through multiple re-pairings.
So I began to wonder if it would be possible to amplify this effect, and generate useful quantities of these 'magic pairs' within a single, 16-colour palette?
A simple search of the entire 12-bit palette space on STE versus a sample image would provide an answer. But do the math and you'll find the search takes quite a long time. Even the 9-bit palette is a pain to search (and it would be a shame to limit any solution to 9 bits!). Brute force works but it's going to take ages to actually do any useful experiments. Worse still, even if the search could be completed in a manageable time, any small changes to the cost of the search would cause it to baloon uncontrollably. I needed something more efficient.
So I developed a 'cryptographic' style search algorithm to 'break' palettes in the shortest possible time. The algorithm requires a source histogram which has already been minimised in various ways (gamma, quantization, population trimming) and a suitable cost function. The cost function is chasing several things at once but fundamentally it is looking for suitable colour pairings, trading divergence against accuracy. I set it up to run in parallel on multiple CPU cores in order to find a solution in minimum time. A solution can be generated for any source image in around 5 minutes on my desktop PC. The cost function operates on multiple axes because it needs to do more than find shared complementary pairs - it has to minimise other problems at the same time (such as interlace flicker).
Here are some early results from the experiment... between 32 and 64 colours can usually be resynthesized reliably. Occasionally up to 100. The samples shown use more than 100 colours to demonstrate extreme cases but a target of 64 colours is more reasonable for accuracy vs stability for the widest range of input. Effectiveness varies a lot, with some images working very well, most working well enough to be worthwhile, a few proving too difficult. I have drawn some conclusions on success rates and how to improve on them, which will follow.
The CryptoChrome-encoded image is on the left, the 16-colour (median cut in Paint Shop Pro) reference image is on the right.
Image displaying 121 distinct colours on STE (deinterlaced), with 0% CPU load...
Image displaying 126 distinct colours on STE (deinterlaced), with 0% CPU load...
Image displaying 107 distinct colours on STE (deinterlaced), with 0% CPU load...
Image displaying 122 distinct colours on STE (deinterlaced), with 0% CPU load...
CIE testcard displaying 98 distinct colours on STE (deinterlaced), with 0% CPU load...
Having got some decent results with static images, it's time to start worrying about moving images, because this really was the point to begin with. The technique relies on interlacing to average opposing colours and interlacing is problematic when used with movement, especially if the movement is a even integral of the interlace pattern. This problem is addressed using several methods at once.
- minimise differential luma significance within complementary pairs
- manage differential chroma significance within complementary pairs
- use special interlace patterns e.g. stochastic, or axis-specific, and assign to 'preshift' style display buffer manager
- make display manager aware of active field and interlace pattern in order to compensate for movement
This is the entire R-Type level #1 reduced to 63 colours (deinterlaced)... this is being used as the test tileset for one of the 50hz realtime STE examples.
Obviously these deinterlaced images don't indicate how flickery or stable or convincing the effect is on real hardware. I have been working on a demonstration which uses the technique with game playfield technology to show that it is in fact usable. Interlacing is always going to have its limits and there will always be source material or a purpose for which it just doesn't suit - but the aim here was to explore what might be possible and try to make something available for people to play with. I'm sure somebody with an idea and some determination can find a great way to use it!
2012 version...
A tool will be released soon which generates CryptoChrome-encoded palettes for arbitrary source images. It will probably be an extension to PCS5.
An STE demo will be released soon which demonstrates CryptoChrome-encoded graphics in a 50hz or 25hz scrolling playfield with sprites etc. and displaying significantly more than 16 colours. Full source will be provided.