Binary space partitioning

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

Binary space partitioning was developed in the context of 3D computer graphics in 1969. The structure of a BSP tree is useful in rendering because it can efficiently give spatial information about the objects in a scene, such as objects being ordered from front-to-back with respect to a viewer at a given location .

Other applications of BSP include: performing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in robotics and 3D video games, ray tracing, virtual landscape simulation, and other applications that involve the handling of complex spatial scenes.

In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representation of objects within the space in the form of a tree data structure known as a BSP tree.

Binary space partitioning was developed in the context of 3D computer graphics in 1969. The structure of a BSP tree is useful in rendering because it can efficiently give spatial information about the objects in a scene, such as objects being ordered from front-to-back with respect to a viewer at a given location .

Other applications of BSP include: performing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in robotics and 3D video games, ray tracing, virtual landscape simulation, and other applications that involve the handling of complex spatial scenes.

Overview

for a 2D index Binary space partitioning is a generic process of recursively dividing a scene into two using hyperplanes until the partitioning satisfies one or more requirements. It can be seen as a generalization of other spatial tree structures such as k-d trees and quadtrees, 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 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 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 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.

Generation

The canonical use of a BSP tree is for rendering polygons (that are double-sided, that is, without back-face culling) with the painter's algorithm. Each polygon is designated with a front side and a backside which could be chosen arbitrarily and only affects the structure of the tree but not the required result.

Such a tree is constructed from an unsorted list of all the polygons in a scene. The recursive algorithm for construction of a BSP tree from that list of polygons is: Choose a polygon P from the list. Make a node N in the BSP tree, and add P to the list of polygons at that node.

For each other polygon in the list: If that polygon is wholly in front of the plane containing P, move that polygon to the list of nodes in front of P. If that polygon is wholly behind the plane containing P, move that polygon to the list of nodes behind P. If that polygon is intersected by the plane containing P, split it into two polygons and move them to the respective lists of polygons behind and in front of P. If that polygon lies in the plane containing P, add it to the list of polygons at node N. Apply this algorithm to the list of polygons in front of P. Apply this algorithm to the list of polygons behind P. The following diagram illustrates the use of this algorithm in converting a list of lines or polygons into a BSP tree. At each of the eight steps (i.-viii.), the algorithm above is applied to a list of lines, and one new node is added to the tree.

The final number of polygons or lines in a tree is often larger (sometimes much larger ) than the original list, since lines or polygons that cross the partitioning plane must be split into two. It is desirable to minimize this increase, but also to maintain reasonable balance in the final tree.

The choice of which polygon or line is used as a partitioning plane (in step 1 of the algorithm) is therefore important in creating an efficient BSP tree.

Traversal

A BSP tree is traversed in a linear time, in an order determined by the particular function of the tree. Again using the example of rendering double-sided polygons using the painter's algorithm, to draw a polygon P correctly requires that all polygons behind the plane P lies in must be drawn first, then polygon P, then finally the polygons in front of P. If this drawing order is satisfied for all polygons in a scene, then the entire scene renders in the correct order.

This procedure can be implemented by recursively traversing a BSP tree using the following algorithm. From a given viewing location V, to render a BSP tree, If the current node is a leaf node, render the polygons at the current node.

Otherwise, if the viewing location V is in front of the current node: Render the child BSP tree containing polygons behind the current node Render the polygons at the current node Render the child BSP tree containing polygons in front of the current node Otherwise, if the viewing location V is behind the current node: Render the child BSP tree containing polygons in front of the current node Render the polygons at the current node Render the child BSP tree containing polygons behind the current node Otherwise, the viewing location V must be exactly on the plane associated with the current node. Then: Render the child BSP tree containing polygons in front of the current node Render the child BSP tree containing polygons behind the current node Applying this algorithm recursively to the BSP tree generated above results in the following steps: The algorithm is first applied to the root node of the tree, node A. V is in front of node A, so we apply the algorithm first to the child BSP tree containing polygons behind A This tree has root node B1.

V is behind B1 so first, we apply the algorithm to the child BSP tree containing polygons in front of B1: This tree is just the leaf node D1, so the polygon D1 is rendered. We then render the polygon B1. We then apply the algorithm to the child BSP tree containing polygons behind B1: This tree is just the leaf node C1, so the polygon C1 is rendered.

We then draw the polygons of A We then apply the algorithm to the child BSP tree containing polygons in front of A This tree has root node B2. V is behind B2 so first, we apply the algorithm to the child BSP tree containing polygons in front of B2: This tree is just the leaf node D2, so the polygon D2 is rendered. We then render the polygon B2.

We then apply the algorithm to the child BSP tree containing polygons behind B2: This tree has root node C2. V is in front of C2 so first, we would apply the algorithm to the child BSP tree containing polygons behind C2. There is no such tree, however, so we continue.

We render the polygon C2. We apply the algorithm to the child BSP tree containing polygons in front of C2 This tree is just the leaf node D3, so the polygon D3 is rendered. The tree is traversed in linear time and renders the polygons in a far-to-near ordering (D1, B1, C1, A, D2, B2, C2, D3) suitable for the painter's algorithm.

Application

BSP trees are often used by 3D video games, particularly first-person shooters and those with indoor environments. Game engines using BSP trees include the Doom, Quake, GoldSrc and Source engines. In them, BSP trees containing the static geometry of a scene are often used together with a Z-buffer, to correctly merge movable objects such as doors and characters onto the background scene.

While binary space partitioning provides a convenient way to store and retrieve spatial information about polygons in a scene, it does not solve the problem of visible-surface determination. BSP trees have also been applied to image compression.

See also

Chazelle polyhedron k-d tree Octree Quadtree Hierarchical clustering, an alternative way to divide 3D model data for efficient rendering. Guillotine cutting

Additional references

https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract Describes a randomized Painter's Algorithm..

BSP trees presentation Another BSP trees presentation A Java applet that demonstrates the process of tree generation A Master Thesis about BSP generating BSP Trees: Theory and Implementation BSP in 3D space Graphics Gems V: A Walk through BSP Trees

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376644029 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

11 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.