if we keep calculating colors on players per frame
Per frame?!!
Oh no, gods, no!
I meant this as an additional stage injected into the code that loads the image from disk. Say, the call supports additional parameter(s) describing the masks used and the colors they apply, in addition to the main skin tga file name. Then, from the engine side, this looks like a single file was loaded from disk.
For example, instead of
/models/players/ducky/body.tga
the file name would be
/models/players/ducky/body.tga?mask=/models/players/ducky/stripes.tga&hue=(255,160,200)&mask=/models/players/ducky/stars.tga&hue=(0,255,100)
The beauty of the masks idea is in ZERO overhead during play, the only overhead applies to the loading time.
but sets of heads and their hairs ideally should share the same texture atlas as the body
Well, with 16 players max, this means an overhead of 32 texture switches max, and that's horrible.
I'm not sure (I haven't experimented with this for years) but I think you are slightly overreacting.
When I had been playing with inefficient texture usage (my customized Quake2 renderer), making it that every particle used a different texture, I noticed that problems crop up only when you move to hundreds and thousands of texture switches per frame. And that's on GeForce2 MX.
Still, it would be a nuce guideline for content creators to use one pre-defined texture for all their hairdos. It's just hair, after all!
How to further divide them and preserve compatibility?
I meant OA3, yes. And the new ones, yes.
Backward compatibility is a cake.
You only really need to introduce just one more selectable element "head#2" that is used in parallel with head, with the same transformation matrix. four elements isn't much more than 3. The older Q3 compatible models will just have an empty selector. You could even use the new models back Q3, they'll just be bald.
The same goes for masks.
It all could be done very transparent, otherwise I woud not be suggesting this.