Portals and Quake

This is the first installment in the “Demystifying the PVS” series.

1. Portals and Quake
2. Coarse base visibility
3. Fine visibility via clipping
4. Portal flow brings it all together (to be published)

Ever wanted to know how exactly did Quake’s precomputed visibility work? I did, so I wrote vis.py, a reimplementation of their algorithm in Python. This guide has all the information you need to understand vis, the tool used by Quake, Half-Life and Source Engine games.

During the development of Quake, overdraw became a concern. It means the same pixel getting written many times during the rendering of a frame. Only the last color stays visible and the earlier writes go to waste. This is bad if your game is software rendered and already pushing the mid 90’s PCs to their limits.

How to reduce overdraw? Let’s begin with a very high-level overview of the solution landscape.

Portal culling helps with overdraw

In 3D games, it’s a good idea to reduce the number of drawn objects. Frustum culling is one fundamental method for this, in which objects confirmed to be outside the virtual camera’s view are skipped during rendering. This can be done for example with object bounding boxes or bounding spheres.

Frustum culling still leaves some performance on the table. Many objects may still be within the field of view of the camera even if they don’t contribute any pixels to the final image. This is not a performance catastrophe if everything is rendered from front to back. GPU’s early-z testing will help here. Still, in large worlds it would be faster to never submit these objects for rendering in the first place.

Occlusion culling is a process where you discard objects that you deem to lie behind other objects in the scene. Its purpose is to discard as many occluded objects as possible. It’s not strictly needed, since you’ll get the correct image thanks to the z-buffer anyway. There are a few ways to do this such as the hierarchical z-buffer, occlusion queries, portal culling, and potentially visible sets (PVS). In this article I talk about the last two: portals and the PVS.

In portal culling, the world is divided into spaces where the virtual camera can move around and the openings between them. The spaces are called cells, viewcells, zones, clusters or sectors, and the openings portals. This is a useful split especially in architectural models with cleanly separated rooms connected by doorways or windows. It also works for mostly-indoor video game levels :)

Portal rendering starts from the camera’s cell. The game renders everything inside that cell, and then recursively looks into portals leading away from that first cell to find out what else to draw. It renders all objects in every cell and then examines the cell’s portals. If a portal doesn’t line up with another one on screen, it won’t be visited. Each successive portal shrinks the visible screen area smaller and smaller until the whole portal is clipped away.

A straightforward way to test portals for visibility is to intersect their screenspace bounding boxes. Those are shown in white in the picture below. If two bounding boxes overlap, we can see through the respective portals. More accurate tests can be performed with 3D clipping or per-pixel operations.

The Quake engine uses portals but only during map preparation time. At runtime, the portals are nowhere to be seen. This technique is a variant of Seth Teller’s PVS method presented in his 1992 dissertation that only worked with axis-aligned walls.

Portals of a Quake map disappear

Often portals are placed by hand by a level designer. Quake’s bsp map compilation tool places portals automatically, which is nice, but unfortunately it creates a lot of them!

You see, in Quake the cells are very small. But no portals are tested at runtime. Instead, each cell gets a precomputed list of other cells that can been seen from it. This is the Potentially Visible Set (PVS) for that cell.

In Quake, a cell is a small convex volume of space, so a single room will usually get split into multiple cells. These cells correspond to leaves of a binary space partitioning (BSP) tree. The BSP tree was used to divide the map into cells and portals. For us, the exact method is irrelevant though. But BSP does make it easy to find the cell the camera is in at runtime.

Since we have now entered the Quake territory in our discussion, I’ll start calling a cell a leaf. Leaf is the term used in all source code, level editors, error messages, and other resources on Quake. The meaning stays exactly the same though, it’s just a convex cell connected to other cells via portals. This is how leaves look in our example level:

The portals appear in between leaves, as expected:

Nothing would’ve stopped them from grouping multiple leaves to form larger cells with fewer portals in between. In fact, this is exactly what they did for Quake 2 with its “clusters” of leaves.

With larger clusters of leaves, you do get more overdraw. Also, a cluster made of convex leaves may not be convex itself any more. But even in that case you can still act as if it still is, and assume the portals inside can be seen from anywhere in the cluster. It’s less accurate but works.

High-level overview of vis

The Quake map tool vis takes in portals generated by another tool, bsp, precomputes a leaf-to-leaf visibility matrix, and writes the matrix back to the compiled map file. This article series describes how vis functions.

We know that leaves can see each other only through portals. So we don’t even need to know how exactly the leaves look like, only how they are connected together.

At its most basic level, vis does two recursive depth-first traversals, followed by a quick resolve pass before writing the visibility results back to a compiled map file. Three steps:

1. Base visibility. Estimate a coarse leaf-to-portal visibility.
2. Full visibility. Refine the coarse results via portal clipping.
3. Resolve. Combine the refined portal-to-leaf results to the final leaf-to-leaf visibility.

For a quick visual overview, I can recommend Matthew Earl’s great video on Quake’s PVS.

Portals have a direction

In a portal system, the cells and portals are structured as a cell-and-portal graph. Quake’s map tooling follows this pattern and connects leaves with portals, even though this structure isn’t present at runtime. Leafs are connected by portals:

Each portal is a 3D polygon. They are written by bsp to a plain text file with a version code, the number of leaves and portals, followed by one portal per line. Like this:

PRT1
11
12
4 0 1 (880 -224 -8 ) (880 -272 -8 ) (880 -272 72 ) (880 -224 72 ) 
4 1 2 (832 -224 -8 ) (832 -272 -8 ) (832 -272 72 ) (832 -224 72 ) 
4 2 4 (768 -272 -8 ) (768 -320 -8 ) (768 -320 72 ) (768 -272 72 ) 
4 2 3 (768 -112 72 ) (768 -112 -8 ) (768 -160 -8 ) (768 -160 72 ) 
4 3 5 (720 -112 72 ) (720 -112 -8 ) (720 -160 -8 ) (720 -160 72 ) 
4 4 5 (720 -272 -8 ) (720 -320 -8 ) (720 -320 72 ) (720 -272 72 ) 
4 5 6 (640 -224 -8 ) (640 -288 -8 ) (640 -288 72 ) (640 -224 72 ) 
4 6 7 (592 -224 -8 ) (592 -288 -8 ) (592 -288 72 ) (592 -224 72 ) 
4 7 10 (384 -304 -8 ) (384 -368 -8 ) (384 -368 72 ) (384 -304 72 ) 
4 7 8 (384 -112 -8 ) (384 -176 -8 ) (384 -176 72 ) (384 -112 72 ) 
4 8 9 (240 -176 -8 ) (336 -176 -8 ) (336 -176 72 ) (240 -176 72 ) 
4 9 10 (240 -304 -8 ) (336 -304 -8 ) (336 -304 72 ) (240 -304 72 ) 

Each portal is a loop of 3D points:

┌ the number of points
│ 
▽      x    y    z   x     y    z    x    y   z     x    y   z
4 0 1 (880 -224 -8 ) (880 -272 -8 ) (880 -272 72 ) (880 -224 72 ) 
  △ △ 
  └─┴─ the two leaves the portal is in between

Since portals are interfaces between convex leaves, the polygons are also convex. In 3D, a portal looks like this:

Conceptually, each portal is a two way opening. You can see through it in both directions. However, it’s convenient to make the portals directed. This way we can keep track on what’s visible in different directions. We give each portal a normal vector, the direction the portal can be seen through.

Now a single input portal becomes two directed portals:

Therefore the graph will now have directed edges instead:

The graph in code

Now is the time to present the main data structures of vis.py, the Portal and Leaf classes:

class Portal:
  winding: list[np.ndarray]   # polygon's 3D points
  leaf: int                   # the leaf this portal leads to
  plane: Plane                # plane normal points to destination leaf
  ...                         # (other class attributes omitted)

class Leaf:
  portals: list[int]    # indices of portals leading away from this leaf

Note that a leaf stores only indices of portals leading away from that leaf. The graph is stored in two global arrays called portals and leaves with objects of the respective types. Since the graph is accessed both via indices and direct object references, I came up with the following naming convention:

• pi is the index of a portal, Pi is the actual object Pi = portals[pi], and
• li is the index of a leaf, Li is the actual object Li = leaves[li].

Our goal is to compute which nodes can reach each other in this graph while honoring the 3D visibility relations between portals associated with each edge. But what on earth are those “visibility relations”?

In the next part we’ll use the graph for some quick checks.

I’m also thinking of writing a book. Sign up here if you’re interested.

---

Mastodon Bluesky YouTube Feed

30fps.net