A technical article where I delve into more details about the PVS creation and visibility calculation and their implication on optimization in the Source engine.
IntroAfter I published my article last week about “demystifying source engine visleaves”, several people contacted me and expressed interest in knowing further details about this subject. That article was written to be user-friendly even absolute beginners can understand; I made sure to over-simplify the subject and steer clear from technical jargon.
The previous article will serve you well to understand visleaves and PVS and translate the knowledge into optimization techniques. I didn’t think that there would be much demand for more in-depth details on the subject among designers but it seems there is.
This current article will be a natural follow-up to the previous one where we delve into more details about the PVS creation and visibility calculation and their implication on optimization. It is highly recommended that you read my previous article on visleaves and that you have intermediate knowledge on source engine optimization before reading further in this article.
PVS in real action
What we are about to see regarding PVS and visibility calculation is practically common to all BSP-based engines such as Quake, GoldSrc and of course, Source, despite their slight dissimilarities.
I learned most of what I know about BSP, trees, leaves, and PVS from the amazing work and in-depth technical papers of Gary Simmons back in 2000. His 200+ pages of code, diagrams, and thorough technical explanation were instrumental in getting one to be intimate with the BSP technology, and were even enough to let you code and start your own BSP engine.
I will try my best, using clear terminology and detailed diagrams, to condense all what I previously learned in this simplified article. There won’t be any code obviously since I’m no programmer, but rest assured that all the “meat and gravy” will be here. Grab your cup of tea or coffee, sit tight, clear your mind (and schedule), and prepare to wander through a twisted journey inside the PVS.
The actual processRemember the arrow technique that I told you about in the last article? Good. That was a very over-simplified explanation of what happens to determine the PVS. It is a very useful technique that you, the level designer, can use on the fly when in-game to determine what your current visleaf is seeing and to decide where you need to further cut visibility using hints and areaportals.
In reality, things are a bit more complex and the process of determining the PVS and calculating visibility is not as simple as shooting a straight arrow to the next visleaf. I guess you expected this and saw it coming from miles away (or from the start of this article at least).
Turns out that vvis is not Robin Hood after all; sorry to bust this for you (hey, did I also tell you that Santa is not real?)
Vvis in reality is more “scientific” than an “outlaw” roaming Nottingham forests. Vvis relies more on algebra and geometry to calculate the PVS.
Before diving into the technical explanation and the diagrams (there will be plenty, don’t worry), I need to showcase and explain a specific concept that is key to understanding and visualizing how the engine proceeds with the PVS creation.
The penumbraThis is a Latin word; you can cut out all gawking and eyebrows movement right now.
In all seriousness, umbra is basically the shadow that is cast behind an opaque object when hit by light. Umbra is the darkest shadow area while penumbra is the region of lighter shadow usually at the edges of the umbra. The best way to visualize this effect is by examining a solar or lunar eclipse. You can check out this Wikipedia article for further details.
You can see that the umbra is delimited by the red lines, the penumbra by blue lines, and the area outside the penumbra will be totally lit; since it is the opposite of shadow area, we will call it “anti-penumbra” (please disregard the antumbra in the above image as it is not related to our anti-penumbra).
In everyday life, the anti-penumbra effect is best shown when light floods from a well-lit room into a totally dark room through an opening, usually a door or window.
The area inside the dark room that is lit through the door is the anti-penumbra. Because light propagates in rectilinear paths, there is no way the entire room can be lit, only the portion that can be seen through the exact width of the door opening. Here’s another example.
You can also see here that light goes through the doorway opening to form an anti-penumbra while on both sides of this light are still dark areas (umbra).
Think of these rooms as visleaves, and doorways as portals between leaves. The visibility will be governed by the exact width/length of the portal that determines how much of leaf 2 can be seen from leaf 1.
Portals and clip planesNow that we know the anti-penumbra effect and how it governs the PVS visibility, how about we see all this in action.
To calculate the visibility and therefore establish a PVS using the anti-penumbra effect, the engine needs to have 3 components: the visleaves, the portals, and the clip planes. The method is called anti-penumbra clipping.
Visleaves are the “easiest” part since they are already created and stored in the BSP tree. The engine knows exactly where these leaves are and what is solid and what is empty in the 3D world.
The engine does not initially know the “gaps” between leaves and we have established that we definitely need to know the exact “gap or doorway” between visleaves to be able to create the anti-penumbra.
The engine creates temporary polygons known as “portals” along the splitting plane (the common border if you want) between 2 leaves. The polygon is initially larger than the “border” itself, and it is then clipped against the nodes of the Solid Leaf BSP tree that contains all data about visleaves; since the engine already knows what is solid and what is empty in the game world, any fragments of the polygon/portal that fall in a solid space (inside a wall) or in the void, will be discarded leaving only the part that is actually a gap or doorway between the 2 leaves. This step is known as portal generation and clipping.
These portals are temporary as we said earlier, and only exist to calculate the PVS; they are not part of the PVS and will be discarded once all calculations are finished.
The engine has now visleaves and portals, and still needs clip planes to intersect and form the anti-penumbra. A clip plane is basically a plane, a flat two-dimensional surface that will go from one portal edge to the opposite edge of the second portal, dividing the portals on opposite sides of the plane.
The below image shall clear things up.
From the side view (in 3D perspective), you can observe that the clip plane is made of the 2 vertices A and D of portal 1 and the opposite edge B1 of portal 2 (notice that the portals are just polygons).
From the top view, the clip plane appears as a straight line that goes from portal 1’s edge to the opposite edge of portal 2. With all this said and done, it is not hard to imagine how the anti-penumbra will be created.
There you go. The anti-penumbra is basically the maximum area/volume that can be seen through a portal. The anti-penumbra will stop when it hits a solid brush.
We have now identified the anti-penumbra, the visleaves, the portals, and the clip planes. We have everything we need to start our PVS visibility calculation.
The PVS in actionIf all the above explanation and diagrams made you dizzy and on the edge, do not fret, do not panic. Take another sip of that cup of coffee and relax. You will see all the above unfold before your eyes with some vibrant images and diagrams, and I will try my best to have a very clear explanation of the whole process.
What a colorful and lovely image!
(- very insightful comment, isn’t it?
- Hey, it took me a considerable amount of time to make all those images in Photoshop, show some respect, man and enough with the sarcasm.
- you’re right, I’m sorry)
Please excuse my inner voices fighting and let’s get back on track.
In the above image, we have an assortment of visleaves (ABCDEF) that are connected with each other through different portals (the yellow lines labeled 12345). We will focus our study on visleaf A; what we want to do now is determine and calculate the PVS of A as it is done actually by the engine using anti-penumbra clipping, and not by utilizing Robin Hood’s arrows.
A can connect to B through portal 1 (the actual connection in-game could be a door, doorway, or hallway), and other borders of A are completely solid (think of all these visleaves as rooms with doorways).
Since A is the current visleaf that the PVS is calculated for, it is called the “source leaf”, and ergo, portal 1 is called the “source portal”. Visleaves A and B share a common portal (1), therefore B is automatically in the PVS (B can be seen from A). The engine checks visleaf B, called “destination leaf” and notes the presence of two portals (2 and 3); these will be called “destination portal”. The engine will tackle each destination portal one at a time.
Let’s start with portal 2.
The leaf beyond portal 2 (leaf C) is called “generator leaf” and any portals inside it are called, you guessed it, “generator portal”. This nomenclature is very important and I will be using it a lot in the remainder of this article.
As we explained in the previous paragraph, the engine will create the clip planes between the source portal (1) and the destination portal (2) to create the anti-penumbra 1 in leaf C. The anti-penumbra 1 is in leaf C, therefore leaf C is in the PVS. The anti-penumbra 1 is also the maximum area that can be seen from leaf A through portal 2 (notice how it stopped once it hit the upper solid border/wall of leaf C).
What about the generator portals I hear you ask? Excellent question.
If the generator portal is inside the anti-penumbra or the anti-penumbra touches it (even partially), then the leaf beyond it is visible and in the PVS. If the generator portal is outside the anti-penumbra, it will be clipped and discarded from the PVS (no wonder it is called anti-penumbra clipping, huh).
In our example, generator portal 5 is well outside the anti-penumbra 1, therefore, it is clipped and leaf F is discarded from the PVS. Since there are no further generator portals in C, the PVS calculation relative to this leaf stops here.
The engine now switches to destination portal 3 in leaf B (we’re done with portal 2).
Just as we did with portal 2, the same procedure takes place with portal 3. The clip planes are created between source portal (1) and destination portal (3). B is still the destination leaf but now D is the new generator leaf, ergo, portal 4 is the new generator portal. The anti-penumbra 2 is inside D meaning that D is in the PVS of A.
Generator portal 4 is outside the anti-penumbra 2, therefore, it is clipped and the leaf beyond it, E, is not in the PVS. In summary, the PVS of A is (BCD).
I can see you are about to ask another question. What happens if the generator portal is inside or touches the anti-penumbra? (you were about to ask it, right? right?)
In the examples above, both generator portals 4 and 5 were outside the anti-penumbra, therefore, their respective leaves were not in the PVS. What would happen if they were in the anti-penumbra? What would the engine do? Would it get overwhelmed and ask for a leave? (see what I did here…nevermind).
The engine will man up and charge forward, doing extra calculation. Let’s see this with images.
You can observe that I changed the location of leaf F and portal 5 in a way to touch the anti-penumbra. I also added a seventh leaf called G with an additional portal 6.
If you look closely, you will notice that the anti-penumbra crosses portal 5 in its middle and only half the portal is in the anti-penumbra; this means that only this portion of portal 5 is seen from A through portal 2. Keep this info in mind, we will get back to it very shortly.
The procedure is exactly the same as with the previous example.
The engine will create the clip planes between the source portal (1) and the destination portal (2) to create the anti-penumbra 1 in leaf C. The anti-penumbra 1 is in leaf C, therefore leaf C is in the PVS. Contrary to the previous example where portal 5 was outside the anti-penumbra and was discarded, this time portal 5 is partially in the anti-penumbra. This means that the leaf beyond it, leaf F, is now in the PVS.
The PVS calculation cannot stop now since F is in the PVS and the engine needs to recursively check whether visleaves adjacent to F are also in the PVS. Leaf F has one portal, 6, and it needs to be checked to determine if it is within the anti-penumbra.
You will probably say it’s obvious that portal 6 is not in the anti-penumbra. Here’s the interesting and catchy part. Anti-penumbra 1 was relative to portal 2 and leaf C but now we are checking leaf F and portal 5. So…what to do?
A new anti-penumbra of course (can’t get enough of them).
A is still the source leaf and portal 1 is still the source portal. Leaf C is now the new destination leaf, portal 5 is the new destination portal but there is a little trick. Not all of portal 5 is the destination portal, only the portion that was touched by anti-penumbra 1 (interesting, isn’t it?). This means that when the engine creates the clip planes through portal 5, they will not cover the full width of 5, only half of it, the exact width that was previously in anti-penumbra 1.
Leaf F is the new generator leaf and portal 6 is the new generator portal.
The clip planes will be created between source portal 1 and destination portal 5 (only half of it as we established earlier. Notice that the clip plane goes through its middle and not the full width). The newly created anti-penumbra 3 is narrower and smaller than the previous anti-penumbra; this represents the maximum area/volume of leaf F that can be seen from leaf A through portal 2 and portal 5 successively.
There is one generator portal in F, portal 6, and it is obviously outside the penumbra, therefore, portal 6 is clipped and leaf G is not in the PVS. Since there are no other generator portals and the anti-penumbra hit a solid wall, the PVS calculations will stop here relative to leaf F.
In case portal 6 was touched by the anti-penumbra 3, then the same process will repeat: F becomes destination leaf, 6 becomes the new destination portal, and clip planes will be created between portal 1 and whatever portion of portal 6 that was inside anti-penumbra 3. Generator portals will be clipped against the new anti-penumbra and the process stops if none are in the anti-penumbra, or continues in case one of them falls within the anti-penumbra.
The classic PVS is recursively calculated in the way shown above, the more or less "conservative" approach.
In some PVS implementations, there is also a "reverse clipping" that occurs to further shave off the source portal, ergo the anti-penumbra, and get a slightly more precise PVS, but at the expense of a longer compile time.
After we established that only half of portal 5 is touched by anti-penumbra 1, the engine takes this half-portion and treats it as the new source portal. The engine keeps portal 2 as the destination portal, and considers portal 1 now as the new generator portal. The clip planes will be created between new source portal 5 (the half width), and destination portal 2. This “reverse clipping” leads to a new anti-penumbra 4 that will clip portal 1 as can be seen in the image below.
This result will establish that only this portion of portal 1 can be seen from portal 5 through portal 2. The engine will combine the findings of anti-penumbra 1 and anti-penumbra 4, and the “clip to anti-penumbra” function will recur to re-create a slightly more refined anti-penumbra 3. The smaller anti-penumbra allows the engine to clip out the generator portals faster by recursively reducing the chance of hitting the next generator portal because the anti-penumbra is getting smaller and narrower more quickly (since we are clipping both the source and generator portals).
Notice in the above image how the clip planes are created between half of portal 5 and leftmost portion of portal 1, to create a marginally smaller anti-penumbra 3 that will lead to a slightly more accurate PVS.
In the above image, I highlighted in red the difference between the original anti-penumbra 3 and the refined one (the small red area in leaf F to the left of the yellow anti-penumbra).
After seeing all this visibility calculation in action, I am pretty sure that you will excuse vvis when it takes some time to finish. The “portalclusters” number in vvis is actually the number of visleaves in your map while the “numportals” number is that of portals. The “portalflow” phase is where the advanced algorithm kicks in to do all the calculations we have seen earlier.
Naturally, the more leaves and portals your map has, the more time it is going to take vvis to finish its calculation.
Implication on optimization
We have seen so far how the engine actually creates the PVS and calculates visibility between visleaves. It’s all nice and fancy but the real issue is how to translate this into good optimization.
The answer lies in my previous papers and articles (duh), and in the previous article, we came to the conclusion that the smaller the PVS, the better FPS you will have.
All the visibility calculations won’t do any good if the visleaves in the map are poorly laid and cut. Vbsp is the culprit here as well as the level designer who sloppily placed his brushwork all around.
As I mentioned in my practical guide on hints placement article, vbsp does a poor job in delimiting visleaves; this only gets worse when the designer carelessly designs his layout and places his brushwork in a way to aggravate the situation. Visleaves end up being tall, wide, long, extending to upper skybox level, peeking around corners, poking through doors, windows, and hallways. The PVS grows bigger and the fps gets lower. You get the picture, it’s pretty grim.
Knowing how visleaves, portals, and anti-penumbra work, you have the right tools to shape your visleaves the way you want and make the maximum of the visibility calculations that we have seen earlier.
Getting back to our first example in this article, let’s see how we can shape the PVS using hints and areaportals.
As we have established earlier in the first example, the PVS for A is (BCD). When the PVS is being created, every leaf that is visible to A is flagged (1) in the PVS array in the BSP tree. When you, the player, are standing in visleaf A (anywhere in the visleaf, exact position doesn’t matter), the engine will go through the PVS array for A and render any leaf flagged (1). Visleaves B, C, and D will be drawn and all their content rendered.
In the image above, the player (the nice white dot) is standing in visleaf A, next to the letter A (top view). B, C, and D, as well as their content, are rendered.
This is a total waste if you ask me. Logically speaking, you are standing at the leftmost part of A, so technically the area in B next to the letter B, the area in C around the letter C, and almost all the area of D cannot be seen by the player.
Despite this logical view, the engine doesn’t care much; as long as you are in visleaf A, all of the PVS is rendered. The PVS size in the example is considerable, almost 3 times the size of A, and if these visleaves (BCD) are highly detailed, then expect frame rate drops. The engine after all has limited resources to spend, and if you force it to over-render, putting an additional overhead, other resources will suffer and fps will decrease.
Let’s see what we can do with hints (hint: a lot).
If you remember correctly, the anti-penumbra was the maximum area/volume that the source portal (ergo the source leaf) could see of the generator leaf through the destination portal. With this info available, we can deduce that our best shot of reducing visibility is by placing hints along the clip planes. Check out the below image.
The white dot is still the player’s location, the purple lines (4 in total – A to C, A1D2, A2C2, B2D) are the hint brushes (the blue lines that are resting on the doorways between the leaves are areaportals but we’ll get to them a bit later).
I know, you must be thinking right now: are you out of your mind? (I’m not, thanks for asking). The number of visleaves just exploded (A-A1-A2-A3-B-B1-B2-B3-B4-B5-B6-B7-C-C1-C2-D-D1-D2-E-F); is it bad? No it’s not.
Remember that our aim is the PVS, not the number of visleaves. We’re playing a game of chess against the engine; sometimes we sacrifice a pawn to capture its queen. Hint brushes will cut visleaves into smaller ones but this is done for the greater good of PVS.
With this setup in place, the player is still in visleaf A, but A is now a shadow of its former self (hello…Shakespeare called, he wants his fancy words back). Visleaf A is now a much smaller leaf that has no direct line of sight to half of leaf B, all of leaf C, and all of leaf D. An image will clearly illustrate this.
I painted the new PVS of A in white to better see it and gauge the proportions. The PVS consists now of visleaves A1, A2, A3, B2, B3, and B5.
How cool is that! We reduced the PVS to approximately 1/3 of its former size. Visleaf A now does not see B, B1, B4, B6, B7; it also cannot see anything in C/C1/C2 or D/D1/D2. The player in A will enjoy considerably higher fps than it was the case with the old PVS.
The trade-off in this case is that we increased the number of visleaves, therefore, we also increased the number of portals between these leaves. As a result, vvis will take more time to finish but that is really a small price to pay for enjoying luxurious frame rate in-game.
This is also the exact reason why I said in a previous article of mine (common misconceptions in source engine optimization) that one should not confuse vvis time with in-game performance. A long vvis time does not necessarily mean a badly optimized map; it could actually be quite the opposite in some cases. A large, tightly-optimized map can see vvis time jump from couple of seconds to several minutes and even an hour due to all the additional visleaves/portals/anti-penumbras the engine has to calculate and deal with. The high fps in-game will totally justify this vvis time.
We have reduced the PVS using hints placed along the clip planes/anti-penumbras. How about we further reduce the content rendered inside the PVS? Sounds like a good idea.
Remember in our example that we had areaportals placed on the doorways between the visleaves (the blue lines in the image). Areaportals are best placed in the location where the portals were created (the temporary polygons during PVS calculation – don’t confuse the two). This works best when the 2 visleaves are actually 2 rooms with solid walls connected by a door/window (like our example image above). Obviously, it does not work well when the 2 visleaves can see each other totally without solid walls in between.
The player is still in A and can still fully see A1-A2-A3, however, when looking through the doorway, there is an areaportal in place. The view frustum culling effect is added; in simple terms, the areaportal will cull whatever parts of the PVS behind it that are outside the player’s view frustum (field of view). I highlighted in light blue the view frustum behind the areaportal and the 2 white areas on its sides will be culled (not rendered, which includes both world geometry and props/models). This effect is an utmost necessity in optimization and that’s why I cringe when I review a map and notice that the level designer did not include areaportals, at least on doors/windows and hallway ends.
You have to admit that this is really phenomenal if you take a second to think of it (take more if you need). We reduced the PVS/content to be rendered from full (BCD) to the measly A1-A2-A3 in addition to the tiny blue portion of B2-B3-B5.
I guarantee that the fps will see huge improvements after implementing hints and areaportals to control the PVS. To give a you rough idea, on many third party projects that I previously worked on, it was not uncommon to see the fps increase anywhere between 10-15 to 80-90 fps after implementing the optimization system and keeping the visibility under tight control.
If you need to know more about hints and areaportals and where to strategically place them in your map, check out my previous articles: “practical guide on hints placement” and “practical guide on areaportals placement”.
ConclusionThat was quite an article, I give you that. If you read it all and emerged unscathed at this conclusion, then props to you. If it’s any consolation, it was also quite exhausting for me too, to prepare and write this article but I believe it was worth it at the end.
If you understood this article and the previous one, then congratulations; you can now dominate and conquer the Source engine should an optimization war erupt between you two; you already know its innermost secrets.
November 26, 2015