Trees in Games: Binary Space Partitioning Trees

Talking about data structures in game industry, we cannot ignore trees. For example, the Binary Space Partitioning (BSP) Tree is a very common data structure for processing three-dimensional virtual scenes, especially for rendering and collision detection. I have just learnt it from Data Structures and Algorithms for Game Developers by Allen Sherrod, and now it is a good time to write some notes as a review.

In a BSP tree, the child nodes are often called the front and back nodes instead of left and right, and I think this will help you understand ray tracing more easily. The main idea of BSP is choosing a plane, then recursively partition the scene (all polygons) into halves, until some condition is met, which could be a minimum number of polygons in a node, or a certain depth of levels.

The BSP tree is a binary search tree for polygons, and leaf nodes have no children but a list of polygons. Theoretically, the creation of a BSP tree is a generally simple process made up of the following steps:

  1. Set the polygon list to the node (root if this is the first node).
  2. Calculate a plane that will be used as the splitter plane.
  3. Loop through all polygons to choose side. If there is a polygon spans the splitter plane, split it into two new planes.
  4. Repeat steps 1 to 3 for the font and back notes recursively until the stop condition is met.

The pseudo code can look like this:

listOfPolygons = new PolygonList(...);
bspTree = CreateBSPNode(listOfPolygons);

CreateBSPNode(listOfPolygons)
{
    node = new BSPNode();

    // stop recursion if threshold is met
    if(listOfPolygon.count <= MIN_NODE_POLY_COUNT)
    {
        node.polygonList = listOfPolygons;
        return node;
    }
    // else continue
    splitPlane = GetBestSplitter(listOfPolygons);

    for each(element i in listOfPolygons)
    {
        if(splitPlane.Classify(listOfPolygons[i]) == FRONT)
        {
            // front polygons
            subPolyListFront.push(listOfPolygons[i]);
        }
        else if(splitPlane.Classify(listOfPolygons[i]) == BACK)
        {
            // back polygons
            subPolyListBack.push(listOfPolygons[i]);
        }
        else
        {
            // Return two split polygons in pf and pb
            splitPlane.ClipPolygon(listOfPolygons[i], &pf, &pb);
            subPolyListFront.push(pf);
            subPolyListBack.push(pb);
        }
    }

    node.frontNode = CreateBSPNode(subPolyListFront);
    node.backNode  = CreateBSPNode(subPolyListBack);

    return node;
}

One of the challenges of making a BSP tree is to pick up a good splitter plane. If the tree is severely unbalanced, performance traversing the tree can suffer. We may choose it by a simple scoring algorithm that performs these steps:

  1. Loop through all polygons and create a plane for each one.
  2. For every plane add up the number of polygons on each side.
  3. Whichever plane has the lowest absolute difference (Math.abs(frontTotal – backTotal) is the best splitting plane, also know as the score.

This is how to implement a BSP tree, I will take a further look on using it in some real conditions later.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s