Editing Binary space partitioning (section)

==Overview==
[[File:2D Binary Index.svg|thumb|An example of a recursive binary space partitioning [[quadtree]] for a 2D index.]]

Binary space partitioning is a generic process of [[recursion|recursively]] dividing a scene into two until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as [[K-d tree|''k''-d trees]] and [[quadtree]]s, one where hyperplanes that partition the space may have any orientation, rather than being aligned with the coordinate axes as they are in ''k''-d trees or quadtrees. When used in computer graphics to render scenes composed of planar [[Polygon mesh|polygons]], the partitioning planes are frequently chosen to coincide with the planes defined by polygons in the scene.

The specific choice of partitioning plane and criterion for terminating the partitioning process varies depending on the purpose of the BSP tree. For example, in computer graphics rendering, the scene is divided until each node of the BSP tree contains only polygons that can be rendered in arbitrary order. When [[back-face culling]] is used, each node, therefore, contains a convex set of polygons, whereas when rendering double-sided polygons, each node of the BSP tree contains only polygons in a single plane. In collision detection or ray tracing, a scene may be divided up into [[Geometric primitive|primitives]] on which collision or ray intersection tests are straightforward.

Binary space partitioning arose from computer graphics needing to rapidly draw three-dimensional scenes composed of polygons. A simple way to draw such scenes is the [[painter's algorithm]], which produces polygons in order of distance from the viewer, back to front, painting over the background and previous polygons with each closer object. This approach has two disadvantages: the time required to sort polygons in back-to-front order, and the possibility of errors in overlapping polygons. Fuchs and co-authors<ref name="fuchs80"/> showed that constructing a BSP tree solved both of these problems by providing a rapid method of sorting polygons with respect to a given viewpoint (linear in the number of polygons in the scene) and by subdividing overlapping polygons to avoid errors that can occur with the painter's algorithm. A disadvantage of binary space partitioning is that generating a BSP tree can be time-consuming. Typically, it is therefore performed once on static geometry, as a pre-calculation step, prior to rendering or other real-time operations on a scene. The expense of constructing a BSP tree makes it difficult and inefficient to directly implement moving objects into a tree.