Fillrate and VSD (Visible Surface Determination)

It is brought to our attention that some games have different fill-rate requirements than others. The Quake2 engine, for example, does two pass rendering (multitexturing), and this lowers the FPS of games using the Quake2 engine. A major aspect of fill-rate that is somewhat neglected; however, is overdraw. Overdraw is largely dependant on the algorithm the 3D engine uses to do something called Visual Surface Determination (VSD for short). The algorithm used by the 3D engine greatly affects overdraw, thus greatly impacting fill-rate requirements.

Overview

VSD stands for Visual Surface Determination, as mentioned above. As the name implies, VSD is the process of determining which surfaces are visible to the viewer. (in a 3D engine) As you may have guessed, there are many different methods of approaching the problem of determining the surfaces (pixels, polygons, or scanlines, depending on the algorithm) which are visible. Many of them involve storing the world in an organized data structure. The algorithms which will be discussed are: BSP Trees, Portals, an algorithm I call "Sectors" [Still haven't made up a cool acronym for it], and other approaches such as only Z-buffer (not really feasible for games, explained later), and depth sorting (not really used because it sucks, maybe in Playstation) Read on to learn about BSP Trees and how they can be a pain for your graphic accelerator.