Binary space partitioning (BSP) is a method for recursively subdividing a space
Euclidean space
Around 300 Before Christ, the Ancient Greece mathematician Euclid undertook a study of relationships among distances and angles, first in a plane and then in space.... into convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object.... s by hyperplane
Hyperplane
A hyperplane is a concept in geometry. It is a higher-dimensional generalization of the concepts of a line in the plane and a plane in 3-dimensional space.... s. This subdivision gives rise to a representation of the scene by means of a tree data structure
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked Vertex_. It is an acyclic connected graph where each node has a set of zero or more children nodes, and at most one parent node.... known as a BSP tree.
In other words, it is a method of breaking up intricately shaped polygons into convex sets, or smaller polygons consisting entirely of non-reflex angles (angles smaller than 180°).
Discussion
Ask a question about 'Binary space partitioning'
Start a new discussion about 'Binary space partitioning'
Answer questions from other users
Full Discussion Forum
Encyclopedia
Binary space partitioning (BSP) is a method for recursively subdividing a space
Euclidean space
Around 300 Before Christ, the Ancient Greece mathematician Euclid undertook a study of relationships among distances and angles, first in a plane and then in space.... into convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object.... s by hyperplane
Hyperplane
A hyperplane is a concept in geometry. It is a higher-dimensional generalization of the concepts of a line in the plane and a plane in 3-dimensional space.... s. This subdivision gives rise to a representation of the scene by means of a tree data structure
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked Vertex_. It is an acyclic connected graph where each node has a set of zero or more children nodes, and at most one parent node.... known as a BSP tree.
In other words, it is a method of breaking up intricately shaped polygons into convex sets, or smaller polygons consisting entirely of non-reflex angles (angles smaller than 180°). For a more general description of space partitioning, see space partitioning
Space partitioning
In mathematics, space partitioning is the process of dividing a space into two or more disjoint subsets . In other words, space partitioning divides a space into non-overlapping regions.... .
3D computer graphics are graphics that use a Cartesian coordinate system#Three-dimensional coordinate system representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images.... to increase the rendering
Rendering (computer graphics)
Rendering is the process of generating an image from a 3D model, by means of computer programs. The model is a description of three-dimensional objects in a strictly defined language or data structure.... efficiency. Some other applications include performing geometrical operations with shapes (constructive solid geometry
Constructive solid geometry
Constructive solid geometry is a technique used in solid modeling. CSG is often, but not always, a procedural modeling technique used in 3D computer graphics and CAD.... ) in CAD, collision detection
Collision detection
In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids.... in robotics
Robotics
Robotics is the science and technology of robots, and their design, manufacture, and application. Robotics has connections to electronics, mechanics, and software.... 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 correctly is the painter's algorithm
Painter's algorithm
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics.... : 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.
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software.... 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
Tree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited.... 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 shooter
First-person shooter
File:Freedoom aaa.pngFirst-person shooter is a Video game genres, featuring a First person , with which the player views the action as if through the eyes of the protagonist and in which the primary element is combat based around shooting.... s and those with indoor environments. Probably the earliest game to use a BSP data structure was Doom (see Doom engine
Doom engine
Doom Engine, also called id Tech 1, is the game engine that powers the id Software video game Doom and Doom II. It is also used by Hexen, Heretic , Strife and Doom WAD#Total conversions, and other games produced by licensees.... for an in-depth look at Doom's BSP implementation). Other uses include ray tracing
Ray tracing
In computer graphics, ray tracing is a technique for generating an digital image by tracing the path of light through pixel in an . The technique is capable of producing a very high degree of photorealism; usually higher than that of typical scanline rendering methods, but at a greater computation time.... and collision detection
Collision detection
In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids.... .
Generation
Binary space partitioning is a generic process of recursively
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... 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
Painter's algorithm
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics.... 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
Self-balancing binary search tree
In computer science, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically.... . 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
Face (geometry)
In geometry, a face of a polyhedron is any of the polygons that make up its boundaries. For example, any of the square s that bound a cube is a face of the cube.... ; in 2D space lines split an object's segments
Line segment
In geometry, a line segment is a part of a line that is bounded by two end Point , and contains every point on the line between its end points.... .
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.
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
Painter's algorithm
The painter's algorithm, also known as a priority fill, is one of the simplest solutions to the visibility problem in 3D computer graphics.... 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.
traverse_tree(bsp_tree* tree,point eye)
Other space partitioning structures
BSP trees divide a region of space into two subregions at each node. They are related to quadtree
Quadtree
A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions.... s and octree
Octree
An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants.... s, which divide each region into four or eight subregions, respectively.
A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions....
An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants....
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
Kd-tree
In computer science, a kd-tree is a space partitioning data structure for organizing Point s in a k-dimensional Euclidean space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key .... .
Timeline
from [WINTER99]
1969 Schumacker 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.
Henry Fuchs is the Federico Gil Professor of Computer Science, Adjunct Professor of Biomedical Engineering, and Adjunct Professor of Radiation oncologist at the University of North Carolina at Chapel Hill.... et al. [FUCH80] refined Schumacker’s idea, and formalised a pre-process that partitions a virtual environment using planes that lie coincident with polygons. The result of the pre-process is a hierarchical polygon database known as a Binary Space Partitioning tree.
Henry Fuchs is the Federico Gil Professor of Computer Science, Adjunct Professor of Biomedical Engineering, and Adjunct Professor of Radiation oncologist at the University of North Carolina at Chapel Hill.... et al. discussed the creation of BSP trees and their use in the fast rendering of polygonal objects.
1987 Thibault and Naylor outlined how arbitrary polyhedra may be described using a BSP tree as opposed to the traditional b-rep (boundary representation). Set operations were mentioned, enabling the application of Constructive Solid Geometry (CSG).
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 was the paper used by John Carmack in the making of Doom.
1992 Teller’s PhD thesis described the efficient generation and use of potentially visible sets for offline visible surface determination in arbitrary 3D polygonal environments.
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.
Portable Document Format is a file format created by Adobe Systems in 1993 for document exchange. PDF is used for representing two-dimensional documents in a manner independent of the application software, hardware, and operating system.... )
