Archived

This topic is now archived and is closed to further replies.

BSP Tree

This topic is 5115 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

Hi all, Recently I'm trying to develop a BSP Tree generator, so I started to read this document: www.gamedev.net/reference/programming/ features/bsptree/bsp.pdf Now my engine load a 3DS file and show it, the player can walk through it. So with this geometry I'm trying to generate the bsp tree. When the polygons are convex the algorithm stop. And this is my problem, for example when I tried with a cube, this isn't a convex polygon but any face of the cube isn't a good divider, so the program loop to the infinity. To choose a good divider I take each plane polygon and calculate how many polygons are infront and behind and calculate relation dividing these amounts, finally I choose the best plane divider polygon. I need HELP !! ... Thanks J.Martin Garcia Rangel [edited by - jgarcia on December 14, 2003 4:46:41 PM]

Share this post


Link to post
Share on other sites
In the case of a solid node BSP. Once you use a polygon as a divider you mark that polygon as used, you also need to mark any coplanar polygons that have the same normal as the dividing polygon as used as well since its really a plane thats dividing up the geometry and not really the polygon.

When its time to loop through the list of polygons and pick a polygon to use as a splitter you can skip any of those that have already been used.

Also any coplanar polygons that share the same normal as the chosen splitter and the splitter itself, need to be added to the list of polygons that lie on the front side of the splitter.

This should fix the infinte loop issue.

-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
Thanks, good point.
But I think that I''ll still having problems. Imagine a simple cube with the normals pointing to outside, what plane of any face that belongs to the cube will be a good divider ?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
with a single cube there really aren''t any plane that is better than the other, you will end up with about the same no matter what plane you use first... choosing splitter is simply a matter of what you think is more important a balanced tree or as few splits as possible. i made a simple routine that checked all planes and set up a score for it, how many faces it split and how balanced it would be, if you dont want splits make the score it gets for splitting a plane higher than the unbalance score etc. worked like a charm for me at least

Share this post


Link to post
Share on other sites
A cube with the normals on the outside isn''t going to give you anything youll be able to run around in as far as 3d goes. What you''ll end up with is a 3d brick floating out in space with the user stuck either in the middle of it or outside of it. However computing a BSP tree for this should still work with no problems.

Youll prolly want the normals facing inward to give the player an enclosed space to run around in assuming this of course the goal of all this. =)

Like AP said, in the case of just a simple cube, any of the polygons makes for a equally good splitter and at this point you just have to choose one and go with it. Due to how the test ususally goes for choosing a best splitter, this will prolly end up being the last unused one you test that gets picked, at least until you start running into the problems of a splitter splitting other polygons. At this point the number of polygons youre splitting becomes just as important a factor as how balanced the tree ends up.

If you end up splitting 20 polygons just to get one more polygon closer to having a balanced tree, then its definately a better idea to go with the less balanced tree if it only splits 2 polygons instead of 20.

-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
Thanks for your help.
I''m using a simple cube only for testing purposes, but in the 3D "house" that I create, all walls are "large" cubes with the normals pointing outside because the wall can be viewed from in and out of the "house".

I''m thinking, when the splitting must stop ?, in the PDF document the author indicate that it must stop when the node has only convex polygons, I think this isn''t a good idea, because maybe I''ll never have a convex polygon in one node, so I was thinking in calculate the sum of the area of the faces inside one node and define a limit.
For example:

#define cLIMIT_AREA 50

if ( CalculateTotalAreaOfNode(pNode->PolygonSet) <
cLIMIT_AREA )
return;
else
//Continue with the split
...
...


What do you think ?

Share this post


Link to post
Share on other sites