
related topics 
{math, number, function} 
{@card@, make, design} 
{system, computer, user} 
{area, part, region} 
{film, series, show} 
{line, north, south} 
{game, team, player} 
{church, century, christian} 

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 rendering efficiency by precomputing the BSP tree prior to lowlevel rendering operations. 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.
Contents
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 is the painter's algorithm: draw it from back to front painting over the background 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.
Zbuffering 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 Zbuffer and eliminate the need to sort the objects; as a simple tree traversal will yield them in the correct order. It also serves as a basis for other algorithms, such as visibility lists, which attempt to reduce overdraw.
The downside is the requirement for a time consuming preprocessing 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 Zbuffer, and using the Zbuffer to correctly merge movable objects such as doors and characters onto the background scene.
BSP trees are often used by 3D computer games, particularly firstperson shooters and those with indoor environments. Probably the earliest game to use a BSP data structure was Doom (see Doom engine for an indepth look at Doom's BSP implementation). Other uses include ray tracing and collision detection.
Full article ▸


related documents 
Cyclone (programming language) 
Commutator 
Banach algebra 
Möbius function 
Elementary function 
Squarefree integer 
Dimension (vector space) 
PreAbelian category 
HMAC 
String searching algorithm 
Bounded set 
Fermat's little theorem 
Principal ideal domain 
Tuple 
Enriched category 
Transfinite induction 
Multiplication table 
Infimum 
Linear classifier 
Homomorphism 
Caesar cipher 
Floor and ceiling functions 
Division ring 
Semicontinuity 
Loss of significance 
Pseudocode 
Twin prime 
Counting sort 
Ternary numeral system 
Cofinality 
