Jump to content
  • Advertisement
Sign in to follow this  
gorgorath

BSP tree ( leaf ) question

This topic is 5461 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 Cheers Gorgorath

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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 )

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites



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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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



When you have found a bsp-tree,you will generate the portals, try to see the bsp tree map generator of quake3,I have learned from it.

Bye
Davide

Share this post


Link to post
Share on other sites
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


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!