willem: yes, and thank god for it too.

shambler: on the bright side, you get about 4 or 5 maps instead of one! 

that makes Vis take so goddamn long? I never really grasped that. 

Quake is meant for small to medium sized enclosed levels made of rooms and hallways and the technology was optimized for that. It's not a general purpose rendering engine, really.

So, deviate from that spec too much and you get pain. 

I understand that (from painful experience). I'm seeking technical reasons beyond "it was designed to do x not y" :) 

i also think that when qbsp is creating portals, it can't seem to deal with angled floors so it creates a bunch of small portals to approximate the shape.
when you consider terrain where you have pretty much an infinite amount of different slopes and what-have-you, you can imagine how bad it can get.

had a brief chat with aguirRe and what i understood is that you should be aiming to do all your major vis-blocking with a fast vis.
fast vis discards massive amounts of calculations that won't have to be done when you're doing a full vis.

unfortunately, a canyon, for example (or a high cliff wall that isn't flush with the ceiling) isn't enough for fast vis to work with, so it then delegates all that calculation to the full vis process which then has to iterate through everything bit by bit. 

"I understand that (from painful experience). I'm seeking technical reasons beyond "it was designed to do x not y" :)"

Well, the two seem sort of hand in hand. The technology was designed around a certain level design style (highly occluded environments with simple geometry) so it would stand to reason that any inefficiencies that didn't conflict with that goal would be left unoptimized as it doesn't stop them from shipping.

I don't know specifics but the overall gist seems fairly clear. :) 

take for example a simple square 128x128 hallway.

from what little i understand, the interior of this completely square hall is 1 leaf.

if the hallway had a 16 unit deep and 64 unit wide trough running down the center of the hall, that would be either 2 or 3 leafs.
if 2: 1 leaf for the 16x64 trough space + the hallway leaf.
if 3: 1 leaf for each side of the trough and 1 leaf for the trough from floor to ceiling.

each time there's a leaf, vis has to figure out if it's visible from another leaf.

the more complex the geometry, the more leafs there will be, hence the more calculations required.

in the case of some funky canyon with all kinds of angles everywhere, there might be say 50 leafs for a small cross-section of it. (totally guessing with arbitrary numbers here, but you get the point).

now, say you had your 128x128 hallway with a 90 degree bend in it. calculating what's visible around the corner is simple as there's only 1 leaf for each part of the hallway split by the corner.

if you had a same 90 degree corner on your canyon, vis will have to take into account the 50 leafs on one side and test each leaf against the other 50 on the other side of the corner. that's 50x50 = 2500 checks.

i don't think i'm entirely correct here, but this is the gist of it, afaik. 

there must be an engine port out there that will display leafs in-game? i know hl2 can do that which helps when optimizing with details. 

I understand very little, but it gives me some idea of what you guys have to wrestle with. 

darkplaces can display portals, which is similar (you can infer the shapes of the leafs based on the portals) 

and as for the question of why vis takes so long...

First, imagine shaking hands with everyone in the room. With a room of 10 people, there are 90 handshakes needed. With 100 people, there are 9900 handshakes needed. So the cost of adding a person is greater with more people already in the room, it's not linear.

Vis is even worse than that, though....

Imagine you have to pass notes to everyone in the room. If people are far away your note has to be passed between many people to get to the recipient. So in a room of 10 people, 90 notes need to be passed, but each note requires an average of (say) 5 passes, that's 450 passes.

With 100 people, that's 9900 notes to pass, with an average of 50 passes per note, for 495000 passes.

Okay, but Vis is even worse than that....

Now imagine you need to send a note to everyone in the room and you need to send a copy of that note through every possible route that connects you to the recipient. That's pretty much what vis does.

This exponential growth far outpaces the geometric growth of CPU power in the last twelve years.

This is why vis seems best suited for smaller, less detailed, less open maps. The exponential growth can take something that seems trivial (2 minute vis) and turn it into something insane (200 hour vis) over a relatively small growth in map complexity (say, 4x the geometric details.) 

For people who know some computer science, particularly complexity theory, it's worth considering just how complex vis is to process. If you have n leafs, then you need to make n*n visibility tests. But don't be fooled into thinking that makes it O(n^2).

The problem is that one visibility test consists of seeing if ANY of the other n-2 leafs lie in-between the two leafs you are testing. The two bits of good news:

1) If you find any leaf which totally separates the two leafs, then you can stop. Obviously this is more beneficial in maps where line-of-sight is blocked.

2) You only need to look as far as the common node of the two leafs in the bsp tree. Anything on the other side of the separating plane at the node above can't come between the two leafs you are testing.

The latter point is helpful for leafs which are close together, as it should mean that they also near on the bsp tree. However, the problem for open maps in 1) is made worse by 2). Once you start having two leafs which can see each other from a great distance away, you have a huge chunk of the bsp to test in order to verify that they can see each other, and you have to test it all.

So I think in the worst case, like a big open subdivided cube where every leaf sees every other one, you have to conclude that vis is O(n^3), which is why it gets so much longer as you make the maps larger. In the worst case, that means doubling vis time every time you increase the leafs by 25%.

Disclaimer: I did not refer to any of the source code for the above code, it's all just off the top of my head, so correct me if anything is inaccurate 

 

ah and Scapie you never been a good Quake mapper why try wo2 or what the fucking name is?

quit?
get a life out of the internet?
stop been a stupid fuck? 

Don't rise to it. He's clearly drunk and been turned down by the mrs for the 700th day running... 

Holy. Shit.

How does that play into parallelization? Would a map consisting of one huge open area not benefit much from multiple threads? 

 

metlslime explanation is quite clear, and well depicted: vis process is a recursive algorithm. checking the code you can easily see it... However the stop condition is pretty unclear to me, still today.
It explains why it is exponentially runtime consuming regarding the map geometry... the more portals/volume you have the worst the runtime will be. The only way to improve it is "donuts" vis blocking, and map occlusion, in order to cut the map into pieces, and limit the number of branches in the recursive tree... though...
I don't whether it would be possible to rework the Quake engine to make it working with 3D GFX in order to let it in charge of the map rendering.. As far as I understood, today the Quake engines are software rendering only.. or am I wrong ? Please correct me if so..

PS: Please read me correctly, I don't want to port Quake up to nowadays engine level complexity... The fun with Quake is that it is easy to map for. Being able to build beautiful maps with lot of limitations inherited from the game engine makes the fun, else if it would have been possible since the very beginning to do giant wide open map, I think it would have been that fun... my 2 cents ;) 

...I think it would NOT have been that fun.... 

yes yes 

Shambler, i don't even understand half of what they're talking about myself, and look how many maps I made. it's no wonder they were all so small. 

Really I don't understand why it has not been done for Q1 yet, DETAIL BRUSHES!

All these crazy VIS times would just go away as the compiler would work with simple shapes again. Lets face it, all of the latest Q1 engines everyone uses are so far away from the original Q1 spec, why not just add a special new detail brush switch? So people can go nuts and create crazy angled stuff.

@Trinca, terrible comment. >:( 

sock I had worse comments on some of my maps and i didn�t deserved or died... 

"Shambler, i don't even understand half of what they're talking about myself, and look how many maps I made. it's no wonder they were all so small."

Well, that was part of the beauty of Quake. You didn't HAVE to know any of that stuff to produce a map. As long as you had a copy of VIS.EXE, you were good to go. :)

"All these crazy VIS times would just go away as the compiler would work with simple shapes again. Lets face it, all of the latest Q1 engines everyone uses are so far away from the original Q1 spec, why not just add a special new detail brush switch? So people can go nuts and create crazy angled stuff. "

It's not the engines that need to support that, it's the tools. I tried to add detail brushes to QBSP but that code is, quite honestly, a god damned nightmare. It's a horrid mess and I wasn't able to figure out what to do to make it work fully. 

I wasn't able to figure out what to do to make it work fully

I believe the solution involves a large mallet...