Inside Quake: Visible Surface Determination
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.
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:
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:
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.
