DevMaster.net  
[[ Home | Forums | 3D Engines Database | Articles/Tutorials | Game Dev Jobs | IRC Chat Network | Contact Us ]]

Graphics Theory & Implementation > Algorithms and Data Structures


BSP Trees: Theory and Implementation      
10/09/2003

Introduction

Other Articles in the Series

* BSP Trees: Theory and Implementation
* Hidden Surface Removal
* Radiosity and BSP-Tree Rendering
* Physics in BSP-Trees: Collision Detection

When the original design of the algorithm for Binary Space Partitioning (BSP)-trees was formulated the idea was to use it to sort the polygons in the world. The reason for this was there did not exist hardware accelerated Z-buffers, and software Z-buffering was too slow. Today that area of usage is obsolete, since hardware accelerated Z-buffers exist. Instead the usage is to optimize a wide variety of areas, such as radiosity calculations, drawing of the world, collision detection and networking.

Binary Space Partioning (BSP)-trees were first described in 1969 by Shumacker et al[1]., it was hardly meant to be an algorithm used to develop entertainment products, but since the beginning of the 90’s BSP-trees have been used in the gaming industry to improve performance and make it possible to use more details in the maps[*]. The first game ever to use the technology is Doom, created by John Carmack and John Romero, two legends in the gaming industry[2]. Since then almost all First Person Shooting (FPS[*]) games have been using that technique.

We set out to examine the areas where one can draw advantages of the structure supplied and study the generating process. A BSP-tree is a very useful structure in most game engines. Although there are some drawbacks with it, such as that it is static and it is very expensive to modify during run-time. Hopefully some ideas can be taken from the BSP-tree algorithm to develop a more dynamic structure that has the same advantages as the BSP-tree.

BSP Trees: Background

A Binary Space Partitioning-tree is a structure that, as the name suggests, subdivides the space into smaller sets. These days, given hardware accelerated Z-buffers; the benefit of this is that one has a smaller amount of data to consider given a location in space. But in the beginning of the 90’s the main reason BSP-trees were being used was that they sorted the polygons in the scene so that you always drew back-to-front, meaning that the polygon with the lowest Z-value[*] was drawn last. There are other ways to sort the polygons so that the closest polygon is drawn last, for example the Painter’s algorithm[3], but few are as cheap as BSP-trees, because the sorting of the polygons is done during the pre-processing[*] of the map and not under run-time. The algorithm for generating a BSP-tree is actually an extension of Painter’s algorithm[5]. Just as the original design of the BSP algorithm, the Painter’s algorithm works by drawing the polygons in the scene in back-to-front order. However, there are some major drawbacks with Painter’s algorithm:

  • Polygons will not be drawn correctly if they pass through any other polygon.
  • It is difficult and computationally expensive to calculate the order that the polygons should be drawn in for each frame.
  • The algorithm cannot handle cases of cyclic overlap as shown in the figure below.


Figure 1: Cyclic Overlap[4]

The BSP Algorithm

The original idea for the creation of a BSP-tree is that you take a set of polygons that is part of a scene and divide them into smaller sets, where each subset is a convex set of polygons. That is, each polygon in this subset is in front of every other polygon in the same set. Polygon 1 is in front of polygon 2 if each vertex in polygon 1 is on the positive side of the plane polygon 2 defines or in that plane that. A cube made of inward facing polygons is a convex set, whilst a cube made of outwards facing polygons is not.


Figure 2: The difference between a convex set and a non-convex set

The functions needed to determine whether a set of polygons is a convex set would look like this:

► CLASSIFY-POINT
// Indata:
//   Polygon – The polygon to classify the point versus.
*   Point   - 3D-point to classify versus the plane defined by the polygon.
* Outdata:
*   Which side the point is of the polygon.
* Effect:
*   Determines on which side of the plane defined by the polygon the point is located.

CLASSIFY-POINT (Polygon, Point)
1 SideValue = Polygon.Normal * Point
2 if (SideValue = Polygon.Distance)
3     then return COINCIDING
4 else if (SideValue < Polygon.Distance)
5     then return BEHIND
6 else return INFRONT


► POLYGON-INFRONT
* Indata:
*   Polygon1 – The polygon to determine whether the other polygon is in front of or not
*   Polygon2 – The polygon to check if it is in front of the first polygon or not
* Outdata:
*   Whether the second is in front of the first polygon or not.
* Effect:
*   Checks each point in the second polygon is in front of
*   the first polygon. If so is the case it is considered
*   to be in the front of it.

POLYGON-INFRONT (Polygon1, Polygon2)
1 for each point p in Polygon2
2     if (CLASSIFY-POINT (Polygon1, p) <> INFRONT)
3         then return false
4 return true


► IS-CONVEX-SET
* Indata:
*   PolygonSet – The set of polygons to check for convexity
* Outdata:
*   Whether the set is convex or not
* Effect:
*   Checks each polygon against each other polygon, to see if they are
*   in front of each other, if any two polygons doesn’t fulfill that
*   criteria the set isn’t convex.

IS-CONVEX-SET (PolygonSet)
1 for i f 0 to PolygonSet.Length ()
2     for j f 0 to PolygonSet.Length ()
3         if(i <> j && not POLYGON-INFRONT(PolygonSet[i], PolygonSet[j]))
4             then return false
5 return true

The function POLYGON-INFRONT is a non-symmetric comparison, meaning that if Polygon2 is in front of Polygon1 it does not necessarily imply that Polygon1 is in front of Polygon2. This can easily be shown with the following example:


Figure 3: The non-symmetric nature of the comparison
POLGON-INFRONT

In Figure 3 Polygon1 is in front of Polygon2 since both p3 and p4 is on the positive side of Polygon2, but Polygon2 is not in front of Polygon1 since p2 is behind Polygon1. The idea can be slightly modified as the need of convex sets is not as acute when you can use hardware accelerated Z-buffers. Later in this series it will be described how this can be solved.

The structures needed for a BSP-tree can be defined as follows:

class BSPTree
{
    BSPTreeNode RootNode          // The root node of the tree.
}
class BSPTreeNode
{
    BSPTree Tree                  // The tree this node belongs to.
    BSPTreePolygon Divider        // The polygon that lies in middle w of the two sub trees.
    BSPTreeNode *RightChild       // The right sub tree of this node.
    BSPTreeNode *LeftChild        // The left sub tree of this node.
    BSPTreePolygon PolygonSet[]   // The set of polygons in this node.
}
class BSPTreePolygon
{
    3DVector Point1               // Vertex 1 in the polygon.
    3DVector Point3               // Vertex 2 in the polygon. 
    3DVector Point3               // Vertex 3 in the polygon.
}

As you can see each polygon is represented by only three points. This is because the hardware in graphic cards is designed to draw triangles. But the algorithm for generating BSP-trees is designed to take care of polygons with any number of points, as long as all points are in the same plane.

There are several ways to split up the set of polygons into smaller subsets. For example, you can choose an arbitrary plane in space and divide the polygons by putting the ones on the positive side of the plane in the right sub tree and the polygons on the negative side in the left sub tree. The problem with this approach is that it is very difficult to find a plane that divides the polygons into two approximately equally sized sets, since there are an infinite set of planes in space. So the most common way to do this is by taking one of the polygons in the scene and dividing the polygons according to the plane that polygon defines.

We have defined an algorithm, POLYGON-INFRONT, which can classify whether a polygon is on the positive side of another polygon. Now we need to modify that algorithm to be able to also determine whether the polygon is spanning the plane defined by the other polygon. The algorithm is defined as follows:

► CALCULATE-SIDE
* Indata:
*   Polygon1 – The polygon to classify the other polygon against
*   Polygon2 – The polygon to classify
* Outdata:
*   Which side of polygon1 polygon 2 is located on.
* Effect:
*   Classifies each point in the second polygon versus the
*   first polygon. If there are points on the positive side but no
*   points on the negative side, Polygon2 is considered to be in front
*   of Polygon1. If there are points on the negative side but no
*   points on the positive side, Polygon2 is considered to be behind
*   Polygon1. If all points are coinciding polygon2 is considered to
*   be coinciding with Polygon1. The last possible case is that there
*   are points on both the positive and the negative side, then
*   polygon2 is considered to be spanning Polygon1.

CALCULATE-SIDE (Polygon1, Polygon2)
1  NumPositive = 0, NumNegative = 0
2  for each point p in Polygon2
3     if (CLASSIFY-POINT (Polygon1, p) = INFRONT)
4         then NumPositive = NumPositive + 1
5     if (CLASSIFY-POINT (Polygon1, p) = BEHIND)
6         then NumNegative = NumNegative + 1
7  if (NumPositive > 0 && NumNegative = 0)
8     then return INFRONT
9  else if(NumPositive = 0 && NumNegative > 0)
10    then return BEHIND
11 else if(NumPositive = 0 && NumNegative = 0)
12    then return COINCIDING
13 else return SPANNING

This gives us a problem when it comes to determining which subset a polygon that is spanning the plane should be placed in. The algorithm deals with this by splitting such a polygon into two polygons. This also solves two of the problems in Painter’s algorithm, namely cyclic overlap and intersecting polygons. Below is example of how a polygon is splitted:


Figure 4: Splitting a polygon

In the figure above Polygon1 is the classifying polygon and Polygon2 is the polygon that is classified. Since Polygon2 is spanning the plane defined by Polygon1 it has to be splitted. The result is the picture to the right. Polygon2 is now completely in front of Polygon1 and Polygon3 is completely behind. The glitch between Polygon2 and Polygon3 is just there to illustrate that it is two separate polygons, after a split the two resulting polygons will be adjacent to each other.

When a BSP-tree is created, one has to decide whether the need is of a balanced tree, meaning that there should not be too big a difference in depth between the left and the right sub tree of each node, or try to limit the number of splits, since each split creates new polygons. If too many new polygons is created during the BSP-tree creation the graphic card will have a hard time rendering the map, thus reducing the frame rate, while a unbalanced tree will require more expensive traversal of the tree. We decided to accept a certain number of splits in order to get a more balanced tree. But the main concern was reducing the number of new polygons created. Below is our loop for choosing the best dividing polygon from a set of polygons:

► CHOOSE-DIVIDING-POLYGON
* Indata:
*   PolygonSet – The set of polygons to search for the best dividing polygon.
* Outdata:
*   The best dividing polygon
* Effect:
*   Searches through the set of polygons and returns the polygons that
*   splits the set into the two best resulting sets. If the set is
*   convex no polygon can be returned.

CHOOSE-DIVIDING-POLYGON (PolygonSet)
1  if (IS-CONVEX-SET (PolygonSet))
2      then return NOPOLYGON
3  MinRelation = MINIMUMRELATION
4  BestPolygon = NOPOLYGON
5  LeastSplits = INFINITY
6  BestRelation = 0
   // Loop to find the polygon that best divides the set.
7  while(BestPolygon = NOPOLYGON)
8      for each polygon P1 in PolygonSet
9          if (Polygon P1 has not been used as divider previously
               during the creation of the tree)

               // Count the number of polygons on the positive side, negative side
               // of and spanning the plane defined by the current polygon.
10             NumPositive = 0, NumNegative = 0, NumSpanning = 0
11             for each polygon P2 in PolygonSet except P1
12                 Value = CALCULATE-SIDE(P1, P2)
13                 if(Value = INFRONT)
14                     NumPositive = NumPositive + 1
15                 else if(Value = BEHIND)
16                     NumNegative = NumNegative + 1
17                 else if(Value = SPANNING)
18                     NumSpanning = NumSpanning + 1

           // Calculate the relation between the number of polygons in the two
           // sets divided by the current polygon.
19         if (NumPositive < NumNegative)
20             Relation = NumPositive / NumNegative
21         else
22             Relation = NumNegative / NumPositive

           // Compare the results given by the current polygon to the best this
           // far. If the this polygon splits fewer polygons and the relation
           // between the resulting sets is acceptable this is the new candidate
           // polygon. If the current polygon splits the same amount of polygons
           // as the best polygon this far and the relation between the two
           // resulting sets is better -> this polygon is the new candidate
           // polygon.
23         if (Relation > MinRelation && (NumSpanning < LeastSplits ||
               NumSpanning = LeastSplits && Relation > BestRelation))
24            BestPolygon = P1
25            LeastSplits = NumSpanning
26            BestRelation = Relation

       // Decrease the number least acceptable relation by dividing it with
       // a predefined constant.
27     MinRelation = MinRelation / MINRELATIONSCALE
28 return BestPolygon

Complexity Analysis

Because of the while loop it is very hard to find a bound to this function. Depending of the structure of the scene the while loop might loop for a very long time. The MINRELATIONSCALE is what decides how much the acceptable relation decreases per iteration, thus how long it will take before the minimum relation will be small enough to accept the best possible solution. The worst case is that we have a set consisting of n polygons that is not a convex set and the best possible solution is a dividing polygon that splits the set into one part consisting of n-1 polygons and another set consisting of 1 polygon. This solution will only be acceptable when the minimal acceptable relation is less than 1/(n-1) (see line 19-23 in the algorithm). Meaning that MinRelation / MINRELATIONSCALEi < 1/(n-1) where i is the number of iterations in the loop, this is due the division by MINRELATIONSCALE at line 27 in the algorithm. Let’s assume that the initial value for MinRelation is 1, which is the highest possible value since the relation is always between 0 and 1 (see lines 19-22 in the algorithm). We have:

1 / MINRELATIONSCALEi < 1/(n-1)
1 < MINRELATIONSCALEi/(n-1)
(n-1) < MINRELATIONSCALEi
logMINRELATIONSCALE (n-1) < i

This is no upper bound for i, but since i will be very close to logMINRELATIONSCALE (n-1) we will, for simplicity assume they are equal. Another practical assumption to make is that MINRELATIONSCALE always should be greater than or equal to 2. Thus giving us:

logMINRELATIONSCALE (n-1) = i MINRELATIONSCALE >= 2
i = logMINRELATIONSCALE (n-1) < lg(n-1) = O(lg n)

Inside the while loop, there are two iterations over the set of polygons. Giving us that the worst case behavior of this algorithm is of order O(n2 lg n), but the typical behavior is almost always closer to O(n2) as there tend to exist a polygon that will fulfill the requirements in the first iteration.

The loop in CHOOSE-DIVIDING-POLYGON might look as if there are cases where it will not terminate, but this is not true since if the set of polygons is a non-convex set there is always one polygon that can divide the polygons into two sets. CHOOSE-DIVIDING-POLYGON selects the polygon that splits the least number of polygons. To prevent from choosing polygons that would not divide the set, the relation between the sizes of the two resulting sets must be better than a threshold value. To better illustrate this we show an example where choosing the polygon that splits the fewest amount of polygons would render in an infinite loop:


Figure 5: Problems when choosing dividing polygon

In the above example choosing either polygon 1,6,7 or 8 would not render in the split of any polygon, but on the other hand each of the polygons in the set is on the positive side of those polygons, so in the next loop the same polygon would be chosen again, rendering in a infinite loop. As a matter of fact 1,2,3 and 4 is on the border of the least convex hull that can hold the polygon set, polygons for which this is true cannot be used as a dividing polygon since all other polygons in the set is on the positive side of them. Choosing polygon 2,3,4 or 5 would each cause one split but it would also divide the set into two smaller sets.

Another reason why a it is not always good to choose the polygon that splits the fewest polygons is that in most cases that heuristic will render in a unbalanced set. A balanced tree will perform better during runtime than an unbalanced one.

When the best polygon has been chosen the rest of the polygons is divided according to that polygon. There are two ways to do deal with the dividing polygon:

  1. A leafy tree can be created, meaning that all polygons are put into the leaf nodes, thus the dividing polygons have to be categorized to be on one of the sides. In our example we count the polygons in the same plane as the dividing polygon as being on the positive side of the plane.
  2. The other way is to store the dividing polygons in the internal nodes. This process is repeated for each sub tree until each leaf contains a convex set of polygons.

The algorithm for generating a leafy BSP-tree looks like this:

► GENERATE-BSP-TREE
* Indata:
*   Node - The sub tree to build of the type BSPTreeNode.
*   PolygonSet – The set of polygons to create a BSP-tree from.
* Outdata:
*   A BSP-tree stored in the incoming node.
* Effect:
*   Generates a BSP-tree out of a set of polygons.

GENERATE-BSP-TREE (Node, PolygonSet)
1  if (IS-CONVEX-SET (PolygonSet))
2      Tree = BSPTreeNode (PolygonSet)
3  Divider = CHOOSE-DIVIDING-POLYGON (PolygonSet)
4  PositiveSet = {}
5  NegativeSet = {}
6  for each polygon P1 in PolygonSet
7      Value f CALCULATE-SIDE (Divider, P1)
8      if(Value = INFRONT)
9          PositiveSet = PositiveSet U P1
10     else if (Value = BEHIND)
11         NegativeSet = NegativeSet U P1
12     else if (Value = SPANNING)
13         Split_Polygon (P1, Divider, Front, Back)
14         PositiveSet = PositiveSet U Front
15         NegativeSet = NegativeSet U Back
16 GENERATE-BSP-TREE (Tree.RightChild, PositiveSet)
17 GENERATE-BSP-TREE (Tree.LeftChild, NegativeSet)

Complexity Analysis

The call to CHOOSE-DIVIDING-POLYGON is of order O(n2 lg n), which dominates the rest of the function except for the recursive calls. If we assume that the division of the polygon set is fairly even we can formulate the following function to calculate the bounds of GENERATE-BSP-TREE:

    T(n) = 2T(n/2) + O(n2 lg n)

Using Masters Theorem[5] we get that the order of complexity is Θ (n2 lg n), where n is the number of polygons in the incoming set.

Following there is an example of how a BSP-tree is generated. The structure below is the original set of polygons, we have numbered them to make the example easier to follow. This set of polygons is going to be divided into a BSP-tree.


Figure 6: Example Structure

To be able to run the algorithm we must choose a couple of constants, namely: MINIMUMRELATION and MINRELATIONSCALE. We found that choosing MINIMUMRELATION = 0.8 and MINRELATIONSCALE = 2 will give quite good result, but one can experiment we those numbers. The higher the MINIMUMRELATION is the better balanced the tree will be, but the number of splitted polygons will probably increase too.

The starting set of polygons is obviously not a convex set, so a dividing polygon will be chosen. After a quick glance at the structure we can see that polygons {1,2,6,22,28} cannot be used as dividing polygons since they define convex hull that contains the whole set of polygons. But all the other polygons are candidates for being dividing polygon. The polygons that split the fewest number of polygons and give the best relation between the sizes of the two resulting sets are 16 and 17, they lie on the same line and do not split any other polygon. The two resulting sets is almost equally sized namely |negative|= 15 and |positive| = 13 polygons in each of the resulting sets. Let us choose polygon 16 as the divider. The result will look as follows:


Figure 7: The result of a split at polygon 16

Neither the right nor the left sub tree contains a convex set of polygons so a new dividing polygon must be chosen in both.

In the left sub tree {1,2,6,7} is on the convex hull so they cannot be used as dividers. Polygon 4 and 10 is on the same line and they do not split any other polygon. The sizes of the resulting sets is |negative|= 7 and |positive| = 8 which is very balanced. We choose 4 as the divider.

{16,17,22,23,28} contains the right sub tree, so they will not be dividers. The polygons that will not split any other polygons are {18,19,27,26} but the sizes of the resulting sets for all of them will be |negative|= 3 and |positive| = 11, 3/11 is below the minimum relation(0.5) so we will have to check the other polygons to see if they can provide us with a more balanced solution. Each of {20,21,24,25} splits exactly one polygon, but the most balanced set is attained by polygon 21, which after splitting polygon 22 produces resulting sets of size |negative|= 6 and |positive| = 8.

The following shows the result after these operations:


Figure 8: The second step

None of the sub trees contain a convex set of polygons so the algorithm will move on in the same manner; the resulting tree will look like this:


Figure 9: The final tree

Even though it is not the optimal solution it is quite close to it and it does not take that long time.

Drawing the BSP Tree

Now that the BSP-tree is created it is very easy to draw the polygons the tree, with zero chance of failure in the drawing. Below the algorithm of that process is described. We assume there is a function IS-LEAF that given a BSP-node it returns true if that node is a leaf otherwise false.

► DRAW-BSP-TREE
* Indata:
*   Node – The node to draw.
*   Position – The viewer’s position.
* Outdata:
*   None
* Effect:
*   Draws the polygons contained in the node and its sub trees.

DRAW-BSP-TREE (Node, Position)
1  if (IS-LEAF(Node))
2      DRAW-POLYGONS (Node.PolygonSet)
3      return
 
   // Calculate which sub tree the viewer is in.
4  Side = CLASSIFY-POINT (Node.Divider, Position)
 
   // If the viewer is in the right sub tree draw that tree before the
   // left.
5  if (Side = INFRONT || Side = COINCIDING)
6      DRAW-BSP-TREE (Node.RightChild, Position)
7      DRAW-BSP-TREE (Node.LeftChild, Position)
 
   // Otherwise draw the left first.
8  else if(Value = BEHIND)
9      DRAW-BSP-TREE (Node.LeftChild, Position)
10     DRAW-BSP-TREE (Node.RightChild, Position)

This way of drawing gives us no reduction in number of polygons that is drawn to the screen. Since a map can consist of hundreds of thousands of polygons, it is no good solution. In some way nodes that are not visible or even polygons that are not visible should be discarded. This is called hidden surface removal. There are several ways to do this; we will explain some of them in the next series article.

Related Readings

  • Sunsted, Tod. 3D computer graphics: Moving from wire-frame drawings to solid, shaded models
  • Sobey, Anthony. Software Engineering
  • Southwick, Andrew R. Quake Rendering Tutorial
  • Meanie, Mr.. Binary Space Partitioning Trees
  • Royer, Dan. Dan’s Programming Tutorials
  • Feldman, Mark. Introduction to Binary Space Partioning Trees

References

  1. Shumacker, R., Brand, R., Gilliland, M., Sharp, W. Study for Applying Computer-Generated Images to Visual Simulation
  2. http://www.idsoftware.com/
  3. Sobey, Anthony. Software Engineering and Sunsted, Tod. 3D computer graphics: Moving from wire-frame drawings to solid, shaded models
  4. Feldman, Mark. Introduction to Binary Space Partioning Trees, 1997
  5. Cormen, Thomas H. Leiserson, Charles E. and Rivest, Ronald L.: Introduction to Algorithms

Glossary

FPS First person shooter, a game viewed in first person perspective, where the goal is to eliminate the opponents.

Map An object that contains the geometry of the world.

BSP-tree Binary Space Partioning tree, a tree structure used to divide a map into smaller parts.

Z-Value This is a measurement used to classify how close a polygon is to the viewer’s position.

Frame rate The number of times the screen is updated per second. This has nothing to do with the refresh rate of the monitor. It is the number of times the world is drawn per second. Usually this should be above 30 times/sec to give a continuous feeling.

Pre-processing Calculations that are done before run-time, thus saving valuable CPU time at run time that can be used for other things.

Polygon A polygon is a many-sided planar figure composed of vertices and edges. Triangles, squares, hexagons, and pentagons are examples of polygons that have names, but any closed series of line segments forms a polygon. [Unknown Author, Basic Math FAQ]. To be meaningful in this area of usage all vertices must be on the same plane, i.e. 2-dimensional.

Plane equation The mathematic formula for a 3 dimensional plane. Ax+By+Cz+D, where A-D is the constant coefficients of the equation, A-C is the normal of the plane and D is the distance from origin in the direction of the normal to the plane.

Node A part of a tree. Each node consists of a left- and a right sub tree.




Discuss this article in the forums
Print article

© 2003-2004 DevMaster.net. All Rights Reserved. Terms of Use & Privacy Policy Want to write for us? Click here