A faster way to generate PLAYPAL / COLORMAP

[RjY]

Start with a palette: 768 bytes, 256 RGB triples. In Freedoom this is named playpal-base.lmp.



PLAYPAL

Construct red, gold, and green ("lime" in SVG/MVG parlance) blends.

convert -size 256x1 -depth 8 rgb:playpal-base.lmp \
  \( -clone 0 \( +clone -fill red -colorize 75% \) -morph 7 -delete 0 \) \
  \( -clone 0 \( +clone -fill gold -colorize 50% \) -morph 3 -delete 0 \) \
  \( -clone 0 -fill lime -colorize 25% \) \
  -append rgb:playpal.lmp

Freedoom has a different bonus flash colour of course, this is just an example. I'm sure you can see how to change the colours!

COLORMAP

Construct fade to black, and inverse. Clear the unused final colormap to black. Finally, map to the original palette (quantise).

convert -size 256x1 -depth 8 rgb:playpal-base.lmp -write mpr:pal \
  \( -clone 0 \( +clone -fill black -colorize 95% \) -morph 30 -delete 0 \) \
  \( -clone 0 -colorspace gray -negate \) \
  \( -clone 0 -evaluate set 0 \) \
  -append +dither -remap mpr:pal colormap.ppm

At this point we need to convert this image from RGB triples into a greymap of palette indices, essentially the reverse of ImageMagick's -clut operator. Unfortunately I have not been able to coerce ImageMagick into performing a "reverse CLUT" operation. Instead for this I (ab)used rdatawad, from the PrBoom+ distribution, but I expect Freedoom does not want to build-depend on PrBoom+.

rdatawad -palette playpal-base.lmp -flats colormap.ppm -o playpal.wad
dd iflag=count_bytes,skip_bytes if=playpal.wad skip=12 count=8704 > colormap.lmp

This final step could be achieved relatively quickly in Python, however - since the colormap is already quantised to the palette, there is no expensive nearest-colour matching to be done, only an exact hash lookup is needed. (This is exactly what rdatawad does.)

Justification

Doing number crunching in pure Python, as playpal.py and colormap.py are currently, is tremendously slow. I always feel like I'll die of old age before the colormaps are built. Using ImageMagick is orders of magnitude faster, while doing the job just as well, and IMO remaining just as "hackable" as the scripts it is seeking to replace.

If this is of interest, I will try to generalise the process to other shaded colormaps, integrate it into misc-lumps, and post patches for review.

[fabian]

RjY said:

red, gold, and green

Karma Karma Karma Karma
Karma Chameleon

No, seriously, great imagemagick-foo. And we already depend on this tool anyway...

[Jon]

fabian said:

Karma Karma Karma Karma
Karma Chameleon

No, seriously, great imagemagick-foo. And we already depend on this tool anyway...

That's caused a fair share of compatibility problems as the tool changes, or it was forked, Debian carried the fork (graphicsmagick) with a compatibility layer that wasn't compatible; also the scaler quality seemed to change between releases, I remember chungy saying he wasn't happy with the quality of recent imagemagicks for some of the freedoom operations.

If the Python solutions are slow I suspect they could be written better: even in Python. Sure for scientific-class number crunching people might move to something more performant, but for generating such a small amount of data, it shouldn't be a problem.

I know freedoom can only realistically be built on *nix at the moment but imagemagick is one of the reasons why; python is a lot more portable.

(Not to detract from RjY's achievements in taming imagemagick.I just think it's the wrong direction...)

[Gez]

Here's why ImageMagick is being dropped

[Blastfrog]

Should Freedoom really be using different fade colors than Doom? It's disregarded by ports that do their own fading, anyway.

[fabian]

Sodaholic said:

Should Freedoom really be using different fade colors than Doom? It's disregarded by ports that do their own fading, anyway.

By "fading" do you mean the red/gold/green blends of the palettes after the first one?

[Blastfrog]

fabian said:

By "fading" do you mean the red/gold/green blends of the palettes after the first one?

Yes.

[raymoohawk]

it would be cool if freedoom had its own colormap (hopefully prettierr than doom's), maybe someone with experience in this field like soda or essel could toss a new one together?

[Linguica]

raymoohawk said:

it would be cool if freedoom had its own colormap (hopefully prettierr than doom's), maybe someone with experience in this field like soda or essel could toss a new one together?

The palette has to remain identical for obvious reasons, so I'm a little confused about what a "prettier" colormap would possibly be.

[Blastfrog]

Honestly, I have to wonder why bother generating it on compile in the first place.

Linguica said:

I'm a little confused about what a "prettier" colormap would possibly be.

Probably something like Strife's that's much pickier about the colors it uses, preferring to keep within the same range rather than use the whole palette.

I did my own attempt at this a few years ago, but am personally unsatisfied with the results and I didn't even consider it finished back then. I may attempt another for the sake of it, whether it's appropriate for Freedoom or not.

Problem (or not) with it is, it tends to look more cartoony, since things become more saturated than they should in the dark. It can also lead to some pretty ugly color banding on images that heavily use various desaturated colors.

While I do feel strongly about the palette staying identical to Doom's, I'm mostly indifferent about the colormap so long as it doesn't look uglier than the original.

[Linguica]

SLADE makes it pretty easy to generate colormaps using other algorithms, and IMO none work as well as the simplistic method Carmack used.


The normal RGB method Carmack used.


HSL.


CIE 76.


CIE 94.


CIEDE 2000.

[Gez]

More precisely, it changes only the color matching algorithm. The algorithm for generating the truecolor colormap before it is palettized is always the same; and it is possible that a better one could be written.

[Linguica]

I suppose so. I quickly banged out a colormap that falls off on a sine curve instead of linearly:

for i in range(32):
	darken_factor = 0.5*(math.cos(math.pi * i/32)) + 0.5

http://www.doomworld.com/linguica/colormaps/colormap.wad



It certainly has an effect. It's more... contrast-y I guess?

[chungy]

Not applying to all the posters here, but please don't dismiss improvements to the ImageMagick-based system unless we've actually made progress towards replacing ImageMagick; the effort hasn't yet been put it. It's not unreasonable to improve the system as it currently exists :P

[Blastfrog]

I think the PLAYPAL and COLORMAP should be pre-generated and simply included during build. The source to generate it should be available, but there's absolutely no reason to recalculate it when simply building an IWAD.

Generated text can and does change far more frequently than the assets in discussion here, so it's justified there.

[RjY]

Thanks for the comments, encouragement, and kind remarks, everyone.

fabian said:

And we already depend on this tool anyway...

Jon said:

That's caused a fair share of compatibility problems as the tool changes, or it was forked, Debian carried the fork (graphicsmagick) with a compatibility layer that wasn't compatible; also the scaler quality seemed to change between releases, I remember chungy saying he wasn't happy with the quality of recent imagemagicks for some of the freedoom operations.

Indeed. I was aware of the operating plan to move away from ImageMagick eventually; I had seen the bug report Gez linked to. But I did it anyway, because cool hacks are cool hacks and I love messing with ImageMagick regardless of whether Freedoom uses it or not :)

Nevertheless you can take it as read that I would be very sad to see it go.

I will also note that many of the problems observed at the time the bug was raised were due to Debian being stuck for two stable release cycles on a very old version of ImageMagick that in the middle of its internal linear to sRGB colorspace transition. This led to a whole host of annoyances like nonlinear gradients and broken -clut operators. Fortunately it is long past that now.

Jon said:

If the Python solutions are slow I suspect they could be written better: even in Python. Sure for scientific-class number crunching people might move to something more performant, but for generating such a small amount of data, it shouldn't be a problem.

Allow me to assure you the build time is a problem for me! My computer is old, please buy me a new one. ;)

But yes you are right, search_palette and generate_colormap could be improved a lot, I believe. I guess I need to go learn about k-d trees...

Jon said:

I know freedoom can only realistically be built on *nix at the moment but imagemagick is one of the reasons why; python is a lot more portable.

I am fairly sure ImageMagick is adequately portable: [1] [2]

If Freedoom isn't realistically buildable on non-unixlike platforms I feel it's because it simply has a non-trivial number of build dependencies, which, due to Windows lack of package management each take time and effort to set up, not because of one in particular.

Linguica said:

The palette has to remain identical for obvious reasons

In fairness it would be feasible, provided the replacement remained "compatible" - green is still green, but the precise shades can be varied. I recall someone proposed a palette with the usual desaturated blues, and "minty greens" a few years ago.

That said, I'm still against changing it.

Sodaholic said:

Honestly, I have to wonder why bother generating it on compile in the first place.

If it can be generated from something simpler, it is likely not the preferred form of modification. Free software ethics demand the authors distribute the preferred form of modification, and make available the tools to transform it into its final form.

Sodaholic said:

I think the PLAYPAL and COLORMAP should be pre-generated and simply included during build. The source to generate it should be available, but there's absolutely no reason to recalculate it when simply building an IWAD.

Ah now that's a different thing. That's more like the distinction between a VCS checkout, which should not contain generated files, and a "make dist"-generated GNU tarball.

There's a reasonable argument for supplying certain generated files in source distributions aimed at end-users, usually because you do not expect said end-users to have some possibly esoteric developer tool installed on their machine.

[chungy]

RjY said:

I will also note that many of the problems observed at the time the bug was raised were due to Debian being stuck for two stable release cycles on a very old version of ImageMagick that in the middle of its internal linear to sRGB colorspace transition. This led to a whole host of annoyances like nonlinear gradients and broken -clut operators. Fortunately it is long past that now.

The bad behavior still exists in current versions of ImageMagick, at least the versions provided by Arch and Debian Sid. I have Debian Wheezy in Docker explicitly to build Freedoom releases with the "good" old version.

RjY said:

I am fairly sure ImageMagick is adequately portable: [1] [2]

If Freedoom isn't realistically buildable on non-unixlike platforms I feel it's because it simply has a non-trivial number of build dependencies, which, due to Windows lack of package management each take time and effort to set up, not because of one in particular.

Freedoom is pretty simple to build on Windows, actually, though it requires Cygwin to work. the COMPILING document actually describes the scenario.

[Jon]

Why don't we just bundle the palette? it's not copyrightable anyway. I guess we'd still need to generate the colormap.

[fraggle]

chungy said:

Not applying to all the posters here, but please don't dismiss improvements to the ImageMagick-based system unless we've actually made progress towards replacing ImageMagick; the effort hasn't yet been put it. It's not unreasonable to improve the system as it currently exists :P

I disagree. The eventual goal is to get off ImageMagick and we don't help achieve that goal by digging ourselves into a deeper hole by adding even more dependencies on it. We have something that works already and it's a bit slow but not so slow that modern machines take a really huge amount of time to build the colormaps.

RjY's idea is an elegant solution but I think the desire to eventually get off ImageMagick should rule it out. Otherwise what are we going to do, change to it and then change back again?

[RjY]

All right, I won't pursue this avenue further. It's enough for me to have the process written up and published, anyway. I don't do it often enough.

chungy said:

The bad behavior still exists in current versions of ImageMagick, at least the versions provided by Arch and Debian Sid.

I'm sorry to hear that. Evidently also I don't understand exactly what your undesirable behaviour actually is! :)

Unless it's "using different versions of IM produce slightly different results", which isn't a surprise, you wouldn't expect two binaries built from the same source with gcc-4.9 and gcc-5 to be exactly the same either.

Jon said:

Why don't we just bundle the palette? it's not copyrightable anyway. I guess we'd still need to generate the colormap.

I think the "preferred form of modification" is the base palette (which is indeed bundled, as playpal-base.lmp) plus whatever functions and parameters are used to generate the palette flashes. No reason you couldn't distribute the generated PLAYPAL/COLORMAP lumps in freedoom-source.zip but IMO they shouldn't be in freedoom.git.

fraggle said:

I think the desire to eventually get off ImageMagick should rule it out. Otherwise what are we going to do, change to it and then change back again?

The transition from IM to PIL depends on the assumption that PIL can do everything Freedoom uses IM to do. Then each use of IM can be rewritten in Python with PIL. Migrating my palette/colormap generation process from IM to PIL would just be another step on that path.

I assume using PIL to do what I've done with IM here would be both possible and have similar tangible performance benefits. In fact if you're definitely switching to PIL, I'm going to have to learn PIL, and this might be a good way to start.

[esselfortium]

A purely programatically-generated COLORMAP won't be as good as one that's been given per-pixel adjustments by a human. Treating COLORMAP as an art asset like any other graphical lump would better allow for future enhancements that would be impractical to code into it.

[andrewj]

I agree with essel, the build process should just be converting a image into the COLORMAP lump.

Of course leave the code for generating the image somewhere findable for people who want to experiment with different approaches, but it really does not need to be part of the build process for the FreeDoom wads.

[raymoohawk]

does anyone want to give making a manually improved color map a try?

[Linguica]

On 9/20/2015 at 11:23 AM, raymoohawk said:

does anyone want to give making a manually improved color map a try?

jmickle66666666666666 shared with me a manually edited colormap she had made a while back where she defined color ramps. It was interesting (it avoided the desaturation problem) but went a little overboard in the opposite direction, e.g., demons and barons turned CRAZY BLOOD RED in low light.

[Da Werecat]

That's Doom palette for you. The colormap is either butt, or it's ass. I've tried. Some of the results were acceptable, but still looked weird.

Certain graphical assets looked weirder than others. For example, imp's teeth are using white from the red range. It means that if you preserve saturation for the whole red range, white pixels will turn to red in the dark. Another example (which is harder to fix) would be the CEMENT texture family. It has a lot of bright saturated dots. They look fine when a texture is at full brightness, but when it starts to fade they pop immediately. Essentially, the solution for bad fading produces bad fading itself.

Unless you take extra time to fade the brightest colors separately from their ranges. Kinda like in BtSX, but you won't have the benefit of a tweaked palette.

[andrewj]

Da Werecat said:

That's Doom palette for you.

But this is FreeDoom, we *could* have a palette with better coverage of dark colors. For example, it is crazy that the darkest red is (67, 0, 0)

[raymoohawk]

if anyone wants to alter the pallete at least make sure it is compatible with the original, otherwise it will cause problems for the spriters (aka: me)

ive tried converting heretic sprites to blasphemer's pallete and they look horrible

[RjY]

esselfortium said:

Treating COLORMAP as an art asset like any other graphical lump would better allow for future enhancements that would be impractical to code into it.

andrewj said:

I agree with essel, the build process should just be converting a image into the COLORMAP lump.

It used to be like this until someone (Fabian, iirc) requested they be programmatically generated by the build process.

[fabian]

RjY said:

It used to be like this until someone (Fabian, iirc) requested they be programmatically generated by the build process.

Yep, else COLORMAP would just be a 8704 byte binary blob of obfuscated algorithm, which I find unacceptable in a FLOSS project.

[Jon]

fabian said:

Yep, else COLORMAP would just be a 8704 byte binary blob of obfuscated algorithm, which I find unacceptable in a FLOSS project.

I can see both points of view. If we can't match the quality of a hand made COLORMAP (which is a bit of a straw man at the moment as it doesn't exist) then we should ship a binary blob as it's the same as a sprite frame. But if the basis of that was algorithmically generated, we should keep the generation code in the tree.

But I'm not seeing many arguments against the quality of the current COLORMAP. The main issue this thread was talking about was the efficiency of the generator.