In the following article we would like to go a little deeper into the so-called “Quake Hidden Surface Removal”. It often plays an important role in 3D configurator projects.
Moving objects and Z-buffers.
We start with a few remarks about the problems with moving objects (billboards/sprites, BSP models like doors, items, polygon models) with a BSP. The BSP provides all polygons of the static world in a perfectly sorted order. These could be used to fill the Z buffer (delete saving a separate Z buffer). The performance impact for this pass can be about 10 percent. Note that this pass must be performed separately from the actual texture mapping of the respective polygons (which also includes a z calculation per pixel for a perspective correct texture mapping), as there are no registers on i586 processors.
The Z buffer is actually used for billboards (sprites), polygon models (whose triangles could possibly intersect), and special effects that were introduced later (once the Z buffer was already inside) like particles. BSP models are treated differently. The effects on Z reading, comparison, and writing performance vary widely, averaging about 10 percent.
After all, the memory requirement is about 128K for 320×200. Accordingly, the same 16bit Z buffer depth uses 1.3 Mb with the 960×720 modes that we occasionally use with Linux/Xfree86. That sounds like a lot, but the game needs 8 Mb anyway, and the interface cache will probably use a lot more if it’s only available.
Level performance and sorted spans.
The back-to-front static world approach that John Cormack tried with PVS didn’t deliver equivalent performance because of the different overdrafts. For the most part, it is assumed that back-to-front rendering with Painter’s algorithm is not a useful approach for scalable, sealed environments anyway. For example, a beam-tree similar approach was also considered, but quickly discarded because it had already been tried to determine the visible area. The overall performance was not reliable and there was an overhead problem.
Subsequently, they differed in solving the HSR task on chip plane instead of polygon plane. He sketches the bsische idea of sorted chips and discusses two alternatives:
Little of the latter has remained in our memories and we will therefore refrain from providing an explanation here.
There is no conclusive answer as to which technique should be preferred. Quake opted for edge sorting rasterizers with some advantages:
Edge sorting basics.
The rest of the article deals with some details. It is explained that using 1/z instead of z as a sorting key has several advantages:
We refer you to Chris Hecker’s series on texture mapping in Game Developer’s Magazine in relation to the behavior of Z gradients in different spaces. The alternative that Hecker discusses is to use the order of the BSP traversal for key allocation. They actually did this with Quake, but used 1/z keys at the time of the article. The decision was made in the last days before shipping. The disadvantage of BSP-based keys is that moving BSP objects must be split by World BSP levels, which increases the number of polygons. For 1/z sorting, it is not necessary to split BSP model polygons. In addition, the 1/z key triggers the merging of the BSP model drawing sequence into the worldwide BSP drawing sequence (which ideally breaks down into the merging of two already sorted lists, methinks).
Finally, it explains how to efficiently obtain a 1/z value and any point on the polygon using a plane equation with respect to the View Space z and Screen Space x,y, and gives the approximate cost on a Pentium as about six cycles.
Handling BSP models.
As already mentioned, the BSP models are not rendered with a Z-buffer read/compare. BSP objects therefore offer a coating reduction – doors block any surface behind them around edge-graded screens. Consequently, BSP models must be cut off against world polygons to avoid interpenetrations. This is not necessary for polygon models, billboards and particles, as z-compares take intersections into account. This is evident on navigable laya/water surfaces.
We hope that we were able to give you a first overview of the topic. If you have any questions or suggestions, please feel free to contact our experts in our forum.
Thank you very much for your visit.