Binary Space Partitioning Trees
By Nathan Whitaker
Contents
Creating the bsp tree
Before I start I shall point out that there is no easy way of describing bsp trees ( I am now wishing I never started! ) so I suggest glancing over the first two sections and then coming back here.
In essence a bsp tree is a pre sorted list of polygons that describing a scene. A bsp tree in conjunction with the painters algorithm will produce a perfectly sorted world and will even account for interpenetrating polygons. You may be wondering how a perfect
sort order can be found for more than one viewpoint from one data set. Consider the example below:-
Figure 1 - This is a representation of a simple scene comprised of 8 polygons. The scene is only in 2d but, there is little difference between a 2d and 3d bsp tree. The small arrows correspond to plane normals and the dotted line corresponds to the plane running through polygon E.
If we were to create a bsp tree for the scene above we would first pick a polygon to use as our head node. For this example I shall pick polygon E ( the dotted line shows the plane formed by polygon E ). Next we classify all remaining polygons with regard to E’s plane. By classify I mean checking to see if a polygon is in front of, behind or spanning the plane ( in front and behind ). If a polygon is in front of E we add it to the front ( left ) branch otherwise we add it to the back ( right ) branch so we are now left with the following two lists.
Figure 2 - This shows the front and back lists created with polygon E as the head node. The two branches coming from the head node are the nodes children which become nodes ( parents ) themselves if they are used to classify other polygons. If they have no children they are called a leaf.
From now on we recursively pick a polygon from each list to be a splitting node used to partition the polygons remaining in the list into two new lists. We stop recursing when there is only one polygon left in the list which we add as a leaf. At the end of the above process the bsp tree may look something like this.
Figure 3 - This is the final tree and the split planes used to partition the polygon lists.
At this point you have a very simple bsp tree storing one polygon per node and using no tests for picking the best polygon to use as a splitter at each node. By the end of this document you hopefully will have a nice clean bsp tree storing polygons at the leaves of the tree and only splitters as the nodes.
Classifying polygons
In the example above I metioned classifying each polygon to find if its in front of or behind another polygons plane. If you look at figure 4 you can see that polygon A is behind polygon B’s plane ( shown by dotted line ) and polygon C is in front of polygon B’s plane. In terms of programming the classify polygon routine I have seen a few people using parametric lines but, for our purpose we shall utilise the power of the dot product. To classify our polygons we do a dot product operation for each vertex of the poly we are testing ( relative to any point on the splitters plane ) with the splitters surface normal. We can then check the sign of the result to see if the poly is in front ( + ) or behind ( - ).
int GetSideOfPlane( VECTOR *normal, VECTOR *normorg, VECTOR *point )
{
VECTOR work;
// Make wall coordinates relative to the planes origin.
work.vx = point->vx - normorg->vx;
work.vy = point->vy - normorg->vy;
work.vz = point->vz - normorg->vz;
// The code below performs a dot product against the walls normal - this returns the
// signed distance of the point from the plane.
return ( work.vx * normal->vx ) + ( work.vy * normal->vy ) + ( work.vz * normal->vz );
}
int ClassifyPolygon( int poly, VECTOR *plane_normal, VECTOR *plane_origin )
{
VECTOR point1, point2;
int p1, p2;
point1.vx = walls[ poly ].w0.vx;
point1.vy = 0;
point1.vz = walls[ poly ].w0.vz;
p1 = GetSideOfPlane( plane_normal, plane_origin, &point1 );
point2.vx = walls[ poly ].w1.vx;
point2.vy = 0;
point2.vz = walls[ poly ].w1.vz;
p2 = GetSideOfPlane( plane_normal, plane_origin, &point2 );
if ( p1 == 0 && p2 == 0 )
return ( CO_PLANAR );
else
if ( p1 >= 0 && p2 >= 0 )
return ( IN_FRONT );
else
if ( p1 <= 0 && p2 <= 0 )
return ( IS_BEHIND );
else
return ( SPANNING );
}
Splitting polys
The polygons in the examples were simple to process as each was either behind another polygons plane or in front of a polygons plane. You may be wondering what to do if a polygon is in front and behind - spanning. In the case of polygons which are spanning a plane we must split the poly into two polys along the plane. This gives us a new polygon in front and a new polygon behind the plane. We then treat these new polygons like any other polygon and put them in the correct branches. Unfortunately the original, poor, harmless, unsplit polygon doesn’t go anywhere and gets disregarded from the tree. The actual routine for splitting the polygons is quite simple for our 2d examples and there are many ways to do it but, I suggest using the numbers the good old dot product returned us. These numbers represent the distance a vertex is from the plane so if we can this distance as a ratio of the distance between the two vertices. We can then apply this ratio to the polygon to find the intersection. What I have just wrote may be confusing ( I’m crap at explaining things ) so here is a fragment of code.
case SPANNING : point1.vx = walls[ poly ].w0.vx;
point1.vy = 0;
point1.vz = walls[ poly ].w0.vz;
p1 = GetSideOfPlane( &plane_normal, &plane_origin, &point1 );
point2.vx = walls[ poly ].w1.vx;
point2.vy = 0;
point2.vz = walls[ poly ].w1.vz;
p2 = GetSideOfPlane( &plane_normal, &plane_origin, &point2 );
point3.vx = point2.vx - point1.vx;
point3.vy = point2.vy - point1.vy;
point3.vz = point2.vz - point1.vz;
p3 = ( point3.vx * plane_normal.vx ) + ( point3.vy *
plane_normal.vy ) + ( point3.vz * plane_normal.vz );
intersection.vx = ( point3.vx * abs( p1 ) ) / abs( p3 );
intersection.vy = ( point3.vy * abs( p1 ) ) / abs( p3 );
intersection.vz = ( point3.vz * abs( p1 ) ) / abs( p3 );
intersection.vx += point1.vx;
intersection.vy += point1.vy;
intersection.vz += point1.vz;
// at this point we build 2 new polys using the original
// vertices and the intersection point and put them into the correct
// branches.
Using / traversing the bsp tree
In section ( 1 ) I showed you how to create a simple bsp tree for the scene in figure 1. In this section I will demonstrate how you can use the bsp tree I created to get a perfectly z sorted scene from any viewpoint. Walking the bsp tree ( like construction ) is a recursive process involving a simple test at each node. The key to this test is that each node of the bsp tree can be used to determine which of its children is further away from the viewer. If we apply this test recursively we can go to the furthest polygon from the viewer, draw it and then move to the next furthest, draw it etc and voila we have perfect drawing order for any viewpoint.
Figure 4 - Scene with viewpoint indicated ( by thick black arrow ) and the bsp tree compiled earlier.
If you take a look at figure 4 you will see that it now contains a thick black arrow which is not used for decoration but, to indicate the viewers position in the scene. If we were to draw the scene in back to front order we would start by checking if the viewer was looking at the front or the back of the head node’s ( E ) plane. We are looking at the front of E so we know that we should draw everything behind E first. With this in mind we proceed down E’s back child and come to node D. We do the same test with D and we find that we are looking at the back of D so we should draw everything in front of D. Now we move to D’s front child A, which we see we are looking at the front so we move to A’s back child B. At B we find we cant move any further so we draw B and return to A. At A we also cant go any further so we draw A and move to D. We then draw D and proceed down D’s unchartered back ( right ) branch to C. At C we do the same test and find that we should draw everyhting in front of C. There is nothing in front of C so we draw C and proceed down the back branch and draw F ( we cant go any further ). We then return all the way back to the head node E, draw it and then we proceed down E’s front child to node G. At node G we find that we should draw everything in front of G but, nothing exists in front of G so we draw it and proceed down the back branch to H which we draw and terminate recursion. We now find that we drew all faces in correct back to front order B,A,D,C,F,E,G,H courtesy of a bsp tree.
As I mentioned earlier in the section this is a recursive process and thus is quite difficult to explain ( well I found it difficult ), here is a section of code to demonstrate a recursive bsp tree walk:-
int NormalFacingViewer( VECTOR *plane_normal, VECTOR *plane_origin )
{
/*
This function could have many different flavours - this one checks the
sngle between the plane normal and the viewer. We could check the
sign of the plane normal in screenspace but, this would mean all polygons
would have to be transformed regardless of whether they are used.
*/
int x, z;
// Example is in 2d - get viewpoint normal....
x = rsin( worldangle.vy );
z = -rcos( worldangle.vy );
if ( ( x * normal->vx ) + ( z * normal->vz ) > 0 )
return FACING_AWAY;
else
return FACING_TOWARDS;
}
// ------------------------------------------------------------------------
void WalkBspTree( BSP_ENTRY *this )
{
BSP_ENTRY *front, *back;
int status;
front = this->front;
back = this->back;
// Are we looking at front or back of polygon.
status = NormalFacingViewer( &this->normal, &this->origin );
if ( status == FACING_TOWARDS )
{
if ( back != NULL )
WalkBspTree( back );
// Draw polygon.
DrawFace( this->id );
if ( front != NULL )
WalkBspTree( front );
}
else
{
if ( front != NULL )
WalkBspTree( front );
// If backface culling is desired - remove the draw code below.
DrawFace( this->id );
if ( back != NULL )
WalkBspTree( back );
}
}
Selecting the best parent
Whilst I was explaining the basics of bsp tree compilation in section one I explained that you had to pick a polygon to use as a splitter at each node. The polygon which is picked can directly effect the performance / size of the tree. For example if you were to pick a polygon that split almost every other polygon in the tree the size of the bsp tree will increase rapidly. If you were to pick a polygon that had no other polygons behind it, only polygons in front then the tree won’t be balanced. The size of the tree and the balancing of the tree directly effect tree traversal time. With this in mind I suggest performing a ‘good parent’ test on each poly in the remaining list and picking the best parent rather than picking any polygon. In a perfect world we could test all possibilities but, try to imagine how many combinations there would be even in a simple 1000 polygon bsp tree.
The ‘good parent’ test
This test involves temporarily making each polygon in the remaining list a parent and then processing the other polygons against this test parent. This is exactly the same process used when compiling the tree except no data is output, only the number of splits, number of polys to the front and back values are worked out. With these values we apply a ‘good parent’ calculation which yields a value based upon the number of polygons split and how balanced the list is:-
value = abs( num_front polys - num_back_polys ) + ( num_splits * 2 );
The polygon which splits the least amount / combines the best balance will return the lowest value.
Improving storage
In all the examples above we store one polygon per node or leaf which results in a lot of nodes. We could store all polygons that are co planar with the splitting polygon ( share the same plane ) at each node. This would reduce the size slightly but, if we want a real improvement we will have to examine the bsp tree leaves closer. Each leaf has the property that it is a convex subspace bounded by its parents planes. What this means to us is that every time we perform a split we can check if the polys in that subspace are convex ( can be drawn from any angle without error ) and if they are we can write all the polygons out to a leaf. Also instead of storing a polygon at the node we will store only split plane information at the node. The resulting tree will have convex groups of polygons at the leaves and splitting planes at the nodes. We will immediately notice tree traveral times and tree size decreasing. This is also the groundwork behind creating a Potential Visibility Set ( PVS ala quake ). With the pvs we store any potential leaves visible from each leaf. This increases drawing performance as only polygons in the leafs that are potentially visible are processed.
Testing whether a list of polygons is convex is a simple task - basically the list is convex if:-
- All polygons are co planar
- All polygons lie behind eachothers plane ( co planar polys are ok )
- All polygons lie in front of eachothers plane ( co planar polys are ok )
- Obviously the list is convex if there is only one polygon.
Testing the above involves looping through the polygon list testing every polygon against every other polygon:-
int ConvexTest( char *list )
{
VECTOR plane_normal, plane_origin;
int status, loop1, loop2;
int front = 0, behind = 0, num_polys = 0, test_poly;
while ( list[ num_polys ] != 0xff )
num_polys++;
for ( loop1 = 0; loop1 < num_polys; loop1++ )
{
test_poly = list[ loop1 ];
plane_normal = polys[ test_poly ].normal;
plane_origin = polys[ test_poly ].origin;
// Check for convex list.
for ( loop2 = 0; loop2 < num_polys; loop2++ )
{
if ( list[ loop2 ] != test_poly )
{
status = ClassifyPolygon( list[ loop2 ], &plane_normal,
&plane_origin );
switch ( status )
{
case IN_FRONT :
if ( behind )
return 0;
else
front++;
break;
case IS_BEHIND :
if ( front )
return 0;
else
behind++;
case CO_PLANAR : break;
case SPANNING : return 0;
}
}
}
}
return 1;
}
You may be wondering what we do with the polygon we used as a split plane now that we are storing no polys at the nodes. In short you simply push it down either the front or back list and don’t use it as a splitter again. It doesn’t matter which list you push the polygon down but, you could maybe add an extra check like seeing if the front / back lists would be convex if they contained the polygon ( it really depends how complex you want the compiler to be ).
See Also:
