Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
RjY

A faster way to generate PLAYPAL / COLORMAP

Recommended Posts

raymoohawk said:

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

I was not advocating major change to the palette, just tweaking the intensity of the dark colors so that things look better in low light levels.

Fabian said:

Yep, else COLORMAP would just be a 8704 byte binary blob of obfuscated algorithm

(a) it would be a real image file (e.g. PNG), not a binary blob
(b) the python script would stay in the tree, so hardly "obfuscated"

Share this post


Link to post
Linguica said:

jmickle66666666 shared with me a manually edited colormap he had made a while back where he 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.


Yeah I think my method might work ok for a custom palette with saturation levels taken into account properly in the ramps, but with the doom palette it gets way too fucky

Share this post


Link to post

Honestly, I don't see the problem

$ rm -f ./lumps/cph/misc-lumps/colormap.lmp && time make -C ./lumps/cph/misc-lumps
make: Entering directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'
./colormap.py playpal.lmp > colormap.lmp
make: Leaving directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'

real	0m1.408s
user	0m1.388s
sys	0m0.016s
Edit: Okay, I see, but still...
$ make clean -C lumps/cph/misc-lumps
make: Entering directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'
rm -f playpal.lmp colormap.lmp bloodmap.lmp bluemap.lmp lavamap.lmp nukemap.lmp fogmap.lmp mfademap.lmp
make: Leaving directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'

$ time make -C lumps/cph/misc-lumps
make: Entering directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'
./playpal.py playpal-base.lmp > playpal.lmp
./colormap.py playpal.lmp > colormap.lmp
./colormap.py --tint_color='#ff0000' --dark_color='#500000' \
              --tint_pct=100 playpal.lmp > bloodmap.lmp
./colormap.py --tint_color='#0000ff' --tint_pct=100 \
              --tint_bright=0.6 playpal.lmp > bluemap.lmp
./colormap.py --tint_color='#ff6000' --tint_pct=80 \
              --tint_bright=0.8 --dark_color='#ff6000' \
	      playpal.lmp > lavamap.lmp
./colormap.py --tint_color='#00ff00' --tint_pct=70 \
              --dark_color='#005000' playpal.lmp > nukemap.lmp
./colormap.py --dark_color='#505050' playpal.lmp > fogmap.lmp
./colormap.py --dark_color='#2b230f' playpal.lmp > mfademap.lmp
make: Leaving directory '/home/greffrath/Debian/freedoom-0.9/lumps/cph/misc-lumps'

real	0m9.845s
user	0m9.764s
sys	0m0.064s

Share this post


Link to post
fabian said:

Honestly, I don't see the problem

I do the bleeding edge builds on a Raspberry Pi and it takes a long time there. But I don't think we should be designing the build system around such low-spec hardware.

Linguica said:

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

I had a think about this a while back because I do really love the fresh, bright blues that appear in the BTSX palette and it got me thinking about how it would be possible to change the Freedoom palette while retaining compatibility.

The palette can be viewed as a collection of points in the three dimensional RGB color space. Therefore you can probably make some compatible palette changes by applying deformations to this color space. Think of it like applying a lens. As long as the deformations are continuous it shouldn't break compatibility - for example color ramps would just take a slightly different path through the color space and other "nearby" colors would be similarly distorted. In theory I think it should even work correctly with mods that do COLORMAP changes without PLAYPAL changes, and vice versa.

It's probably easy enough but I expect it requires an understanding of certain branches of higher mathematics that I'm not familiar with.

RjY said:

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

The origin of some of the Boom alternative COLORMAP lumps was uncertain - they were added in the early days of the project. So they were changed to be generated programatically. I think it's the better solution - the fewer binary blobs the better.

RjY said:

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.

If you can find out a way to get PIL to do the same thing then go for it. As I said, it's an elegant solution (and I hope I wasn't too harsh in my previous comment). I'm just concerned that we shouldn't be adding more, deeper dependency on ImageMagick when we're trying to get away from it.

Share this post


Link to post
andrewj said:

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)


Tell me if I'm being too cautious/nitpicky over copyright here, but I think changing the palette has unpleasant consequences for downstreams.

GPL-licenced engines with external graphics (such as PrBoom/+ and Odamex) all require a palette as a build dependency for their data wads, to convert RGB values in source images into palette indices for Doom's patch format - even for free graphics not derived from the IWAD's menu font and so forth.

In order to be shipped with the software, this palette also needs to be free, that is to say, GPL-compatible. Currently the Freedoom palette can be used, as — by an astonishing coincidence — it is identical to Doom's palette.

It's already quite uncomfortable abusing this loophole to ship Doom's palette with GPL source code, but if Freedoom's palette changed, I think it would become untenable.

fabian said:

Seriously, people, I don't see the problem

# lumps/cph/misc-lumps
make  29.71s user 0.08s system 95% cpu 31.148 total
# graphics/text (textgen)
make  16.59s user 31.68s system 82% cpu 58.225 total
# full rebuild from topdir
make  50.34s user 32.84s system 94% cpu 1:27.66 total
This isn't just about colormaps. I have some frustration borne from years of "death by a thousand cuts". Allow me to share it with you.

When I first joined in with Freedoom development, it was built mostly using deutex, with makefiles, and some perl scripts, for glue. At about the same time, Fraggle returned, and began to reimplement all the perl scripts in python. I admit I didn't understand why. There was no bug fixed by the work; the existing scripts did their jobs and were bug-free. As far as I could (sarcastically) tell, the only problem the transition solved was "Freedoom builds too quickly, please make it take twice as long". But I kept my mouth shut because it was essentially an "I don't like your choice of programming language" argument and those are never useful.

Forward a couple of years. During the period 2011-2013 or so, I was handling many of the submissions. As proper diligence insists and a desire to keep master always releasable requires, I tested everything before pushing out the commits. This involved repeated rebuilds of Freedoom from a clean tree. When I started, with the perl scripts, a full rebuild took about thirty seconds. With python, and the increasing number of objects built by scripts instead of just stored as blobs, it was taking well over a minute.

At some point, textgen went in. The benefits were obvious, but it took the build time past a minute and a half. This was sufficiently intolerable to investigate. It turned out textgen was calling ImageMagick twice per graphic generated. Reducing that took Freedoom's build time to under a minute for the first time in years, which made porting Double Impact, and the dozens and dozens of test builds/runs that entailed, almost pleasant.

However soon after, the colormap generation scripts went in. These ate all the time I had clawed back, and then some. After that and as much for other reasons, I drifted away from Freedoom, finding myself presented with other things to do instead. I created a scripted build system for 200minvr that was highly inspired by Freedoom's — that was a lot of fun! Fortunately, Chungy had recently returned from a long absence and picked up the slack in Freedoom submission handling, so no-one noticed I had stopped.

Thus things stood for over a year, until last week, when for an unrelated purpose I needed a PLAYPAL and COLORMAP that were both completely different from Doom's. I thought of Freedoom's generator but wondered if I could instead do it in ImageMagick. The answer was of course "yes", because frankly you can do anything in ImageMagick. I wrote up the procedure, resulting in this thread, and now here we are.

fraggle said:

If you can find out a way to get PIL to do the same thing then go for it. As I said, it's an elegant solution (and I hope I wasn't too harsh in my previous comment). I'm just concerned that we shouldn't be adding more, deeper dependency on ImageMagick when we're trying to get away from it.


Not at all; I understand the desire to migrate away from IM for build reproducibility reasons. Though I will say I don't care for the "it doesn't matter how resource-intensive the software is, because you can just go and buy new hardware" sentiment which sadly seems to pervade a great deal of modern development.

Share this post


Link to post
fraggle said:

I do the bleeding edge builds on a Raspberry Pi and it takes a long time there. But I don't think we should be designing the build system around such low-spec hardware.


I did do nightly builds on our shared VPS (free.doomer.org) but everyone seemed to forget they existed so I deleted it in a fit of pique. We could bring that back.

The origin of some of the Boom alternative COLORMAP lumps was uncertain - they were added in the early days of the project. So they were changed to be generated programatically. I think it's the better solution - the fewer binary blobs the better.


Although there's a comment in the generator saying the older LAVAMAP (which Cyb contributed) was better than the auto-generated one. I'm not sure I agree, it's a matter of taste. (I recently compared the two.)

RjY said:

In order to be shipped with the software, this palette also needs to be free, that is to say, GPL-compatible. Currently the Freedoom palette can be used, as — by an astonishing coincidence — it is identical to Doom's palette.


I don't think a palette -expressed as a literal collection of colours/numbers - is copyrightable.this makes interesting reading, but it's not comprehensive. They argue that the things they distribute are more than just a literal collection of colours/numbers. But that would not apply to the Doom palette.

Unrelated, but I think the PNAMES lump is similarly uncopyrightable.

Share this post


Link to post
Jon said:

I don't think a palette -expressed as a literal collection of colours/numbers - is copyrightable.this makes interesting reading, but it's not comprehensive. They argue that the things they distribute are more than just a literal collection of colours/numbers. But that would not apply to the Doom palette.

Verbatim:

But, what is protected is the arrangement of those colors into the rectangular shape that they are on COLOURlovers displayed along with their names.

They're copyrighting a representation of the palette, instead of the palette itself.

This argument is indeed irrelevant for the PLAYPAL lump, as it is raw data and not a visual representation.

Share this post


Link to post

Did anybody try optimizing the existing Python code that's doing the COLORMAP generation?

I do not for example see a hitlist/hashtable approach being used to reduce closest color matching operations. So every one is a full linear search through the palette. This is probably important when you're doing several thousand of them back to back and probably matching the same colors multiple times in some cases.

I am also skeptical of use of dynamic collection style objects for such a task. There's nothing done in the process of generating a COLORMAP that should require something on the order of a C++ vector<> object. Fixed number of operations generating a fixed-size output; dynamic allocation overhead is unjustified and is going to cause garbage collection noise.

I won't go as far to suggest fixed point math *yet* though I do know there is zero benefit to doing operation on an RGB colorspace in double-precision floating point - you are exploding operations with a maximum of 16 bits of precision into an 80-bit number (on Intels) and then throwing away everything but 8 bits of it when you're done. Conversions from int to float or vice versa are also expensive regardless of the language they're performed in, especially if the Python interpreter hasn't taken to using SSE2 instructions yet when they're available.

Share this post


Link to post
fraggle said:

It's probably easy enough but I expect it requires an understanding of certain branches of higher mathematics that I'm not familiar with.

Or applying some Photoshop filters. :)

Share this post


Link to post

Looking at freedoom's colormap.py, you can get a 2x speedup by making simple optimizations to the Python code (in the function search_palette(), inline the square function, and unpack the RGB values to local variables instead of indexing tuples).

In Omgifol, which is written in pure Python, I precompute a table of palette entries close to a given brightness level. You can come up with fancier algorithms, but this is trivial to code, and it speeds up RGB->palette conversion by an order of magnitude. I just tested the Omgifol code and it generates PLAYPAL / COLORMAP in less than 0.01 seconds on my laptop. I don't think it generates completely identical tables to the IWAD lumps, but the visual difference should be minor.

Share this post


Link to post

As a trivial work-around, will it probably help if the removal of the lumps is moved from the clean: to the dist-clean: target? So they would not have to get recreated after intermediate cleaning, but only after dist-cleaning.

Share this post


Link to post
Fredrik said:

Looking at freedoom's colormap.py, you can get a 2x speedup by making simple optimizations to the Python code (in the function search_palette(), inline the square function, and unpack the RGB values to local variables instead of indexing tuples).

In Omgifol, which is written in pure Python, I precompute a table of palette entries close to a given brightness level. You can come up with fancier algorithms, but this is trivial to code, and it speeds up RGB->palette conversion by an order of magnitude. I just tested the Omgifol code and it generates PLAYPAL / COLORMAP in less than 0.01 seconds on my laptop. I don't think it generates completely identical tables to the IWAD lumps, but the visual difference should be minor.

JSYK there was an issue with the colormap generator in omgifol last time i used it, it generated the entire thing as the first row, for all light levels. I fixed it here https://github.com/devinacker/omgifol/commit/199ed2d7bb78288c9fbe3d9f25c2b474a8f2e091 (not sure what was going on, though. just unpacked a few things and it worked)

Share this post


Link to post
jmickle66666666 said:

JSYK there was an issue with the colormap generator in omgifol last time i used it, it generated the entire thing as the first row, for all light levels. I fixed it here https://github.com/devinacker/omgifol/commit/199ed2d7bb78288c9fbe3d9f25c2b474a8f2e091 (not sure what was going on, though. just unpacked a few things and it worked)

Yeah, I downloaded the fixed version. It was certainly possible to use it to build colormaps before that, as I did lots of experiments with palettes and colormaps back when I wrote the code, but it might have required calling methods in a certain order. Unfortunately, omgifol was written before I had a clue about things such as unit testing :(

Share this post


Link to post
Quasar said:

Did anybody try optimizing the existing Python code that's doing the COLORMAP generation?

There's probably some room for optimisation. I suspect the O(n^2) color lookup is the main issue but any optimisation should be done based on profiling rather than guesses. Personally I don't think it's worth the time to improve it - the script is "fast enough".

Fredrik said:

Yeah, I downloaded the fixed version.

omgifol hasn't seen a new release in several years and there are several different forks on Github to fix known bugs. Maybe you could hand off maintainership / "bless" one of these forks?

Share this post


Link to post
fraggle said:

There's probably some room for optimisation. I suspect the O(n^2) color lookup is the main issue but any optimisation should be done based on profiling rather than guesses. Personally I don't think it's worth the time to improve it - the script is "fast enough".
omgifol hasn't seen a new release in several years and there are several different forks on Github to fix known bugs. Maybe you could hand off maintainership / "bless" one of these forks?

I used devinacker/omgifol. If it's the most up to date fork, then by all means consider it the official version. I have no time to work on omgifol, let alone interfere with what others do with it.

For any new releases, it seriously ought to be converted to a proper Python package, though (with setup.py and at least some unit tests)...

Share this post


Link to post
fraggle said:

omgifol hasn't seen a new release in several years and there are several different forks on Github to fix known bugs. Maybe you could hand off maintainership / "bless" one of these forks?


The doom-utils github group would be a good home for it. I'm sure Chungy would be happy to add you to the group.

EDIT: in fact I'd request that we host it there,if you are willing.

Share this post


Link to post

yeah i'd be down for there to be a canonical repo for omgifol. i treat devinacker/omgifol as such for now but something more 'official' would make more sense

Share this post


Link to post

AlexMax's fork on BitBucket has 15 commits and was last updated n June 2012; JMinor's fork on GitHub has 33 commits and was last updated in May 2014; Devin Acker's fork on Github has 35 commits and was last updated in July 2015.

Share this post


Link to post
Jon said:

The doom-utils github group would be a good home for it. I'm sure Chungy would be happy to add you to the group.

EDIT: in fact I'd request that we host it there,if you are willing.

Sounds like a terrific idea!

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×