Binary Space Partitioning Tree

Binary Space Partitioning Tree

A Binary Space Partitioning Tree (BSP Tree) is a very complex, and very effective method to render indoor environments/scenes in a 3d game. It is used to create effective Depth Testing. Depth Testing is a method that determines which objects in a scene are furthest from the camera. After which, it will draw the polygons in the order of furthest to closest, so that you see everything correctly.

Consider this drawing. As you can see, the white polygon covers the yellow polygon in Removal B, and the yellow polygon covers the white polygon in Removal A. Without Depth Testing, we may see the yellow polygon on top of the white polygon at Removal A and Removal B, despite the fact that at Removal B the yellow polygon is behind the white one. Obviously Depth Testing is a requirement.

OpenGL, the 3d library I use to render polygons, does provide Depth Testing automatically, but it is slow, and a slow program is a bad program. That is why we use a BSP Tree. A BSP Tree sorts the polygons into a tree of nodes quickly and efficiently at loadup, so then we can easily know which polygons are furthest from the camera at run-time.

In this scene, the yellow letters represent walls, the pink lines represent the position of the camera, and the dotted lines represent the camera's view area.

This scene is obviously going to need Depth Testing. Without it, A and E could end up covering D, B, and/or E, which is not acceptable. We are going to need to make a BSP Tree. The BSP Tree will accomplish the following tasks when being built:

1) Choose a polygon from the polygons passed to the function
2) Turn that polygon into a plane
3) Classify all of the polygons passed to the function as In Front Of, Behind, Coincident With, or Spanning the plane
4) Split any polygons that Span the plane
5) If there are any polygons In Front Of the plane, go to step one passing those front polygons
6) If there are any polygons Behind the plane, go to step one passing those polygons
7) Add any Coincident polygons to the current node's list

This may be hard to grasp at first, so let's go through each step. Notice that this function is passed a list of polygons. When you want to build the polygon, you pass all of the polygons to this function.

In step one, we choose a polygon (either based on an algorithm or randomly) to act as a partition.

In this example, we choose polygon B. In step two, we turn that polygon into a plane. Notice that a plane extends in 2 directions infinitely.

Now we have a plane B. Now, in step 3, we must classify all of the polygons. In the following illustration, a yellow polygon is Behind, a purple polygon In Front Of, an green polygon is Spanning, and a blue polygon is Coincident to the plane.

We classify each polygon by going through each point and use the Planar Equation to get the distance from the plane. Then, based on the distances, we classify the polygon.

Step 4 requires us to Split any spanning polygons. Once we have finished splitting, we should look like the following:

Almost there, just a few more steps. Steps 5 and 6 require us to go to step one passing the polygons In Front Of and Behind our plane. This technique (calling a function inside of itself) is called recursion. Naturally, we only execute steps 5 and 6 if there are polygons In Front Of or Behind our partition. If we always executed those steps, we would never quit building nodes. The final step adds any coincident polygons to its (the current node's) personal polygon list.

Congratulations, we have just made our first split. Right now our tree looks like the following:

 Node 1 (Partition B): B | Back: Cb, A, Fb---------Front: Ca, G, D, E, Fa

Good, but we need more splitting. Let's get another partition in our front polygons.

This time we are going to use D as our partition. After classifying and splitting we have the following:

With that, our BSP Tree now looks like this:

 Node 1 (Partition B): B | Back: Cb, A, Fb---------Front (Partition D): D | Back: Ca,Gb---Front: Ga,E,Fa

We would continue to partition our level until our list looked like the following:

 Node 1: B | Back: A----------------Front: D | | Front: Cb Back: Ca--------Front: E | | | Front: Fb Front: Gb Back: Gaa---Front: Gab | Front: Fa

All partitioned! We have a total of 11 nodes, each branching off of a parent node.

Now this is all amazing, but what good is this? I mean, really, this doesn't do much beside split a few polygons. Well, all that is for when we render at run-time.

When we are rendering, we compare position Camera to each and every plane, and draw our nodes in order based on the distances. We start with our base node, B, and will execute the following steps:

1) Find the distance of position Camera from our plane<br>
2) If the distance is greater than 0:
   a.  Go to step one with our Back node
   b.  Draw our node's polygons
   c.  Go to step one with our Front node
3) If step 2 is false:
   a.  Go to step one with our Front node
   b.  Draw our node's polygons
   c.  Go to step one with our Back node

And that is it! So based on where position Camera is, we would be drawing the nodes in the following order:

Node A, Node Cb, Node Fb, Base Node, Node Fa, Node Gab, Node Gaa, Node E, Node Gb, Node Ca, Node D

Paul Frazee (The Rainmaker)


HOME TWITTER FACEBOOK RSS ATOM FORUM
Binary Space Partitioning Tree Binary Space Partitioning Tree A Binary Space Partitioning Tree (BSP Tree) is a very complex, and very effective method to render indoor environments/scenes in a 3d game. It is used to create effective Depth Testing. Depth Testing is a method that determines which objects in a scene are furthest from the camera. After which, it will draw the polygons in the order of furthest to closest, so that you see everything correctly. Consider this drawing. As you can see, the white polygon covers the yellow polygon in Removal B, and the yellow polygon covers the white polygon in Removal A. Without Depth Testing, we may see the yellow polygon on top of the white polygon at Removal A and Removal B, despite the fact that at Removal B the yellow polygon is behind the white one. Obviously Depth Testing is a requirement. OpenGL, the 3d library I use to render polygons, does provide Depth Testing automatically, but it is slow, and a slow program is a bad program. That is why we use a BSP Tree. A BSP Tree sorts the polygons into a tree of nodes quickly and efficiently at loadup, so then we can easily know which polygons are furthest from the camera at run-time. In this scene, the yellow letters represent walls, the pink lines represent the position of the camera, and the dotted lines represent the camera's view area. This scene is obviously going to need Depth Testing. Without it, A and E could end up covering D, B, and/or E, which is not acceptable. We are going to need to make a BSP Tree. The BSP Tree will accomplish the following tasks when being built: 1) Choose a polygon from the polygons passed to the function 2) Turn that polygon into a plane 3) Classify all of the polygons passed to the function as In Front Of, Behind, Coincident With, or Spanning the plane 4) Split any polygons that Span the plane 5) If there are any polygons In Front Of the plane, go to step one passing those front polygons 6) If there are any polygons Behind the plane, go to step one passing those polygons 7) Add any Coincident polygons to the current node's list This may be hard to grasp at first, so let's go through each step. Notice that this function is passed a list of polygons. When you want to build the polygon, you pass all of the polygons to this function. In step one, we choose a polygon (either based on an algorithm or randomly) to act as a partition. In this example, we choose polygon B. In step two, we turn that polygon into a plane. Notice that a plane extends in 2 directions infinitely. Now we have a plane B. Now, in step 3, we must classify all of the polygons. In the following illustration, a yellow polygon is Behind, a purple polygon In Front Of, an green polygon is Spanning, and a blue polygon is Coincident to the plane. We classify each polygon by going through each point and use the Planar Equation to get the distance from the plane. Then, based on the distances, we classify the polygon. Step 4 requires us to Split any spanning polygons. Once we have finished splitting, we should look like the following: Almost there, just a few more steps. Steps 5 and 6 require us to go to step one passing the polygons In Front Of and Behind our plane. This technique (calling a function inside of itself) is called recursion. Naturally, we only execute steps 5 and 6 if there are polygons In Front Of or Behind our partition. If we always executed those steps, we would never quit building nodes. The final step adds any coincident polygons to its (the current node's) personal polygon list. Congratulations, we have just made our first split. Right now our tree looks like the following: Node 1 (Partition B): B \| Back: Cb, A, Fb---------Front: Ca, G, D, E, Fa Good, but we need more splitting. Let's get another partition in our front polygons. This time we are going to use D as our partition. After classifying and splitting we have the following: With that, our BSP Tree now looks like this: Node 1 (Partition B): B \| Back: Cb, A, Fb---------Front (Partition D): D \| Back: Ca,Gb---Front: Ga,E,Fa We would continue to partition our level until our list looked like the following: Node 1: B \| Back: A----------------Front: D \| \| Front: Cb Back: Ca--------Front: E \| \| \| Front: Fb Front: Gb Back: Gaa---Front: Gab \| Front: Fa All partitioned! We have a total of 11 nodes, each branching off of a parent node. Now this is all amazing, but what good is this? I mean, really, this doesn't do much beside split a few polygons. Well, all that is for when we render at run-time. When we are rendering, we compare position Camera to each and every plane, and draw our nodes in order based on the distances. We start with our base node, B, and will execute the following steps: 1) Find the distance of position Camera from our plane<br> 2) If the distance is greater than 0: a. Go to step one with our Back node b. Draw our node's polygons c. Go to step one with our Front node 3) If step 2 is false: a. Go to step one with our Front node b. Draw our node's polygons c. Go to step one with our Back node And that is it! So based on where position Camera is, we would be drawing the nodes in the following order: Node A, Node Cb, Node Fb, Base Node, Node Fa, Node Gab, Node Gaa, Node E, Node Gb, Node Ca, Node D Paul Frazee (The Rainmaker)