3.1. Rendering without a Z-Buffer

BSP trees were introduced to computer graphics in [Fuchs et al. 80]. At the time, hidden-surface removal was still a major obstacle to interactive computer graphics, because a Z-buffer was just too costly in terms of memory.

In this section, we will describe how to solve this problem, not so much because the application itself is relevant today, but because it nicely exhibits one of the fundamental features of BSP trees: they enable efficient enumeration of all polygons in visibility order from any point in any direction. ^[1]

A simple algorithm to render a set of polygons with correct hidden-surface removal, and without a Z-buffer, is the painters algorithm : render the scene from back to front as seen from the current viewpoint. Front polygons will just over-write the contents of the frame buffer, thus effectively hiding the polygons in the back. There are polygon configurations where this kind of sorting is not always possible, but we will deal with that later.

How can we efficiently obtain such a visibility order of all polygons? Using BSP trees, this is almost trivial: starting from the root, first traverse the branch that does not contain the viewpoint, then render the polygon stored with the node, and then traverse the other branch containing the viewpoint (see Figure 3.3).

Figure 3.3: BSP trees are an efficient data structure encoding visibility order of a set of polygons.

For the sake of completeness, we would like to mention a few strategies to optimize this algorithm. First, we should make use of the viewing direction by skipping BSP branches that lie completely behind the viewpoint.

Furthermore, we can perform back-face culling as usual (which does not cause any extra costs). We can also perform view-frustum culling by testing all vertices of the frustum against the plane of a BSP node.

Another problem with the simple algorithm is that, potentially , a pixel gets overwritten many times (this is exactly the pixel complexity ), although only the last write survives. To remedy this, we must traverse the BSP from front to back. But in order to actually save work, we also need to maintain a 2D BSP for the screen that allows us to quickly discard those parts of a polygon that fall onto a screen area that is already occupied. In that 2D screen BSP, we mark all cells as either free or occupied.

Initially, each BSP consists only of a free root node. When a new polygon is to be rendered, it is first run through the screen BSP, splitting it into smaller and smaller convex parts until it reaches the leaves . If a part reaches a leaf that is already occupied, nothing happens; if it reaches a free leaf, then it is inserted beneath that leaf, and this part is drawn on the screen.

^[1] Actually, the first version of Doom used exactly this algorithm to achieve its fantastic frame rate (at the time) on PCs, even without any graphics accelerator.