I'd be interested in looking at some sort of Umbra-style occlusion culling for huge levels.

For your regular quake levels I'm sure by far the quickest thing is to just draw the entire level every frame.

(*disclaimer: not a graphics programmer so probably not best to take my advice) 

what are you going to do instead? just submit the entire thing in one go? go ahead!... your engine will start to struggle on complex maps due to all the extra overdraw that you're now doing.
as a partitioning scheme, bsp is just as valid as its always been.

http://triptohell.info/moodles/junk/youredoingitwrong.png
(yes, it still does lightmap animations)
the trick is to not give a damn about frustum culling. once you've done that, you can cache your batches between frames, and once you've done that, you're drawing the entire world with a single draw call, with the only overhead being a point-to-leaf call and a check to see if it changed.
note that you still need the bsp for the pvs, so that you're only using textures that are actually likely to be seen, as well as avoiding overlapping surfaces that have no chance of being seen.
this aproach beats quake's aproach in pretty much every case, the primary exception being if you've got geometry with unique textures behind you (note that bindless textures or texture arrays will massively mitigate this). The other case is if your gpu's vertex processing is weaker than the cpu, which is rare nowadays.

http://triptohell.info/moodles/junk/sixtyfivekay.png
model rendering, with 512 models per glMultiDrawElementsIndirect call, drawing a grid of 65k individually (well, progmatically with different) animating entities in no particular order.

http://triptohell.info/moodles/junk/onedraw.zip windows+sdl binaries, includes source.
this thing's performance pwns my own engine too, but is so much more limited, from-scratch rewrites have that kind of problem.

bsp, kdtree, quadtree, octtree, these are the main aproaches, and not using anything is crazy talk. you still need the tree, you just want to take the emphasis off it. q3map2 gives jumbo leaves, for instance with multiple logical surfaces merged into a single trisoup surface/mesh, whereas my onedraw thing caches everything instead to avoid rebatching. 

Can you please provide a definition for the following terms:

- pvs
- jumbo leaves 

pvs = potentially visible set (which other leaves each leaf can see, meaning you can avoid wasting time with irrelevant geometry).

jumbo leaves = large volumes that do not necessarily define a single convex area with a single content type (thereby allowing more surfaces to be pre-merged reducing costs to deal with them, the further you go with this the leakier and less effective the pvs is, q1bsp as a format isn't suitable for this).

but yeah, you need to stop thinking in terms of surfaces, and start thinking in terms of trisoup and how you can merge that efficiently to avoid overheads.
typically its faster to just merge a few more indicies into your batch than it is to try to cull that geometry - with sse, you can potentially load/store 8 indicies with a single instruction. gpus are massively paralell and won't even notice until you reach a 2048 boundary (and even then, meh).

and yeah, glMultiDrawElementsIndirect is awesome (and potentially emulatable). combine it with array textures to win (these exist in gles3 - use one array per 'shape' and you can significantly reduce batch counts/draw calls). 

TrenchBroom is a map editor that runs on a Mac. 

Cool! Nice to know. So... what was the point, again? :) 

Using a map editor a few times would give you more insight into the Quake map format and how the bsp works. 

Ah. That is actually a good point :) 

For example ... how would you describe an unvised map?

Now, every mapper here knows what that is.

But if Spike makes references to things that the average mapper knows, but you don't know what they are --- how are you going to participate in your own conversation? 

.map and .bsp are fairly far removed.

small note, fte can actually load .map directly (map foo.map - the extension must be included).
of course, the overdraw is a killer, and the tracelines are excessive. Its fine for small maps of course, but when you have those big maps it can end up unworkable, especially if you have rtlights enabled.

and yeah, macs can be an issue. glMultiDrawElementsIndirect only has its full functionality with gl4.3, while macs are still limited to gl4.1. luckily, its really the texture arrays that are the biggest saving, but its still annoying.