• Advertisement

Archived

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

Coplanar polygons in BSP trees

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

I''m currently developing a demo to test the efficiency of different BSP implementations, and I''ve come across a problem that I''m not 100% sure how to solve. I understand the theory and all behind BSP trees, but am having a little bit of trouble with the implementation. My problem is this: what do you do when you run across polygons that are coplanar with the one you are using as the one defining your cutting plane while constructing the tree? While this wouldnt happen all of the time, it is still a case that needs to be dealt with (and would be likely to show up with vertical walls, etc). As of yet I have not been able to find a place that describes how to handle this. A post on a different topic suggested that those coplanar polygons should be by default set as behind the cutting plane. This strikes me as odd because it would mean further processing of the cutting plane you''re already using when those polygons are processed later in the tree. The idea of having a node possibly hold multiple polygons (or references to polygons) has occurred to me, but then the problem is which one of these do you draw first? second? etc? also, the logistics of the data structure escape me at the moment. I''m currently using an array of polygons to hold those in the scene - the nodes are storing indices into that array (I''m basing it off of the code presented in Ben Humphrey''s work on GameTutorials.com if you''re wondering, as I am not experienced in loading level files (.bsp format), and am on a truncated time table for when this needs to be done). So, if a node could hold multiple polygons, it would have to store an indeterminate number of indices into this array, meaning either an array of size x (x being the maximum number of polygons that could potentially be coplanar for a level - impossible to say how many this could be and is overall VERY wasteful of memory, as it will rarely be used, and when it is, almost never to its full extent), or possibly an STL vector or something like that. Also, while I''m at it, what do you do if your camera (viewpoint) is right one of the cutting planes? I''d think you''d define it as default in front of or behind it, or possibly set the players position as being a float like 50.0000005 to begin with, and only allow them to move in integer increments (or increments much larger than the little bit added to the position), so that even factoring in the fact that with trig decimal positions would occur, it the chances of the camera being EXACTLY coplanar with one of the cutting planes would be astronomical. Any thoughts? Thanks ahead of time for the patience nearly all of you exhibit on this forum, its really appreciated to those who are still learning their way around.

Share this post


Link to post
Share on other sites
Advertisement
quote:
My problem is this: what do you do when you run across polygons that are coplanar with the one you are using as the one defining your cutting plane while constructing the tree? While this wouldnt happen all of the time, it is still a case that needs to be dealt with (and would be likely to show up with vertical walls, etc). As of yet I have not been able to find a place that describes how to handle this.


(I''m going to assume a solid node BSP tree)

Compare the coplanar polygon''s normal with that of the splitting plane, if they''re the same (within some tolerance) add the polygon to the front list, if they''re not, add the poly to the back list.

Also while I''m here I''ll mention another little tip since you may run into this down the line. Normally when constructing the BSP you keep track of which polygons have been used as splitting planes. Whenever you pick a polygon to be used to create a splititng plane, all other coplanar polygons, sharing the same normals or not, should also be marked as having been used as a splitter.


-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
First of all - you do not want to store polygons in the nodes, but only leafs, i.e. solid leafy BSP it is...
Quake 1 (not sure about 2) used your approach, but since then switched to leafy tree.
Why?
Because that way you do collect all polys in the leafs in batches, polygons naturally group in the convex leafs.

Some tips: extract all unique planes from the geometry, and choose splitting planes from it, not from polys themselves - it is faster, and easier to maintain. Sometimes there are many polys sharing single plane. And yes, here we put polys that share a plane, and may have opposite normals too.
Just when build the tree, move the polys with the same normal as the plane into the front list, others with the opposite normal - in the back list.
In leafs store just the first index of the polys and their count. Then put all geometry of the level into single continious array. Or maybe just an index into an array with descriptors, each of them saying that there are N polys at index X with material M, that way you''ll have 2 arrays - with material descriptors, where the BSP tree will point, and a geometry array where the descriptor array will be point to. For faster shader sorting.
Of course when you choose a plane for a splitter, you mark it as ''used'', so it will not be used again in the child recursion (and unmark it as recursion goes back, so that same plane can be used as a splitter in the other side of the tree...).
And maybe it is good to process the polys first, to get the planes they use for choosing the splitter plane later, because using just extracted planes may result in choosing a plane that are not shared by even single polygon in the current list.
Which is not so bad, but is not good for clear portalization later.

Share this post


Link to post
Share on other sites
Thanks for the information,guys, I really appreciate it. I have a few questions though (why is it that whenever one question is answered, 10 more make themselves known? lol)

First of all what are the advantages/disadvantages to the solid node vs solid leaf BSP trees? I''d think that making it a solid leaf tree would make the tree more complex, larger with deeper levels of recursion. The reason I am thinking this is because the polygons that would be stored in the nodes in a solid node system would have to be stored as leaves, requiring more leaves to be made, and thus larger size and complexity in the tree. (note I am referring to a full bsp tree, where when fully constructed, each node containing polygons only stores 1. This is contrary to some of the quake systems, where the nodes referred to sectors).

Secondly, how would you handle the "unmarking" of splitting planes when recursing back? I would think you could pass a boolean array that referred to an array or similar structure of your splitting planes. This array would be passed to each new node, which would choose a plane, modify the array, and pass it on to its children (this obviously could not be by reference). That way the nodes receive an up to date list from the parent, but the back branch will not be affected by the plane choices of the front branch. Is this a good way to implement it?

"Which is not so bad, but is not good for clear portalization later."
- keep in mind I am not building a portal engine - just strictly a BSP engine (I probably did not make that clear in my original post, sorry about that). Each polygon will be referred to by a unique node. I realize portal engines have their advantages, but for this current project, all I need is a basic BSP engine

I do like the idea of precalculating all the possible splitting planes and keeping track of them that way - as this would be computationally expensive early on, I think it would save time and trouble later in the tree build not having to worry about making sure that polygons coplanar with the splitting plane are not used as splitters further down the line.

Thanks for all the help, I really appreciate it. and what do you know? that was less than 10 questions.

Beware programmers who carry around screwdrivers

How many programmers does it take to screw in a lightbulb? none. That''''s a hardware problem

Is it a bad sign when you start ending all of your sentences with semicolons?;

Share this post


Link to post
Share on other sites
quote:
Original post by RobotCoder
First of all what are the advantages/disadvantages to the solid node vs solid leaf BSP trees? I'd think that making it a solid leaf tree would make the tree more complex, larger with deeper levels of recursion. The reason I am thinking this is because the polygons that would be stored in the nodes in a solid node system would have to be stored as leaves, requiring more leaves to be made, and thus larger size and complexity in the tree. (note I am referring to a full bsp tree, where when fully constructed, each node containing polygons only stores 1. This is contrary to some of the quake systems, where the nodes referred to sectors).


No, just think about the finish criteria of you recursion - one is when you stop when all current polys form a convex shape, and other is when all polys was used as splitter planes. The difference is that in the first case, when you meet convex shape, you stop and do not need to use any of its polys as splitters.. Hmm, not as I think that is not solid tree.
Then the difference of solid vs non-solid tree is just the storing of polys - in the leafs ot in the nodes. In the leafy tree all the polys fall down the tree into leaves, and in the non-leafy tree they stick into nodes they form.
So, the the use of non-leafy tree is when you need polygons in the nodes, while traversing the tree. Maybe for some collision or wierd VSD (extracting polygon properties ASAP).
Tell us what do you want to archieve, and I'll tell you if you need non-leafy tree. Leafy one is sufficient in most of the cases.

quote:
Secondly, how would you handle the "unmarking" of splitting planes when recursing back? I would think you could pass a boolean array that referred to an array or similar structure of your splitting planes. This array would be passed to each new node, which would choose a plane, modify the array, and pass it on to its children (this obviously could not be by reference). That way the nodes receive an up to date list from the parent, but the back branch will not be affected by the plane choices of the front branch. Is this a good way to implement it?

It is not a good way of implementing it, the ultimate way ( is to have global boolean array (maybe even a member in the plane array itslef, for better cache coherency), and to mark a node when you use it, recurse, and after recursion unmark the node.
Just basic recursion skills...

quote:
"Which is not so bad, but is not good for clear portalization later."
- keep in mind I am not building a portal engine - just strictly a BSP engine (I probably did not make that clear in my original post, sorry about that). Each polygon will be referred to by a unique node. I realize portal engines have their advantages, but for this current project, all I need is a basic BSP engine

Hmm, strange. What do you plan to do with that BSP tree alone?
I do not know of engine that use just plain BSP tree.. Maybe Unreal at some degree (in single zone) used just the BSP tree for culling, but these days are gone...

quote:

I do like the idea of precalculating all the possible splitting planes and keeping track of them that way - as this would be computationally expensive early on, I think it would save time and trouble later in the tree build not having to worry about making sure that polygons coplanar with the splitting plane are not used as splitters further down the line.

This is O(N) operation over the polys, which is extremely fast compared with the BSP building process itself. The bad thing is when you have little coplanar polys, but that is rare (especially if you use triangles as polys). On architectural levels it will be faster, but on organic ones maybe it will fail to beat the simpler solution using only polys...
Try it for yourself.

..
Oh, by the way, the process of choosing a splitter iterate through polys, not planes, just when choosing a poly first check its plane ID for being already used (my polys have ID of their plane) and that way disable using coplanar polys as different splitters...

[edited by - Zemedelec on April 11, 2004 5:08:30 PM]

Share this post


Link to post
Share on other sites
Ok, well first of all I think I should clarify what I am trying to do, and what I am NOT trying to do. I am basically doing this to investigate different BSP optimizations in a comparative study for a research project. If I can find articles with data describing the tips and techniques you''re suggesting, I can include them into my study, but only as options. I''m starting out with a simple, basic BSP tree (strictly a plain BSP tree) then adding in each system one at a time and trying to measure (if I can do this on time) pre-calculation time, average run-time frame rate, average CPU load, and memory requirements (size of tree required basically).

I am NOT trying to produce a modern or commercial rendering system here, this is all basically theoretical, research-driven stuff

Going with the basic BSP concept, I plan on having each node (or leaf) in the final tree contain only one polygon, not one convex shape - although one of the optimizations is an object-oriented approach that sounds similar to this concept). As far as leafy vs non-leafy, I am not sure which would be better in this case, hence why I am asking for advantages/disadvantages of each one (or just tell me which one is better for my situation with a short description of why if you would).

I considered a global boolean array (or one bound to the plane array), but the one thing I dont know how to do is how to keep track of which flags were set at which depth of recursion. For example, a plane that gets eliminated from the list of possible cutting planes at a depth of 5 (on the front side of the originating depth 4 node) should get reset to be a possibility when doing the calculations for depth 5 on the back side of the same depth 4 node, while a plane that was eliminated at a depth of 1 or 2 should not be reset. How to keep track of which one was eliminated at which level would require an integer array, or.....

one possible implementation would be to have each node keep a record of whatever planes it eliminated, and once it has finished recursing its two subtrees, it will reset the flag before returning to its parent for further analysis. This would probably be a more elegant solution, and as the nodes should have some reference to which cutting plane they are using anyway, this should be easy to implement. Is this a good way of doing it? It had not occurred to me before.

and as far as the small coplanar polys goes, wouldnt precreating a list of potential cutting planes actually be advantageous when this occurs, as repeat instances would be handled once right then as opposed to being recalculated for each polygon that lies in that plane during the recursive BSP tree building process?

Thanks for all the help, I really appreciate it.
_________________________________________________________


Beware programmers who carry around screwdrivers

How many programmers does it take to screw in a lightbulb? none. That''''s a hardware problem

Is it a bad sign when you start ending all of your sentences with semicolons?;

Share this post


Link to post
Share on other sites
quote:
Original post by RobotCoder
Ok, well first of all I think I should clarify what I am trying to do, and what I am NOT trying to do. I am basically doing this to investigate different BSP optimizations in a comparative study for a research project. If I can find articles with data describing the tips and techniques you're suggesting, I can include them into my study, but only as options. I'm starting out with a simple, basic BSP tree (strictly a plain BSP tree) then adding in each system one at a time and trying to measure (if I can do this on time) pre-calculation time, average run-time frame rate, average CPU load, and memory requirements (size of tree required basically).

That's fine, but we are talking just about different kinds of BSP tree, which must be used wisely depending on the task they are supposed to solve, right? So, it not make much sense to compare different BSPTs on single task, it must be clear which one to use - and others will fail... Or you didn't understand your goal again?

quote:

Going with the basic BSP concept, I plan on having each node (or leaf) in the final tree contain only one polygon, not one convex shape - although one of the optimizations is an object-oriented approach that sounds similar to this concept).

Ok, that is solid tree.

quote:
As far as leafy vs non-leafy, I am not sure which would be better in this case, hence why I am asking for advantages/disadvantages of each one (or just tell me which one is better for my situation with a short description of why if you would).

Ok, this one again - non-leafy tree you do need only when you need splitting polys IMMEDIATELY when traversing the tree. For wierd reasons, i.e. ordering the polygons for example front to back, or reverse.
In all other cases you need leafy tree. Sometimes (collision) you need only the tree, without any of the polys...

quote:
I considered a global boolean array (or one bound to the plane array), but the one thing I dont know how to do is how to keep track of which flags were set at which depth of recursion.


You clearly do not need that.

quote:
and as far as the small coplanar polys goes, wouldnt precreating a list of potential cutting planes actually be advantageous when this occurs, as repeat instances would be handled once right then as opposed to being recalculated for each polygon that lies in that plane during the recursive BSP tree building process?


No, this will be waste of time - precalculating distinct planes must be done just once.

Here are some pseudocode for the build procedure of a solid leafy BSP tree.


struct BSPPlane
{
D3DXPLANE plane;
bool bUsed;
} * g_pPlanes;

struct BSPNode // unified structure for nodes & leaves, for simplicity of explanation

{
D3DXPLANE plane;
int firstPolyID;
int polyCount;
int flags; // solid, non-solid

BSPNode * pChild[2];
};

BSPNode * BuildSolidLeafyBSPT( IN original_polygons, OUT & bspt_polygons )
{
g_pPlanes = ComputePlanesFromPolys( original_polys ); // find all unique planes, mark them as unused and remember in each poly its plane


BSPNode * pRoot = BuildSolidLeafyBSPT_r( original_polygons, bspt_polygons );

delete[] g_pPlanes;
return pRoot;
}

BSPNode * BuildSolidLeafyBSPT_r( IN polys, IN OUT & bspt_polys )
{
if( polys is empty ) return NULL;

int splitter = FindBestSplittingUnusedPlane( polys ); // iterate through polys' planes and find best one


BSPNode * pNode = new BSPNode();

if( splitter == -1 ) // all planes are used, so a leaf must be created

{
pNode->firstPolyID = bspt_polys.size();
pNode->polyCount = polys.size();

bspt_polys.insert_at_the_end( polys );

pNode->flags = LEAF;
pNode->pChild[0] = pNode->pChild[1] = NULL;

return pNode;
}

SplitPolysByPlane( polys, front_polys, back_polys );

g_pPlanes[splitter].bUsed = true; // lock that plane, so it's not goind to be used in the subtrees


pNode->flags = NODE;
pNode->pChild[0] = BuildSolidLeafyBSPT( front_polys, bspt_polys );
pNode->pChild[1] = BuildSolidLeafyBSPT( back_polys, bspt_polys );

g_pPlanes[splitter].bUsed = false; // unlock plane as we recurse back


return pNode;
}



quote:
Thanks for all the help, I really appreciate it.

You're wellcome!

[edited by - Zemedelec on April 12, 2004 5:17:48 AM]

Share this post


Link to post
Share on other sites

  • Advertisement