|
|
| Home > Photo, Video, Graphics > graphics > |
Binary Space Partitioning Trees FAQ |
Section 2 of 2 - Prev - Next
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 side 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 cinducted as an intersection operation,
where segments landing in external nodes are discarded.
Tree merging
--
Last Update: 04/30/95 15:45:20
How do you perform collision detection with a BSP Tree?
Overview
Detecting whether or not a point moving along a line intersects
some object in space is essentially a ray tracing problem.
Detecting whether or not two complex objects intersect is
something of a tree merging problem.
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.
--
Last Update: 04/30/95 15:45:20
How do you handle dynamic scenes with a BSP Tree?
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 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
Inserting a point into the BSP tree is very cheap, because there
is only one front/back test at each node. Points are never split,
which explains the requirement of separation by a plane. The
dynamic object will always be drawn completely in front of the
static objects behind it.
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.
Advanced methods
Tree merging, "ghosts", real dynamic trees... MORE TO COME
--
Last Update: 04/29/95 03:14:22
How do you compute shadows with a BSP Tree?
Overview
--
Last Update: 04/30/95 15:45:20
How do you extract connectivity information from BSP Trees?
Overview
--
Last Update: 04/30/95 15:45:20
How are BSP Trees useful for robot motion planning?
Overview
--
Last Update: 04/30/95 15:45:20
How are BSP Trees used in DOOM?
Overview
Before you can understand how DOOM uses a BSP tree to accelerate
its rendering process, you have to understand how the world is
represented in DOOM. When someone creates a DOOM level in a level
editor they draw linedefs in a 2d space. Yes, that's right, DOOM
is only 2d. These linedefs (ignoring the special effects linedefs)
must be arranged so that they form closed polygons. One linedef
may be used to form the outline of two polygons (in which case it
is known as a two-sided linedef) and one polygon may be contained
within another, but no linedefs may cross. Each enclosed area of
the world (i.e. polygon) is assigned a floor height, ceiling
height, floor and ceiling textures, a lower texture and an upper
texture. The lower texture is visible when a linedef is viewed
from a direction where the floor is lower in the adjoining area.
An equivalent thing is true for the upper texture. A set of these
enclosed areas that all have the same attributes is known as a
sector.
When the level is saved by the editor some new information is
created including the BSP tree for that level. Before the BSP tree
can be created, all the sectors have to be split into convex
polygons known as sub-sectors. If you had a sector that was a
square area, then that would translate exactly into a sub-sector.
Whereas if that sector was contained inside another larger square
sector, the larger one would have to be split into four, four
sided sub-sectors to make all the sub-sectors convex. When more
complex sectors are split into sub-sectors the linedefs that bound
that sector may need to be broken into smaller lengths. These
linedef sections are called segs.
Given a point on the 2d map, the renderer (which isn't discussed
here) wants a list of all the segs that are visible from that
viewpoint in closest first order. Because of the restrictions
placed on the DOOM world, the renderer can easily tell when the
screen has been filled so it can stop looking for segs at this
time. This is quicker than rendering all the segs from back to
front and using a method like painters algorithm.
Each node in the BSP tree defines a partition line (this does not
have be a linedef in the world but usually is) which is the
equivalent to the partition plane of a 3d BSP tree. It then has
left and right pointers which are either another node for further
sub-division or a leaf, the leaf being a sub-sector in DOOM. The
BSP tree in DOOM is effectively being used to sort whole
sub-sectors rather than individual lines front to back. Each node
also defines an orthogonal bounding box for each side of the
partition. All segs on a particular side of the partition must be
within that box. This speeds up the searching process by allowing
whole branches of the tree to be discarded if that bounding box
isn't visible. The test for visibility is simply if the bounding
box lies wholly or partly within the cone defined by the left and
right edges of the screen.
During the display update process the BSP tree is searched
starting from the node containing the sub-sector that the player
is currently in. The search moves outwards through the tree
(searching the other half of the current node before moving onto
the other half of the parents node). When a partition test is
performed the branch chosen is the one on the same side as the
player. This facilitates the front to back searching. Each time a
leaf is encountered the segs in that sub-sector are passed to the
renderer. If the renderer has returned that the screen is filled
then the process stops, otherwise it continues until the tree has
been fully searched (in which case there is an error in the level
design).
In case you're thinking that it is inefficient to dump a whole
sub-sectors worth of segs into the renderer at once, the segs in a
sub-sector can be back-face culled very quickly. DOOM stores the
angle of linedefs (of which segs are part). When the angle of the
players view is calculated this allows segs to be culled in a
single instruction! Angles are stored as a 16 bit number where 0
is east an 65535 is 1/63336 south of east.
--
Last Update: 04/30/95 15:45:20
How can you make a BSP Tree more robust?
Overview
--
Last Update: 04/30/95 15:45:20
How efficient is a BSP Tree?
Space complexity
For hidden surface removal and ray tracing accelleration, the
upper bound is O(n ^ 2) for n polygons. The expected case is O(n)
for most models. MORE LATER
Time complexity
For hidden surface removal and ray tracing accelleration, the
upper bound is O(n ^ 2) for n polygons. The expected case is O(n)
for most models. MORE LATER
--
Last Update: 04/30/95 15:45:20
How can you make a BSP Tree more efficient?
Bounding volumes
Bounding spheres are simple to implement, take only a single plane
comparison, using the center of the sphere.
Optimal trees
Construction of an optimal tree is an NP-complete problem. The
problem is one of splitting versus tree balancing. These are
mutually exclusive requirements. You should choose your strategy
for building a good tree based on how you intend to use the tree.
Minimizing splitting
An obvious problem with BSP trees is that polygons get split
during the construction phase, which results in a larger number of
polygons. Larger numbers of polygons translate into larger storage
requirements and longer tree traversal times. This is undesirable
in all applications of BSP trees, so some scheme for minimizing
splitting will improve tree performance.
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
Tree balancing is important for uses which perform spatial
classification of points, lines, and surfaces. This includes ray
tracing and solid modelling. Tree balancing is important for these
applications because the time complexity for classification is
based on the depth of the tree. Unbalanced trees have deeper
subtrees, and therefore have a worse worst case.
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
If balancing is an important concern for your application, it will
be necessary to trade off some balance for reduced splitting. If
you are choosing your hyperplanes from the polygon candidates,
then one way to optimize these two factors is to randomly select a
small number of candidates. These new candidates are tested
against the full list for splitting and balancing efficiency. A
linear combination of the two efficiencies is used to rank the
candidates, and the best one is chosen.
Reference Counting
Other Optimizations
--
Last Update: 05/16/95 01:16:38
How can you avoid recursion?
standard binary tree search/sort techniques apply.
--
Last Update: 03/02/95 23:40:07
What is the history of BSP Trees?
Overview
--
Last Update: 04/30/95 15:45:20
Where can you find sample code and related online resources?
BSP tree FAQ companion code
The companion source code to this document is available via FTP
at:
+ file://ftp.graphics.cornell.edu/pub/bsptree/
or, you can also request that the source be mailed to you by sending
e-mail to bsp-faq@graphics.cornell.edu with a subject line of
"SEND BSP TREE SOURCE". This will return to you a UU encoded copy
of the sample C++ source code.
Other BSP tree resources
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. They seem to have an unusual affinity for
ftp sites, and therefore won't link the BSP tree FAQ from their
document:
+ http://www.csh.rit.edu/~pat/misc/3dFaq.html
+ file://ftp.csh.rit.edu/pub/3dfaq/
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.
+ http://www.ddj.com/ddj/issues/j9507a.htm
+ http://www.ddj.com/ddj/issues/j9507b.htm
Michael Abrash's columns in the '95 DDJ Sourcebooks are an
excellent introduction to the concept of BSP trees, especially in
two dimensions. The source code for these is available as part of
a package.
+ ftp://ftp.mv.com/pub/ddj/1995/1995.cpp/asc.zip
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.
+
ftp://metallica.prakinf.tu-ilmenau.de/pub/PROJECTS/GENERIC/gen
eric1.1.tar.gz
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.
+
file://x2ftp.oulu.fi/pub/msdos/programming/theory/bsp_tree.zip
Mel Slater has made available his C source code for computing
shadow volumes based on BSP trees:
+ http://www.dcs.qmw.ac.uk/~mel/BSP.html
Graphics Gems
The Graphics Gems archive at
file://ftp.princeton.edu/pub/Graphics/GraphicsGems/ 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.
More sources for sample BSP tree code
+
file://ftp.idsoftware.com/tonsmore/utils/level_edit/node_build
ers/
+ file://ftp.cs.brown.edu/pub/sphigs.tar.Z
General resources for computer graphics programming
Algorithm, Incorporated, an Atlanta-based Scientific and
Engineering Research and Development Company specializing in
Computer Graphics Programming and Business Internet
Communications, has lots of good pointers and useful offerings.
If you are interested in game programming, check out the
rec.games.programmer.faq:
http://www.ee.ucl.ac.uk/~phart/FAQ/rgp_FAQ.html.
--
Last Update: 08/23/95 10:16:23
References
A partial listing of textual info on BSP trees.
1. Abrash, M., BSP Trees, Dr. Dobbs Sourcebook, 20(14), 49-52,
may/jun 1995.
2. Dadoun, N., Kirkpatrick, D., and Walsh, J., The Geometry of Beam
Tracing, Proceedings of the ACM Symposium on Computational
Geometry, 55--61, jun 1985.
3. Chin, N., and Feiner, S., Near Real-Time Shadow Generation Using
BSP Trees, Computer Graphics (SIGGRAPH '89 Proceedings), 23(3),
99--106, jul 1989.
4. Chin, N., and Feiner, S., Fast object-precision shadow generation
for area light sources using BSP trees, Computer Graphics (1992
Symposium on Interactive 3D Graphics), 25(2), 21--30, mar 1992.
5. Chrysanthou, Y., and Slater, M., Computing dynamic changes to BSP
trees, Computer Graphics Forum (EUROGRAPHICS '92 Proceedings),
11(3), 321--332, sep 1992.
6. Naylor, B., Amanatides, J., and Thibault, W., Merging BSP Trees
Yields Polyhedral Set Operations, Computer Graphics (SIGGRAPH '90
Proceedings), 24(4), 115--124, aug 1990.
7. Chin, N., and Feiner, S., Fast object-precision shadow generation
for areal light sources using BSP trees, Computer Graphics (1992
Symposium on Interactive 3D Graphics), 25(2), 21--30, mar 1992.
8. Naylor, B., Interactive solid geometry via partitioning trees,
Proceedings of Graphics Interface '92, 11--18, may 1992.
9. Naylor, B., Partitioning tree image representation and generation
from 3D geometric models, Proceedings of Graphics Interface '92,
201--212, may 1992.
10. Naylor, B., {SCULPT} An Interactive Solid Modeling Tool,
Proceedings of Graphics Interface '90, 138--148, may 1990.
11. Gordon, D., and Chen, S., Front-to-back display of BSP trees, IEEE
Computer Graphics and Applications, 11(5), 79--85, sep 1991.
12. Ihm, I., and Naylor, B., Piecewise linear approximations of
digitized space curves with applications, Scientific Visualization
of Physical Phenomena (Proceedings of CG International '91),
545--569, 1991.
13. Vanecek, G., Brep-index: a multidimensional space partitioning
tree, Internat. J. Comput. Geom. Appl., 1(3), 243--261, 1991.
14. Arvo, J., Linear Time Voxel Walking for Octrees, Ray Tracing News,
feb 1988.
15. Jansen, F., Data Structures for Ray Tracing, Data Structures for
Raster Graphics, 57--73, 1986.
16. MacDonald, J., and Booth, K., Heuristics for Ray Tracing Using
Space Subdivision, Proceedings of Graphics Interface '89, 152--63,
jun 1989.
17. Naylor, B., and Thibault, W., Application of BSP Trees to Ray
Tracing and CSG Evaluation, Tech. Rep. GIT-ICS 86/03, feb 1986.
18. Sung, K., and Shirley, P., Ray Tracing with the BSP Tree, Graphics
Gems III, 271--274, 1992.
19. Fuchs, H., Kedem, Z., and Naylor, B., On Visible Surface
Generation by A Priori Tree Structures, Conf. Proc. of SIGGRAPH
'80, 14(3), 124--133, jul 1980.
20. Paterson, M., and Yao, F., Efficient Binary Space Partitions for
Hidden-Surface Removal and Solid Modeling, Discrete and
Computational Geometry, 5(5), 485--503, 1990.
--
Last Update: 06/19/95 09:59:42
_________________________________________________________________
This document was last updated on
Andrew Kunz (ank@graphics.cornell.edu)
Section 2 of 2 - Prev - Next
| Back to category graphics - Use Smart Search |
| Home - Smart Search - About the project - Feedback |
© allanswers.org | Terms of use