I'm not astute when it comes to the inner workings of how vis works, I am simply aware of what it likes and doesn't like from the many years of using it. When it comes to Ter Shibboleth, vis was never designed to be used on very large open maps, neither was the original quake engine for that matter really. To make vis do its job on any of the shib maps would in my guess, require a complete re-write of the program from scratch, which may then result in a new BSP format. If by some miracle vis were to complete its task on those maps, there would be visual problems everywhere such as invisible and stretched faces. And even then, the difference in framerate would be negligible because of the open nature of said maps.

I'm not a programmer, the only one who could give you in depth knowledge of how vis works would be ericw. What I can attest however, is that with the advanced rendering methods of vkquake and especially FTE, vis is not really a necessity anymore. Although it is still good practice to release a map fully vised whenever possible. 

A lot of work has been done with the tools, most changes to QBSP and VIS were done way back in the old days but there are still active developments on LIGHT.

Some of the old branches that people used:

Bengt Jardrup's tools: http://bjp.fov120.com/

Tyrann's tools: https://disenchant.net/utils/

One limitation for a lot of improvements you might imagine is the desire for the final format to be compatible with existing engines. It's easy to say that VIS and QBSP are inefficient but they are designed to create the data structures that the quake renderer expects.

I think the main improvements to VIS are making it multithreaded, and also, the more recent development of adding func_detail support to QBSP which has the side benefit of speeding up VIS times quite a bit. 

The best, simplest explanation of the Vis process I've ever seen is in this short (under 3 minutes) presentation by Michael Abrash. He steps you through exactly what the solution is, and it seriously couldn't be clearer.

https://m.youtube.com/watch?v=1AUxDCHaw84

One problem with classic Quake Vis is that it every surface in a map contributes exponentially to the complexity. This is manageable for coarse structures like the ID1 maps. When lots of small detail and trim is added, the number of surfaces jumps and the complexity is too much.

A second problem is that the "visibility through portals" approach doesn't work well with large open spaces.

A third problem is that the generated PVS is static, so moving objects, such as doors, don't help to reduce map complexity.

Much of this is solved by Quake 2, where the BSP format separates structural brushes from detail brushes, and where areaportals can allow doors to exclude parts of the map behind them.

It's true that rendering optimisations can help reduce the requirement for Vis, but only in the renderer. Vis is also used to optimise entity interactions on the server, as well as server-to-client traffic. An unvised map won't be able to use those optimizations. 

Some previous discussion 

https://twitter.com/BruceDawson0xB/status/1120381406700429312

"O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there." 

Thank you all for your answers, and thank you for the quality of them.

That's a fascinating topic. The video of Michael Abrash really helped to clarify the complexity of the problem.

Thank you @chedap of your brief answer about vis (I assume that you are talking about vis) time complexity. When hearing Michael Abrash explain the basics of vis, I had reminiscence about my work in college about the Traveling Salesman Problem; a NP-complete problem that is of time complexity, at best, O(n²).

Therefore, O(n³) leave little hope for easy optimization outside of multi-threading… unless someone hires me for a PhD, and I vigorously refresh my knowledge about computability and complexity, and graph theory.

Interesting story nonetheless. I'll keep digging on my side. I'm still open to any additional information. 

The big optimization with Vis is separation into detail and structure. The idea here is that only structural brushes get used in PVS generation - walls, floors, ceilings. Trim, detail, ornaments, etc are not used in this step.

The algorithm is still O(n²), of course, but the benefit comes from keeping the value of n low.

Here's Carmacks plan explaining it: https://github.com/ESWAT/john-carmack-plan-archive/blob/master/by_day/johnc_plan_19970810.txt

The last significant thing that I am working on in the map format is leaf clustering for vis operations. You can specify some map brushes as "detail" brushes, and others as "structural" brushes. The BSP and portal list is built for just the structural brushes, then the detail brushes are filtered in later.

This saves a bit of space, but is primarily for allowing complex levels to vis in a reasonable amount of time. The vis operation is very sensitive to complexity in open areas, and usually has an exponentially bad falloff time. Most of the complexity is in the form of small brushes that never really occlude anything. A box room with ten torch holders on the walls would consist of several dozen mostly open leafs. If the torch holders were made detail brushes, the room would just be a single leaf.