An article in which I explain Source visleaves in layman's terms to allow beginners and veterans alike to understand the cornerstone of source optimization
Demystifying Source Engine Visleaves
Intro
Another fitting title for this article would
have been “a beginners’ guide to source engine visleaves”; this is because I
will be simplifying the definition of visleaves using layman’s terms and plain
English in a way that even beginners can understand and grasp.
I won’t be using technical jargon or advanced
lingo; just simple terms even absolute beginners can follow. It is very
important to grasp the concept of visleaves, otherwise all optimization efforts
will be useless and aimless. Once visleaves are understood, optimization
becomes very easy; you can trust me on this one and you will see it unfold
throughout this article.
Definition in plain English
Before defining visleaves and giving
tangible examples, let me give you a brief historical background about them.
Visleaves were first discovered by
Adam and Eve as they used “leaves” to cover the “visibility” of their private
parts. The guys at Id Software learned about this discovery and wanted to
acquire the copyrights of these visleaves. Adam refused, so Id threatened to
summon a powerful “Quake” that will bring “Doom” upon humanity. Adam had no
choice but to relinquish visleaves to Id.
Now with this “accurate and very
true” historical background out of the way, let us examine the modern
definition of visleaves, in the frame of the Source engine (if you want an
in-depth look at BSP and visleaves concept, please consult my paper Man Vs
Engine, paragraph II).
In the simplest definition possible,
a visleaf is just a polyhedron (polygon in 3D space), most likely a cube or
rectangular cuboid, although other shapes are viable options too. Think of a
visleaf as a room with 4 walls, a floor and a ceiling, only these are
transparent and non-solid.
Any map in Source is basically a group of these
“rooms” connected together where the player can freely travel from one to
another (as long as they are on ground level); the player can only be in one “room”
at any time.
The size and borders of these “rooms” are
generally decided by the surrounding geometry (the world brushes) and by hints
and areaportals. The creation and division of these “rooms” is done by vbsp
during the map’s compiling.
Let us check some examples about these “rooms”
or better revert to calling them visleaves, shall we. I will use my map cs_calm
for the examples.
Can you see the blue lines going on
the XYZ axes to form a rectangular cuboid? Good. This is the visleaf, plain and
simple. I, the player, am standing right inside the visleaf.
Let me switch to third person view
so you could have a better angle to check the visleaf.
Much better now?
You can clearly see that the player
is within the borders of the visleaf. As I said earlier, the player can only be
in 1 visleaf at any time.
From the top view, we can represent
the flat visleaf as a rectangle. We will call this visleaf “A” for the
remainder of this article.
Once these visleaves are created, vvis runs an
algorithm to calculate visibility between these visleaves and to determine what
we colloquially refer to as a visleaf “seeing” another visleaf.
In the simplest explanation of how
“seeing” is determined, just imagine that vvis is Robin Hood with his bow and
arrows; vvis, sorry Robin, will stand in the visleaf and fire his arrow towards
another visleaf in a perfect straight line. If the arrow reaches the other
visleaf unobstructed, then a direct line of sight (LOS) between these 2
visleaves is established, and we can say that the first visleaf can “see” the
second visleaf. If the arrow has to cross a world brush/geometry, a skybox
brush or travel in parabolic/hyperbolic trajectory to reach the second visleaf,
then there is no LOS and these 2 visleaves cannot “see” each other.
In the screenshot above, visleaf B
is adjacent to our visleaf A, therefore, a direct LOS can be established
between them (white arrow). A and B can see each other.
The second visleaf does not need to
be adjacent to be seen. A visleaf further away can still be directly seen by A.
In the screenshot above, the white
arrow shoots straight from A to C which means A can see C (no pun intended)
In the screenshot above, a straight line cannot be established between visleaves A and X, therefore A cannot see X
(the arrow can start anywhere inside the first visleaf and end anywhere inside
the second visleaf).
Remember that one visleaf is not restricted to
see only one other visleaf, it can see several visleaves that are surrounding
it (just imagine you are in the bedroom with the door open and you can see the
living room, the dining room, the second bedroom and possibly part of the
kitchen). The number of other visleaves that can be seen from one visleaf is
called the potentially visible set (PVS).
The PVS is dynamic by nature; it changes as
soon as you move your position to another visleaf. If visleaf A can see
visleaves B, C, and D, then the PVS when standing in A is (BCD). If you move to
visleaf B and B can see A, C, D, E, and F, then the PVS when standing in B is
(ACDEF).
An image would be better illustrating the PVS.
In the screenshot above, we still have our initial visleaf A and the 2 visleaves B and C which we established that they can be seen from A. In addition, I have painted in orange all the visleaves/areas that are seen from A (a direct LOS can be established).
This orange area in addition to B and C is basically the PVS, the collection of all visleaves that can be seen from visleaf A. Please note that these visleaves that I highlighted are for a well optimized map, otherwise the PVS would have been bigger.
Link between optimization and visleaves
Now that we know what a visleaf is,
how it is created, and how visibility and interaction with other visleaves is
done, the big question looms in the horizon.
What does all this have to do with
optimization? After all, I promised you earlier that once you understand
visleaves, optimization becomes the easy part. I’m a man of my word and I will
keep my promise.
As I said in the intro, I won’t be using
technical definitions or go into in-depth analysis but I still need to briefly
and very clearly explain the BSP concept so we can relate visleaves with
optimization.
The BSP, or Binary Space Partition, is the
method that the Source engine uses to compute visibility. We have already seen
that during the compile phase, vbsp takes care of creating the visleaves in the
map then vvis shoots its arrows and calculates the visibility between
visleaves. All this info (visleaves’ locations, PVS, visibility matrix) are
stored in the BSP tree (think of it as a big library shelf where each book is
neatly labeled and indexed for easier retrieval at a later stage).
The BSP uses “visibility from a region”
approach since the regions or visleaves are already created and the visibility
matrix is calculated. What does that mean in plain English?
I, the player, am standing in visleaf A as we
have seen earlier. The engine immediately knows that I can be in only one
visleaf at a time and it is currently visleaf A. The engine goes quickly to the
neatly indexed book shelf (the BSP tree) and checks visleaf A. The information
retrieval is instantaneous and the engine swiftly recognizes what other
visleaves can be directly seen from A (The PVS).
With all this info clearly available, the
engine will proceed to render ALL
the visleaves in the PVS of A; when the visleaves are rendered, ALL their content is rendered too.
Let’s get back to the previous screenshot to better display this info.
The engine does not care where I am
exactly standing in visleaf A; it does not matter if I am standing to the left
or right, in the center, or on the edges. As long as I’m inside visleaf A, the
engine renders all the PVS of A, the orange area in addition to B and C (that
is why it is called visibility from a region method).
Other games might use the “visibility from a
point” approach where the engine calculates and renders the world around you in
real time relative to the exact position you are standing at. The Source engine
doesn’t care about your exact location rather about the visleaf you are
standing in, to determine what is rendered and what is not.
You can now clearly notice the quintessential
role and importance of the visleaf in your optimization endeavor.
The immediate conclusion you can
draw from all this explanation is that the smaller the PVS, the better fps you
will have. A smaller PVS means fewer visleaves to draw and fewer visleaves’
content to render (brushes, textures, props, entities…).
There you go; I kept my promise :)
All you need to focus and
concentrate on while optimizing a map in Source is to make sure any given
visleaf in the map can see the minimum amount of visleaves around it.
In my paper Man Vs Engine, I
summarized optimization in one sentence and I feel I should repeat it here to
emphasize what I just said.
Your ultimate goal is to make
a specific visleaf “see” the least amount
of adjacent leaves thus preventing the engine from rendering the content of
these “unseen” leaves which will reduce engine overhead and increase frame
rate.
Now that you know the essence of optimization,
the tools and techniques become easier. You will mostly use the layout itself, skybox
brushes, func_detail, and hint brushes to delimit visleaves, cut large
visleaves into smaller ones and make sure the visleaf in hand sees the utmost
minimal amount of surrounding visleaves.
For visleaves’ content, and in addition to
hints, you will likely use areaportals, occluders, props fade distance, and
nodraw to keep visible render-able content at a minimum and prevent the engine
from over-rendering which will inevitably lower your fps.
Let’s re-examine the PVS screenshot but this
time assuming the map to be un-optimized properly.
You can note that, in addition to
our original PVS (orange area + B + C), the PVS of the un-optimized map is
bigger with the additional purple area added. Without proper optimization and
control, the visleaves tend to be large, covering wide areas, and extending
around corners and upwards. This only means that visleaf A will see a much
larger number of surrounding visleaves; the PVS will be bigger. When you stand
in visleaf A now, the engine will render practically twice the number of
visleaves compared to the optimized map version (orange area). When your PVS
doubles, your fps will decrease, and depending on the visleaves’ content and
amount of brushes/models/entities, it could be as severe as plunging to half its
original value.
Conclusion
As I promised you in the beginning and as we
have seen throughout this article, optimization in itself is quite easy once
you grasp the concept of visleaf.
Visleaves are the cornerstone of the Source
engine since the whole visibility calculation and approach relies on them and
their spatial order.
Once you realize how Source engine
uses visleaves to compute visibility, optimization becomes intuitive; fewer visleaves
visible at a time, higher fps and everyone is happy.
Indeed, I hold some interest in game engine design (and my primary occupation is in the field of programming). I also just cannot sleep peacefully if I'm using any piece of software or hardware that I do not have a sufficient comprehension of. Not being aware of inner workings and relying on some sort of behind-the-scenes magic just doesn't cut it - it only gets me more paranoid about all the possible and impossible ways for things to go wrong in that device or application.
That's what led me to seek documentation on original Quake, and, just like you mentioned, the most useful and complete material I've found was in form of theses describing visibility optimization techniques used in Quake and Unreal, including breakdown of level space using BSP trees and using these to calculate PVS.
I'm pretty sure that this part would be of great interest to at least some level designers, in a form of mildly run-down version of those old articles with little to no code and updated schematics. Maybe I'll even write one some day, after I'm done with CS:GO gamemode I'm working on right now.
We do have this in common then, not programming, but the urge to know a system from the inside out to have some peace of mind :)
It seems some mappers/designers are showing interest to know more about this subject as I'm getting requests from Reddit and other places, so I guess I'll write a follow up to this article delving a little more into details about PVS creation and visibility calculation. I won't tackle the programming side obviously since I'm no programmer, and I'll leave this aspect for your article should you decide to write it :)
Always a pleasure to have technical conversations with you, cheers.
Posted by will2k I doubt level designers would be interested enough to know all these in details. I guess this would be interesting for engine programmers or computer science majors (which I assume you are one?), and these folks would be better suited to check some advanced papers on BSP and PVS.
For mappers, knowing the basics of visleaves and PVS and how it relates to optimization efforts is more than enough to produce solid maps in my opinion. If someone is curious enough to know more about these subjects, there are some excellent papers and theses from the Quake era. Just be prepared to go through pages upon pages of mind-melting code and diagrams; I did that couple of years ago out of curiosity and I'm not even a programmer or computer science major haha :)
Indeed, I hold some interest in game engine design (and my primary occupation is in the field of programming). I also just cannot sleep peacefully if I'm using any piece of software or hardware that I do not have a sufficient comprehension of. Not being aware of inner workings and relying on some sort of behind-the-scenes magic just doesn't cut it - it only gets me more paranoid about all the possible and impossible ways for things to go wrong in that device or application.
That's what led me to seek documentation on original Quake, and, just like you mentioned, the most useful and complete material I've found was in form of theses describing visibility optimization techniques used in Quake and Unreal, including breakdown of level space using BSP trees and using these to calculate PVS.
I'm pretty sure that this part would be of great interest to at least some level designers, in a form of mildly run-down version of those old articles with little to no code and updated schematics. Maybe I'll even write one some day, after I'm done with CS:GO gamemode I'm working on right now.
It's a nice entry-level read, made even better by the fact that it's immediately available - as opposed to PDF downloads.
But I'm fairly sure that explaining the anti-penumbra method actually used to calculate visibility wouldn't be all that hard. You could present it visually as a light-filled room (the initial visleaf) trying to flood second order neighbouring rooms with light through visportals.
This, however, does require an introduction of visportal concept. I guess this option is out if you're to keep the guide really simple.
Hey, thanks for dropping by :)
You changed your username and this confused me for a couple of seconds.
Robin Hood beats anti-penumbra any day XD
Explaining the actual PVS creation process in this "beginners" article would be way out of scope; the notions of portal generation, anti-penumbra clipping, source leaf, destination leaf, source portal, destination portal and view frustum culling would have to be explained and expanded.
I doubt level designers would be interested enough to know all these in details. I guess this would be interesting for engine programmers or computer science majors (which I assume you are one?), and these folks would be better suited to check some advanced papers on BSP and PVS.
For mappers, knowing the basics of visleaves and PVS and how it relates to optimization efforts is more than enough to produce solid maps in my opinion. If someone is curious enough to know more about these subjects, there are some excellent papers and theses from the Quake era. Just be prepared to go through pages upon pages of mind-melting code and diagrams; I did that couple of years ago out of curiosity and I'm not even a programmer or computer science major haha :)
It's a nice entry-level read, made even better by the fact that it's immediately available - as opposed to PDF downloads.
But I'm fairly sure that explaining the anti-penumbra method actually used to calculate visibility wouldn't be all that hard. You could present it visually as a light-filled room (the initial visleaf) trying to flood second order neighbouring rooms with light through visportals.
This, however, does require an introduction of visportal concept. I guess this option is out if you're to keep the guide really simple.
TF2
Team Fortress 2
CS:S
Counter-Strike: Source
CS1.6
Counter-Strike 1.6
CS:CZ
Counter-Strike: Condition Zero
MK8
Mario Kart 8
SSBU
Super Smash Bros. for Wii U
SSB3DS
Super Smash Bros. For Nintendo 3DS
BOTW
Zelda: Breath of the Wild (Wii U & Cemu)
SM
Sonic Mania
GB
GameBanana
CS:GO
Counter-Strike: Global Offensive
RAVENFIELD
Ravenfield
UMVC3
Ultimate Marvel vs Capcom 3
HL2
Half-Life 2
HL
Half-Life
HL2:DM
Half-Life 2: Deathmatch
MP7
Mario Party 7
GMOD
Garry's Mod
STALKER
S.T.A.L.K.E.R.: Shadow of Chernobyl
P2
Portal 2
100% OJ
100% Orange Juice
GOLDSRC
GoldSrc Engine
BAYO PC
Bayonetta
F-ZERO GX
F-Zero GX
FE HEROES
Fire Emblem Heroes
BF2:SF
Battlefield 2: Special Forces
CS2D
Counter-Strike 2D
DDD
Dino D-Day
SW JK:JA
Star Wars Jedi Knight: Jedi Academy
SSBB
Super Smash Bros. Brawl
DOD
Day of Defeat
HL:BS
Half-Life: Blue Shift
DOOM3
Doom 3
BM
Black Mesa
INSURGENCY
Insurgency
GTA5
Grand Theft Auto V
GTA4
Grand Theft Auto IV
KP
Kingpin: Life of Crime
MC
Minecraft
HL2:EP2
Half-Life 2: Episode Two
FF
Fortress Forever
PRTL
Portal
SONIC GEN
Sonic Generations
FEAR
First Encounter Assault Recon
SOURCE
Source Engine
SMM
Super Mario Maker
GTA:VC
Grand Theft Auto: Vice City
MUGEN
M.U.G.E.N
COF
Cry of Fear
FPWR
Fire Pro Wrestling Returns
Offline
