BSP Trees: Theory and Implementation

BSP Trees: Theory and Implementation
Author: Samuel Ranta-Eskola
Description: This article offers a detailed explanation of Binary Space Partitioning (BSP) theory for real-time engines, along with various implementation details, complexity anaylsis, optimzations, and rendering.

Post your discussions/comments here by clicking on Add Reply.

nice article !
some constructive criticism though...
right at the beginning you say that the bsp tree isn't used anymore for depth sorting a scene. so it would have been nice if you would have written a little more in depth about the uses it has today. what i mean is that instead of only explaining how to construct and render a bsp tree you should have also mentioned how to construct a PVS or how to actually do colission detection with a bsp tree. maybe you could do a second part about that. that would be really cool since i like the style of your article very much

Thanks anubis for your comments.

I should have mentioned it before, but this is a 4-article series. The other articles will be:

1. Hidden Surface Removal
2. Radiosity
3. Physics in BSP Trees

That should hopefully answer your question


Thanks to the author for his valuable contribution.

oh, that clears it up... in that case ignore my comments =]
hm... i think we can soon start to open different sections for a few tutorial topics
at the beginning a seperation like gfx, audio, general might be sufficent

radiosity? iieehhk..

ugly

Hi everbody

I wrote this article about 2 years ago. At that stage I was a rookie gameprogammer. Thus there exist some minor mistakes and things that might look strange to the more experienced. There are also a few errors that has been pointed out to me, but they weren't to significant and I actually don't remember what they were

The best way to consider this article is as a guide to BSP-trees. Most of the thinking you will have to do yourselves. Some solutions are plain dumb and definetly need polishing.

If anybody has any questions you can post them here and I'll try to answer them as good as I can.

Thanks Samuel for this useful and excellent article! Can't wait for the next one

after reading the artical i have implemented the classify function as follows which classify a point against the plane passed

int My3DApplication::classifyPoint( D3DXVECTOR3 *pos, POLYGON *Plane )
{
D3DXVECTOR3 *vec1 = (D3DXVECTOR3 *)&Plane->VertexList[0];
D3DXVECTOR3 Direction = (*vec1) - (*pos);
float result = D3DXVec3Dot(&Direction,&Plane->Normal);

if( result < -0.001f )
return POINTPOSITION_FRONT;

if( result > 0.001f )
return POINTPOSITION_BACK;

return POINTPOSITION_ONPLANE;
}
but its not working

This thread is three years old. Please start a new thread.

Originally Posted by Reedbeta

This thread is three years old. Please start a new thread.

The article links to this thread though.

hi there seems to be a small error in the GENERATE-BSP-TREE algo?
In GENERATE-BSP-TREE
line 2 should be
Tree = BSPTreeNode (Node)
instead of Tree = BSPTreeNode (PolygonSet)

correct me if i am wrong, but in that case node seems to have no use in that function.