BSP tree construction

From CGAFaq

Contents 1 Overview 2 Choosing the partition plane 3 Partitioning polygons 4 When to stop 5 Pseudo C++ code example

Overview

Given a set of polygons in three dimensional space, we want to build a BSP tree which contains all of the polygons. For now, we will ignore the question of how the resulting tree is going to be used.

The algorithm to build a BSP tree is very simple:

1. Select a partition plane.
2. Partition the set of polygons with the plane.
3. Recurse with each of the two new sets.

Choosing the partition plane

The choice of partition plane depends on how the tree will be used, and what sort of efficiency criteria you have for the construction. For some purposes, it is appropriate to choose the partition plane from the input set of polygons (called an autopartition). Other applications may benefit more from axis aligned orthogonal partitions.

In any case, you want to evaluate how your choice will affect the results. It is desirable to have a balanced tree, where each leaf contains roughly the same number of polygons. However, there is some cost in achieving this. If a polygon happens to span the partition plane, it will be split into two or more pieces. A poor choice of the partition plane can result in many such splits, and a marked increase in the number of polygons. Usually there will be some trade off between a well balanced tree and a large number of splits.

Partitioning polygons

Partitioning a set of polygons with a plane is done by classifying each member of the set with respect to the plane. If a polygon lies entirely to one side or the other of the plane, then it is not modified, and is added to the partition set for the side that it is on. If a polygon spans the plane, it is split into two or more pieces and the resulting parts are added to the sets associated with either side as appropriate.

When to stop

The decision to terminate tree construction is, again, a matter of the specific application. Some methods terminate when the number of polygons in a leaf node is below a maximum value. Other methods continue until every polygon is placed in an internal node. Another criteria is a maximum tree depth.

Pseudo C++ code example

Here is an example of how you might code a BSP tree:

 struct  BSP_tree
 {
    planepartition;
    list polygons;
    BSP_tree  *front, *back;
 };

This structure definition will be used for all subsequent example code. It stores pointers to its children, the partitioning plane for the node, and a list of polygons coincident with the partition plane. For this example, there will always be at least one polygon in the coincident list: the polygon used to determine the partition plane. A constructor method for this structure should initialize the child pointers to NULL.

 void    Build_BSP_Tree (BSP_tree *tree, list polygons)
 {
    polygon   *root = polygons.Get_From_List ();
    tree->partition = root->Get_Plane ();
    tree->polygons.Add_To_List (root);
    list front_list, back_list;
    polygon   *poly;
    while ((poly = polygons.Get_From_List ()) != 0)
    {
      int result = tree->partition.Classify_Polygon (poly);
      switch (result)
      {
      case COINCIDENT:
          tree->polygons.Add_To_List (poly);
          break;
      case IN_BACK_OF:
          back_list.Add_To_List (poly);
          break;
      case IN_FRONT_OF:
          front_list.Add_To_List (poly);
          break;
      case SPANNING:
          polygon   *front_piece, *back_piece;
          Split_Polygon (poly, tree->partition, front_piece, back_piece);
          back_list.Add_To_List (back_piece);
          front_list.Add_To_List (front_piece);
          break;
      }
  }
  if ( ! front_list.Is_Empty_List ())
  {
      tree->front = new BSP_tree;
      Build_BSP_Tree (tree->front, front_list);
  }
  if ( ! back_list.Is_Empty_List ())
  {
      tree->back = new BSP_tree;
      Build_BSP_Tree (tree->back, back_list);
  }
}

This routine recursively constructs a BSP tree using the above definition. It takes the first polygon from the input list and uses it to partition the remainder of the set. The routine then calls itself recursively with each of the two partitions. This implementation assumes that all of the input polygons are convex.

One obvious improvement to this example is to choose the partitioning plane more intelligently. This issue is addressed separately in the page, How can you make a BSP Tree more efficient?.

Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.