Fillrate and VSD (Visible Surface Determination)

As far as we are concerned, A BSP tree is a method of organizing polygon data. How does a BSP tree organize the polygon data? Despite the complicated name (BSP + Binary Space Partition), the *theory* behind the BSP tree is not that complicated: Construct a binary tree (bold face terms explained at the end of article) starting with a plane (the plane you would like to organize your data by) as the root node, and then classify each polygon as either behind the plane, or in front of the plane. Store the behind polygons in one branch, the infront in another. Get the next polygons and put them in the tree using the same method. (recurse through the tree placing the polygon either in the left branch or right branch, depending on orientation in relation to the splitting plane). While implementing this in actual code is far from simple, the basic idea is not that complicated. As you may have noticed; however, there is a flaw in the above. What happens if polygons pierce each other? How do we know which polygon is in front or in back of which? Unfortunately, there is no way to classify these polygons. What do we do then? Well, we split the piercing polygon into two polygons, and then store each of those parts in the tree. Traditional rendering the polygons stored in a BSP Tree  is done by performing a back to front traversal of the tree and rendering each polygon.

Back to Front

Everytime you see back to front, that probably means a lot of overdraw. The diagram below illustrates this.

In the example above, well over 200% of the pixels necessary would be drawn if the above were stored in a BSP Tree.

Why back to front?

In actuality, no current game uses Back to Front rendering. One method of reducing the overdraw associated with BSP Trees is to render front-back using a Z-buffer, or simpler yet (if you don't want to have any moving characters), simply check if a pixel was already drawn before proceeding to draw.

Quake2 takes BSP Trees a set further and uses an algorithm known as PVS (potentially visible set) to determine the, you guessed it, potentially visible set of polygons. While this algorithm is extremely complicated (it involves constructing a tree of intersections/unions of primitives (tetrahedrons, cylinders,etc.) to form more complex shapes.) I don't believe any current game supports all of these primitives for constructing the world (these unions/intersections of primitives are subspaces). Quake supports 3D planes, Quake2 and Unreal support polyhedra only, I believe. (Speculation) Quake uses a ray cast algorithm from sample points to determine which part of the scene is visible (according to a reliable e-mail received earlier today) and then probably renders them front-back using a Z-buffer, since a Z-buffer is necessary to display the characters/items anyway. Unreal uses Span Buffering (speculation again) to help reduce the potentially visible set.

What else do BSP Trees mean?

BSP trees also mean static environments. If you have played Unreal or Quake2, you know what I mean. There is very few, if any real changes in the environment. There is virtually no deformations (i.e. changing the shapes of things, not just moving static objects around) in these games at all. Since BSP trees cannot currently be calculated in real time, games using them are limited to static environments.

Why use BSP Trees?

The main reasons BSP Trees are used is for blazing fast raycasting. Raycasting is used all the time in 3D games for tasks such as determining if bullets hit targets or if you are in the line of sight of a monster. In many cases, BSP Tree's limitations are worth the speed advantages.

Read on to find out about an arrangement which allows for dynamic environments and reduces overdraw!