Binary Space Partitioning

The term Binary Space Partitioning ( BSP; binary space partitioning German ) refers to a technique for partitioning multidimensional data by a set of hyperplanes. The data structure so created is a binary tree and is called a BSP tree.

Probably the most common application of BSP trees is the spatial subdivision of geometric objects. BSP is mainly used in graphics engines of computer games (especially in FPS games ) for objects or parts of the "world", the geometrically not change during the game. Another application can be found by raytracing.

A special case of BSP trees are kd - trees, often referred to as axis -aligned BSP tree ( axis-aligned BSP trees). In the kd - tree partitioning hyperplanes are always aligned along the axes of the coordinate system.

Method

When GNP of the entire space is initially divided by a (initially arbitrarily selectable ) plane of division into two parts. Both the half-spaces is then made the same as with the entire first area, that is, the world is divided recursively continues. Each inner node of the binary tree thus represents a parting plane, while the two sub- trees of a node then each representing an inner subspace. The end of the partition is generally achieved when only one data element of the original amount (e.g., a basic geometric object such as a triangle, or polygon) is present in a partial space.

The division planes fall out of practical reasons, often together with the polygons of the geometric objects. When you create the BSP tree is a polygon from the current subspace is chosen, with the plane of the sub space is further divided. In this case, care is taken that approximately the same number of polygons on each side of the selected level, on the other hand, that as few polygons of the subspace are cut by the plane, because the cutting leads to more polygons, which increases the time needed to for example, to draw the polygons.

The data of the output quantity can either be stored only in the leaves of the tree, or both in the leaves and in the internal nodes - for example, by the polygon was used to divide, is added to one of the two resulting subspaces or directly on the same data item as the level is stored. This is called the BSP tree then leaf -based ( "Sheet Based " ) or node- based ( " node based ").

Applications and alternatives

By the BSP technology, many calculations, such as collision detection or masking calculation of polygons faster too. Examples of the use of Binary Space Partitioning in computer games are the game engines of Doom (it is two-dimensional BSP, ie the division planes are actually dividing line), the Quake series and Doom 3

Raytracing BSP trees are used as an acceleration technique for performing an intersection test with only a minimum number of primitives.

Other methods for hierarchical subdivision of space are quadtrees and octrees.

Example 1

Building the tree

The picture above shows an example of the decomposition of a room with four routes can be seen. In the red box you can see the resulting binary tree.

First line divides the space into two one half-spaces (indicated by the blue dashed line) and the distance 2 in the two sections 2a and 2b. The orientation of the normal of the routes classified the two half-spaces now as a half space in front of the line and a half-space behind it. Consequently, the ( partial) lines which are located in front of the left, those who are behind it, inserted in the right subtree of the tree and continued with the two resulting half-spaces.

Considering first the route 2b so shares this space again in two half-spaces before line 1 However, there is no more distance in the same half space in front of her ( route 4 was " banned " by the decomposition of line 1 in the area behind section 1 ). Behind Route 2b is the same argument also nothing that would have to be placed in the tree and the procedure scheduled for this subtree.

Distance 2a, however, divides the space into two subspaces and re- route 4 is in the half-space before, section 3 belongs to the half-space behind it.

The lines 3 and 4 divide the space while again in each case again two half- spaces, but add nothing to the tree, so that the tree is created in the red box.

Pass the tree

Referring now to the viewer at the point where there is the box with the BSP tree ( the viewing direction is not important here ), then the throughput and thus drawing order of the lines is given as follows:

Starting from the root (node ​​1 ), first the nodes that are seen by the viewer from behind this line, drawn, then the track itself and then the routes, mainly the track - ie on the side of the observer - are.

In this case provides the passage of the tree as follows:

3, 2a, 4, 1, 2b First you enter the tree through the roots (1). Well you first need to draw all the lines behind the track 1 and so enters the right subtree and ends up at the root of 2a. Now you must also run only the nodes draw behind this root and rises again in the right subtree and ends at node 3 This is a sheet and can be issued immediately. Then route 2a is drawn and then the node before - so 4 Well, this part of the tree is processed and finally draws the node 1 and 2b.

Example 2

In computer graphics, the BSP tree is often used to store information about the geometry of an object. Such BSP trees are sometimes referred to as leaf - Storing BSP trees, because the information is primarily stored in the leaves.