Binary space partitioning
Binary Space Partitioning ( BSP ; German binary space partitioning or BSP tree) is a technique in computer science for partitioning multidimensional data through a set of hyperplanes . The data structure created in this way is a binary tree and is called a BSP tree.
The most widespread application of CLT trees is the spatial subdivision of geometric objects. BSP is mainly used in graphics engines for computer games for objects or parts of the "world" that no longer change geometrically during the game. Another application is in ray tracing .
A special case of BSP trees are k -d trees , often also referred to as axis-aligned BSP trees (axially parallel BSP trees). In the case of k d trees, the subdividing hyperplanes are always aligned along the axes of the coordinate system.
Procedure
With the CLT, the entire room is initially divided into two parts by a (initially freely selectable) partition level. The same thing is then done for both half-spaces as was done first with the entire space, that is, the world is recursively subdivided further and further. Each inner node of the binary tree thus represents a division level, while the two subtrees of an inner node then each represent a part of the space. The end of the subdivision is usually reached when only one data element of the initial set (e.g. a basic geometric object such as a triangle or polygon) is present in a subspace.
For practical reasons, the planes of division often coincide with the polygons of the geometric objects. When creating the BSP tree, a polygon is then selected from the current subspace, with the level of which the subspace is further subdivided. In doing so, it is ensured on the one hand that there are approximately the same number of polygons on each side of the selected level, on the other hand that as few polygons as possible in the sub-space are cut by the level, because cutting leads to more polygons, which increases the time required to z. B. draw the polygons. The aim when creating the BSP tree is to create a tree which has an optimal runtime behavior when it is later traversed. Usually an attempt is made to achieve this by creating a balanced tree .
The data of the initial set can either be stored exclusively in the leaves of the tree or both in the leaves and in the inner nodes - for example, by adding the polygon that was used for the division to one of the two subspaces created or directly in the same data element how the plane is saved. The BSP tree is then called leaf-based (" leaf-based ") or node-based ("node-based").
Applications and alternatives
With the BSP technology, many calculations, such as collision detection or the calculation of the occlusion of polygons, can be carried out much faster. Examples of the use of binary space partitioning in computer games are the game engines from Doom (this is a two-dimensional BSP, i.e. the partition planes are actually dividing lines), the Quake series, and Doom 3.
In ray tracing , BSP trees are used as an acceleration technique in order to only carry out an intersection test with as few primitives as possible .
Further methods of hierarchical subdivision of space are quadtrees and octrees .
example 1
Building the tree
Figure 1 shows an example of the decomposition of a room with four lines. In the red box you can see the resulting binary tree .
First divides route 1 the space into two half spaces (indicated by the dotted blue line) and the path 2 in the two sections 2a and 2b. The orientation of the normals of the routes now classifies the two half-spaces as a half-space in front of the route and a half-space behind it . As a result, the (partial) stretches that are in front of it are inserted into the left, those that are behind it are inserted into the right subtree of the tree and the two resulting half-spaces are continued.
If you first look at route 2b, it divides the space again into two half-spaces in front of route 1. However, there is no further route in the same half-space in front of it (route 4 was "banished" by splitting route 1 into the area behind route 1 ). With the same reasoning, there is also nothing behind segment 2b that would have to be classified in the tree and the procedure terminates for this subtree.
Line 2a, on the other hand, divides the space again into two sub-spaces and line 4 is placed in the half-space in front of it, line 3 in the half-space behind it.
Lines 3 and 4 divide the space again into two half-spaces, but do not add anything further to the tree, so that the tree was created in a reddish box.
Pass of the tree
If you now assume the viewer where the box with the CLT tree is (the direction of view is not important here), the sequence of the routes and thus the drawing sequence results as follows:
Starting from the root (node 1 ), first the nodes that lie behind this line as seen by the observer are drawn, then the line itself and then the lines that are in front of the line - i.e. on the observer's side.
In the present case, the tree's run looks like this:
3, 2a, 4, 1, 2b
First you enter the tree via the root ( 1 ). Now you first have to draw all the lines behind the line 1 and so go to the right subtree and land there at the root 2a . Now you first have to draw the nodes behind this root and then descend to the right subtree and land at node 3 . This is a sheet and can be issued immediately. Then line 2a is drawn and then the nodes in front of it - i.e. 4 . Now this subtree has also been processed and nodes 1 and 2b are finally drawn .
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 , since the information is primarily stored in the leaves. The illustration opposite describes the creation of such a tree. It should be noted that the normals of the edges (used for the assignment on the front or back) all point towards the interior of the object (room).
Building the tree
At the beginning, the object is subdivided at any edge, here edge D , and used as the root for the BSP tree. It should be noted that the selection of the starting edge is one of the decisive factors for the later traversing speed, which is much better with a balanced tree . Below all the remaining edges in front of and behind the node D divided area. For this decision, as here, the normal of the straight line is often taken, which points in the direction in front of the object . As already mentioned, all normals of the edges in this example point into the interior of the object. As can be seen in this first step, the edge A and the edge G are each divided into two parts, as these intersect with the edge D , which is extended to infinity . This gives the current tree:
D
/ \
A1,G2,H,I,J,K,L,M,N,O,P A2,B,C,E,F,G1
In the following, the subtrees are subdivided again. In the example of the sub-tree: . Edge N is selected and the remaining edges of the subtree are again divided into the front and back of edge N accordingly . In this step, too, edges (edge A 1 and edge K ) must be subdivided. The section A 1 of the edge A is again divided into two parts. This gives the current tree:
A1,G2,H,I,J,K,M,N,O,P
D
/ \
N A2,B,C,E,F,G1
/ \
A12,G2,H,I,J,K1 A11,K2,L,M,O,P
Using edge I , the left subtree is subdivided below node N according to the above scheme. This gives the following tree:
D
/ \
N A2,B,C,E,F,G1
/ \
I A11,K2,L,M,O,P
/ \
A12 G2,H,J,K1
Since the left subtree only consists of node A 12 , the left branch cannot be subdivided any further, so the right branch from node I is processed. Edge J is selected for the subdivision and the edges in this subspace are accordingly arranged again in the left and right subtree. This results in the following tree:
D
/ \
N A2,B,C,E,F,G1
/ \
I A11,K2,L,M,O,P
/ \
A12 J
/ \
K1 G2,H
Now that the left subtree has been completely processed under node J , the left subtree only consists of one node, here K 1 , the process continues with the right subtree. Edge H is chosen and the resulting tree looks like this:
D
/ \
N A2,B,C,E,F,G1
/ \
I A11,K2,L,M,O,P
/ \
A12 J
/ \
K1 H
/
G2
The procedure is identical for all further subtrees that have more than one child node. In the end, a possible solution for the BSP tree would be:
D
/ \
/ \
/ \
/ \
/ \
/ \
/ \
N E
/ \ / \
/ \ / \
/ \ / \
/ \ / \
I O F C
/ \ / \ / /
A12 J P L G1 B
/ \ / / /
K1 H A11 M A2
/ /
G2 K2
It should be noted that the previously created BSP tree is only one possible solution. Since an edge has to be chosen for the subdivision of the tree, starting with the edge for the root towards an edge for the subdivision of the children of each node, a variety of CLT trees can be constructed which correctly subdivide the space. Depending on the application, the performance in terms of traversing the various CLT trees can vary greatly. In most cases an attempt is made to avoid creating a degenerate tree.
See also
literature
- Henry Fuchs et al. a .: On Visible Surface Generation by A Priori Tree Structures. In SIGGRAPH '80 Proceedings, pp. 124-133. ACM, New York 1980, ISBN 0-89791-021-4
- Christer Ericson: Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) . Morgan Kaufmann Verlag , pp. 349-382, 2005, ISBN 1-55860-732-3
Web links
- BSP FAQ (English)
- Java applet for BSP