|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
BSP Tree Frequently Asked Questions (FAQ)Indexed Listing
Questions
Answers
-- Last Update: 09/06/101 14:50:28
General A pointer to this document will be posted monthly to comp.graphics.algorithms and rec.games.programmer. It is available via WWW at the URL:
The most recent newsgroup posting of this document is available via ftp at the following URL:
Requesting the FAQ by mail
About the maintainer
Requesting assistance If you do not receive a reply within a reasonable amount of time, it most likely that your reply e-mail address is invalid. If you did not get an acknowledgement from the auto-responder, then you can be sure this is the case. Check your return address and try again.
Copyrights and distribution
Warranty and disclaimer
The contents of this article do not necessarily represent the opinions of Silicon Graphics, Incorporated.
Web Space
About the contributors
Contributors
If I have neglected to mention your name, and you contributed, please let me know immediately!
As of 2001-09-20, this faq does not appear to be maintained.
Overview In order to provide effective examples, it is necessary to assume that certain classes already exist, and can be used without presenting excessive details of their operation. Basic classes such as lists and arrays fall into this category. Other classes which will be very useful for examples need to be presented here, but the definitions will be generic to allow for freedom of interpretation. I assume points and vectors to each be an array of 3 real numbers (X, Y, Z). Planes are represented as an array of 4 real numbers (A, B, C, D). The vector (A, B, C) is the normal vector to the plane. Polygons are structures composited from an array of points, which are the vertices, and a plane. The overloaded operator for a dot product (inner product, scalar product, etc.) of two vectors is the '|' symbol. This has two advantages, the first of which is that it can't be confused with the scalar multiplication operator. The second is that precedence of C++ operators will usually require that dot product operations be parenthesized, which is consistent with the linear algebra notation for an inner product.
The code for BSP trees presented here is intended to be educational, and may or may not be very efficient. For the sake of clarity, the BSP tree itself will not be defined as a class.
Overview (under development) It is common to see BSP trees which represent two and three dimensional space, but the definition of the structure is not constrained to these. For these two cases, the polytope stored is a line segment and a polygon, respectively.
Overview 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
or the ASCII art version: +-----------+ +-----+-----+ +-----+-----+ | | | | | | | | | | | | | | d | | | | | | | | | | | a | -> | b X c | -> +--Y--+ c | -> ... | | | | | | | | | | | | | | e | | | | | | | | | | +-----------+ +-----+-----+ +-----+-----+
a X X ...
-/ \+ -/ \+
/ \ / \
b c Y c
-/ \+
/ \
d e
Other space partitioning structures
Overview The algorithm to build a BSP tree is very simple:
Choosing the partition plane 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 or more 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
When to stop
Pseudo C++ code example
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. For this example, 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:
back_list.Add_To_List (poly);
break;
case IN_FRONT_OF:
front_list.Add_To_List (poly);
break;
case SPANNING:
polygon *front_piece, *back_piece;
Split_Polygon (poly, tree->partition, front_piece, back_piece);
back_list.Add_To_List (back_piece);
front_list.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 routine recursively constructs 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. This implementation assumes that all of the input polygons are convex.
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?".
Overview The basic algorithm is to loop across all the edges of the polygon and find those for which one vertex is on each side of the partition plane. The intersection points of these edges and the plane are computed, and those points are used as new vertices for the resulting pieces.
Implementation notes 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. Convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.
Pseudo C++ code example
void Split_Polygon (polygon *poly, plane *part, polygon *&front, polygon *&back)
{
int count = poly->NumVertices (),
out_c = 0, in_c = 0;
point ptA, ptB,
outpts[MAXPTS],
inpts[MAXPTS];
real sideA, sideB;
ptA = poly->Vertex (count - 1);
sideA = part->Classify_Point (ptA);
for (short i = -1; ++i < count;)
{
ptB = poly->Vertex (i);
sideB = part->Classify_Point (ptB);
if (sideB > 0)
{
if (sideA < 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
outpts[out_c++] = ptB;
}
else if (sideB < 0)
{
if (sideA > 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
inpts[in_c++] = ptB;
}
else
outpts[out_c++] = inpts[in_c++] = ptB;
ptA = ptB;
sideA = sideB;
}
front = new polygon (outpts, out_c);
back = new polygon (inpts, in_c);
}
A simple extension to this code that is good for BSP trees is to combine its functionality with the routine to classify a polygon with respect to a plane.
Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.
Overview 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
+------+
| |
+---------------| |--+
| | | |
| | | |
| | | |
| +--------| |--+
| | | |
+--| |--------+ |
| | | |
| | | |
| | | |
+--| |---------------+
| |
+------+
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 The trick to making a scanline approach successful is to have an efficient method for masking pixels. One way to do this is to maintain a list of pixel spans which have not yet been written to for each scan line. For each polygon scan converted, only pixels in the available spans are written, and the spans are updated accordingly. The scan line spans can be represented as binary trees, which are just one dimensional BSP trees. This technique can be expanded to a two dimensional screen coverage algorithm using a two dimensional BSP tree to represent the masked regions. Any convex partitioning scheme, such as a quadtree, can be used with similar effect.
Implementation notes
Pseudo C++ code example
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. The coincident polygon list does not need to be drawn in this case, because those polygons will not be visible to the user.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. It is worth noting that this improvement resembles the method for tracing a ray through a BSP tree, which is discussed in another section of this document.
Front to back tree traversal is accomplished in exactly the same manner, except that the recursive calls to
Overview BSP trees can be used to compute visible fragments of polygons in a scene in at least two different ways. Both methods involve the use of a bsp tree for front to back traversal, and a second tree which describes the visible space in the viewing volume.
Screen partitioning
Beam tree
First DRAFT.
Overview
Implementation notes A large improvement can be made over the voxel walking algorithm for recursive ray tracing by using the parent node of the ray origin as a hint. Because ray tracing is a spatial classification problem, balancing is the key to performance. Most spatial partitioning schemes for accellerating ray tracing use a criteria called "occupancy", which refers to the number of primitives residing in each partition. A BSP tree which has approximately the same occupancy for all partitions is balanced. Balancing is discussed elsewhere in this document.
MORE TO COME
Overview An in/out test is a different way of talking about the front/back test we have been using to classify points with respect to planes. The necessity for this shift in thought is evident when considering polytopes instead of just polygons. A point can not be merely in front or back of a polytope, but inside or outside. Somewhat formally, a point is inside of a convex polytope if it is inside of, or in back of, each hyperplane which composes the polytope, otherwise it is outside.
Incremental construction It is useful to examine the construction process in two dimensions. Consider the following figure:
A B
+-------------+
| |
| |
| E | F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D | C |
| |
| |
+-------------+
H G
Two polygons, ABCD, and EFGH, are to be inserted into the tree. We wish to find the union of these two polygons. Start by inserting polygon ABCD into the tree, choosing the splitting hyperplanes to be coincident with the edges. The tree looks like this after insertion of ABCD:
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ *
CD
-/ \+
/ \
/ *
DA
-/ \+
/ \
* *
Now, polygon EFGH is inserted into the tree, one edge at a time. The result looks like this:
A B
+-------------+
| |
| |
| E |J F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
/ * \ \
EJ KH \
-/ \+ -/ \+ \
/ \ / \ \
/ * / * \
LE HL JF
-/ \+ -/ \+ -/ \+
/ \ / \ / \
* * * * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Notice that when we insert EFGH, we split edges EF and HE along the edges of ABCD. this has the effect of dividing these segments into pieces which are inside ABCD, and outside ABCD. Segments EJ and LE will not be part of the boundary of the union. We could have saved our selves some work by not inserting them into the tree at all. For a union operation, you can always throw away segments that land in inside nodes. You must be careful about this though. What I mean is that any segments which land in inside nodes of the pre-existing tree, not the tree as it is being constructed. EJ and LE landed in an inside node of the tree for polygon ABCD, and so can be discarded.Our tree now looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| | |
| | |
| | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Now, we would like some way to eliminate the segments JC and CL, so that we will be left with the boundary segments of the union. Examine the segment BC in the tree. What we would like to do is split BC with the hyperplane JF. Conveniently, we can do this by pushing the BC segment through the node for JF. The resulting segments can be classified with the rest of the JF subtree. Notice that the segment BJ lands in an out node, and that JC lands in an in node. Remembering that we can discard interior nodes, we can eliminate JC. The segment BJ replaces BC in the original tree. This process is repeated for segment CD, yielding the segments CL and LD. CL is discarded as landing in an interior node, and LD replaces CD in the original tree. The result looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| |
| |
| L |
+-------+ |
D | |
| |
| |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BJ
-/ \+
/ \
/ \
LD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
As you can see, the result is the union of the polygons ABCD and EFGH.To perform other boolean operations, the process is similar. For intersection, you discard segments which land in exterior nodes instead of internal ones. The difference operation is special. It requires that you invert the polytope before insertion. For simple objects, this can be achieved by scaling with a factor of -1. The insertion process is then conducted as an intersection operation, where segments landing in external nodes are discarded.
Tree merging
Overview Typically, motion is computed in a series of Euler steps. This just means that the motion is computed at discrete time intervals using some description of the speed of motion. For any given point P moving from point A with a velocity V, it's location can be computed at time T as P = A + (T * V). Consider the case where T = 1, and we are computing the motion in one second steps. To find out if the point P has collided with any part of the scene, we will first compute the endpoints of the motion for this time step. P1 = A + V, and P2 = A + (2 * V). These two endpoints will be classified with respect to the BSP tree. If P1 is outside of all objects, and P2 is inside some object, then an intersection has clearly occurred. However, if P2 is also outside, we still have to check for a collision in between. Two approaches are possible. The first is commonly used in applications like games, where speed is critical, and accuracy is not. This approach is to recursively divide the motion segment in half, and check the midpoint for containment by some object. Typically, it is good enough to say that an intersection occurred, and not be very accurate about where it occurred.
The second approach, which is more accurate, but also more time consuming, is to treat the motion segment as a ray, and intersect the ray with the BSP Tree. This also has the advantage that the motion resulting from the impact can be computed more accurately.
Overview 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 a dynamic object is separated from each static object by a plane, the dynamic object can be represented as a single point regardless of its 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 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.
Caveats
Advanced methods
Overview
Overview
Overview
Example Now, a planning graph can be built, using some point inside of each polygon, and connecting to a point inside of each of its neighbors. Note that the selection of the point location has implications for the length of resulting paths. Planning begins by identifying the cell which contains the start point, and the cell which contains the end point. Then a standard A* style search can be used on the planning graph to find the set of polygons that must be crossed to get to the end point from the start point.
Implementation Notes
FIRST DRAFT
Overview
Overview
Space complexity It will be extremely difficult to construct a case which satisfies this formula. The "expected" case, repeatedly expressed by Naylor, is O(n).
Time complexity
Bounding volumes
Optimal trees
Minimizing splitting Bear in mind that minimization of splitting requires pre-existing knowledge about all of the polygons that will be inserted into the tree. This knowledge may not exist for interactive uses such as solid modelling.
Tree balancing For the hidden surface problem, balancing doesn't significantly affect runtime. This is because the expected time complexity for tree traversal is linear on the number of polygons in the tree, rather than the depth of the tree.
Balancing vs. splitting
Reference Counting
Overview
Implementation Notes
void Enumerate (BSP_tree *tree)
{
if (tree->front)
Enumerate (tree->front);
if (tree->back)
Enumerate (tree->back);
}
To eliminate the recursion, you have to explicitly model the recursion using a stack. Using a stack of pointers to
void Enumerate (BSP_tree *tree)
{
Stack stack;
while (tree)
{
if (tree->back)
stack.Push (tree->back);
if (tree->front)
stack.Push (tree->front);
tree = stack.Pop ();
}
}
On some processors, using a stack will be faster than the recursive method. This is especially true if the recursive routine has a lot of local variables. However, the recursive approach is usually easier to understand and debug, as well as requiring less code.
Overview Sage: Long ago in a small village in Nepal, a minor godling gave a special nut to the priests at an out of the way temple. With the nut, was a prophecy: When a group of three gurus, two with red hair, and the other who was not what he seemed, came to the temple on pilgrimage, if the nut was given unto them, and they nurtured it together, it would produce a tree of great benefit to mankind. Many years later, ... N: no! No! NO! The TRUE story. S: OK. Long ago (by computer industry standards) in a rapidly growing sunbelt city in Texas, a serendipitous convergence of unusual talents and personalities occurred. A brief burst of graphics wonderments appeared, and the convergence diverged under its own explosive production, leading to further graphics developments in several new locations. One of the wonderous paths followed ... N: ...No! The facts! S: Huh? Oh you want FACTS. Boring stuff? Henry Fuchs started teaching at an essentially brand new campus, the University of Texas at Dallas, in January 1975. He returned to Utah to complete his PhD the following summer. He returned to Dallas and taught for the 1975-76, 1976-77 and 1977-78 academic years, before being lured away to UNC-Chapel Hill. Zvi Kedem joined this faculty in the fall of 1975. He was (and still is I suppose) a "theory person," but a special theory person. He is good at applying theory to practical problems. Bruce Naylor had a bachelors degree from the U of Texas (Austin - "the real one"), in philosophy if I recall correctly. He had talked his way into a job at Texas Instruments in Dallas. (Something about philosophy makes you good in logic, which is really the same as computers...!?) He came to UTD to take some computer courses. He was spotted as "good" - probably by Kedem, but I can't swear to it - and convinced to become a full time graduate student. Graphics, of course, is dazzling and wonderful. Henry was (is) full of energy and enthusiasm. It was natural that he attracted lots of the grad students. Kedem was a perfect complement, providing not only the formal rigor and proofs, but also the impetus to "write this part up" before going on to "the next thing and the next thing and ..." Kedem and Fuchs together (and most of the grad students) also found a new thrust in the CS theory community, called computational geometry, particularly interesting. Henry liked to talk about the Schumacker priority driven visible surface algorithm when the class got to that topic. He seemed to think there was something more to be done in that vein. Naylor being a grad student in search of a topic, looked into it. The result was two SIGGRAPH papers and Naylor's PhD dissertation, and the launch of BSP-trees into the world. The two papers are Fuchs, Kedem and Naylor, "Predeterming Visibility Priority in 3-D Scenes" SIGGRAPH '79, pp 175-181. (subtitled "preliminary report") and Fuchs, Kedem and Naylor, "On Visible Surface Generation by A Priori Tree Structures" SIGGRAPH '80, pp124-133. The first paper isn't really BSP-trees, but rather the preliminary work which led to BSP-trees as the solution. The second paper is the "classic" starting point referenced in texts, etc. Both reference Schumacker, Brand, Gilliland and Sharp, "Study for Applying Computer-Generated Images to Visual Simulation" AFHRL-TR-69-14, US AF Human Resources Lab, 1969 and the description of this algorithm more easily found in Sutherland, Sproull and Schumacker, "A Characterization of Ten Hidden Surface Algorithms", ACM Computing Surveys, v 6, no 1, pp 1-55.
Naylor finished in 1981 (?) and went to Georgia Tech, and later to
Bell Labs. He has continued to work on related and similar ideas with
a variety of students and collaborators. Others have also taken the
ideas in new directions.
BSP tree FAQ companion code
Also in this directory is the BSP tree demo application for MacOS and Win95. This demo shows how to use BSP trees for basic Boolean modelling and hidden surface removal, and includes an implementation of Ken Shoemake's ArcBall interface. The MacOS package includes all of the source for the demo application in several Metrowerks CodeWarrior projects. The Win95 package is based on the MacOS package, and includes all the source for the demo in a single Microsoft Visual C++ 4.2 project. An X-Windows port is in progress. Information about the ArcBall controller can be found in Graphics Gems IV (see below). The original paper and demo application for 68k based Apple Macintosh computers is available via WWW or FTP at:
Graphics Gems
It is an invaluable resource for all things graphical. In particular, there are some BSP tree references worth looking over. Peter Shirley and Kelvin Sung have C sample code for ray tracing with BSP trees in Graphics Gems III Norman Chin has provided a wonderful resource for BSP trees in Graphics Gems V. He provides C sample code for a wide variety of uses.
Other BSP tree resources
It has many good articles which involve the use of BSP trees or compares them to other data structures for ray tracing efficiency. It's definitely worth a look. The DejaNews research service is a search engine for newsgroup postings. Conduct a search on "BSP tree" to read over recent, as well as old, discussions about BSP trees. DejaNews is available at:
Pat Fleckenstein and Rob Reay have put together a FAQ on 3D graphics, which includes a blurb on BSP trees, and an FTP site with some sample code:
Dr. Dobbs Journal has an article in their July '95 issue about BSP trees, By Nathan Dwyer. It describes the construction of BSP trees for visible surface processing, how to split polygons with planes, and how to dump the tree to a file. There is C++ source code to accompany the article.
Michael Abrash's columns in the DDJ Sourcebooks are an excellent introduction to the concept of BSP trees, and the practical details of implementing them for games like Doom and Quake. The source code for these articles is distributed over several sites.
Ekkehard Beier has made available a generic 3D graphics kernel intended to assist development of graphics application interfaces. One of the classes in the library is a BSP tree, and full source is provided. The focus seems to be on ray tracing, with the code being based on Jim Arvo's Linear Time Voxel Walking article in the ray tracing news.
Eddie Edwards wrote a commonly referenced text which describes 2D BSP trees in some detail for use in games like DOOM. It includes a bit of sample code, too.
Mel Slater has made available his C source code for computing shadow volumes based on BSP trees. There is also a paper which compares three shadow volume algorithms. These are available via FTP at:
The SPHIGS distribution that accompanies the famous Foley, et al. Computer Graphics textbook contains a BSP tree implementation and can be obtained at:
John Holmes, Jr. has a paper about BSP trees and boundary representations online. This paper touches on many aspects of BSP trees in a scientific manner, and is available at:
A.T. Campbell III has placed his doctoral dissertation online. This document describes the use of BSP trees for surface meshing in a radiosity algorithm. He has also made available source code in both C and C++ for many BSP tree tasks, including an implementation of tree merging. This is all available on his home page at:
Andrea Marchini and Stefano Tommesani have made available a BSP tree compiler and viewing program as part of the "Purple Haze" project. There is some nice accompanying documentation of the process of BSP tree construction, as well. The web page is at:
Paton Lewis has built an excellent demonstration of BSP trees using Java. If you have had problems visualizing the tree contruction process, you should take a look at this tool. The user draws lines in an interactive construction space, and three other view panes show the split segments, a traditional graph representation of the tree, and a first person perspective view of the line segments as walls. This is how DOOM works. The web page is:
A general graphics programming resources has an article about building BSP trees using axis-aligned partitioning planes. The article calls this structure a bintree, after a 1994 paper by Tamminen. The URL is:
John Whitley has a short tutorial page about BSP trees which covers general details of tree construction and display. It includes psuedo-code for a front to back tree traversal, and an annotated bibliography. The location of this resource is:
Tom Hammersly has put up a web page with his experience in building a BSP tree compiler and viewer. The web page is at:
Id software has made a great deal of source code for games and utilities available, much of which deals extensively with BSP trees. The source code is complete, and easy to understand. The site is at:
General resources for computer graphics programming
The computational geometry web page contains lots of information and pointers to related computational geometry tools and algorithms: http://www.cs.duke.edu/~jeffe/compgeom/. Another computational geometry page to look at is http://www.ics.uci.edu:80/~eppstein/geom.html. This page seems to have a more tutorial nature than the first page.
A partial listing of textual info on BSP trees.
Kindly sponsored by Silicon Graphics, Incorporated. Questions
Answers
-- Last Update: 09/06/101 14:50:28
General A pointer to this document will be posted monthly to comp.graphics.algorithms and rec.games.programmer. It is available via WWW at the URL:
The most recent newsgroup posting of this document is available via ftp at the following URL:
Requesting the FAQ by mail
About the maintainer
Requesting assistance If you do not receive a reply within a reasonable amount of time, it most likely that your reply e-mail address is invalid. If you did not get an acknowledgement from the auto-responder, then you can be sure this is the case. Check your return address and try again.
Copyrights and distribution
Warranty and disclaimer
The contents of this article do not necessarily represent the opinions of Silicon Graphics, Incorporated.
Web Space
About the contributors
Contributors
If I have neglected to mention your name, and you contributed, please let me know immediately!
As of 2001-09-20, this faq does not appear to be maintained.
Overview In order to provide effective examples, it is necessary to assume that certain classes already exist, and can be used without presenting excessive details of their operation. Basic classes such as lists and arrays fall into this category. Other classes which will be very useful for examples need to be presented here, but the definitions will be generic to allow for freedom of interpretation. I assume points and vectors to each be an array of 3 real numbers (X, Y, Z). Planes are represented as an array of 4 real numbers (A, B, C, D). The vector (A, B, C) is the normal vector to the plane. Polygons are structures composited from an array of points, which are the vertices, and a plane. The overloaded operator for a dot product (inner product, scalar product, etc.) of two vectors is the '|' symbol. This has two advantages, the first of which is that it can't be confused with the scalar multiplication operator. The second is that precedence of C++ operators will usually require that dot product operations be parenthesized, which is consistent with the linear algebra notation for an inner product.
The code for BSP trees presented here is intended to be educational, and may or may not be very efficient. For the sake of clarity, the BSP tree itself will not be defined as a class.
Overview (under development) It is common to see BSP trees which represent two and three dimensional space, but the definition of the structure is not constrained to these. For these two cases, the polytope stored is a line segment and a polygon, respectively.
Overview 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
or the ASCII art version: +-----------+ +-----+-----+ +-----+-----+ | | | | | | | | | | | | | | d | | | | | | | | | | | a | -> | b X c | -> +--Y--+ c | -> ... | | | | | | | | | | | | | | e | | | | | | | | | | +-----------+ +-----+-----+ +-----+-----+
a X X ...
-/ \+ -/ \+
/ \ / \
b c Y c
-/ \+
/ \
d e
Other space partitioning structures
Overview The algorithm to build a BSP tree is very simple:
Choosing the partition plane 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 or more 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
When to stop
Pseudo C++ code example
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. For this example, 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:
back_list.Add_To_List (poly);
break;
case IN_FRONT_OF:
front_list.Add_To_List (poly);
break;
case SPANNING:
polygon *front_piece, *back_piece;
Split_Polygon (poly, tree->partition, front_piece, back_piece);
back_list.Add_To_List (back_piece);
front_list.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 routine recursively constructs 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. This implementation assumes that all of the input polygons are convex.
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?".
Overview The basic algorithm is to loop across all the edges of the polygon and find those for which one vertex is on each side of the partition plane. The intersection points of these edges and the plane are computed, and those points are used as new vertices for the resulting pieces.
Implementation notes 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. Convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.
Pseudo C++ code example
void Split_Polygon (polygon *poly, plane *part, polygon *&front, polygon *&back)
{
int count = poly->NumVertices (),
out_c = 0, in_c = 0;
point ptA, ptB,
outpts[MAXPTS],
inpts[MAXPTS];
real sideA, sideB;
ptA = poly->Vertex (count - 1);
sideA = part->Classify_Point (ptA);
for (short i = -1; ++i < count;)
{
ptB = poly->Vertex (i);
sideB = part->Classify_Point (ptB);
if (sideB > 0)
{
if (sideA < 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
outpts[out_c++] = ptB;
}
else if (sideB < 0)
{
if (sideA > 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
inpts[in_c++] = ptB;
}
else
outpts[out_c++] = inpts[in_c++] = ptB;
ptA = ptB;
sideA = sideB;
}
front = new polygon (outpts, out_c);
back = new polygon (inpts, in_c);
}
A simple extension to this code that is good for BSP trees is to combine its functionality with the routine to classify a polygon with respect to a plane.
Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.
Overview 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
+------+
| |
+---------------| |--+
| | | |
| | | |
| | | |
| +--------| |--+
| | | |
+--| |--------+ |
| | | |
| | | |
| | | |
+--| |---------------+
| |
+------+
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 The trick to making a scanline approach successful is to have an efficient method for masking pixels. One way to do this is to maintain a list of pixel spans which have not yet been written to for each scan line. For each polygon scan converted, only pixels in the available spans are written, and the spans are updated accordingly. The scan line spans can be represented as binary trees, which are just one dimensional BSP trees. This technique can be expanded to a two dimensional screen coverage algorithm using a two dimensional BSP tree to represent the masked regions. Any convex partitioning scheme, such as a quadtree, can be used with similar effect.
Implementation notes
Pseudo C++ code example
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. The coincident polygon list does not need to be drawn in this case, because those polygons will not be visible to the user.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. It is worth noting that this improvement resembles the method for tracing a ray through a BSP tree, which is discussed in another section of this document.
Front to back tree traversal is accomplished in exactly the same manner, except that the recursive calls to
Overview BSP trees can be used to compute visible fragments of polygons in a scene in at least two different ways. Both methods involve the use of a bsp tree for front to back traversal, and a second tree which describes the visible space in the viewing volume.
Screen partitioning
Beam tree
First DRAFT.
Overview
Implementation notes A large improvement can be made over the voxel walking algorithm for recursive ray tracing by using the parent node of the ray origin as a hint. Because ray tracing is a spatial classification problem, balancing is the key to performance. Most spatial partitioning schemes for accellerating ray tracing use a criteria called "occupancy", which refers to the number of primitives residing in each partition. A BSP tree which has approximately the same occupancy for all partitions is balanced. Balancing is discussed elsewhere in this document.
MORE TO COME
Overview An in/out test is a different way of talking about the front/back test we have been using to classify points with respect to planes. The necessity for this shift in thought is evident when considering polytopes instead of just polygons. A point can not be merely in front or back of a polytope, but inside or outside. Somewhat formally, a point is inside of a convex polytope if it is inside of, or in back of, each hyperplane which composes the polytope, otherwise it is outside.
Incremental construction It is useful to examine the construction process in two dimensions. Consider the following figure:
A B
+-------------+
| |
| |
| E | F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D | C |
| |
| |
+-------------+
H G
Two polygons, ABCD, and EFGH, are to be inserted into the tree. We wish to find the union of these two polygons. Start by inserting polygon ABCD into the tree, choosing the splitting hyperplanes to be coincident with the edges. The tree looks like this after insertion of ABCD:
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ *
CD
-/ \+
/ \
/ *
DA
-/ \+
/ \
* *
Now, polygon EFGH is inserted into the tree, one edge at a time. The result looks like this:
A B
+-------------+
| |
| |
| E |J F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
/ * \ \
EJ KH \
-/ \+ -/ \+ \
/ \ / \ \
/ * / * \
LE HL JF
-/ \+ -/ \+ -/ \+
/ \ / \ / \
* * * * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Notice that when we insert EFGH, we split edges EF and HE along the edges of ABCD. this has the effect of dividing these segments into pieces which are inside ABCD, and outside ABCD. Segments EJ and LE will not be part of the boundary of the union. We could have saved our selves some work by not inserting them into the tree at all. For a union operation, you can always throw away segments that land in inside nodes. You must be careful about this though. What I mean is that any segments which land in inside nodes of the pre-existing tree, not the tree as it is being constructed. EJ and LE landed in an inside node of the tree for polygon ABCD, and so can be discarded.Our tree now looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| | |
| | |
| | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Now, we would like some way to eliminate the segments JC and CL, so that we will be left with the boundary segments of the union. Examine the segment BC in the tree. What we would like to do is split BC with the hyperplane JF. Conveniently, we can do this by pushing the BC segment through the node for JF. The resulting segments can be classified with the rest of the JF subtree. Notice that the segment BJ lands in an out node, and that JC lands in an in node. Remembering that we can discard interior nodes, we can eliminate JC. The segment BJ replaces BC in the original tree. This process is repeated for segment CD, yielding the segments CL and LD. CL is discarded as landing in an interior node, and LD replaces CD in the original tree. The result looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| |
| |
| L |
+-------+ |
D | |
| |
| |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BJ
-/ \+
/ \
/ \
LD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
As you can see, the result is the union of the polygons ABCD and EFGH.To perform other boolean operations, the process is similar. For intersection, you discard segments which land in exterior nodes instead of internal ones. The difference operation is special. It requires that you invert the polytope before insertion. For simple objects, this can be achieved by scaling with a factor of -1. The insertion process is then conducted as an intersection operation, where segments landing in external nodes are discarded.
Tree merging
Overview Typically, motion is computed in a series of Euler steps. This just means that the motion is computed at discrete time intervals using some description of the speed of motion. For any given point P moving from point A with a velocity V, it's location can be computed at time T as P = A + (T * V). Consider the case where T = 1, and we are computing the motion in one second steps. To find out if the point P has collided with any part of the scene, we will first compute the endpoints of the motion for this time step. P1 = A + V, and P2 = A + (2 * V). These two endpoints will be classified with respect to the BSP tree. If P1 is outside of all objects, and P2 is inside some object, then an intersection has clearly occurred. However, if P2 is also outside, we still have to check for a collision in between. Two approaches are possible. The first is commonly used in applications like games, where speed is critical, and accuracy is not. This approach is to recursively divide the motion segment in half, and check the midpoint for containment by some object. Typically, it is good enough to say that an intersection occurred, and not be very accurate about where it occurred.
The second approach, which is more accurate, but also more time consuming, is to treat the motion segment as a ray, and intersect the ray with the BSP Tree. This also has the advantage that the motion resulting from the impact can be computed more accurately.
Overview 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 a dynamic object is separated from each static object by a plane, the dynamic object can be represented as a single point regardless of its 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 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.
Caveats
Advanced methods
Overview
Overview
Overview
Example Now, a planning graph can be built, using some point inside of each polygon, and connecting to a point inside of each of its neighbors. Note that the selection of the point location has implications for the length of resulting paths. Planning begins by identifying the cell which contains the start point, and the cell which contains the end point. Then a standard A* style search can be used on the planning graph to find the set of polygons that must be crossed to get to the end point from the start point.
Implementation Notes
FIRST DRAFT
Overview
Overview
Space complexity It will be extremely difficult to construct a case which satisfies this formula. The "expected" case, repeatedly expressed by Naylor, is O(n).
Time complexity
Bounding volumes
Optimal trees
Minimizing splitting Bear in mind that minimization of splitting requires pre-existing knowledge about all of the polygons that will be inserted into the tree. This knowledge may not exist for interactive uses such as solid modelling.
Tree balancing For the hidden surface problem, balancing doesn't significantly affect runtime. This is because the expected time complexity for tree traversal is linear on the number of polygons in the tree, rather than the depth of the tree.
Balancing vs. splitting
Reference Counting
Overview
Implementation Notes
void Enumerate (BSP_tree *tree)
{
if (tree->front)
Enumerate (tree->front);
if (tree->back)
Enumerate (tree->back);
}
To eliminate the recursion, you have to explicitly model the recursion using a stack. Using a stack of pointers to
void Enumerate (BSP_tree *tree)
{
Stack stack;
while (tree)
{
if (tree->back)
stack.Push (tree->back);
if (tree->front)
stack.Push (tree->front);
tree = stack.Pop ();
}
}
On some processors, using a stack will be faster than the recursive method. This is especially true if the recursive routine has a lot of local variables. However, the recursive approach is usually easier to understand and debug, as well as requiring less code.
Overview Sage: Long ago in a small village in Nepal, a minor godling gave a special nut to the priests at an out of the way temple. With the nut, was a prophecy: When a group of three gurus, two with red hair, and the other who was not what he seemed, came to the temple on pilgrimage, if the nut was given unto them, and they nurtured it together, it would produce a tree of great benefit to mankind. Many years later, ... N: no! No! NO! The TRUE story. S: OK. Long ago (by computer industry standards) in a rapidly growing sunbelt city in Texas, a serendipitous convergence of unusual talents and personalities occurred. A brief burst of graphics wonderments appeared, and the convergence diverged under its own explosive production, leading to further graphics developments in several new locations. One of the wonderous paths followed ... N: ...No! The facts! S: Huh? Oh you want FACTS. Boring stuff? Henry Fuchs started teaching at an essentially brand new campus, the University of Texas at Dallas, in January 1975. He returned to Utah to complete his PhD the following summer. He returned to Dallas and taught for the 1975-76, 1976-77 and 1977-78 academic years, before being lured away to UNC-Chapel Hill. Zvi Kedem joined this faculty in the fall of 1975. He was (and still is I suppose) a "theory person," but a special theory person. He is good at applying theory to practical problems. Bruce Naylor had a bachelors degree from the U of Texas (Austin - "the real one"), in philosophy if I recall correctly. He had talked his way into a job at Texas Instruments in Dallas. (Something about philosophy makes you good in logic, which is really the same as computers...!?) He came to UTD to take some computer courses. He was spotted as "good" - probably by Kedem, but I can't swear to it - and convinced to become a full time graduate student. Graphics, of course, is dazzling and wonderful. Henry was (is) full of energy and enthusiasm. It was natural that he attracted lots of the grad students. Kedem was a perfect complement, providing not only the formal rigor and proofs, but also the impetus to "write this part up" before going on to "the next thing and the next thing and ..." Kedem and Fuchs together (and most of the grad students) also found a new thrust in the CS theory community, called computational geometry, particularly interesting. Henry liked to talk about the Schumacker priority driven visible surface algorithm when the class got to that topic. He seemed to think there was something more to be done in that vein. Naylor being a grad student in search of a topic, looked into it. The result was two SIGGRAPH papers and Naylor's PhD dissertation, and the launch of BSP-trees into the world. The two papers are Fuchs, Kedem and Naylor, "Predeterming Visibility Priority in 3-D Scenes" SIGGRAPH '79, pp 175-181. (subtitled "preliminary report") and Fuchs, Kedem and Naylor, "On Visible Surface Generation by A Priori Tree Structures" SIGGRAPH '80, pp124-133. The first paper isn't really BSP-trees, but rather the preliminary work which led to BSP-trees as the solution. The second paper is the "classic" starting point referenced in texts, etc. Both reference Schumacker, Brand, Gilliland and Sharp, "Study for Applying Computer-Generated Images to Visual Simulation" AFHRL-TR-69-14, US AF Human Resources Lab, 1969 and the description of this algorithm more easily found in Sutherland, Sproull and Schumacker, "A Characterization of Ten Hidden Surface Algorithms", ACM Computing Surveys, v 6, no 1, pp 1-55.
Naylor finished in 1981 (?) and went to Georgia Tech, and later to
Bell Labs. He has continued to work on related and similar ideas with
a variety of students and collaborators. Others have also taken the
ideas in new directions.
BSP tree FAQ companion code
Also in this directory is the BSP tree demo application for MacOS and Win95. This demo shows how to use BSP trees for basic Boolean modelling and hidden surface removal, and includes an implementation of Ken Shoemake's ArcBall interface. The MacOS package includes all of the source for the demo application in several Metrowerks CodeWarrior projects. The Win95 package is based on the MacOS package, and includes all the source for the demo in a single Microsoft Visual C++ 4.2 project. An X-Windows port is in progress. Information about the ArcBall controller can be found in Graphics Gems IV (see below). The original paper and demo application for 68k based Apple Macintosh computers is available via WWW or FTP at:
Graphics Gems
It is an invaluable resource for all things graphical. In particular, there are some BSP tree references worth looking over. Peter Shirley and Kelvin Sung have C sample code for ray tracing with BSP trees in Graphics Gems III Norman Chin has provided a wonderful resource for BSP trees in Graphics Gems V. He provides C sample code for a wide variety of uses.
Other BSP tree resources
It has many good articles which involve the use of BSP trees or compares them to other data structures for ray tracing efficiency. It's definitely worth a look. The DejaNews research service is a search engine for newsgroup postings. Conduct a search on "BSP tree" to read over recent, as well as old, discussions about BSP trees. DejaNews is available at:
Pat Fleckenstein and Rob Reay have put together a FAQ on 3D graphics, which includes a blurb on BSP trees, and an FTP site with some sample code:
Dr. Dobbs Journal has an article in their July '95 issue about BSP trees, By Nathan Dwyer. It describes the construction of BSP trees for visible surface processing, how to split polygons with planes, and how to dump the tree to a file. There is C++ source code to accompany the article.
Michael Abrash's columns in the DDJ Sourcebooks are an excellent introduction to the concept of BSP trees, and the practical details of implementing them for games like Doom and Quake. The source code for these articles is distributed over several sites.
Ekkehard Beier has made available a generic 3D graphics kernel intended to assist development of graphics application interfaces. One of the classes in the library is a BSP tree, and full source is provided. The focus seems to be on ray tracing, with the code being based on Jim Arvo's Linear Time Voxel Walking article in the ray tracing news.
Eddie Edwards wrote a commonly referenced text which describes 2D BSP trees in some detail for use in games like DOOM. It includes a bit of sample code, too.
Mel Slater has made available his C source code for computing shadow volumes based on BSP trees. There is also a paper which compares three shadow volume algorithms. These are available via FTP at:
The SPHIGS distribution that accompanies the famous Foley, et al. Computer Graphics textbook contains a BSP tree implementation and can be obtained at:
John Holmes, Jr. has a paper about BSP trees and boundary representations online. This paper touches on many aspects of BSP trees in a scientific manner, and is available at:
A.T. Campbell III has placed his doctoral dissertation online. This document describes the use of BSP trees for surface meshing in a radiosity algorithm. He has also made available source code in both C and C++ for many BSP tree tasks, including an implementation of tree merging. This is all available on his home page at:
Andrea Marchini and Stefano Tommesani have made available a BSP tree compiler and viewing program as part of the "Purple Haze" project. There is some nice accompanying documentation of the process of BSP tree construction, as well. The web page is at:
Paton Lewis has built an excellent demonstration of BSP trees using Java. If you have had problems visualizing the tree contruction process, you should take a look at this tool. The user draws lines in an interactive construction space, and three other view panes show the split segments, a traditional graph representation of the tree, and a first person perspective view of the line segments as walls. This is how DOOM works. The web page is:
A general graphics programming resources has an article about building BSP trees using axis-aligned partitioning planes. The article calls this structure a bintree, after a 1994 paper by Tamminen. The URL is:
John Whitley has a short tutorial page about BSP trees which covers general details of tree construction and display. It includes psuedo-code for a front to back tree traversal, and an annotated bibliography. The location of this resource is:
Tom Hammersly has put up a web page with his experience in building a BSP tree compiler and viewer. The web page is at:
Id software has made a great deal of source code for games and utilities available, much of which deals extensively with BSP trees. The source code is complete, and easy to understand. The site is at:
General resources for computer graphics programming
The computational geometry web page contains lots of information and pointers to related computational geometry tools and algorithms: http://www.cs.duke.edu/~jeffe/compgeom/. Another computational geometry page to look at is http://www.ics.uci.edu:80/~eppstein/geom.html. This page seems to have a more tutorial nature than the first page.
A partial listing of textual info on BSP trees.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
made by Digital Vintage with nginx-s3-gateway and some magic digitalvintage.ru t.me/digitalvintage_ru instagram.com/digitalvintage.ru |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
