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.
Originally, this approach was proposed in 3D computer graphics to increase the efficiency of computer rendering. Among other applications are 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's 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: 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 used. 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 simply walking the tree will yeld 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 impossible to 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 they satisfy one or more requirements, the specific method of division varying 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's 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 a implementation. In 3D space, planes are used to partition and split an object's faces; in 2D space lines plit 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 vertexes of the polygon and intersected none of its segments. If the partitioning line interesects 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.
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 possibilites 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 usuallly requires long computations.
There is a Java applet which demonstrates the process of tree generation at the address: http://symbolcraft.com/graphics/bsp/
BSP (binary space partition) tree
BSP trees are a geometric tool that can be used for a variety of tasks, including resolving visibility, computing shadows and also to reject polygons that are outside the view volume. BSPs are too complex to implement in hardware (at least today), so those operations will be performed by the CPU rather than the GPU. BSPs are particularly useful for walkthrough/flythrough applications where the viewpoint is allowed to move but (most of) the scene and the lights are fixed (however, extending them to handle scene is, to some extent, possible). Historically, they have been used with great success in flight simulators. Variants of BSP trees are commonly used in computer games too.
The above is a direct quote from http://www.cc.gatech.edu/classes/AY2004/cs4451a_fall/bsp.pdf
Binary space partition trees (BSP trees) were introduced by Fuchs, Kedem, and Naylor around 1980. This graphics trio produced two papers: "Predeterming Visibility Priority in 3-D Scenes" and "On Visible Surface Generation by A Priori Tree Structures" which outlined the usefulness of BSP trees and how to implement them. Fuchs, Kedem, and Naylor primarly focused on enhancing rendering of static scenes. Later authors built on the above papers to incorporate shadow generation and handling of dynamic scenes.
Simply, a BSP tree is a heirarchical subdivisions of n dimensional space into convex subspaces. Each node has a front and back leaf. Starting off with the root node, all subsequent insertions are partitioned by the hyperplane of the current node. In 2 dimensional space, a hyperplane is a line. In 3 dimensional space, a hyperplane is a plane. The end goal of a BSP tree if for the hyperplanes of the leaf nodes to be trivially "behind" or "in front" of the parent hyperplane.
BSP trees are very useful for real time interaction with displays of static images. Before the static scene is rendered, the BSP tree is calculated. BSP trees can be traversed very quickly (linear time) for hidden surface removal and shadow casting. With some work, BSP trees can be modified to handle dynamic events in a scene.
The above is a direct quote from http://www.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html
A binary space-partitioning (BSP) tree represents a recursive, hierarchical partitioning, or subdivision, of n-dimensional space into convex subspaces. BSP tree construction is a process which takes a subspace and partitions it by any hyperplane that intersects the interior of that subspace. The result is two new subspaces that can be further partitioned by recursive application of the method.
A "hyperplane" in n-dimensional space is an (n − 1)-dimensional subspace that divides the space into two half-spaces. For example, in three-dimensional space, the "hyperplane" is a plane. In two-dimensional space, it is a line.
BSP trees are extremely versatile, because they are powerful sorting and classification structures. They have uses ranging from hidden surface removal and ray tracing hierarchies to solid modeling and robot motion planning.
Example
An easy way to think about BSP trees is to limit the discussion to two dimensions. To simplify the situation, let's say that we will use only lines parallel to the X or Y axis, and that we will divide the space equally at each node. For example, given a square somewhere in the XY plane, we select the first split, and thus the root of the BSP Tree, to cut the square in half in the X direction. At each slice, we will choose a line of the opposite orientation from the last one, so the second slice will divide each of the new pieces in the Y direction. This process will continue recursively until we reach a stopping point, and looks like this:
+-----------+......+-----+-----+......+-----+-----+
|-----------|......|-----|-----|......|-----|-----|
|-----------|......|-----|-----|......|--d--|-----|
|-----------|......|-----|-----|......|-----|-----|
|---- a ----|..->..|--b--X--c--|..->..+--Y--+--f--| -> ...
|-----------|......|-----|-----|......|-----|-----|
|-----------|......|-----|-----|......|--e--|-----|
|-----------|......|-----|-----|......|-----|-----|
+-----------+......+-----+-----+......+-----+-----+
The resulting BSP tree looks like this at each step:
a X X ...
-/ \+ -/ \+
/ \ / \
b c Y f
-/ \+
/ \
e d
Other space partitioning structures
BSP trees are closely related to quadtrees and octrees which divide subspaces into four and eight new subspaces, respectively. Quadtrees and octrees can be considered special cases of BSP trees.