BSP tree ( leaf ) question

Quote:

A short one, i have created a BSP tree compiler for the Geometry, but some of my leafs contain only one polygon. Is this normal since all the documents i've read say that a leaf is always a convex space. So is a single polygon a convex space. Furthermore some of the leafs contain zero polygons. Which seems very odd to me, can I safely delete those leafs? The BSP Code is located here http://home.hccnet.nl/pj.holverda/Source/Compiler/BSP.java

This is a quake3 like bsp tree, aren't they? (Polygon alligned)
If the answer is yes, it's normal that at the end of splitting, there is no polygon in the convex space, because this space will be used to find the portals beetween them and after this you will check all polygons against the bsp to find where the polygon is within the bsp tree.
But this tecnique is too old,try to use the Axis Aligned Bps-Tree.. it is more clear and you can control how many polygon you want in each leaf node ;-)

Bye Davide

yes the data is imported from quake III .map files but i don't see why it is 'old' to use a BSP tree, because they are lightning fast when performing collision detection( only testing the leaf's planes it's convex anyway) and I need them to find the portals between the leafs( don't know how to do it with other approaches ) When i have the portals it is easy to remove leafs that are never seen ( basically the ones outside the level )

Quote:

Original post by davidino79 But this tecnique is too old,try to use the Axis Aligned Bps-Tree.. it is more clear and you can control how many polygon you want in each leaf node ;-)

I think you mean an ABT, which stands for Adaptive Binary Tree.

Quote:

Original post by python_regious I think you mean an ABT, which stands for Adaptive Binary Tree.

Not only, ABT is a special kind of axis aligned binary tree

Quote:

yes the data is imported from quake III .map files but i don't see why it is 'old' to use a BSP tree,

Not properly old but, it is perfect for indoor scenes (it is very quick for occlusion culling).
But the axis aligned bsp-tree (Quake style) is very tedius for outdoor or mixed scenes, and you can replace the portal occlusion culling with tecnique such as HOM or hierarchical Z-buffer.

Quote:

Original post by gorgorath because they are lightning fast when performing collision detection( only testing the leaf's planes it's convex anyway) and I need them to find the portals between the leafs( don't know how to do it with other approaches ) When i have the portals it is easy to remove leafs that are never seen ( basically the ones outside the level )

If you understand this,then you should not be surprised that your leafs is empty...This leafs describe a convex space that will be linked by portals...so when you have found the leafs and the portals,you will include the geometry that cross the leafs.

Bye,
Davide

If you understand this,then you should not be surprised that your leafs is empty...This leafs describe a convex space that will be linked by portals...so when you have found the leafs and the portals,you will include the geometry that cross the leafs.
/quote]

Basically i beleaf it was the other way around, when you found your leaf( no more front or back splits ) you can keep the information in that node ( list of polygons, and flag that node as a leaf ) after that you can build portals with each of the nodes and start sending them down the BSP tree until they pop out at a leaf, and if the portal exist in two leafs start clipping it against the leaf's polygons.

But correct me if i'm wrong it's my first attempt to create a BSP tree ever:)

Gorgorath

thanks for the reply,

after some spitting into the code i've discovered the possible cause of my problems, some nodes share the same plane which is EVIL. A plane ( and it's inverted plane ) should never be used as split plane again!

But somehow in my code it creates nodes again, with the same plane, i've been debugging for almost a week now, but can't seem to find it.
The function where the bug probably occured should be in these two methods "buildBSPTree( Node node )" and "selectBestSplitter( Node node, int numPolygons )".

The first method recursively calls "selectBestSplitter" which gives the index of the best splitting plane of the current polygon list in the node, or '-1' if this node seems to be a leaf. If the node seams to be a leaf don't bother anymore and return from the 'buildBSPTree' function.

If it isn't a leaf we have a splittingplane so mark it as 'usedSplitter' it won't be a splitter again. BUT also mark all the polygons that are ONPLANE with this splitter also, coz their planes should never be a splitterplane again.

the code for this is here:

http://home.hccnet.nl/pj.holverda/Source/Compiler/BSP.java

if someone is willing enough to give it a quick look and can say to me where i'm doing things the very wrong way. Or if my logic isn't correct please tell me coz i'm completely lost:)

cheers,

Paul