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. Around 300 BC, the Greek mathematician Euclid laid down the rules of what has now come to be called Euclidean geometry, which is the study of the relationships between angles and distances in space. ... Look up Convex set in Wiktionary, the free dictionary. ... A hyperplane is a concept in geometry. ... In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ...

In simpler 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^o). For a more general description of space partitioning, see space partitioning. An angle is the figure formed by two rays sharing a common endpoint, called the vertex of the angle. ... In mathematics, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). ...

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. A 3D rendering with raytracing and ambient occlusion using Blender and Yafray 3D computer graphics are works of graphic art created with the aid of digital computers and 3D software. ... This article or section does not cite its references or sources. ... The light cycles from the movie Tron were constructed using Constructive Solid Geometry Constructive solid geometry (CSG) is a technique used in solid modeling. ... CAD is a TLA that may stand for: Cadiz Railroad (AAR reporting mark CAD) Canadian dollar – ISO 4217-code Capital Adequacy Directive Card Acceptance Device Children of the Anachronistic Dynasty Computer-aided design Computer-aided detection (medical) Computer-aided diagnosis (medical) Computer-assisted dispatch Computer-assisted drafting Coronary artery disease... In physical simulations, video games and computational geometry, collision detection includes algorithms from checking for intersection between two given solids, to calculating trajectories, impact times and impact points in a physical simulation. ... It has been suggested that this article or section be merged with robot. ... A computer game is a game composed of a computer-controlled virtual universe that players interact with in order to achieve a defined goal or set of goals. ...

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: 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. The painters algorithm is one of the simplest solutions to the visibility problem in 3D computer graphics. ...

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. Z-buffer data In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional (3-D) graphics, usually done in hardware, sometimes in software. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ...

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. A computer game is a game composed of a computer-controlled virtual universe that players interact with in order to achieve a defined goal or set of goals. ... This article or section does not cite its references or sources. ... Doom (or DOOM)[1] is a 1993 computer game by id Software that is among the landmark titles in the first-person shooter genre. ... Doom Engine is a psychedelic doom metal band based in Oxfordshire. ... A ray traced scene. ... In physical simulations, video games and computational geometry, collision detection includes algorithms from checking for intersection between two given solids, to calculating trajectories, impact times and impact points in a physical simulation. ...

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. A visual form of recursion known as the Droste effect. ... The painters algorithm is one of the simplest solutions to the visibility problem in 3D computer graphics. ...

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. Binary space partition illustration. ... Binary space partition illustration. ...

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. The Quadtree is a tree data structure in which each internal node has up to four children. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

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. A 3-dimensional kd-tree. ...

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.

• 1980 Fuchs 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.

• 1983 Fuchs 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.

For the Stargate SG-1 episode, see 1969 (Stargate SG-1). ... 1980 (MCMLXXX) was a leap year starting on Tuesday. ... 1983 (MCMLXXXIII) was a common year starting on Saturday of the Gregorian calendar. ... 1987 (MCMLXXXVII) was a common year starting on Thursday of the Gregorian calendar. ... 1990 (MCMXC) was a common year starting on Monday of the Gregorian calendar. ... 1991 (MCMXCI) was a common year starting on Tuesday of the Gregorian calendar. ... John D. Carmack II (born August 20, 1970) is a widely recognized figure in the video game industry. ... Doom (or DOOM)[1] is a 1993 computer game by id Software that is among the landmark titles in the first-person shooter genre. ... 1992 (MCMXCII) was a leap year starting on Wednesday. ...

References

[WINTER99] AN INVESTIGATION INTO REAL-TIME 3D POLYGON RENDERING USING BSP TREES. Andrew Steven Winter. April 1999. available online

[CHEN91] S. Chen and D. Gordon. “Front-to-Back Display of BSP Trees.” IEEE Computer Graphics & Algorithms, pp 79–85. September 1991.

[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.

See also

• Image:The Wotch My Sister, Myself BSP tree usage.png — How BSP trees are used in The Wotch: My Sister, Myself video game.

Image File history File links Size of this preview: 189 × 599 pixel Image in higher resolution (894 × 2831 pixel, file size: 533 KB, MIME type: image/png) A chart detailing how BSP trees are used in The Wotch: My Sister, Myself for collision detection and pathing. ...

External links

• The BSP FAQ
• BSP trees presentation
• Another BSP trees presentation (PDF)

• A Java applet which demonstrates the process of tree generation