I'm going to rabbit on about this for a while cos it's something that I've done a lot of research on, and the end results were a little counter-intuitive. It's also useful to provide the background and reasoning for what I'm advocating; it demonstrates that I have done the research and that I have the figures to prove it.

So, I'd always been aware that lightmap updates were a bottleneck in GLQuake, and it really hit bad on some RMQ (and other) maps. There are basically two steps to a lightmap update: R_BuildLightmap and glTexSubImage2D.

Contrary to what I expected, when I benchmarked I found that R_BuildLightmap was actually not the bottleneck. You can comment out the calls to R_BuildLightmap so that it still does the glTexSubImage upload, and you get the same bad performance. You can comment out the calls to glTexSubImage but leave R_BuildLightmap in and it runs fast.

With glTexSubImage there are 3 factors that influence performance: size of data being uploaded, whether or not the driver needs to do a format conversion, and whether or not the driver needs to stall the pipeline. 

For typical Quake lightmap usage, data size is hugely unimportant. Unless you consider extreme cases (e.g update nothing versus update everything) data size just doesn't matter.

Format conversions can kill performance, and the stock FitzQuake code will always need to do a format conversion.

Stock FitzQuake requests lightmaps in GL_RGB format on the GPU, but (unless you're using very weird hardware) there's no such thing as a 24-bit GPU texture format. It's powers of 2 all the way: 8-bit, 16-bit, 32-bit, etc. GL_RGB is also an unsized format, so the driver is free to give you 5/6/5, 10/10/10/2, 10/11/11, 8/8/8/8 or whatever. What you most likely will get is 32-bit, 8/8/8/8 with the last 8 unused, but you're not actually 100% guaranteed that unless you ask for it (i.e GL_RGB8).

At this point some people will kick and scream about "wasting memory". I loathe that term; it's not "wasting" it, it's using it. There may be nothing stored in the memory, it may never be read from or written to, but the extra byte per texel is being used to increase performance. This is the very same principle as cache-aligning data, aligning allocations on page boundaries, aligning (or padding) to 16-bytes for SIMD, etc etc etc on the CPU. Why are people so fucking surprised that similar principles apply on GPUs? Get over it. 

So stock FitzQuake code has (most likely) a 32-bit texture on the GPU, but supplies 24-bit data on the CPU. That's a format conversion, right there, and you're totally at the mercy of the driver for how efficient (or not) it is.

NVIDIA always seemed to take the fastest path for the type of conversion needed, so a simple conversion might take 1ms but the most complex take 40ms.

AMD/ATI always seemed to take a similar path irrespective, so conversion times might bob around 10ms to 20ms.

Intel was batshit insane. I can't remember the times but they were off the chart. The only explanation I could think of was that the driver downloaded the entire texture from GPU to CPU, did the conversion, then re-uploaded the entire texture back to the GPU. I don't know if that's actually true or not. 

Stock FitzQuake also did a glTexSubImage upload per-surface rather than per-lightmap. With a typical ID1-sized map, that could be several hundred uploads instead of maybe a maximum of 10. And each one of those uploads is a pipeline stall, so it totally breaks CPU/GPU asynchronous operation. Instead of the CPU handing a bunch of work off to the GPU and being able to continue itself, it instead handed a small bit of work off, waited for it to finish, handed another small bit off, waited, etc, several hundred times per frame.

That's the same codepath that stock GLQuake with R_DrawSequentialPoly took, and the same performance characteristics are observable there. But stock GLQuake didn't have GL_RGB lightmaps, so it didn't do any format conversions; stock FitzQuake just got the worst of every possible world.

This wasn't such a huge problem in the old 3DFX days because the graphics pipeline (or at least the part of it that was implemented by the GPU) wasn't as deep back then. Only per-fragment and framebuffer ops happened on the GPU, so the effects of a stall were significantly reduced. On modern hardware it's catastrophic. It's the equivalent of putting a glFinish call after drawing each msurface_t. 

Stock GLQuake with multitexture disabled batches up glTexSubImage calls so that they only occur once per lightmap rather than once per surface. It also doesn't do any format conversions.

Stock FitzQuake with multitexture disabled also batches up glTexSubImage calls so that they only occur once per lightmap rather than once per surface. It still does format conversions, but the impact is reduced. It's still horrible on Intel though.

That's why "disable multitexture" was the standard advice when using stock FitzQuake on maps with lots of lightstyle animations. It wasn't that the single-texture path was any faster in the general sense, it was that lightmap uploads were implemented in a more performant manner.

But it's possible to write a multitexture path that also batch-uploads all lightmaps before drawing anything, and in that case disabling multitexure will just make everything slower. 

So, current QuakeSpasm fixes all of this with the exception that it uses GL_RGBA/GL_UNSIGNED_BYTE on the CPU. That will still trigger a format conversion on (?some?) Intel drivers. On those drivers, the only combination that doesn't trigger a format conversion is GL_BGRA/GL_UNSIGNED_INT_8_8_8_8_REV. I believe that on D3D10+ class hardware it's not a problem, however.

None of this scales. It runs fine on ID1 maps, it runs fine on medium-sized maps, it runs fine on small maps with many light updates, it runs fine on large maps with few light updates. It will still excessively slow down on large maps with many light updates. Again, the number of lightmaps grows, the number of glTexSubImage calls increases, factor in brush models and add lots of them, and you're back to hundreds of uploads per frame and all the herkie-jerkies that come from that.

Brute-forcing it on the CPU isn't the answer. With that kind of surface count you'll probably get something worthwhile by threading R_BuildLightmap (which will be called so many times as to make this worthwhile) but you'll still hit a single-thread ceiling with your glTexSubImage calls.

You need to solve it more creatively, and moving the updates entirely to the GPU is the answer. You never need to check if a lightstyle is modified, you never need to run R_BuildLightmap, you never need to call glTexSubImage2D.

And here's something else where parts of the Quake community need to pull a collective stick out of their collective arse. The best-case will run a little slower with this kind of set up. So instead of getting 4000 FPS in DM3 you might get 2500. That doesn't matter a bollocks. You don't optimize the best case, you optimize the worst. Sacrificing a tiny piece of performance (0.15ms) in the best case in exchange for a huge performance increase in the worst (to the extent that there can potentially be no difference between them) is the right thing. 

At this point some people will kick and scream about "wasting memory". I loathe that term; it's not "wasting" it, it's using it. There may be nothing stored in the memory, it may never be read from or written to, but the extra byte per texel is being used to increase performance. This is the very same principle as cache-aligning data, aligning allocations on page boundaries, aligning (or padding) to 16-bytes for SIMD, etc etc etc on the CPU.

[...]

The best-case will run a little slower with this kind of set up. So instead of getting 4000 FPS in DM3 you might get 2500. That doesn't matter a bollocks. You don't optimize the best case, you optimize the worst. Sacrificing a tiny piece of performance (0.15ms) in the best case in exchange for a huge performance increase in the worst (to the extent that there can potentially be no difference between them) is the right thing.

I wholeheartedly agree.

_o_ Here's a hug. 

Also, I'd love to see any hardware, ever, where you can run at 2500 FPS. Optimizing is good; obsessing over it is not. 

Nice writeup, it all seems to make sense even though I don't have much to do with rendering stuff. For reference, it was fitzquake085 on the last map of The Five Rivers Land. Big wide arena mostly covered with torchlight and often a half-dozen dynamic-lit projectiles crossing it. Stuttering went away just by facing outwards, so I thought it must be a rendering thing. Quakespasm copes with it without the adverse reaction. 

Sometimes some newbie shows up and asks why "the Quake community" doesn't do X, Y, or Z like [insert other game, for example "like the Doom community" or "Quake 3"].

But there is no such thing as "the Quake community". Just different individuals of different interests doing stuff they want to do for free.

Its not like someone is demanding Barnak do this or that some Steam user must do this.

No --- because no one makes demands of free loaders and newbies and insists they must do things. 

Ah, I clicked submit instead of preview.

What I was trying to say that even a well-intentioned highly skilled engine coder diatribe about how things should work is still basically saying that someone else has to spend their time a certain way for free.

That point of view has merit.

And it is Tragedy of the Commons because such demands are only directed at the "top producers".

No one makes demands of noobs. 

In a commercial project that would be sold and generates sales, you'd be absolutely right.

In a free project that is a pastime, I don't know if you are right.

And one of the most important rules for a pastime is knowing it is a pastime.

And The Tradegy of the Common very much applies, you made an exit back in 2013 for this reason and I was already making an exit and once I saw you declare your exit, I left too. It was too much of an out-of-control zoo. 18 months later I'd come back -- sort of --- with firm boundaries in my head and communicate clearly the limitation of what I was willing to (not) do and when I was willing to (not) do it. 

MH's now dead engine, DirectQ, could easily clock 5000+ fps on an id1 map. 

I'm pretty sure that's true, no doubt about it.
Do we have, however, some kind of display who can actually show those 5K FPS?
That was really kind of my point. :) 

Here is a partial list of "blockbuster" map releases in the last few years:

a) A Roman Wilderness of Pain [aka ARWOP]
b) The Alter of Storms [aka ne_ruins]
c) Rubicon Rumble
d) Remake Quake

that will grind down to single digit frames per second in a traditional GLQuake style engines. But a DirectQ or FTEQW can instead of getting 12 fps will get 150 fps or 300 fps.

And these kind of mega-maps have been "the norm" in the last 5-6 years. There are plenty more where those came from. 

Whoa. Can they run on vanilla? I'd love to test them on a iPhone ;) 

a) requires enhanced network protocol (FitzQuake 666 or similar)
b) requires enhanced network protocol (FitzQuake 666 or similar)
c) requires BSP2 support, enhanced network protocol (FitzQuake 666 or similar) and should have alpha masked texture support.
d) requires the Remake Quake engine bundled in the download (BSP2, alpha masked texture support, Remake Quake's protocol 999, hurt blurs, other 2D effects) 

What kind of hardware is actually limited to low FPS in those maps? Laptops with Intel GPUs? No system I've played them on with Nvidia GPUs has had issues. 

With what engine? Quakespasm since late 2014 or thereabout has used vertex arrays so the performance is about triple the norm on maps with tons and tons of monsters. 

Usually Quakespasm. 

try them. fix stuff that doesn't work. job done.
its not like engines that support this stuff are closed source, so it shouldn't be that hard considering the stuff you've previously managed. 

Sample source code implementing protocol 666 download source

Every single protocol 666 change is marked with:

#ifdef FITZQUAKE_PROTOCOL

Yeah, every last change is marked. 

Do we have, however, some kind of display who can actually show those 5K FPS?

That's kinda not the part that's important; it's a bit of a strawman, in fact. As some of us have hinted, running DM3 at 5k FPS is actually not an interesting problem. Take 200 FPS: say someone has a 144Hz display and bump the target framerate to 200 to allow headroom for transient peaks. Running DM3 at 200 FPS isn't an interesting problem either. I'm pretty sure that even a low-end phone can do that nowadays.

Running a big, complex map with big, complex scenes at 200 FPS - now that's an interesting problem. You can solve anything if you throw enough brute force at it; but solving it on lower-end hardware too: even more interesting.

Historically the Quake engine was viewed as "can't do big scenes" or "unsuitable for open areas" but it turned out that none of that was actually true. It's obviously not the best engine for this kind of thing, but a primary cause of it's historical problems was in the implementation of it's renderer, and it wasn't too difficult to make the necessary changes to solve those problems.

So do that and what will happen is that running DM3 at thousands of FPS will also happen, but as a side-effect, not as the primary goal. 

1. per-texel lightmap blending?

How does quake's software renderer achieve per-texel blending? example

2. how and where in the rendering pipeline does "palettization" occur?

I assume that illegal colors are produced after a lightmap is blended with the diffuse texture? If so, my best guess is that palettizing is the last step before being drawn, though I have a feeling this is probably certainly wrong.

3. a practical way to achieve this look for a modern game?

Software render? GL render? GL render + GLSL shaders or some other form of post processing?

here is a screenshot palettized in photoshop. I'm currently using these janky mockups to help inform art direction. Obviously, this method is sub-optimal and I suspect this is not close to what an actual game renderer would output. It's a pain in the ass because this rendering style depends on an appropriate art style else it all turns to shit... hence the previous questions.

After spending months testing color palettes, I have a whole new level of respect for the id art team. Cramming quake in to essentially 240-ish colors is an art form in itself.