# 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