Portal flow brings it all together
January 18th, 2025
This is the fourth and final installment in the “Demystifying the PVS” series.
- Portals and Quake
- Coarse base visibility
- Fine visibility via clipping
- Portal flow brings it all together
So far we have
- constructed a graph with directed portals,
- computed a list of possibly visible leafs per portal, and
- learned how to estimate visibility through a sequence of three portals.
Almost done! We mix these three ingredients to get the final leaf-to-leaf visibilities. We follow the same recipe as we did in the coarse pass: A depth-first traversal from a portal’s destination leaf that recursively enters neighboring leaves through portals. It’s just spiced up with more accurate visibility tests.
Once all portals are ready, each leaf looks at its portals and adds all potentially visible leaves from each to its own PVS. Finally we’re done.
Recursive clipping by example
To recap what was explained previously, we have three portals: source, pass, and target. The source portal is the first one visible and where the traversal starts. The pass portal represents an opening known to visible from the source portal. The target portal is being tested for visibility through the other two portals. That’s done by clipping.
Many possible portal sequences are tested for each source portal. It’s not like in the coarse pass where a quick geometric test was enough. This time visibility through the whole sequence is captured in a shrinking pass portal.
Below is an illustrated step-by-step example of the algorithm. I’ve labeled the portals with their variable names used in my code.
Flowing through portals in Python
Like said, the traversal happens like in the coarse visibilty case. A sketch looks like this:
# A simplified sketch of the full visibility calculation code.
# Doesn't actually run!
# Called once for each portal 'Ps'
def portal_flow(Ps: Portal):
# The recursive leaf visitor function
def leaf_flow(leafnum: int, mightsee: np.ndarray)
Ps.vis[leafnum] = True # Mark leaf visible
for pt in leaf.portals:
Pt = leaves[pt]
# Can the previous portal possibly see the target leaf?
if not mightsee[Pt.leaf]:
continue
# [Some portal clipping here]
# If portal 'Pt' wasn't clipped away, recurse through it
if Pt is not None:
leaf_flow(...)
# Start the traversal from Ps's destination leaf
leaf_flow(Ps.leaf, Ps.mightsee)
# Call for every portal
for prt in portals:
portal_flow(prt)
# Now each portal's 'vis' array has been populated.The portal_flow function starts the traversal, just like base_portal_flow did in the coarse pass. The callstack looks something like the inset below.
The visibility results depend on the whole path traversed so far. That’s why in the sketch leaf_flow takes as the argument mightsee, a filtered portal-to-leaf visibility array.
In the beginning, mightsee contains source portal’s coarse visibility result: the leaves that may be visible from it. The array gets progressively thinner as the recursion proceeds. For the example sequence shown earlier it looks like below.
Notice how on the last step in leaf 3, we can’t enter back to leaf 5 because it’s not marked visible anymore in mightsee. The recursion may terminate based on just the array becoming so sparse that no more portals get entered. A portal getting clipped away completely is another way.
The full implementation
Here’s the whole thing. Compared to the sketch above, there’s more clipping, there’s filtering of the might array, and a new early out test for portals that don’t lead to any leaves we haven’t already seen.
# vis.py's recursive portal clipping
# Allocate the portal->leaf visibility matrix
portal_vis = np.zeros((num_portals, num_leaves), dtype=bool)
# Assign each portal a row of the matrix
for pi, Pi in enumerate(portals):
Pi.vis = portal_vis[pi, :]
# We can accelerate the processing a bit if we know which portals already
# got their final visibility
portal_done = np.zeros(num_portals, dtype=bool)
def portal_flow(ps: int, Ps: Portal):
def leaf_flow(
leafnum: int,
mightsee: np.ndarray,
src_poly: Winding,
pass_plane: Plane,
pass_poly: Union[Winding, None],
):
Ps.vis[leafnum] = True
# Test every portal leading away from this leaf
for pt in leaves[leafnum].portals:
Pt = portals[pt] # Candidate target portal
# Can the previous portal possibly see the target leaf?
if not mightsee[Pt.leaf]:
continue
# Use the final visibility array if the portal has been processed
if portal_done[pt]:
test = Pt.vis
else:
test = Pt.mightsee
# Filter away any leaves that couldn't be seen by earlier portals
might = np.bitwise_and(mightsee, test)
# Skip if we could see only leaves that have already proven visible
if not any(np.bitwise_and(might, np.bitwise_not(Ps.vis))):
continue
# Clip the target portal to source portal's plane
if not (target_poly := clip_winding(Pt.winding, Ps.plane)):
continue
# Immediate neighbors don't need other checks
if pass_poly is None:
leaf_flow(Pt.leaf, might, src_poly, Pt.plane, target_poly)
continue
# Make sure the target and source portals are in front and behind
# of the pass portal, respectively
if not (target_poly := clip_winding(target_poly, pass_plane)):
continue
if not (src_clipped := clip_winding(src_poly, -pass_plane)):
continue
# Finally clip the target and source polygons with separating planes
if test_level > 0:
target_poly = clip_to_separators(
src_clipped, Ps.plane, pass_poly, target_poly)
if not target_poly:
continue
if test_level > 1:
target_poly = clip_to_separators(
pass_poly, pass_plane, src_clipped, target_poly, backside=True
)
if not target_poly:
continue
if test_level > 2:
src_clipped = clip_to_separators(
target_poly, Pt.plane, pass_poly, src_clipped)
if not src_clipped:
continue
if test_level > 3:
src_clipped = clip_to_separators(
pass_poly, pass_plane, target_poly, src_clipped, backside=True
)
if not src_clipped:
continue
# If all the checks passed we enter the leaf behind portal 'Pt'.
# The old target portal becomes the new pass portal. The 'might'
# list is now filtered more. Both 'src_clipped' and 'target_poly'
# polygons may have been clipped smaller.
leaf_flow(Pt.leaf, might, src_clipped, Pt.plane, target_poly)
leaf_flow(Ps.leaf, Ps.mightsee, Ps.winding, Ps.plane, None)
portal_done[ps] = TrueThis is code directly from vis.py with a couple of extra comments. In the end it isn’t much simpler than the original RecursiveLeafFlow function.
One thing that can look worrying at a first glance is the fact that the graph has cycles but the traversal can visit leaves many times. In practice it’s not a problem because the progressively thinning mightsee array stops the traversal before it gets stuck in a loop.
Process simpler portals first
Let’s talk about an important performance optimization next. We call portal_flow for each portal in “complexity” order. In this case, portal’s “complexity” means how many leaves were estimated to be possibly visible in the coarse pass. Portals with small numbers are processed first.
This is the part of the above code where the stricter vis array is used instead of the lax mightsee results:
# Use the final visibility array if the portal has been processed
if portal_done[pt]:
test = Pt.vis
else:
test = Pt.mightsee
# Filter away any leaves that couldn't be seen by earlier portals
might = np.bitwise_and(mightsee, test)The big idea is that portals leading to smaller areas have been done earlier, so larger areas can use their final results for early outs.
Leaf visibility through portals
Each leaf can see other leaves only through its portals. That’s why a leaf’s potentially visible set is the union of its leaving portals’ PVS’s.
portal 1 . x x . x x x x . . x 2 x . . . . . . . . . . 3 . . x x x x x x . . x 4 x x . . . . . . . . . 5 . . . . x x x x x . x 6 x x x . . . . . . . . 7 . . . x . x x x . . x 8 . x x . . . . . . . . 9 . . . . . x x x . . . 10 . . x x . . . . . . . 11 . . . . . x x x x . x 12 x x x . x . . . . . . 13 . . . . . . x x x . x 14 x x x x x x . . . . . 15 . . . . . . . x x . x 16 x x x x x x x . . . . 17 . . . . . . . . . . x 18 x x x . x x x x . . . 19 . . . . . . . . x x . 20 . . x . x x x x . . . 21 . . . . . . . . . x x 22 . . . . . . . x x . . 23 . . . . . . . x . . x 24 . . . . . . . . x x . 1 2 3 4 5 6 7 8 91011 leaf
The resulting leaf-to-leaf visibilites are represented by a square boolean matrix I dubbed final_vis:
You can see the intermediate portal_vis matrix on the left.
In these the symbol x means visibility.
Taking the union of sets represented as boolean arrays or bitvectors can be done with the logical OR operation. We loop over portal_vis’s rows and OR the per-portal results to per-leaf rows of the final_vis array that gets written to the BSP file.
# Compute final per-leaf visibility
final_vis = np.zeros((num_leaves, num_leaves), dtype=bool)
for li, leaf in enumerate(leaves):
for pi in leaf.portals:
np.bitwise_or(final_vis[li], portal_vis[pi], out=final_vis[li])
final_vis[li, li] = True # leaf is visible to itselfIn the game
The vis tool writes the final leaf-to-leaf visibility matrix straight into to the already-compiled mapname.bsp file.
The serialization code packs the the matrix rows first to a series of bitvectors, and then compresses each with run-length encoding that skips repeated zero bytes.
In the game, decompression is done on demand. Therefore the full matrix is never fully loaded in memory.
Enjoying the results
It’s a great feeling to go from some portals loaded in a Python program
to the actual game!
Here’s also a low-quality video of the example map’s PVS. Unfortunately, I’ve yet to process the full E1M1 with vis.py since it’s so slow.
Making it faster
I have to admit that vis.py is very slow. There’s still room for some optimizations.
The first is multiprocessing. It’s simple to process each portal in parallel. This was already done in the original vis that ran on a four-core DEC Alpha server. In Python this could be done with the standard library’s worker pool and a shared memory array that’s fed as the backing storage to numpy arrays via np.frombuffer
From ericw-tool’s vis.cc and flow.cc files we can find some new tricks:
- Bounding sphere tests for portals to avoid testing all their points.
- Filtering the mightsee arrays quicker. Occasionally during fine visibility leaf traversal, every other portal is tested against the current source-pass portal sequence. The approach bears some similarity to Doom 3’s simpler PVS introduced in the next section.
- Caching: Their separator clipping code resus some planes from earlier tests. It’s unclear to me how exactly it works.
In C and C++ implementations, the recursion stack is managed manually. I’m not sure if that would be a win in Python code though.
Looking back
Precomputed visibility made it possible for Quake maps to have more polygons with stable framerates. It didn’t eliminate overdraw but kept it at a manageable level at minimal runtime cost.
Even though Seth Teller’s 1992 dissertation already presents a method for static precomputed visibility (and John Airey in 1990), it was a late addition to Quake. Originally the BSP tree was chosen to render the world front to back with a beam tree, but in the end was used to partition the world for the PVS and do collision testing. A BSP tree can be traversed in visibility order but this property was not needed at all, since Quake’s span renderer resolved visibility on its own anyway.
The PVS stuck around a long time in Quake’s sequels and other game series such as Half-Life and Counter-Strike. Even today you can compute something like that in Unreal Engine 5.
Is the PVS a good idea?
Workflow-wise, it’s not great. Level designers always have to wait before they see how well a map performs in game. They also need to think about irrelevant technical concepts such as hint brushes. Quake’s tools also expect a map to be perfectly sealed; watertightly split in interior and exterior sides. Breaking this assumption results in errors about “leaks” that makes the PVS computation fail. I don’t think anyone misses those.
Marketing-wise, high visual fidelity is great. Quake was obviously targeted to make a splash with its solid, texture-mapped 3D worlds. A stable framerate helps to sell the illusion. Since engineering is always about tradeoffs, it meant the worlds had to be static and the level designers patient. Slow iteration times might have made the game design less ambitious, resulting in a worse product. The game’s development was troubled in any case, and it’s not clear if faster map compilation speeds would’ve improved the situation though.
What if you compute the PVS real fast?
Apparently in Doom 3 they went with hand-placed portals tested at runtime and a level load-time PVS. The coarse pass is similar to Quake but the fine pass is quicker.
First they precalculate what portals are possibly visible through any pair of source and pass portals. In the code this per-portal-pair array is called a “passage” and is computed with separating planes and clipping like in Quake. When it’s time to recursively flood through the portal graph, no clipping needs to be done. Instead they check in the passage arrays if a target portal can be seen through the current source and pass portals. The set of possibly visible portals gets sparser as the recursion progresses, like the mightsee array did earlier.
Overall the whole process appears really fast.
I searched for its debug log messages online and found this 2007 result for the game/erebus1 map:
512 bytes passage memory used to build PVS
1 msec to calculate PVS
36 areas
60 portals
6 areas visible on average
288 bytes PVS dataOnly 60 portals! In comparison, Quake’s first map has 3077 portals. Waiting milliseconds during loading sure is better than hours during map compilation. Of course, the level designers are now responsible for placing the portals and levels still have to be sealed.
It’s intriguing to think how the Doom 3 approach would’ve worked in Quake. In complex vistas you’d still need to clip many portals, but you’d have the PVS there to help and fewer portals overall. Would make a great retro research project! :) See the end for relevant source code references.
Farewell
For me personally, writing vis.py was very educational. I had to learn how to really work with plane equations, read up on portals, and exercise my debugging skills. Making my code easy to read and writing about it forced me to clarify many details, which wouldn’t have happened by just reading some code.
Finally, I hope you found this series helpful, inspirational, and perhaps even entertaining. Even if you’re not rolling your own vis, now you should appreciate where it came from and why. Computer graphics was and still is a great field for inventors.
Resources for development
The vis.py repo is on GitHub. A local copy: vis_py.zip.
- TrenchBroom for level editing.
- ericw-tools for compiling maps.
- The original vis source code with Fabien Sanglard’s commentary.
- Michael Abrash’s Black Book chapters 59–70
- Video: Quake’s PVS: A hidden gem of rendering optimization
- Video: BSP Trees: The Magic Behind Collision Detection in Quake
- Video: Excerpt: Quake Postmortem - Optimizing Level Viewing (original)
Some links to Doom 3’s portal and PVS implementations. The code uses the term “area” instead of a “leaf” since they now refer to not-necessarily-convex cells.
- Runtime portal testing with clipping. Screenspace rectangles are tracked only for graphics API’s “scissor” tests.
- The PVS init function gives an overview of the process.
- The coarse PVS pass should look familiar.
- Passage precomputation. Note that confusingly, the pass portal is called “target” here and the portal “p” is the one getting clipped.
- Finding separating planes using the algorithm described in the third part of this series.
- Fine PVS pass.
- Resolving the final PVS. It stores both visible areas and portals.
Map and portal data
Here are two test maps I made. Note that portal and leaf indexing starts at zero in these files. In this article series I’ve used one-based indexing in diagrams and worked-out examples.
The example map
- example.map for TrenchBroom
- example.prt exported portals
- example.bsp exported BSP
The first rooms of E1M1
I botched the door speed here, sorry about that.
- e1m1_opening.map for TrenchBroom
- e1m1_opening.prt exported portals
- e1m1_opening.bsp exported BSP
Acknowledgements
Thanks to the usual suspects for proofreading and good commentary on early drafts. Thanks to the HN commenter dahart for bringing up the UE5 PVS. Finally, thank you J for encouraging me pursue my crazy projects.
I’m also thinking of writing a book. Sign up here if you’re interested.
