|
How VIS works
by Egir Helgrimson>
Disclaimer
This document is more like a how it might work, than how it actually works. I have yet to learn what is actually going on. For now I'm just guessing, and the idea is that I'll update this document as I get more enlightened. In order to get it right, you might have to start by getting it wrong, in that way you are at least getting it B). I am going to write as if what I am writing is facts, but I have neither sources, nor any experiments to prove myself, so if you need a source for some school assignment, this document does not qualify.
Introduction 
VISing is the part of the compile process where visibility is calculated. This however is a quite delicate process, divided into two faces. Which according to the compile log are:
Nodes
Before the VIS compiler is invoked, the BSP compiler has done a VIS preparing task that is essential to map performance, when it is run in game. It devides the map into nodes. Nodes are basically little rooms filling up the map, so that no mater where the player is, he will be inside some node, as long as he is inside the map. To explain further, I'll use an example.
Example 1 - filling the map with nodes
This is our map, seen from above.
BSP now figures out how to fill the map with nodes. It may look something like this, where each colour represents a node.
Where nodes intersect we have a portal. Now that we know everything about how an when nodes are created we can move along to the next exciting topic.
BasePortalVIS
The name suggests that these calculations are all about which portals are visible from the active node. What we can see and what we can't see can be hard to predict, though we can be pretty sure that we can see what's inside the node we're in, and what's inside the node next to the node that we are in. (The ajacant node).
Since we have five nodes in our example, we would initialise 5 node trees. Building the BasePortalVIS will make us end up with five trees looking something like this.
The darker colours represent the root nodes, and the lighter colours represent the adjacent nodes. These calculations aren't especially hard to do (de_slap took about 1 minute).
Now we know what in any case should be able to see, and that is whats in the node in which we are, and what is in the node next to us. But what about the nodes that lie next to the nodes that lies next to the node that we are currently in. And what about the nodes lying next to them etc...
LeafThread
The nodes that lie next to the nodes that lie next to the root node are metaphorical leafs on the tree since they are in the opposite end of the tree trunk as the tree root. Since I take it that very few of my readers knows what a tree looks like I've drawn an overview so you won't get lost in my technical language.
Now it is clear what LeafThreads needs to do, it needs to find the leaves that correspond to each leaf node. I'll again surrender to the power of an example.
Example 2 - Finding the leaves corresponding to the orange node.
We find leaves be checking which portals we can see from a portal in the root node, through a portal in a node next to the root node. This is illustrated below.
Obviously we can see the portal between the red and yellow nodes, but we cant see any of the portals either between the yellow and blue node, nor between the blue and the green node. This will result in that, when you are in the orange node, only polygons in the orange, red and yellow rooms are rendered. This is illustrated below.
Nodes hatched with orange are the only nodes visible from orange. (which makes them leaves on the orange tree, so to say).
How is this done?
If a portal has a coordinate that lies within any span of vectors each made by two points in an already visible portal and a portal from the root node respectively, its nodes are visible if and only if this portal belongs to an already visible node from the corresponding portal in the root node. HLVIS recursively repeats this from the newly sighted portal, and the corresponding portal from the root node to see if we can spot additional portals. Only portals next to an already visible node needs to be tested to see if they are within the prior mentioned span.
I trust what I just wrote in the previous paragraph didn't make sense to anyone. So I guess I once again have to spawn another example.
Example 3
We have only the portals to worry about. The orange portal belongs to the root node. The blue portal belongs to a neighbour node. And the green portal is the one that we will try to see if we can actually see. In other words, the question is, can we see the green portal, from the orange portal through the blue portal.
To solve this problem out, all we have do do is find all the vectors that we can make using one point from the orange portal, and one point from the blue portal respectively. That leaves us with no less than 16 vectors, as illustrated below.
It looks like a mess to be honest, and this is also what explains the long compile time HLVIS uses for the LeafThread calculations. Whether all vectors are used, or some bright head figured out which one could be spared away, I have no idea. By scaling these 16 vectors with different scalars, and then adding them together, we may be able to reach a coordinate somewhere in the green portal, and if so, we can conclude that the green portal is indeed visible from the orange portal. Just like this.
Whether this has anything to do with the quite useful point file created if a LEAK is found I will leave to your imagination to figure out, since I have no idea.
Conclusion
I conclude that because of the complexity of calculating the LeafThread the very same calculations are quite time consuming. I have a good idea on how to theoretically half this time, if this article contains a bit of truth in it. I hope you enjoyed reading this, and that has helped you to understand my understanding on how HLVIS works.
| 