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).
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
Another example
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.
Other space partitioning structures
BSP trees are closely related to quadtrees and octrees. Quadtrees and Octrees are space partitioning trees which recursively divide subspaces into four and eight new subspaces, respectively. A BSP Tree can be used to simulate both of these structures.
The above is a direct quote from http://www.faqs.org/faqs/graphics/bsptree-faq/