The purpose of this document is to provide answers to Frequently Asked Questions about Binary Space Partitioning (BSP) Trees. This document will be posted bi-weekly to comp.graphics.algorithms. It is also available via WWW at the URL:
This document is maintained by Bretton Wade, a graduate student at the Cornell University Program of Computer Graphics. All serious job offers considered (shameless plug)!
This document is Copyright © 1994 Bretton Wade. I grant permission to freely distribute this document so long as this notice is retained. No part of this document may be reproduced for profit without my permission.
--
Last Update: 01/19/95 03:06:23
This document would not have been possible without the selfless contributions of many individuals. I would like to take the opportunity to thank each one of them. Please be aware that these people may not be amenable to recieving e-mail on a random basis. If you have any special questions, please contact Bretton Wade (bwade@graphics.cornell.edu) before trying to contact anyone else on this list. In no particular order:
If I have neglected to mention your name, and you contributed, please let me know immediately!
--
Last Update: 01/27/95 10:11:00
Please send all new questions, corrections, suggestions, and contributions to Bretton Wade (bwade@graphics.cornell.edu).
--
Last Update: 01/27/95 10:11:44
Overview After reading through as much literature as I could get my hands on, I am thoroughly convinced that Bruce Naylor gives the most lucid explanation. So, with credit where credit is due...
A Binary Space Partitioning (BSP) tree represents a recursive, hierarchical partitioning, or subdivision, of n-dimensional space. It is most easily understood as a process which takes a subspace and partitions it by any hyperplane that intersects the interior of that subspace. The result is two new subspaces that can be further partitioned by recursive application of the method.
A "hyperplane" in n-dimensional space is an n-1 dimensional object which can be used to divide the space into two half-spaces. For example, in three dimensional space, the "hyperplane" is a plane. In two dimensional space, a line is used.
BSP trees are extremely versatile, because they are powerful sorting and classification structures. They have uses ranging from hidden surface removal and ray tracing hierarchies to solid modeling and robot motion planning.
Example
An easy way to think about BSP trees is to limit the discussion to two dimensions. To simplify the situation, let's say that we will use only lines parallel to the X or Y axis, and that we will divide the space equally at each node. For example, given a square somewhere in the XY plane, we select the first split, and thus the root of the BSP Tree, to cut the square in half in the X direction. At each slice, we will choose a line of the opposite orientation from the last one, so the second slice will divide each of the new pieces in the Y direction. This process will continue recursively until we reach a stopping point, and looks like this:
+-----------+ +-----+-----+ +-----+-----+ | | | | | | | | | | | | | | d | | | | | | | | | | | a | -> | b X c | -> +--Y--+ f | -> ... | | | | | | | | | | | | | | e | | | | | | | | | | +-----------+ +-----+-----+ +-----+-----+
The resulting BSP tree looks like this at each step:
a X X ...
-/ \+ -/ \+
/ \ / \
b c Y f
-/ \+
/ \
e d
Other space partitioning structures
BSP trees are closely related to Quadtrees and Octrees. Quadtrees and Octrees are space partitioning trees which recursively divide subspaces into four and eight new subspaces, respectively. A BSP Tree can be used to simulate both of these structures.
--
Last Update: 01/27/95 10:22:40
Overview
Given a set of polygons in three dimensional space, we want to build a BSP tree which contains all of the polygons. For now, we will ignore the question of how the resulting tree is going to be used.
The algorithm to build a BSP tree is very simple:
Choosing the partition plane
The choice of partition plane depends on how the tree will be used, and what sort of efficiency criteria you have for the construction. For some purposes, it is appropriate to choose the partition plane from the input set of polygons. Other applications may benefit more from axis aligned orthogonal partitions.
In any case, you want to evaluate how your choice will affect the results. It is desirable to have a balanced tree, where each leaf contains roughly the same number of polygons. However, there is some cost in achieving this. If a polygon happens to span the partition plane, it will be split into two pieces. A poor choice of the partition plane can result in many such splits, and a marked increase in the number of polygons. Usually there will be some trade off between a well balanced tree and a large number of splits.
Partitioning polygons
Partitioning a set of polygons with a plane is a matter of determining which side of the plane each polygon is on. This is usually referred to as a front/back test, and is performed by testing each point in the polygon against the plane. If all of the points lie to one side of the plane, then the whole polygon is added to the set associated with that side. If some points lie on both sides of the plane, then the polygon is split into two pieces by the plane, and the parts are added to the sets for either side as appropriate.
When to stop
The decision to terminate tree construction is, again, a matter of the specific application. Some methods terminate when the number of polygons in a leaf node is below a maximum value. Other methods continue until every polygon is placed in an internal node. Another criteria is a maximum tree depth.
Implementation notes
Classifying a point with respect to a plane is done by passing the (x, y, z) values of the point into the plane equation, Ax + By + Cz + D = 0. The result will be positive if the point is on the side of the plane pointed to by the normal vector, negative otherwise. If the result is 0, the point is on the plane.
For those not familiar with the plane equation, The values A, B, and C are the coordinate values of the normal vector. D can be calculated by substituting a point known to be on the plane for x, y, and z.
Psuedo C++ code example
Without going into a great deal of detail, here is an example of how you might code a BSP tree using C++. This is not a class based design.
struct BSP_tree
{
plane partition;
list polygons;
BSP_tree *front,
*back;
};
This structure definition will be used for all subsequent example code. It stores pointers to its children, the partitioning plane for the node, and a list of polygons coincident with the partition plane. There will always be at least one polygon in the coincident list: the polygon used to determine the partition plane. A constructor method for this structure should initialize the child pointers to NULL.
void Build_BSP_Tree (BSP_tree *tree, list polygons)
{
polygon *root = polygons.Get_From_List ();
tree->partition = root->Get_Plane ();
tree->polygons.Add_To_List (root);
list front_list,
back_list;
polygon *poly;
while ((poly = polygons.Get_From_List ()) != 0)
{
int result = tree->partition.Classify_Polygon (poly);
switch (result)
{
case COINCIDENT:
tree->polygons.Add_To_List (poly);
break;
case IN_BACK_OF:
backlist.Add_To_List (poly);
break;
case IN_FRONT_OF:
frontlist.Add_To_List (poly);
break;
case SPANNING:
polygon *front_piece, *back_piece;
Split_Polygon (poly, tree->partition, front_piece, back_piece);
backlist.Add_To_List (back_piece);
frontlist.Add_To_List (front_piece);
break;
}
}
if ( ! front_list.Is_Empty_List ())
{
tree->front = new BSP_tree;
Build_BSP_Tree (tree->front, front_list);
}
if ( ! back_list.Is_Empty_List ())
{
tree->back = new BSP_tree;
Build_BSP_Tree (tree->back, back_list);
}
}
This is a crude routine for recursively constructing a BSP tree using the above definition. It takes the first polygon from the input list and uses it to partition the remainder of the set. The routine then calls itself recursively with each of the two partitions.
One obvious improvement to this example is to choose the partitioning plane more intelligently. This issue is addressed separately in the section, "How can you make a BSP Tree more efficient?".
--
Last Update: 01/27/95 12:48:47
Overview
Probably the most common application of BSP trees is hidden surface removal in three dimensions. BSP trees provide an elegant, efficient method for sorting polygons via a depth first tree walk. This fact can be exploited in a back to front "painter's algorithm" approach to the visible surface problem, or a front to back scanline approach.
BSP trees are well suited to interactive display of static (not moving) geometry because the tree can be constructed as a preprocess. Then the display from any arbitrary viewpoint can be done in linear time. Adding dynamic (moving) objects to the scene is discussed in another section of this document.
Painter's algorithm
The idea behind the painter's algorithm is to draw polygons far away from the eye first, followed by drawing those that are close to the eye. Hidden surfaces will be written over in the image as the surfaces that obscure them are drawn. One condition for a successful painter's algorithm is that there be a single plane which separates any two objects. This means that it might be necessary to split polygons in certain configurations. For example, this case can not be drawn correctly with a painter's algorithm:
+------+
| |
+---------------| |--+
| | | |
| | | |
| | | |
| +--------| |--+
| | | |
+--| |--------+ |
| | | |
| | | |
| | | |
+--| |---------------+
| |
+------+
One reason that BSP trees are so elegant for the painter's algorithm is that the splitting of difficult polygons is an automatic part of tree construction. Note that only one of these two polygons needs to be split in order to resolve the problem.To draw the contents of the tree, perform a back to front tree traversal. Begin at the root node and classify the eye point with respect to its partition plane. Draw the subtree at the far child from the eye, then draw the polygons in this node, then draw the near subtree. Repeat this procedure recursively for each subtree.
Scanline hidden surface removal
It is just as easy to traverse the BSP tree from front to back as it is for back to front. We can use this to our advantage in a scanline method method by using a write mask which will prevent pixels from being written twice.
MORE LATER, when I have the reference handy.
Implementation notes
When building a BSP tree specifically for hidden surface removal, the partition planes are usually chosen from the input polygon set. However, any arbitrary plane can be used if there are no intersecting or concave polygons, as in the example above.
Psuedo C++ code example
Using the BSP_tree structure defined in the section, "How do you build a BSP Tree?", here is a simple example of a back to front tree traversal:
void Draw_BSP_Tree (BSP_tree *tree, point eye)
{
real result = tree->partition.Classify_Point (eye);
if (result > 0)
{
Draw_BSP_Tree (tree->back, eye);
tree->polygons.Draw_Polygon_List ();
Draw_BSP_Tree (tree->front, eye);
}
else if (result < 0)
{
Draw_BSP_Tree (tree->front, eye);
tree->polygons.Draw_Polygon_List ();
Draw_BSP_Tree (tree->back, eye);
}
else // result is 0
{
// the eye point is on the partition plane...
Draw_BSP_Tree (tree->front, eye);
Draw_BSP_Tree (tree->back, eye);
}
}
If the eye point is classified as being on the partition plane, the drawing order is unclear. This is not a problem if the Draw_Polygon_List routine is smart enough to not draw polygons that are not within the viewing frustum. It is clear that the coincident polygon list does not need to be drawn in this case.It is possible to substantially improve the quality of this example by including the viewing direction vector in the computation. You can determine that entire subtrees are behind the viewer by comparing the view vector to the partition plane normal vector. This test can also make a better decision about tree drawing when the eye point lies on the partition plane.
Front to back tree traversal is accomplished in exactly the same manner, except that the recursive calls to Draw_BSP_Tree occur in reverse order.
--
Last Update: 01/27/95 12:49:27
No Body
--
Last Update: 01/15/95 00:56:32
No Body
--
Last Update: 01/15/95 00:31:35
No Body
--
Last Update: 01/15/95 00:54:27
No Body
--
Last Update: 01/15/95 00:31:35
Overview
So far the discussion of BSP tree structures has been limited to handling objects that don't move. However, because the hidden surface removal algorithm is so simple and efficient, it would be nice if it could be used with dynamic scenes too. Faster animation is the goal for many applications, most especially games.
The BSP tree hidden surface removal algorithm can easily be extended to allow for dynamic objects. For each frame, start with a BSP tree containing all the static objects in the scene, and reinsert the dynamic objects. While this is straightforward to implement, it can involve substantial computation.
If dynamic objects are prohibited from intersecting each other or any static object, they can be represented as a single point, regardless of complexity. This can dramatically reduce the computation per frame because only one node per dynamic object is inserted into the BSP tree. Compare that to one node for every polygon in the object, and the reason for the savings is obvious. During tree traversal, each point is expanded into the original object.
Implementation notes
Inserting a point into the BSP tree is very cheap, because there is only one front/back test. Points are never split, which is why the dynamic objects must not interpenetrate. One will always be drawn completely in front of the other.
A dynamic object inserted into the tree as a point can become a child of either a static or dynamic node. If the parent is a static node, perform a front/back test and insert the new node appropriately. If it is a dynamic node, a different front/back test is necessary, because a point doesn't partition three dimesnional space. The correct front/back test is to simply compare distances to the eye. Once computed, this distance can be cached at the node until the frame is drawn.
An alternative when inserting a dynamic node is to construct a plane whose normal is the vector from the point to the eye. This plane is used in front/back tests just like the partition plane in a static node. The plane should be computed lazily and it is not necessary to normalize the vector.
Cleanup at the end of each frame is easy. A static node can never be a child of a dynamic node, since all dynamic nodes are inserted after the static tree is completed. This implies that all subtrees of dynamic nodes can be removed at the same time as the dynamic parent node.
--
Last Update: 01/27/95 12:48:55
No Body
--
Last Update: 01/15/95 00:31:35
No Body
--
Last Update: 01/15/95 00:31:35
No Body
--
Last Update: 01/15/95 00:31:35
No Body
--
Last Update: 01/15/95 00:31:35
No Body
--
Last Update: 01/15/95 00:31:35
standard binary tree search/sort techniques apply.
--
Last Update: 01/18/95 21:34:53
No Body
--
Last Update: 01/15/95 00:54:47
More realistic examples can be found in the sample code ftp location:
No Body
--
Last Update: 01/19/95 02:03:30