This is the first installment in the “Demystifying the PVS” series.
- Portals and Quake
- Coarse base visibility
- Fine visibility via clipping
- 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.
