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... 

Would be like mapper crystal meth. 

@Willem, the source code for the Q3 compiler tools is publicly available, can't it help with the detail brush problem with the Q1 tools?

I still think the engine will need some changes, the AI will certainly need to know about the detail brushes, with maybe some monster clip so they have a simple brush hull as well.

I know Q1 mappers want to create crazy angle stuff but waiting 700hrs for a compile to finish is just barking mad! :P 

But, detail brushes have been done in Quake. Firstly, the Quest compilers have them. They would feel incredibly primitive compared to aguire's tools however.

http://quest-ed.sourceforge.net/

If you have a PowerPC Mac (hah!), then there's a port of said tools with some added features:

http://quake.chaoticbox.com/downloads/equakeutils.sit
http://www.quaketastic.com/upload/files/tools/mac/misc/eUtils_r10.zip (same tools, just more compatible compression)

I'm guessing that Willem was looking at the source of one of these?

Finally, here's a fascinating possibility I found, from the q3map2 readme:

2.5.4 (2003-04-01)

- New: support for Quake 1, Quake 2, Half-Life, Unreal, and UT2K3.
On BSP/-light/-vis, use the -game argument: -quake1 -quake2 -hl -unreal -ut2k3

I have not tested this, and I don't know what it actually means, but there it is, q1 support in q3map2. If it could actually output q1 bsp format, and not just take it as input, then that would almost certainly be the best solution for cutting compile times. 

estimate jumped up to 260h last night so i canceled again.

going to try something else now. i've selected clumps of terrain that are roughly the same height and i chopped all the tops of them off and turned them into func_walls.

this should hopefully preserve shadows a bit but will make the terrain have common planes instead of all different slopes.

if this isn't enough, i'll do the same for all the ground terrain which will be probably 10x more work but should yield good results. it also won't really affect shadows as it's the floor. 

At which percentage did it jump up? Just asking because VIS tend to get slower the further it progresses.

Autist optimization tip: load the prt file with Gtkradiant's prtview plugin and arrange the brushes/portals orderly. 

I think, since the main issue is vis times, the best approach is making changes to the vis process in ways which result in a backwards-compatible bsp file. Rather than making a new bsp format. 

Screenshots:
http://h.imagehost.org/0820/MirageDetail1.jpg
http://h.imagehost.org/0386/MirageDetail2.jpg
http://h.imagehost.org/0679/MiageDetail3.jpg
http://h.imagehost.org/0580/MirageDetail4.jpg

DOWNLOAD!
http://www.mediafire.com/file/qmgnjmemjqz/2p_mirage.zip


To play the map, follow these installation instructions:

Download the Zip file.

Extract the contained 2p_mirage.sga file to:
C:\Program Files\Steam\steamapps\common\dawn of war 2\GameAssets\Mods\

Make a new shortcut to play Dawn of War 2 (in steam, right click on DoW2 and go to 'Desktop Shortcut')

Go to the properties of the shortcut and add
-mod 2p_mirage
to the end of Target section.

Play the game with this shortcut and you will see the map in the drop down list when creating a game.

A few notes:
Base areas are not detailed yet, I'm lazy.
Much of the surrounding terrain isn't detailed yet either.
Haven't done an optimization pass or a fully baked lighting pass yet, which may increase the framerate of the map, but shouldn't really matter much since it's not that bad at the moment anyway (that I've noticed!)
Minimap needs some work.

Not sure how many radical changes I'd be willing to make, but it'll likely be few. Most of the time I hope to spend between now and the Sunday night deadline is cleaning up major issues, finishing up detail work, and baking lighting. 

State 'no sharing this outside of relic' or similar? 

The rule was clarified to be "Any map published and shared previous to the annoucement of this contest isn't allowed".

They fully expected and wanted people to have their maps tested. What they didn't want was anyone taking an already finished map previous to the contest and entering it.