BSP Trees

BSP

Binary Space Partition Trees use Half-Spaces to cut the space in half. This is applied recursively on the new branches. Each half space further sub-dividing the region in two.

In two dimensions the cutter is a line. Here is an example and the associated bsp tree.

If a line is visible to its parent line then the line appears on the rhs branch, else its on the left hand side branch.

The leafs are the regions.

Here I use points to construct the lines. An arbitrary point of the remaining points was chosen to create the next partitions. The remaining points were divided according to which side of the line the points was on. Quick Hull uses a similar partitioning strategy.

It is easy to test if a point is inside the region. Just follow the branch and if all the tests are satisfied then the point is in the region. The test is a dot product of the point with the line (translating both to the origin first) > 0.

Static Collision Detection

BSP trees can be used to handle collision detection between a free object and a static scene. For example a plane flying through the sky is the free object and the mountains and land are the static geometry.

The problem then is to cut the static geometry up into regions. Build the bsp tree as the regions. Then at run time query which region the free object is in, and test for collision between it and the static geometry in the region.

Looking at it from a abstract perspective the free object is a point, find which region the point is in. Since the free object may at times be across the region boundaries static objects geometry could be tested in neighboring regions too. There are other approaches to this too.

The animator usually increments the free objects position forward. If this results in a bad state, the action is reversed and some other situation is calculated. For example a ball bounces off a wall when collision occurs. Or for a character walking in a dungeon hitting a wall the command to go through the wall is ignored as it is impossible to do.

Complicated Static Geometry

In a job interview I was asked how I would reduce the triangle to triangle intersection of a free object (which itself comprises of many triangles) and the static scene which has hundreds of thousands of triangles.

In this case the free object was a plane which may crash into the ground. But a scientific application such as a grinding wheel being the free object grinding into a blank represented as thousands of tetrahedrons could also be another problem.

BSP trees may be part of a solution. The static geometry component can be chopped up into fragments (triangle or tetrahedrons), and then the free object is tested for collision against the fragments. It uses the bsp tree as a point test. From my perspective this is a research problem, and one that may not have simple answers.

Fragmenting geometry easy. Get the static objects in the scene, assume they do not collide. Randomly or otherwise cut the scene up into regions, cutting the geometry. Build the bsp tree.

This is quite involved, but should be general. For example given a scene put the geometry into the blender and out comes the bsp tree for the static geometry.

Point to Point Collision Detection

When several regions are crossed over, for example flying a plane then all these regions need to be tested.

Heres the theoretical answer. Pass a line down the half space bsp tree. If it intersects the current half space cut it up and recursively descend down each branch, else send it down the branch it is in.

The line has been cut up into pieces in each respective region. Now reform the line. Assuming endpoints were stored the line can be ordered and the regions list from start to finish determined.

In 3D this is a line and a plane intersection test. Clearly this generalizes to any dimension.

This is generalized for convex objects which for a linear move sweep out another convex object. Send this new convex object down the bsp tree - cutting it up as it descends. Or keep it as is and test for intersection with objects in the same region.

Indexed BSP Representation

The bsp data structure has to be represented somehow. I am a fan of indexed data structures as an index is literally a pointer to somewhere else where the object/data resides.

By having the index generic the bsp tree was written separate from a realization. For example the underlying bsp tree structure is used in both 2D and 3D half-space implementations. So a generalization was reached through separation.

Here are the properties I used for this.

All nodes are indexes.
Interior nodes are half-spaces.
The half-space is defined to see objects on its left branch.
Leafs have no branches (left and right are null).
Interior nodes have both branches not null.
0 is used to indicate no node.

By having the branches full (no interior node has a 0 branch) inserting a new node means creating new branches.

I also supplied transversal operators and a current state. Built query function on nodes. Built other iterators for example to transverse the leafs.

To represent the data structure for reading and writing (serialization) a list of ordered interior nodes is used. Four indexes and a boolean value are used to describe the position of an interior node in the tree.
node left right parent Is this on parents right branch?

The list is ordered so that new interior nodes refer only to nodes that are before them. This lets the tree be easily built.

Consider the following 2D example.

Visibility

This is one of the nicest properties of the bsp tree - given a point find all the regions back to front of the point. This can be done in O(n) time, from anywhere in the space.

The algorithm itself is so simple that it is often given as a single procedure, here is my version. The public version simply puts the root as the first node to transverse. An ordered list is built through vnds.

I assume nodes on the left are visible to the parent. The visibility test is the isInside function.

  void visibility
  ( 
    vector<INDX> & vnds, 
    PT const & p0 
  ) const;

private:

  /** The indexes are for nodes furthest to nearest point p0. */
  void visibility
  ( 
    vector<INDX> & vnds, 
    treeindexednode<INDX> const * nd,
    PT const & p0 
  ) const;

...

template< typename PT, typename PD, typename INDX >
void bsptreeD2<PT,PD,INDX>::visibility
( 
  vector<INDX> & vnds, 
  treeindexednode<INDX> const * nd,
  PT const & p0 
) const
{
  assert(nd!=0);

  // Is the node internal?
  if (nd->isleaf()==false)
  {
    halfspaceD2<PT,PD> const & h(vi[nd->index]);
    if (h.isInside(p0))
    {
      visibility(vnds,nd->right,p0);
      visibility(vnds,nd->left,p0);
    }
    else
    {
      visibility(vnds,nd->left,p0);
      visibility(vnds,nd->right,p0);
    }
  }
  else
    vnds.push_back(nd->index);
}

While people have correctly pointed out that the hardware-accelerated Z-buffers can correctly render a scene, this can not be done with transparencies, so bsp-trees still have a place.