From Wikipedia, the free encyclopedia
Binary space partitioning
(BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This
subdivision gives rise to a representation of the scene by means of
a tree data structure known as a
BSP tree.
In other words, it is a method of breaking up intricately shaped
polygons into smaller and simpler polygons in such a way as to
eliminate all reflex angles (angles which measure greater
than 180°) from the original shape. For a more general description
of space partitioning, see space partitioning.
Originally, this approach was proposed in 3D
computer graphics to increase the rendering efficiency.
Some other applications include performing geometrical operations
with shapes (constructive solid
geometry) in CAD, collision detection in robotics and 3D computer games, and other computer
applications that involve handling of complex spatial scenes.
Overview
In computer graphics it is desirable that the drawing of a scene
be both correct and quick. A simple way to draw a scene is the painter's
algorithm: draw it from back to front painting the background
over with each closer object. However, that approach is quite
limited since time is wasted drawing objects that will be overdrawn
later, and not all objects will be drawn correctly.
Z-buffering can
ensure that scenes are drawn correctly and eliminate the ordering
step of the painter's algorithm, but it is expensive in terms of
memory use. BSP trees will split up objects so that the painter's
algorithm will draw them correctly without need of a Z-buffer and
eliminate the need to sort the objects; as a simple tree traversal
will yield them in the correct order. It also serves as base for
other algorithms, such as visibility lists, which seek to reduce
overdraw.
The downside is the requirement for a time consuming
pre-processing of the scene, which makes it difficult and
inefficient to directly implement moving objects into a BSP tree.
This is often overcome by using the BSP tree together with a
Z-buffer, and using the Z-buffer to correctly merge movable objects
such as doors and monsters onto the background scene.
BSP trees are often used by 3D computer games,
particularly first-person shooters and those
with indoor environments. Probably the earliest game to use a BSP
data structure was Doom (see Doom engine for an
in-depth look at Doom's BSP implementation). Other uses
include ray tracing and collision
detection.
Generation
Binary space partitioning is a generic process of recursively dividing a
scene into two until the partitioning satisfies one or more
requirements. The specific method of division varies depending on
its final purpose. For instance, in a BSP tree used for collision
detection, the original object would be partitioned until each part
becomes simple enough to be individually tested, and in rendering
it is desirable that each part be convex so that the painter's
algorithm can be used.
The final number of objects will inevitably increase since lines
or faces that cross the partitioning plane must be split into two,
and it is also desirable that the final tree remains reasonably balanced. Therefore
the algorithm for correctly and efficiently creating a good BSP
tree is the most difficult part of an implementation. In 3D space,
planes are used to partition and split an object's faces; in 2D
space lines split an object's segments.
The following picture illustrates the process of partitioning an
irregular polygon into a series of convex ones. Notice how each
step produces polygons with fewer segments until arriving at G and
F, which are convex and require no further partitioning. In this
particular case, the partitioning line was picked between existing
vertices of the polygon and intersected none of its segments. If
the partitioning line intersects a segment, or face in a 3D model,
the offending segment(s) or face(s) have to be split into two at
the line/plane because each resulting partition must be a full,
independent object.
1. A is the root of the tree and the entire polygon
2. A is split into B and C
3. B is split into D and E.
4. D is split into F and G, which are convex and hence become
leaves on the tree.
Since the usefulness of a BSP tree depends upon how well it was
generated, a good algorithm is essential. Most algorithms will test
many possibilities for each partition until finding a good
compromise and might also keep backtracking information in memory
so that if a branch of the tree is found to be unsatisfactory other
alternative partitions may be tried. Therefore producing a tree
usually requires long computations.
BSP trees were also used to represent natural images.
Construction methods of BSP trees of images were first introduced
as efficient representations, where only a few hundred nodes can
represent an image that normally require hundreds-of-thousands of
pixels. Fast algorithms were also developed to construct BSP trees
of images using computer vision and signal processing algorithms.
These algorithms in conjunction with advanced entropy coding and
signal approximation approaches were used to develop image
compression methods.
Rendering a scene with visibility information from the BSP
tree
BSP trees are used to improve rendering performance in
calculating visible triangles for the painter's
algorithm for instance. The tree can be traversed in linear
time from an arbitrary viewpoint.
Since a painter's algorithm works by drawing polygons farthest
from the eye first, the following code recurses to the bottom of
the tree and draws the polygons. As the recursion unwinds, polygons
closer to the eye are drawn over far polygons. Because the BSP tree
already splits polygons into trivial pieces, the hardest part of
the painter's algorithm is already solved - code for back to front
tree traversal. ^{[1]}
traverse_tree(bsp_tree* tree,point eye)
{
location = tree->find_location(eye);
if(tree->empty())
return;
if(location > 0) // if eye in front of location
{
traverse_tree(tree->back,eye);
display(tree->polygon_list);
traverse_tree(tree->front,eye);
}
else if(location < 0) // eye behind location
{
traverse_tree(tree->front,eye);
display(tree->polygon_list);
traverse_tree(tree->back,eye);
}
else // eye coincidental with partition hyperplane
{
traverse_tree(tree->front,eye);
traverse_tree(tree->back,eye);
}
}
Other space partitioning
structures
BSP trees divide a region of space into two subregions at each
node. They are related to quadtrees and octrees, which divide each region into four or
eight subregions, respectively.
Relationship Table
Name |
p |
s |
Binary Space Partition |
1 |
2 |
Quadtree |
2 |
4 |
Octree |
3 |
8 |
where p is the number of dividing planes used, and
s is the number of subregions formed.
BSP trees can be used in spaces with any number of dimensions,
but quadtrees and octrees are most useful in subdividing 2- and
3-dimensional spaces, respectively. Another kind of tree that
behaves somewhat like a quadtree or octree, but is useful in any
number of dimensions, is the kd-tree.
Timeline
- 1969 Schumacker et al published a report that described how
carefully positioned planes in a virtual environment could be used
to accelerate polygon ordering. The technique made use of depth
coherence, which states that a polygon on the far side of the plane
cannot, in any way, obstruct a closer polygon. This was used in
flight simulators made by GE as well as Evans and Sutherland.
However, creation of the polygonal data organization was performed
manually by scene designer.
- 1980 Fuchs et
al. [FUCH80] extended Schumacker’s idea to the representation of 3D
objects in a virtual environment by using planes that lie
coincident with polygons to recursively partition the 3D space.
This provided a fully automated and algorithmic generation of a
hierarchical polygonal data structure known as a Binary Space
Partitioning Tree (BSP Tree). The process took place as an off-line
preprocessing step that was performed once per environment/object.
At run-time, the view-dependent visibility ordering was generated
by traversing the tree.
- 1981 Naylor's Ph.D thesis containing a full development of both
BSP trees and a graph-theoretic approach using strongly connected
components for pre-computing visibility, as well as the connection
between the two methods. BSP trees as a dimension independent
spatial search structure was emphasized, with applications to
visible surface determination. The thesis also included the first
empirical data demonstrating that the size of the tree and the
number of new polygons was reasonable (using a model of the Space
Shuttle).
- 1983 Fuchs et
al. describe a micro-code implementation of the BSP tree algorithm
on an Ikonas frame buffer system. This was the first demonstration
of real-time visible surface determination using BSP trees.
- 1987 Thibault and Naylor described how arbitrary polyhedra may
be represented using a BSP tree as opposed to the traditional b-rep
(boundary representation). This provided a solid representation vs.
a surface based-representation. Set operations on polyhedra were
described using a tool, enabling Constructive Solid Geometry (CSG)
in real-time. This was the fore runner of BSP level design using
brushes, introduced in the Quake editor and picked up in the Unreal
Editor.
- 1990 Naylor, Amanatides, and Thibault provide an algorithm for
merging two bsp trees to form a new bsp tree from the two original
trees. This provides many benefits including: combining moving
objects represented by BSP trees with a static environment (also
represented by a BSP tree), very efficient CSG operations on
polyhedra, exact collisions detection in O(log n * log n), and
proper ordering of transparent surfaces contained in two
interpenetrating objects (has been used for an x-ray vision
effect).
- 1990 Teller and Séquin proposed the offline generation of
potentially visible sets to accelerate visible surface
determination in orthogonal 2D environments.
- 1991 Gordon and Chen [CHEN91] described an efficient method of
performing front-to-back rendering from a BSP tree, rather than the
traditional back-to-front approach. They utilised a special data
structure to record, efficiently, parts of the screen that have
been drawn, and those yet to be rendered. This algorithm, together
with the description of BSP Trees in the standard computer graphics
textbook of the day (Foley, Van Dam, Feiner and Hughes) was used by
John Carmack
in the making of Doom.
- 1992 Teller’s PhD thesis described the efficient generation of
potentially visible sets as a pre-processing step to acceleration
real-time visible surface determination in arbitrary 3D polygonal
environments. This was used in Quake and contributed significantly
to that game's performance.
- 1993 Naylor answers the question of what characterizes a good
bsp tree. He used expected case models (rather than worst case
analysis) to mathematically measure the expected cost of searching
a tree and used this measure to build good BSP trees. Intuitively,
the tree represents an object in a multi-resolution fashion (more
exactly, as a tree of approximations). Parallels with Huffman codes
and probabilistic binary search trees are drawn.
- 1993 Hayder Radha's PhD thesis described (natural) image
representation methods using BSP trees. This includes the
development of an optimal BSP-tree construction framework for any
arbitrary input image. This framework is based on a new image
transform, known as the Least-Square-Error (LSE) Partitioning Line
(LPE) transform. H. Radha' thesis also developed an optimal
rate-distortion (RD) image compression framework and image
manipulation approaches using BSP trees.
References
- [FUCH80] H.
Fuchs, Z. M. Kedem and B. F. Naylor. “On Visible Surface
Generation by A Priori Tree Structures.” ACM Computer Graphics, pp
124–133. July 1980.
- [THIBAULT87] W. Thibault and B. Naylor, "Set Operations on
Polyhedra Using Binary Space Partitioning Trees", Computer Graphics
(Siggraph '87), 21(4), 1987.
- [NAYLOR90] B. Naylor, J. Amanatides, and W. Thibualt, "Merging
BSP Trees Yields Polyhedral Set Operations", Computer Graphics
(Siggraph '90), 24(3), 1990.
- [NAYLOR93] B. Naylor, "Constructing Good Partitioning Trees",
Graphics Interface (annual Canadian CG conference) May, 1993.
- [CHEN91] S. Chen and D. Gordon. “Front-to-Back Display of BSP
Trees.” IEEE Computer Graphics & Algorithms, pp 79–85.
September 1991.
- [RADHA91] H. Radha, R. Leoonardi, M. Vetterli, and B. Naylor
“Binary Space Partitioning Tree Representation of Images,” Journal
of Visual Communications and Image Processing 1991, vol. 2(3).
- [RADHA93] H. Radha, "Efficient Image Representation using
Binary Space Partitioning Trees.", Ph.D. Thesis, Columbia
University, 1993.
- [RADHA96] H. Radha, M. Vetterli, and R. Leoonardi, “Image
Compression Using Binary Space Partitioning Trees,” IEEE
Transactions on Image Processing, vol. 5, No.12, December 1996, pp.
1610-1624.
- [WINTER99] AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING
USING BSP TREES. Andrew Steven Winter. April 1999. available
online
- Mark de Berg, Marc van Kreveld, Mark Overmars, and
Otfried Schwarzkopf (2000). Computational Geometry (2nd
revised edition ed.). Springer-Verlag. ISBN
3-540-65620-0.
Section 12:
Binary Space Partitions: pp.251–265. Describes a randomized
Painter's Algorithm.
- Christer Ericson: Real-Time Collision Detection (The Morgan
Kaufmann Series in Interactive 3-D Technology). Verlag
Morgan Kaufmann, S. 349-382, Jahr 2005, ISBN
1-55860-732-3
External
links