Inside Quake: Visible Surface Determination

An e-mail by Derek Nickel mentioned the follwing article:

   Michael Abrash, "Inside Quake: Visible-Surface Determination"
   In: Dr. Dobb's Sourcebook, January/February 1996, #255
       Ramblings In Real Time, pp. 41-45
This article talks about pushing past the unconscious limits that are often set in a project. It then goes on to describe the various techniques that John Carmack tried out while developing his visible-surface determination and culling algorithms (VSD) in Quake. This includes a description of the potentially visible set (PVS) , a.k.a. visibility lists, on page 45.

BSP-based culling

Michael Abrash points out that, with the limited tasks of rasterization like perspective correct texture mapping being moved into hardware, VSD will prove to be the biggest challenge for coders. Spatial subdivision is one approach, and he mentions the representation of Quake levels as 3D BSP, and points out that this BSP, unlike the one he discussed in previous columns in 1995, does not store polygons in tree nodes, but in the leafs (which, if I understand correctly, is not different from the 2D BSP DOOM used).

He then explains the culling of polygons completely outside the view frustrum, and points out the advantages of culling entire BSP subtress, which requires maintaning bounding boxes or spheres with each node. This, again, is a technique used with DOOM already.


The problem of overdraw is most obvious with back-to-front BSP traversal an painter algorithm. Your world is not rendered in a scalable way, and performance will not only be slow, but worse, it will not be level. He mentions that, with a 10000 polygon Quake level, a wortst-case overdraw of ten times or more was not rare.

To solve this problem, and to reduce overdraw to a manageable and, more important, level magnitude, John Carmack tried a multitude of approaches:

Potentially Visible Sets

The final solution found by John Carmack was a precalculated lookup, providing for each leaf of the BSP a list of potentially visible leafs (the PVS). This again requires the world to be static, and it does not take the direction of view into account (a common misconception with BSP trees as well). A raw PVS is quite large (Abrash mentions several megabyte), but RLE compression and modifications to the BSP builder brought the size down to 20K. The modifications he names are:

Here sealing means calculating some hull of the world to determine surfaces that are not visible from anywhere within the world, and removing them. The idea of Quake-style rendering is being inside a densely occulded world, and a sealing process makes perfect sense. It is related to the Brush based CSG modeling used by QuakeEd (see references on MAP editing for details). Seth Teller mentions a preprocessing step to identify small gaps and other leakage by polygons that are not perfectly adjacent, map faults that increase PVS size immensely.

The BSP heuristic should be changed to generate fewer leaves, prefering the polygons that splits the fewest other polygons. This will generate less balanced trees, which is not a severe disdavantage in this case, if I remember correctly.


I identified the SIGGRAPH paper using the valuable ACM SIGGRAPH Online Bibliography Database. The paper is not available on the web, but Seth Teller provided the dissertation as three parts, and several other recent papers.

home qdev qdev dread rsc qdev doom license web
home dEr95 r3D dread netrsc quake doom legal web
Author: B., email to, with public PGP key
Copyright (©) 1995, 1996 by author. All rights reserved.
Source: $Id: ddjpvs.html,v 1.2 1996/06/08 20:30:51 b1 Exp $