BSP trees

One of the most crucial aspects in rendering a 3D world, is polygon sorting. To correctly display your world, you need to make sure that everything is drawn in the correct order, ensuring that invisble parts of the world are indeed kept invisible. OpenGL allows you to use the depth buffer, but that won't always suffice.

Imagine that you're working on a 3D engine and you want to allow some polygons to be transparent. Simply using the depth buffer in this scenario would be a big mistake. Objects behind a transparent surface need to be drawn before the surface itself - if they're not, the surface's color will not be blended with the object's. The solution is simple: draw your polygons in back-to-front order.

There are plenty of sorting algorithms out there. You've probably heard of quick sort, bubble sort or selection sort, to name but a few. You could use the average depth value of your polygons to sort them back-to-front. Or couldn't you? Take a look at the following examples:

In the first situation, it's just not possible to determine a correct drawing order. No matter how the two polygons are drawn, it's always wrong. The solution is easy, though: always use convex polygons. But that won't help in the second case. If you sort polygons using their average depth value, the red polygon would be drawn behind the blue one. This means that you'd have to avoid polygons that span a large depth range.

As you can probably tell by now, this isn't really going anywhere. No matter what sorting algorithm you use, there's always some degenerate case that can mess things up. One possible solution would be to use BSP (Binary Space Partitioning) trees.

Introduction

A BSP tree closely resembles a binary search tree. If this doesn't ring a bell, look it up before reading any further. The reason why BSP trees do work in the above examples is simple: polygons that could cause problems are chopped into little pieces that can always be drawn in the correct order. If you were to use a BSP tree for the example in figure 2, the result would look like this:

As you can see, the large polygon has been split into two smaller ones, so that the three resulting polygons can always be drawn in the correct order.

The most important part of the BSP tree algorithm is finding out which polygons to split and how. So let's find out.

Polygon splitting

A polygon may need to be split if it lies partially behind and partially in front of another one. Let's say we want to split polygon P because it conflicts with polygon Q. The only correct way to do this, is to use the plane defined by polygon Q - just like we did in figure 3. A plane has an equation of the form Ax + By + Cz + D = 0, where the vector (A, B, C) is the normal vector on the plane, (x, y, z) is any point on the plane, and D can be found by solving the equation. Knowing this, it's easy to find a plane equation for any polygon. Just calculate the polygon's normal - you already have at least three points that are on the plane: your polygon's vertices.

Obviously, we'll only want to split a polygon if it intersects the plane. To find out, substitute the polygon's vertices into the plane equation. The result will be the signed distance from the point to the plane. If the distance is positive, the point lies in front of the plane - if it's negative, the point lies behind. We can find out if a polygon needs to be split by testing all its points in this manner. If the distances all have the same sign, the polygon can be safely ignored. If not, start splitting.

To split a polygon, we basically need to add a vertex to every side that intersects the plane. The point where the side intersects the plane can be calculated as follows. Suppose we have two points, A and B, located on opposite sides of the splitting plane. Also suppose that vector V = B - A. If we divide the distance from A to the plane by the dot product of the plane's normal and V, we get the position between A and B where the polygon's side intersects the plane. If we multiply V with this number and add the result to point A, we get the intersection point. In semi-Delphi:

V := pointB - pointA;
factor := -DistToPlane(ptA, splitPlane) / DotProduct(PlaneNormal(splitPlane), V);
intersectionPoint := ptA + (V * factor);

When we're creating two new polygons, this intersection point needs to be added to both of them.

Tree construction

Now that we know how to slice a polygon in half, remember why we wanted to do so: to ensure that all polygons can be drawn in the correct order. Creating a BSP tree will allow us to do just that. The BSP algorithm starts from an unsorted array of polygons. One of them is arbitrarily chosen to act as the partitioning plane (which I will more easily call the 'splitter'). All other polygons are then divided into two groups: those in front of the splitter and those behind it. If a polygon intersects the plane defined by the splitter, it is cut in half as described above so the two parts can be added to the correct group.

This process is repeated recursively for each of the two groups of polygons. When each group has exactly one polygon, the process is terminated. At each recursion level, the splitter is added as a node to a binary tree. That node's children will be subtrees built from the two subgroups of polygons. In pseudocode, the algorithm looks like this:

Function BuildBSP(list: array of Polygons): BSPTree;
  Splitter := any polygon from the list;
  For all other polygons in the list do
    If polygon in front of splitter then
      Add polygon to FrontGroup;
    Else if polygon behind splitter then
      Add polygon to BehindGroup;
    Else
      Split polygon;
      Add front part to FrontGroup;
      Add behind part to BehindGroup;
    EndIf;
    Result.LeftChild := BuildBSP(BehindGroup);
    Result.Polygon := Splitter;
    Result.RightChild := BuildBSP(FrontGroup);
  EndFor;
End;

As you can see, the algorithm greatly resembles the construction of an ordinary binary tree. The finished tree is a sorted structure of all the polygons in our world.

Rendering from a BSP tree

Now that we have a BSP tree, we'd like to render the polygons in it. As you should know, binary trees can be very easily traversed in sorted order, using a so-called in-order traversal. This is done as follows:

Procedure TraverseTree(tree: BinaryTree);
  If tree <> nil then
    TraverseTree(tree.LeftChild);
    Process(tree.Data);
    TraverseTree(tree.RightChild);
  EndIf;
End;

Using this algorithm, we can draw all polygons in our world in the correct order. Right? No, not right. This could work the very first time, but it won't work once we start applying viewing transformations to the world. Instead of a simple in-order traversal, we need to use a depth-first traversal, based on the position of the viewer. The algorithm looks like this:

Procedure TraverseBSP(tree: BSPTree; viewer: Vector);
  If tree <> nil then
    If viewer in front of tree.Polygon then
      TraverseBSP(tree.LeftChild, viewer);
      DrawPolygon(tree.Polygon);
      TraverseBSP(tree.RightChild, viewer);
    Else
      TraverseBSP(tree.RightChild, viewer);
      DrawPolygon(tree.Polygon);
      TraverseBSP(tree.LeftChild, viewer);
    EndIf;
  EndIf;
End;
 
As you can see, the tree is traversed so that the polygons that are further from the viewpoint get drawn first. The key to this traversal method is testing if the viewpoint lies in front of a polygon or not. This can be done quite easily by retrieving the normal to the polygon and calculating its dot product with the viewpoint. If the result is positive, the viewpoint lies in front of the polygon, otherwise it lies behind.

Drawing the BSP tree this way ensures that we don't have to re-sort our polygons for every animation frame.

Problems

Although BSP trees solve some important problems, they also cause a few.

Most notably, BSP trees don't lend themselves very well to dynamic scenery. If there are moving objects in our world, they need to be merged with the BSP tree at runtime, making sure that they get drawn at the right moment.

Probably the biggest problem from the end-user's point of view is that constructing a BSP tree can take a lot of time. This is why it should almost always be done as a preprocessing step. We can save the tree to a file and distribute that along with our application.

Another issue is that the BSP algorithm increases our polygon counts. This is inevitable, but it would probably be a good idea to reduce polygon splits to the absolute minimum. We can do this when choosing a splitter, by testing every polygon for the number of splits it would cause. We can then pick the one that would cause the lowest number of splits.

If you're somewhat familiar with binary search trees, you'll know that tree balance influences the search speed in the tree. Most 3D applications won't require searching for polygons in a BSP tree, but a 3D modeling program for example, might need to allow the user to select parts of a model. In this case, tree balancing would be important. The same techniques used with regular binary trees also apply to BSP trees, so we won't discuss them here.

Conclusion

I hope this article has given you some insight into the BSP algorithm. BSP trees are very commonly used in today's 3D engines. When used in combination with other techniques, such as portal rendering, they can make for some very fast 3D graphics. If you're having problems implementing the BSP algorithm, a Delphi sample program is available. It demonstrates the BSP algorithm and as such does not use OpenGL's depth buffer. Note, however, that the program does not address the problems described in the previous paragraph.

You can find additional information on BSP trees in most computer graphics textbooks, or online using your favorite search engine.


Delphi3d.net was written and maintained by Tom Nuydens.
Best viewed in 800x600 @ 16 bpp or better.