BSP trees

Here is some code that draws all the polygons in a BSP tree. I know that for the most part BSP trees are no longer used for depth sorting but I am really just experimenting to make sure I fully understand them. I am assuming that all polygons have only 2 Dimensions so when the scene is viewed from above all the polygons look like lines (so they are all perpendicular to the XZ plane).

struct BSP_Node
{
float A,B,C,D; //the plane of that polygon
char name;
BSP_Node *front_pointer;
BSP_Node *back_pointer;
};

BSP_Node *pointers[num_BSP_nodes];

void process_BSP_Node(BSP_Node cur)
{
if (cur->A
camera.xPos + cur->Bcamera.yPos + cur->Ccamera.zPos > cur->D)
{
if (cur->back_pointer != NULL) process_BSP_Node(cur->back_pointer);
display_polygon(cur->name);
if (cur->front_pointer != NULL) process_BSP_Node(cur->front_pointer);
}
else
{
if (cur->front_pointer != NULL) process_BSP_Node(cur->front_pointer);
display_polygon(cur->name);
if (cur->back_pointer != NULL) process_BSP_Node(cur->back_pointer);
}
}

As you can see the array *pointers[] holds all the BSP_Nodes. pointers[0] is the root node for the entire tree and it is the variable that is passed into the function to draw the scene.

My question is this: What if the camera’s viewpoint is on a polygon/plane instead of in front or in back? I am guessing that in that case you could go either way. So the above function should handle that case right?

Other than that can any one give a brief overview of the other uses for a BSP tree? I have heard collision detection, in order drawing of polygons, culling of large amounts of scenery. What else can they be used for? Also, would the above function handle ‘3D’ scenes also where the polygons are not all straight up and down? I think it would but creating the BSP tree would be more complex.

I thought about it and I guess that I should change :

else
{
if (cur->front_pointer != NULL) process_BSP_Node(cur->front_pointer);
display_polygon(cur->name);
if (cur->back_pointer != NULL) process_BSP_Node(cur->back_pointer);
}

TO:

else
{
if (cur->front_pointer != NULL) process_BSP_Node(cur->front_pointer);

if (cur->back_pointer != NULL) process_BSP_Node(cur->back_pointer);
}

because if the viewpoint is on the backside of the polygon then we don’t need to draw it (this is assuming we are culling the backface of the polygon). This is cool to me because it means I could turn off backface culling AND depth testing! Is that cool or what or am I just a big dork?

Yeah, that sould work. You could just accept the positive side as being anything >= 0. Like,

if( distance >= 0 ) {go down front side}
else { go down back side }

Just be consistent and include >= 0 wherever there are side tests.

The skip of the draw will work as long as all the polygons on node face the same direction – the same as the node’s plane. This isn’t necessarily the case, it depends on how you structure your tree. In any case, you need to visit all the nodes, unless you determine the bounds to be outside the view frustum, in which case you can stop (easy way to cull huge chunks of your tree).

As for uses, there are too many to mention.

  1. CSG
  2. Depth sorting
  3. Visibility
  4. Collision
  5. Path finding
  6. Others…

For any non-trivial world, you need some king of structure to optimize searches. This is one of the best. There are other trees (Quad, Oct, and so on), but none match the 3D polygon world quite like a BSP.

By the way, moving from 2D to 3D is a snap, nothing to it at all. If you’re already using 3D planes, you’re already there.

Ax + By + Cz > D has:
3 multiplies
2 additions
one comparison

Ax + By + Cz + D > 0 has
3 multiplies
3 additions
one comparison

At first I thought, why use the extra addition if it is not necesary? But now that I think about it there are probably reasons why you would want to use Ax + By + Cz + D. For instance collision detection. If you test the above equation using the camera’s coordinates you know how far away you are from the plane and if it bellow a thresh-hold (say the distance is .5 but the camera has a bounding sphere with radius of one) then you know you have to test further for collision. And if you have other characters running around the scene you can just use their coordinates to test if they collide with anything.

Exactly. For collision detection, and most everything else, the distance to plane is what you’re interested in, so that works great.

For colliding spheres, a staightforward distance test is usually enough. But for collision in a BSP, unfortunately, it’s not that simple. Well, I should say that it depends on the tree, but any non-convex geometry will generally require different techniques.

A common approach is “plane-shifting”, whereby each plane is “shifted”, or translated along the normal, by some predetermined distance, usually a function of the size of the colliding object. Some older implementations actually precompute this expanded hull and store it as a separate tree. This has many problems though, especially if you have actors of many different sizes.

Another approach is to perform this shifting on-the-fly, by dynamically shifting each relevant plane as it’s encountered. The shift distance can be made to deal with various shapes, such as boxes, cylinders, and spheres.

For either approach to work, in general, the BSP needs to be processed so that adjacent leaves in the tree don’t interfere with each other. This process is sometimes called “beveling”. There was a paper sometime ago that described this process in detail. Try a google for “melax demo”, or something like that.

Also, it’s not strictly necessary to do the beveling in the tree. Alternatively, you could bevel the individual polyhedrons that constitute the convex hull of each leaf, and collide them individually at runtime. This makes life very simple indeed, and it can handle actors of any size.

Have a peek at this for a quick overview of some the various techniques out there:
http://www.faqs.org/faqs/graphics/bsptree-faq/