Last Updated January 8, 2014
A binary space partioning tree, as the name suggests divides each region of space into two sub regions, but the most important difference between BSP trees and Octrees, is that while octrees use a planes on regular grid to determine subdivision, BSP trees can use planes of any orientation and normally the planes used are defined by the faces in the scene. This kind of scheme is often called adaptive partitioning as the partitioning adapts to the actual distribution of objects rather than a regular grid.
A plane divides space in to two regions, technically one of these regions is positive (above the plane) and the other is negative (below the plane). To create a BSP tree, we will use planes to successively divide space.
First choose a plane A to divide space (we will examine strategies later for how to choose A and other planes). A will be the root of our tree and will have two branches representing the positive half-space and the negative half-space. Any objects in the positive half space will ultimately end up in the right half of the tree and objects in the negative half-space will end up in the left half of the tree.
This process continues recursively. we choose a plane B to subdivide the negative half space, B becomes the root of a A's left sub-tree. We also choose a plane C to subdivide the positive half-space.
This process continues until a half space contains only one object and the object becomes a leaf of the tree.
Having constructed a tree (usually a once off operation, done at the build stage), we can now construct a visibility ordering (order all the objects in the scene from nearest to the camera to furthest).
Find the node corresponding to the position of the camera, that object is 'closest' to the camera, the next closest object is the node's sibling, to retrieve the remaining nodes, we must ascend to the next level and traverse the remaining nodes.
In this case 'closest' means that there can be no intervening objects.
Check Out this BSP applet
To generate a visibility order from the BSP tree, follow these steps;
This produces a near to far ordering, but swapping steps 3 & 5 will produce a far to near ordering.
drawbsptree(node){
if(plane intersects viewvolume){
if(distanceA is positive){ // distance from the VP to the plane
drawbsptree(node.right)
render(node.face)
drawbsptree(node.left)
}
else{//distanceA is negative
drawbsptree(node.left)
render(node.face)
drawbsptree(node.right)
}
}
else
//current plane outside viewvolume
//therfore everthing on the far side is not visible
// so need only traverse one subtree
{
if(distanceA<0)
drawbsptree(node.left)
else
drawbsptree(node.right)
render(node.face)
}
}
Early rendering methods used the Painters algorithm to draw visible polygons. Polygons painted in far-to-near ordering. The nearer face simply drawn over the further faces. This is inefficient as rendered polygons are drawn over and the effort to calculate the lighting was wasted.
A more efficient way is to draw the faces is near-to-far, but obviously we need some way to mark which pixels have been written to. To do this we maintain a stencil buffer which records which pixels have been draw and which have not. Drawing can stop when all the pixels in the stencil buffer have been painted.
Use of the BSP tree solves another problem associated with the simple painters algorithm which does not work for intersecting polygons. BSP splits these polygons, which removes the problem.
However transparency effects are much easier to implement with a far-to-near ordering.
Choosing appropriate separating planes can be a difficult problem, and for a scene with n objects we need to choose from n2 planes. For a polygon based scene we can choose our partioning planes containing face polygons. Is is likely that some partioning planes will intersect face polygons. In this case the face will have to be split into two constituents.
The approach to building this tree is recursive;
Determineing whether a point is on the negative or positive side of the face, is a matter of evaluating the Cosine of angle between a vector from the point to the plane and the plane normal, q is a point on the plane;
n.(p-q) =?
if this expression is less than zero, the angle between the vectors is greater than 90 degrees, therefore the point is 'behind', or 'inside' the plane. This expression can be further simplified;
n.(p-q) =n.p-n.q
n.q is constant for any plane, rewrite as 'd'
n.p-d=?
rewrite n=(a b c), and p=( x y z)
ax+by+cz-d=?
all points who evaluate this expression to zero lie on the plane;
ax+by+cz+d=0 ;point on plane
ax+by+cz+d<0 ;point below plane
ax+by+cz+d>0 ;point above plane
Backface culling can be performed at no cost during tree traversal. Whenever the viewpoint is in the negative half-space of a polygon, that polygon can be culled.
BSP can cull against the view frustum. A subtree can be culled in one operation if it can be show that the node plane does not intersect the view frustum, the the 'far' side of the plane will not be visible.
For a finite view frustum (i.e. one with a far plane), a far side BSP tree node can be culled(and all its sub trees) if all 5 points of the view frustum lie on the other side of the partition plane.
A BSP tree has two major attributes, which affect how well it performs is various application;
These factors have different importance depending on application.
For simple visible surface determination, every node is visited, so it is important to keep the size down. For collision detection, ray tracing or other processes which 'search' the tree, balance is the key of efficiency.
One method to control the size and shape is to choose a number of candidate polygons (~100) for each partition, and determining the number of splits required (within the same subspace) and the number of polygons on either side. A weighed sum of these measures is calculated for the candidates and the best one chosen. The weights will depend on the application.
For room type environments, it is best to use the walls/floors as partition faces before subdividing room interiors. A typical approach is to process the faces at the periphery first and work your way to the center. Larger polygons, representing walls are unlikely to intersect objects within a room.
For landscapes the terrain is normally build over a regular grid, in this case partitioning should be done on planes perpendicular to the ground plane and aligned with the x or y-axis.
Moving objects can disrupt the integrity of a BSP tree. A number of methods have been developed to deal with dynamic objects.
The most flexible system is to update the tree as object moves around. The basic approach is to 'delete' an object that has moved, and reinsert the object at its new position.
Insertion is relatively easy, just traverse the tree to find the leaf node 'nearest' to the object and stick the object there.
Deleting a node can result in three trees, merging the three trees can be difficult.
There are 3 types of node removal;
//Initial step: mark all polygons of moved object as "delete"
///////////////////////////////////////////////
Restore(tree){
if tree.empty retun null;
if (tree.root is not marked "delete"){
tree.left=Restore(tree.left) // tidy up left sub tree
tree.right=Restore(tree.right) // tidy up right sub tree
return tree;
}
else{// root is marked for deletion
if (only one child){
chlld= Restore(non-empty child)
replace this node with child
return child;
}
else{// two-non empty children
child=Restore(larger child)
replace this node with child
InsertPolygonsintotree(polygons of smaller tree, larger child)
return child
}
}
}
When a target object is moved, the restore function is only relevant for the first movement. After the object is deleted from the tree, its nodes are removed and reinserted, either as a leaf node or as a subtree of nodes shared with other polygons in the object. In this case only the simple (first type) of node removal is required. All further movements of the object will result in deletion of leaf nodes.
All objects that are likely to be moved should be inserted into the tree last of all.
An enhancement to this process would be to leave in place 'deleted' node whose sub trees are too large. Nodes with large sub trees are, by definition, not common. Leaving them in place (marked as deleted) would prevent having to re-process large subtrees.
© Ken Power 2011