Palette Conversion Issues

Introduction

There are several aspects related to WAD conversion, one of which being the different structured palettes used by DOOM and Quake. Texture conversion has to be done based on matching colors, or finding approximations, and doing dithering if necessary. It might be possible that some, or perhaps even all, textures cannot be converted without detoriating heavily.

If you are not using a true color display, it is recommended to download these pictures and view them with a private colormap.

This is because the dithering or mapping to the standard colormap as done by a WWW browser will change the visual appearance a lot.

Palette matching

Here you will find a few pictures I made to illustrate the difficulties of using DOOM textures in combination with Quake textures.



The DOOM and Quake indexed color palettes, respectively. Both palettes use 18bit of possible 24bit, with 6bit per RGB component as handled by most DAC's on PC video boards. The DOOM palette (left) has 249 unique colors. the Quake palette (right) only 226 unique colors. Both use 16 color ramps and some 8 color ramps, and a couple of other colors. Note that at least 16 colors in the Quake qtest1 palette seem to be unused (all white).

The weighted RGB matches

Rob Shields and me did matches of the DOOM palette against the Quake palette, using different metrics in RGB space. We both used the best match, as given by

     sqr_dist =  sqr(  (cW_Red/cW_Norm)*(quake_Red   - doom_Red)) 
               + sqr((cW_Green/cW_Norm)*(quake_Green - doom_Green))
               + sqr( (cW_Blue/cW_norm)*(quake_Blue  - doom_Blue));
with cW_Norm = cW_Red*cW_Blue*cW_Green to normalize the weights. The idea behind the weights is that the human visual perception has different sensibility for red, green and blue, respectively, and matches should take this into account. In theory, a match should be calculated in CIE-space, or HSV or HLS space at least. I used the weights cW_Red = 2.0; cW_Green = 3.0, and cW_Blue = 1.0, which is a rough approximation of the common formulae used for mapping RGB to greyscale. This has been discussed in the comp.graphics.algorithms Newsgroup a couple of times, and should be in the c.g.a FAQ or the Colorspace FAQ already. A full discussion (that does not provide this guesstimate) can be found in



The left is the match using unity weights (RGB distance), the right one is the weighted match. It is obvious that the improvements are negligible. As are the problems we are facing: the green color ramp of the DOOM palette vanishes entirely, and the leftmost matches to nongrey colors will be disturbing. Pink and dark blue in the bottom row are lost completely as well. The white-to-blue ramp is only partly matched by Quake`s blue-to-black ramp, and so on.

Even worse, a lot of DOOM colors (namely reds, greys and browns) are mapped to the same Quake color. This means that texture details will be lost, which is worse than color shift or mismatch. I have created two PWAD files for download, with straight and with weighted match, that can be used with DOOM and will, in a way, convert the visual appearance to what it will look like in Quake. The 14 palettes have been matched separately, which is not the way to do it - it would be better to shift the Quake palette towards red (pain/berserk palettes), green (rad suit) or white (pickup) in HSV or HLS space. However, the converted palette demonstrates the deteoriation John Carmack talked about.

Global optimization

If you are going to use the PWAD files, you should take a close look at the green acid floor tiles. While DOOM's green colorramp is mapped to a grey one, the mapping seems to preserve the ramp structure, and thus the details of the texture are not lost. This means that our color-by-color matching might not be the best choice in order to preserve the artwork, while it does provide us the best match for each color.

This means that we have to do global combinatorial optimization, i.e. instead if minimizing the distance for each color separately, we have to minimize the sum of distances over all colors. This will give the same results, unless we include additional penalty terms that prohibit multiple use of the same color in the target palette, or fragmentation of color ramps. The problem of matching 256 colors to 256 colors in a 1 to 1 mapping looks a bit similar to the well-known Travelling Salesman Problem (TSP).

Thus we have to minimize an Energy or Cost Function. which is given by the sum of distance calculated using a metrics (in RGB or HSV space) as above, with single color matching. From the TSP we should borrow the idea of pairwise exchange, which is very efficient and guarantees a 1 to 1 mapping throughout the process if our intial mapping fullfills this condition, thus avoiding a penalization term and a free and somehow arbitray parameter. In consequence, we might use a straight stochastich local search, or Simulated Annealing, or some kind of simplification like Threshold Accepting.



This is the result of a local search run, with random seed, the best result of a couple of runs. It is available as PWAD, too. There seem to be quite a lot local minima, and a Simulated Annealing approach might improve things a bit.

As can be seen, the color ramp structure is not preserved. In addition, the many white colors in the qtest1 palette are an additional problem for an absolute 1 to 1 mapping. The latter will change with the final Quake palette, but the colorramps will not be preserved.

Prior to mapping entire colorramps, one might try to abandon pairwise exchange, and change only one color assignment in each step. In this case, we need to introduce a penalization for multiple use of the same Quake color, thus we will be able to fine tune the trade off between weighted RGB distance minimization over all colors and multi-usage penalty. However, I expect results to be worse: it will not preserve colormaps, and multiple use will deteoriate the textures.

Mapping colorramps

Our cost function as sketched above will not prevent fragmentation of colorramps. Preserving local neighborhood, i.e. finding a near-optimal mapping colorramps to colorramps is a bit more difficult. For each color, we need at least the left and right neighbour, or the information to which colorramp it belongs, and which other colors are included in the same set. There has to be some kind of reward for state transitions that decrease fragmentation, and some penalty for those changes that will map a DOOM color to a Quake color where the respective neightbours do not map. Note that this has to ignore whether these are left or right neighbours, as a colorramp might simply be reversed, but identical in the target colormap.

I am not yet sure how to handle this. The topographie preservation required reminds me of deterministic annealing techniques like Elastic Net and Tea Trader-like approaches, but appearances are deceptive.

Finally, the idea of mapping entire colorramps allows for a last resort: have an artist handle this manually, even on a per-image basis. However, as long as the Quake palette is not available, this is a waste of time.

Palette based Lighting

The color ramps correspond with the lighting, as can be seen in this overview of DOOM palette and 32 light level colormap combination (colors from left to right with ascending index, lighting from top to bottom, with descending light level):

It is not possible to create a similar lookup of the Quake color ramps, as the colormaps used by Quake qtest1 are part of the binary, and not in the PACK or WAD2 files. This has already changed; the shareware version will load its colormap lookups from the WAD file, like DOOM did.

Palette Dumps

I have done two simple ASCII dumps of the DOOM and Quake palettes. I will refine these with some matching against X11 RGB database color names, which will probably a bit more useful, and add additional info (like the color assignment to the players in DOOM).


home qdev qdev dread rsc qdev doom license web
home dEr95 r3D dread netrsc quake doom legal web
Author: B., email to bernd@nero.uni-bonn.de, with public PGP key
Copyright (©) 1995, 1996 by author. All rights reserved.
Source: $Id: palette.html,v 1.4 1996/06/16 23:56:53 b1 Exp $