256 colors - an absolute limit?

As a matter of interest - is it theoretically possible, without a major programmatical procedure, to expand Doom's palette from containing 256 colors, to contain 384 or 512?

Anyone who's edited Doom for an extended period have time have bumped heads against the palette limitations after a while - the "too brown" critique is age old. I'm supposing the answer to this question is "no" but I'm curious if anyone out there has any light to shed on the matter?

By now, several ports have explored ways to expand the color gamut on screen, e.g. Mocha Doom, Doom in True Color, and even the original Doom Alphas had a HiColor mode, and I'm sure there have been/will be others.

The only "problem" with these approaches, is that the graphical resources remain 8-bit, 256 colors themselves, as does the base palette. You get more colors on screen due to extended and smoother lighting/shading/palette/colorizing effects, but none of them truly supports e.g. sprites with 512 (9-bit) distinct colors or at least sprites and textures with a different 256-color palette (as the developer of Mocha Doom, I'd say the latter is easier to do). For one, there's the practical problem that resources with more than 256 colors don't exist, as don't standardized formats (I never heard of e.g. a 16-bit 64K color extension to the sprite and texture/flat formats).

Even if e.g. I try pulling this on a whim, it will probably be a one-trick pony supported only by my port, that none else will be willing to follow. And yes, the "programmatical procedure" to do that is quite extensive: Doom's rendering and resource functions are all designed/assume that you're working with 8-bit color LUTs. They can be expanded to assume that you're working with 16-bit LUTs or 16-bit/32--bit direct color data instead, but then you'll have to change the way the lighting system works, too. It can be done (has been partially done in Mocha Doom, at least), but I'm not sure it's worth it. Most people seem to like the "gritty" look of the software renderer anyway, and reception of extended color ports has been lukewarm, at best.

Now, source ports with hardware acceleration/rendering could in theory load true-color textures/resources, though I don't know of any that actually does that. At most they can support true-color skyboxes, I think.

Doom's native picture format uses a single byte per pixel. As you probably know if you've used computers a lot, a byte has 256 possible values -- no more, no less. So even if a palette could have more than 256 colors in it, the images would only be able to reference the first 256 colors of the palette anyway.

There are other picture formats out there, though. It's possible to use PNG images, which can be in truecolor (palette isn't used, instead each pixel is described by its color in 32-bit RGBA format) or paletted, but using its own palette instead of the game's global palette.

Problem is that when you do this, you need the renderer to support colors outside the game palette as well. ZDoom for example supports PNGs, but if you use colors outside the palette, they'll be replaced by their closest match in the palette. Gives results like cyan turning into gray. On the other hand, GZDoom gives truecolor rendering.

The "Holy Grail" of software renderers is to make one that can support more than one palette on the same screen. In theory it can be done in Mocha Doom, but it would require some serious hacks in order to keep tabs on two or more distinct colormaps (one for each different palette).

Some ports like _bruce_'s Chocolate Doom branch use full-frame processing and blow all graphical resources up to 32-bit for supporting true color, but this comes at a considerable CPU overhead. The multiple LUT/COLORMAP method I use in Mocha Doom is way faster, but very complicated to follow, and starts eating memory very quickly if you start cranking up the number of colors and/or start using multiple palettes.

And of course there's the problem of setting STANDARDS to do these things....maybe a PLAYPALx lump where x=0,1,2,3,4,5 ..... and another lump (MULTIPAL? SPRPAL? TEXPAL?)where you can instruct that specific sprites and textures are to use a specific PLAYPALx lump?

I've been using standard png images in GZDoom without them losing any quality. seems like its a great port to use for the engine of a new game.

jmickle66666666 said:

I've been using standard png images in GZDoom without them losing any quality. seems like its a great port to use for the engine of a new game.

Well, that's one of the perks that come with using OpenGL or any form of hardware acceleration -since you have to convert the lighting and color system to something else entirely anyway, you can afford to support stuff like this -check it out, most of the rendering code in such ports is heavily rewritten.

With a software renderer however, you actually have to emulate (!) some aspects of a hardware renderer in order to support more than 256 colors, and that means pretty much rewriting major portions of the rendering code from scratch, something very few people are willing to do, especially when you can keep Doom's code almost as-is and it will work out-of-the-box. As you said, the only "standard" so far is the use of PNG images rather than Doom's sprite format (or an extension thereof), but supporting truecolor is different than just supporting more indexed colors.

Well, there are a hell of a lot of useless colors in Doom's palette. Several identical duplicates, and a whole lot of near-identicals that can be replaced with no ill effect. So if you're willing to remap some of the IWAD graphics you can squeeze a few new color ranges in there.

Maes said:there's the practical problem that resources with more than 256 colors don't exist

Yeah, it is in the interest of rectifying this that I enquire. When starting out on a new texture set for Doom, however modest, it helps to at least scratch that "missing colours" itch first.

And yes, I much prefer the software renderer over the millions-more colour applying engines that use anti-aliasing and such to create new gradients between entries in the existing index. The 16+ bit renderers just don't add new source colors though, and I would need those if I was to add anything truly new to Doom's textures and sprites...

The good old palette will do just fine, but an additional 256 color "companion palette", where you could define a few new source gradients, would be heaven. Emerald greens, deeper reds, a steely light-blue gray range, etc.

If I had the facilities (I'm a mapper/graphic artist, not a coder), I guess I'd pursue the 9-bit grail approach... 512 colors is still manageable, from the perspective of a per-pixel, pixel artist.

Gez said:GZDoom

The mentioned PNG-support i GZDOOM sounds interesting, but is there a way to turn off the anti-aliasing/softening of the textures in GZDOOM, to get hard-edged pixels like that of a software renderer? The pixel-softening effect tends to remove the capability for pixel-perfect texture alignment, as top and bottom pixels typically blend over to each other while being smoothed - losing that signature hard edge of a sector game. You can also get artefacts with GZDOOM's renderer (unles you map specifically around it), like mid-textures showing half a pixels worth of opaque color, where the transparent space borders to a solid pixel.

EDIT:
@esselfortium: Making replacements for the original contents is always going to be a minefield... and does create additional compatibility issues with your new content... I'm trying to avoid that. In theory anyway.

Soundblock said:

the 9-bit grail approach...

Either you use a new planar format (and nobody uses planar formats anymore, outside of the die-hard Amiga community) or you need to use two bytes per pixel anyway, it's just that seven of the second byte's eight bits will be unused. (I suppose you could use them to store alpha, though. 512 palette colors and 128 levels of transparency, seems decent enough I guess.)

It's moot though because there are no such format in existence. Also, it would require a truecolor engine anyway because you'd need to convert the image to an existing bitmap format (8-bit paletted or 32-bit RGBA) to get it displayed on the screen, even if the software side works with your new format.

Soundblock said:

The mentioned PNG-support i GZDOOM sounds interesting, but is there a way to turn off the anti-aliasing/softening of the textures in GZDOOM, to get hard-edged pixels like that of a software renderer?

Yes.

Go there and set texture filter to none or none (nearest mipmap). If your hardware supports GLSL, you will also want to go here and set sector light mode to software.

oh excellent, i didn't know about the software light mode, gonna check it when i get back

first thing i do when setting up any source port is setting nearest neighbour filtering

I don't know if any platform, ever, used an indexed/LUT graphics subsystem with more than 8 bits, to be honest (the Amiga's "12-bit" HAM mode doesn't count, as it doesn't allow setting pixels to arbitrary color). At 9 bits, you already start considering using a RGB (3-3-3) format, and if going beyond 8 bits means wasting another byte, as a minimum, then you DEFINITIVELY want to go full-blown HiColor (non-paletted).

Also, with large palettes, other things would have to grow larger, too: e.g. transparency/translucency blending tables would have to be 512 x 512 (x 9 bits) now, colormaps would need to grow in size etc. and again, you'd be tempted to move to full HiColor instead (10-bit or 12-bit LUT? no thanks).

8 bits is really the "sweet spot" for indexed graphics. Beyond that, it loses its main computational advantages, and doesn't look as good as full RGB approaches.

pardon my lack of knowledge of the subject, but for a few months I'd wondered why since Doom doesn't load graphics that aren't being displayed in the player's field of view, it doesn't do the same for colors?

As in a larger range of red could be used if, for example, there was no blue visible on the screen. But I guess that would encourage people to design their levels with as little color as possible to expand the depth of one color in particular, which might make for some boring level design.

That means it would lock/crash when more than 256 colours are on screen at once. That would end up limiting through practicality the use of colours than just sticking with a standard set of 256.

Basically, you'd need a truecolor renderer to make the image, and then you'd need to process it to quantize it down to 256 colors on the fly.

It's perverse. If you have a truecolor renderer, you don't cripple it by wasting processing time to dumb it back down to 256 colors. Especially not with a dynamic palette.

Another Game project I have has had similar questions. These are the answers derived which could apply to the Doom engine. That project is moving away from a palette centered definition, to an RGB centered approach with allowance for using palette based implementations for some hardware.

1. Multiple palettes are possible in Doom. The problem is which to use at a particular time.

2. The wad may specify additional palettes, giving each a name.
This would be a Doom lump with a table of RGB values, in the same format as the wad default palette.
These lumps could have a name system, but it would be more useful to have them within Palette START END markers.

2a. There shall be no LUT in the wad.
The engine needs to create light LUT tables for each named palette as needed at load time.

2b. This is similar to the Boom additional color maps.
DoomLegacy also allows specifying a colormap in some special linedef.
Those colormaps are index to index, using the Doom colormap to do light, distance, and conversion to RGB.
For speed the engine would do best by keeping additional palette tables that directly translate to RGB, but a set of light LUT per palette would work also. Implementation would only have to change the colormap pointer, similar to what is done for Boom colormaps.

3. The engine must manage the palettes, translation to the RGB format
it is using, and any LUT it may need (or not need).
If it is rendering in RGB, it may not need a LUT.

4. The flat and texture formats must stay with 8 bit, (or RGB, as in PNG). There is no need to change the current Doom patch format.

5. The flat, texture, or sprite could indicate which palette they use.
The default would always be the default Doom palette.
The method of connecting a flat, texture, or sprite to a named palette
is where the port differences might arise.

Option 5a. Each named palette could list which flat, texture, and sprite names it applies to. Each time another texture is created, the palette lump would be modified. Difficult to manage.

Option 5b. A lump could list flat, textures, and sprites, and assign a palette to each. This is the easiest to manage, and is backward compatible. There is only one list needed per wad, and only the few textures that use need to be listed in it. All other textures default to the default wad palette (as loaded from the wad).

Option 5c. Expand the flat, texture, and sprite wad formats to include a palette name field. This option is not backward compatible.

I recently did an abortive implementation of true color as a branch of EE, using a method which used a second drawing pass on columns and spans to put palette indices into a secondary framebuffer. While pushing pixels to the OpenGL texture in the GL backend, the palette to use would be changed by indexing into the secondary framebuffer.

While it works at a very basic level, it of course totally fails in any capacity where the game is required to know it's actually running in 32-bit color, and that particularly means anywhere any blending is done. You can see this in some of the shots, which deliberately included it so that the reason this algorithm wasn't going to be "trunked" in EE would be obvious.

http://imgur.com/a/uOnDc

This reminds me that I tried making a palette that encompassed a fairly comprehensive stretch of a full 24-bit RGB spectrum within 256 colors. I did a little research/math about the subject, and came up with two possibilities that can match pretty much any color you want.

The first is a 3-3-2-bit approach. First three bits are red, second three are green, last two are blue, allowing for 8 shades of red and green and 4 blue for any given byte. You might think having fewer shades for blue would be bad, but apparently blue is intrinsically the hardest primary color of light for the human eye to distinguish between shades of, while green is the easiest; as such, this actually works pretty well.

The biggest issue is with grays, though; there are pretty much no places that blue lines up perfectly with red and green, so anything grayscale will noticeably shift between blue and yellow a bit as it tries to find the closest palette entry to the corresponding gray.

Another one I tried, specifically to combat the gray issue, is 6 shade/8 shade/5 shade with 16 grays. Basically, red goes from 0 to 255 in five steps of 51 each, green goes from 0 to 255 in seven steps of 36.428571428571... (you'll have to round it to the nearest integer, but still), and blue goes from 0 to 255 in four steps of 64 (well, 63.75, but who's counting). The end result is 240 colors that cover most of the 24-bit color spectrum, much like the 3-3-2-bit approach. Also much like the 3-3-2-bit approach, there are no situations where red, green and blue line up, leading to some weird scenarios for grays - so I used the last 16 entries in the 256 for pure grays, stepping up 15 in all three values each time. This was a lot more pleasing overall, I thought.

...but then I abandoned both of them when I saw how they looked with dark areas in Doom (well, ZDoom, specifically, when I converted all of the game's assets to PNG and then used that palette and a COLORMAP lump tailored to it). What's normally a fairly smooth fade from a given shade to black now looked a little too... abrupt. Not sure if they're still worth using to any degree... *shrug*

40oz said:

pardon my lack of knowledge of the subject, but for a few months I'd wondered why since Doom doesn't load graphics that aren't being displayed in the player's field of view, it doesn't do the same for colors?

Doom doesn't do that, it simply happily unloads graphics that are not being used right now if memory is too low. Plus, certain kinds of graphics (like composite textures) are permanently loaded in memory, they can't be dynamically unloaded during gameplay.

I understand what you mean, but you would need an extra marking subsystem to keep track of what resources are in view, and which palettes they use, and situations where you really only see one and not another would be few and far between. Unless you could tolerate some color clash when graphics with too different palettes were in view, this would not be a very practical approach.

I like wesleyjohnson's method: if you have a truecolor renderer, nothing prevents you from having more than one base palette, shaded with the same techniques as the "original" one. Well, other than programming the damn thing, that is. And defining a system for keeping track of which graphics use which palette. THere's also the problem that multi-paletting can make the size of colormaps, lightmaps etc. skyrocket, and doing certain effects efficiently (like colored screen flashes) without resorting to full RGB framebuffer processing can be tricky.

It will STILL have the limitation that individual sprites or textures cannot have more than 256 colors, but that's not necessarily a bad thing: I've seen this approach used in the Warlords Battecry RTS games: it had a HiColor display, but sprites were limited to 256 colors each, including their palette effects (each sprite could have up to 4 different palettes though).

Already am using RGB processing as much as possible in DoomLegacy, which is invoked by -highcolor -truecolor, or -native switches.
This is using integer math instead of float, so it is fast.
It is used for transparency, fog coloring ....
It is fast enough on a 1.6 GHz machine to be preferred over OpenGL (which looks blurry to me).

For OpenGL, the engine analyzes the Boom colormaps to derive a gradient based substitute. This cannot do some of the weirder colormap effects, but is adequate for lava glow, and underwater tinting.

Played around with ideas for internal palette handling.
1. Could map individual texture and sprite palettes to use an internal master colormap at loading time.
The master colormap would be 256, 512, or 1024 colors.
2. Each new color would be registered in the master colormap and given an index value. Only colors actually used in textures get registered.
The textures get the new palette index at load time.
2b. The nearest closest color is checked, so duplicate colors and very close close colors use the same entry and shade table.
2c. If the master colormap space is exhausted, then some colors could be combined into one index to make more room. This is where the idea gets messy, because textures that had been converted already would have to be updated again. Incremental wad loading makes it difficult to determine all colors first, so a preemptive strategy is best.
2d. The best preemptive strategy is to seed the table with basic colors that cover most of the spectrum. Even with a full table, there is always an adequately close color to use as a substitute.
3. With this scheme it does not matter how many palettes there are as they are all merged into one master palette at texture load time.
4. Light levels (shades) of the master colormap would be individually handled with tables that convert a light level and palette color direct to RGB.
5. All of the light, distance, and effect mappings would select the light table for a particular color, and perhaps another blend color.
6. This eliminates the colormaps for each palette, in favor of one larger colormap.
7. The 10 bit palette index is entirely internal to the engine.
8. It is adaptive to the actual palettes in use.
9. It can be entirely bypassed, without loss of quality, to use OpenGL or direct RGB processing. The shading tables can be eliminated by using a RGB multiply with a light level lookup, or by using hardware Shaders.
10. It does not share the light mappings between tints of the same color as well as the index to index colormaps do. But the cost difference is an 8 bit entry in some colormap vrs a 32 bit entry in some shading table.
11. A similar approach is possible where each unique palette gets its own 256 colormap. The shade tables are owned by the master colormap, and referenced by the individual palette colormaps. This allows sharing of the common colors. The textures using the palette can stay the same, with only 8 bit color indexes. This may be less memory intensive simply by not forcing textures to be 16 bit pixels.
11b. Another extension is to allow individual palettes to create and own their own shade tables, and to share the master palette shade tables too. This would use a 256 color master table, preloaded with a palette. Any color not in the master table (by allowed difference setting) would create an individual shade table (for one color) for the individual palette's colormap.

wesleyjohnson said:

2. Each new color would be registered in the master colormap and given an index value. Only colors actually used in textures get registered.
The textures get the new palette index at load time.
2b. The nearest closest color is checked, so duplicate colors and very close close colors use the same entry and shade table.
2c. If the master colormap space is exhausted, then some colors could be combined into one index to make more room. This is where the idea gets messy, because textures that had been converted already would have to be updated again. Incremental wad loading makes it difficult to determine all colors first, so a preemptive strategy is best.

Better solution:
2. New colors are registered. Textures are stored in RGBA format.
2b. same
2c. is no longer a problem.

If you want to, when loading a map, you can convert the texture from the "master/source" texture manager into a paletted copy, using colormatching.

There's another advantage to storing textures as RGBA format. If you don't mind the processing and memory expense, you can have a map system (as in, std::map, not Doom map) to keep track of how many time each color is used by each texture. So when loading textures needed by one level, you can get a count of how many time each color is used by the loaded resources. This can let you optimize the choice to make of which colors to keep in the palette for this level. And then you colormatch the textures to the palette.


To be honest, this is probably a whole lot more cumbersome than straight RGBA rendering.

Reading the above makes my layman brain tingle. In a nice way. I can see there are a lot of roundabout options, though I obviously don't grasp it all fully.

In an attempt to put it bluntly (and again, theoretically) - if I had a new monster-sprite from one 256 color palette (Doom's), that applied more than one half of the colors from that palette, AND I had another monster-sprite from another 256 color palette that applied more than one half of IT's colors (AND didn't share _any_ colors with Doom's palette) - would I be able, using any of the techniques above, to display both of these monsters on the screen at one time, without losing any unique colors in the source art?

A user can not achieve much. Most the above discussion was for code developers thinking about how to support such a request. It is very involved and would be a large effort.

Boom, and DoomLegacy, can specify a colormap, but it applies to sectors, and is limited to mapping one Doom color to another Doom color.
DoomLegacy has the ability to specify a linedef that will tint a sector according to a color gradient. These can be applied to 3d floors, and specifically for fog and underwater. These would only affect sprites in while they are in the sector.

Soundblock said:

In an attempt to put it bluntly (and again, theoretically) - if I had a new monster-sprite from one 256 color palette (Doom's), that applied more than one half of the colors from that palette, AND I had another monster-sprite from another 256 color palette that applied more than one half of IT's colors (AND didn't share _any_ colors with Doom's palette) - would I be able, using any of the techniques above, to display both of these monsters on the screen at one time, without losing any unique colors in the source art?

Yes, if you used one of the techniques that allowed for each monster to use its own palette and colormaps. As a practical example, imagine if you could use Doom's and Heretic's palettes on screen at the same time -but mind you, Doom monsters would only be able to use Doom's palette, and Heretic monsters would only be able to use Heretic palette.

In order to do what you want (a monster used a mixed palette) you'd have to craft that palette, AND it would still count as a separate one, AND it would still have 256 distinct color tops per monster (but those 256 colors could be completely unique). So you'd have Doom's palette ("Palette 1") + a mixed Doom/Heretic palette ("Palette 2"). Your new monsters would only use "Palette 2", and would not be affected by changes to "Palette 1".

But as Gez said, this is just theoretical talk -first some poor code monkey must actually implement this functionality in some source port. And its obvious where I would place my money ;-)