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 backtofront 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 backtofront.
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 semiDelphi:
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; 



Add front part to FrontGroup; 



Add behind part to BehindGroup; 


Result.LeftChild := BuildBSP(BehindGroup); 


Result.Polygon := Splitter; 


Result.RightChild := BuildBSP(FrontGroup); 
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 socalled inorder traversal. This is done as follows:
Procedure TraverseTree(tree: BinaryTree); 


TraverseTree(tree.LeftChild); 


TraverseTree(tree.RightChild); 
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 inorder traversal, we need to use a depthfirst
traversal, based on the position of the viewer. The algorithm looks like
this:
Procedure TraverseBSP(tree: BSPTree; viewer: Vector); 


If viewer in front of tree.Polygon then 



TraverseBSP(tree.LeftChild, viewer); 



DrawPolygon(tree.Polygon); 



TraverseBSP(tree.RightChild, viewer); 



TraverseBSP(tree.RightChild, viewer); 



DrawPolygon(tree.Polygon); 



TraverseBSP(tree.LeftChild, viewer); 

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 resort 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 enduser'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.
