BSP Tree Infinite Loops (Gotta Love 'em)
Author
Hi, I've been working on a BSP tree producer from DirectX meshes for a while now and it works great on loads of the models I throw at it, However, there are some models, particularly large complex ones which cause it to go into an infinte loop where by the number of triangles it is putting into the child nodes just fluctuates around 20-30, never going down, it seems to divide and then split continously over and over. I was hoping to write a tree constructor that could place every triangle in its own leaf but this is driving me crazy, I've been going through the code for hours and hours and it is very hard to debug such complex and large models to find out whats going on since all I'm working with is verticies and indicies.
What I'm looking for is some hints and tips from people who have had similar problems (i.e. infinite loops) and what the cause was, I don't want to put a limit on the tree depth or minimum number of triangles in a leaf, I am currently placing the dividing triangle in the back node and placing coincident triangles based on whether their normal is in-front or behind the dividing plane. I seem to be hitting a situation where a child can keep splitting indefinatly, but my brain just can't get its head around this.
Please help! I'm going mad here :(
Chris
Your method does not terminate in most cases (which includes all cases where your polygons are on the faces of a convex polyhedron).
A common method of ensuring termination of the BSP tree building process is to store the splitting triangle inside the node. This way, every time you split a set of polygons, the number of polygons on each side of the plane will be smaller by at least one polygon than it was at first. This also ensures that there will be fewer splits (since it removes one polygon from the set at every split), and is proven to create a correct ordering in all cases, with or without backface culling.
If you do not want to do that, keep a variable for each polygon to remember if you have already performed a split using that polygon (and pass this value to the two polygons you would get from splitting a given polygon). Splitting twice with the same polygon is useless, because it will not change anything: all cuts have already been done.
Once all the polygons in a leaf have been used at least once for splitting, you know that leaf can't be changed anymore, so you can stop the splitting process there. Usually, polygons in that leaf will be on the sides of a convex polyhedron, so they can be rendered in any order with backface culling.
Without backface culling, you simply have no choice but to use a correct method, (to store polygons in nodes).
A common method of ensuring termination of the BSP tree building process is to store the splitting triangle inside the node. This way, every time you split a set of polygons, the number of polygons on each side of the plane will be smaller by at least one polygon than it was at first. This also ensures that there will be fewer splits (since it removes one polygon from the set at every split), and is proven to create a correct ordering in all cases, with or without backface culling.
If you do not want to do that, keep a variable for each polygon to remember if you have already performed a split using that polygon (and pass this value to the two polygons you would get from splitting a given polygon). Splitting twice with the same polygon is useless, because it will not change anything: all cuts have already been done.
Once all the polygons in a leaf have been used at least once for splitting, you know that leaf can't be changed anymore, so you can stop the splitting process there. Usually, polygons in that leaf will be on the sides of a convex polyhedron, so they can be rendered in any order with backface culling.
Without backface culling, you simply have no choice but to use a correct method, (to store polygons in nodes).
Author
Thanks for your reply. I experimented with storing the dividing ploygon with the node, this opens the question of when to draw the divider? Do you need to check every divider you pass when iterating the tree to decide if it needs drawing? It also didn't solve the problem, since when triangles were split it just increases the number of triangles in the child nodes..
I have a question of convex polyhedra, say I create a cube in a modeller, the normals will point out of the cube faces (unless it was a skybox). Now from what I've read, this isn't a convex polyhedra since the faces "face" outwards, not in... this seems like the wrong assumption?
My divider choosing code checks if a potential divider will cause all triangles to be placed on one side of it with no splits, in this case the divider is on the "outskirts" of the triangles and can't be used, since it would just result in all the triangles being placed into one child. This also means that for say a cube, none of the faces can be used to divide itself, since they would in fact, not cause any divisions, similarly for other objects like that, is this correct?
I understand what you are saying about checking that each triangle is only used once to perform a division, but then comes the problem of the split triangles, each time a triangle is split, the split sections become potential dividers, which can in turn split a dividing triangle that has already been used, result in, more potential dividers... and the loop continues. I think I am having trouble getting my head around this.
It appears that it gets to a point where by it divides the triangles, in the process causing some splits, then the new splits divide the remaining triangles, again causing more splits, which in turn split the triangles and so on... and the number of triangles never decreases since each new divide causes more new splits.
One such shape that causes this can be seen below (it's a snapshot of the triangles in the tree for which an infinite loop follows)
If this is a familiar problematic shape to you please say, the shape just ends up getting split and split and split until it is made up of hundreds more triangles, but maintains its shape.
Sorry if I am being confusing... the nitty gritty of BSP trees isn't pleasant. Any advice very very welcome I'm pulling at straws here :/
Chris
I have a question of convex polyhedra, say I create a cube in a modeller, the normals will point out of the cube faces (unless it was a skybox). Now from what I've read, this isn't a convex polyhedra since the faces "face" outwards, not in... this seems like the wrong assumption?
My divider choosing code checks if a potential divider will cause all triangles to be placed on one side of it with no splits, in this case the divider is on the "outskirts" of the triangles and can't be used, since it would just result in all the triangles being placed into one child. This also means that for say a cube, none of the faces can be used to divide itself, since they would in fact, not cause any divisions, similarly for other objects like that, is this correct?
I understand what you are saying about checking that each triangle is only used once to perform a division, but then comes the problem of the split triangles, each time a triangle is split, the split sections become potential dividers, which can in turn split a dividing triangle that has already been used, result in, more potential dividers... and the loop continues. I think I am having trouble getting my head around this.
It appears that it gets to a point where by it divides the triangles, in the process causing some splits, then the new splits divide the remaining triangles, again causing more splits, which in turn split the triangles and so on... and the number of triangles never decreases since each new divide causes more new splits.
One such shape that causes this can be seen below (it's a snapshot of the triangles in the tree for which an infinite loop follows)
If this is a familiar problematic shape to you please say, the shape just ends up getting split and split and split until it is made up of hundreds more triangles, but maintains its shape.
Sorry if I am being confusing... the nitty gritty of BSP trees isn't pleasant. Any advice very very welcome I'm pulling at straws here :/
Chris
I'll address your questions in order.
The typical process you perform when your renderer reaches a BSP node is to:
- determine which child to render first.
- render that child.
- render the polygon(s) inside the current node.
- render the other child.
You can draw the polygons in the node this way without asking yourself any questions. Just make sure they are rendered between the rendering of the two children.
Right, this is my fault, I forgot to mention something here: there is no need to work with triangles. Building a BSP is much easier when using generic, n-sided polygons, because such a polygon can be split, at most, into two new polygons.
This means that if you process a group of n polygons, you remove one (the splitter), and split the n-1 others, which gives you at most 2n-2 polygons, and at most n-1 in each child.
Once the BSP tree is built, you can go back and turn all those polygons into triangles. This will also help you have fewer triangles in the end.
If you don't want to use generic n-sided polygons, you could always remember the "groups" of triangles that were generated from a split, as if they were polygons. When you choose to split by one of the triangles in such a group, put the entire group in the node (they are coplanar, and can be rendered in any order). This will also make the program terminate.
What is important is not the direction in which the faces "face", but the fact that they all face the same way. A convex polyhedron, in mathematics, doesn't have "facing" since convexity is not a matter of facing. As long as all of your faces are facing outwards (or all are facing inwards), you can render them in any order.
This is true. The cause of all this is because the faces are indifferent to the order of rendering (you can render them in any order). If you were using the standard "n-sided-polygon, store-splitter" method without any optimizing, this case would be an ugly one as it would create a tree of depth 6 (the number of faces on the cube).
This is what I meant by "and pass this value to the two polygons you would get from splitting a given polygon": in fact, it is not the splitting polygons that you should remember, but the splitting planes. It's useless to split a set by a plane more than once. And since once you split a polygon, all the fragments you get lie on the same plane as the polygon, if that polygon's plane was already used, then so were all the fragments' planes, so they will all be marked as "used", just like the original polygon.
Your brown plane is made of many polygons that all lie on the same plane. Once one of them is used, so will be all the others. Mark them as "used" and the problem should disappear.
Actually, the theory of BSP rendering uses n-sided polygons, stores splitting polygons in nodes, and every polygon is split in at most two polygons. This method is extremely clean, the pseudocode for it is at most a dozen lines long, and it has been proven to terminate in any case.
My suggestion is to use this method with n-sided polygons, as it helps:
- easier to write BSP construction code (splitting a polygon is an easy generalization of splitting a triangle)
- using a clean, proven algorithm
- having to split fewer polygons
- having fewer triangles in the end
Quote:I experimented with storing the dividing ploygon with the node, this opens the question of when to draw the divider? Do you need to check every divider you pass when iterating the tree to decide if it needs drawing?
The typical process you perform when your renderer reaches a BSP node is to:
- determine which child to render first.
- render that child.
- render the polygon(s) inside the current node.
- render the other child.
You can draw the polygons in the node this way without asking yourself any questions. Just make sure they are rendered between the rendering of the two children.
Quote:also didn't solve the problem, since when triangles were split it just increases the number of triangles in the child nodes..
Right, this is my fault, I forgot to mention something here: there is no need to work with triangles. Building a BSP is much easier when using generic, n-sided polygons, because such a polygon can be split, at most, into two new polygons.
This means that if you process a group of n polygons, you remove one (the splitter), and split the n-1 others, which gives you at most 2n-2 polygons, and at most n-1 in each child.
Once the BSP tree is built, you can go back and turn all those polygons into triangles. This will also help you have fewer triangles in the end.
If you don't want to use generic n-sided polygons, you could always remember the "groups" of triangles that were generated from a split, as if they were polygons. When you choose to split by one of the triangles in such a group, put the entire group in the node (they are coplanar, and can be rendered in any order). This will also make the program terminate.
Quote:I have a question of convex polyhedra, say I create a cube in a modeller, the normals will point out of the cube faces (unless it was a skybox). Now from what I've read, this isn't a convex polyhedra since the faces "face" outwards, not in... this seems like the wrong assumption?
What is important is not the direction in which the faces "face", but the fact that they all face the same way. A convex polyhedron, in mathematics, doesn't have "facing" since convexity is not a matter of facing. As long as all of your faces are facing outwards (or all are facing inwards), you can render them in any order.
Quote:This also means that for say a cube, none of the faces can be used to divide itself, since they would in fact, not cause any divisions, similarly for other objects like that, is this correct?
This is true. The cause of all this is because the faces are indifferent to the order of rendering (you can render them in any order). If you were using the standard "n-sided-polygon, store-splitter" method without any optimizing, this case would be an ugly one as it would create a tree of depth 6 (the number of faces on the cube).
Quote:
I understand what you are saying about checking that each triangle is only used once to perform a division, but then comes the problem of the split triangles, each time a triangle is split, the split sections become potential dividers, which can in turn split a dividing triangle that has already been used, result in, more potential dividers... and the loop continues. I think I am having trouble getting my head around this.
This is what I meant by "and pass this value to the two polygons you would get from splitting a given polygon": in fact, it is not the splitting polygons that you should remember, but the splitting planes. It's useless to split a set by a plane more than once. And since once you split a polygon, all the fragments you get lie on the same plane as the polygon, if that polygon's plane was already used, then so were all the fragments' planes, so they will all be marked as "used", just like the original polygon.
Quote:If this is a familiar problematic shape to you please say, the shape just ends up getting split and split and split until it is made up of hundreds more triangles, but maintains its shape.
Your brown plane is made of many polygons that all lie on the same plane. Once one of them is used, so will be all the others. Mark them as "used" and the problem should disappear.
Quote:Sorry if I am being confusing... the nitty gritty of BSP trees isn't pleasant. Any advice very very welcome I'm pulling at straws here
Actually, the theory of BSP rendering uses n-sided polygons, stores splitting polygons in nodes, and every polygon is split in at most two polygons. This method is extremely clean, the pseudocode for it is at most a dozen lines long, and it has been proven to terminate in any case.
My suggestion is to use this method with n-sided polygons, as it helps:
- easier to write BSP construction code (splitting a polygon is an easy generalization of splitting a triangle)
- using a clean, proven algorithm
- having to split fewer polygons
- having fewer triangles in the end
Author
*click* Thank You! Something just clicked anyway, I understand what you mean about the image I posted and other concepts (was just the info I was looknig for), I think I will change the code to work with n-sided polygons, the idea of that threw me at first which is why I used triangles instead, but I think that may have just complicated things in the long run. Thanks for all your help, I will get to it and reply the results ;) bet you can't wait lol :)
Chris
Chris
Author
:) It worked! Thanks a lot for your help. It didn't take very long to convert the prog to using n-sided polygons, and omg where you right that splitting polygons is MUCH easier than splitting triangles! After constructing the tree I converted all the polygons into triangles using a triangle-fan technique. I did as you suggested and addded a "Used" property the polygons, this dramatically shrunk the tree size! I also set any polygons that were coincident with the divider to "Used" as well, since they would produce the same dividing plane.
Heres the results of a model hut that was made in 3DS which I converted to a BSP Tree:
Minimum Desired Polygons Per Node: 1
Verticies Before: 98
Verticies After: 198(100 more)
Maximum Depth: 8
Nodes Created: 37
Leaf Nodes: 19
Obviously I'm not going to be using the BSP tree to convert models like this, the tree will be used to convert large scenes created in 3DS->exported to .X into BSP Trees. The hut is an object from the entire scene.
If I set the desired minimum polygons per node to higher than 1 then less splits will occur and the tree will be shallower etc. Do you have any advice on the minimum polygons per leaf? Is 1 too low, and what would you consider to be too many? The "levels" this tree will be converting will typically consist of an outdoor scene with grass, roads and some builds, perhaps a few open windows with a room inside.
Thanks again for your help,
Chris
Heres the results of a model hut that was made in 3DS which I converted to a BSP Tree:
Minimum Desired Polygons Per Node: 1
Verticies Before: 98
Verticies After: 198(100 more)
Maximum Depth: 8
Nodes Created: 37
Leaf Nodes: 19
Obviously I'm not going to be using the BSP tree to convert models like this, the tree will be used to convert large scenes created in 3DS->exported to .X into BSP Trees. The hut is an object from the entire scene.
If I set the desired minimum polygons per node to higher than 1 then less splits will occur and the tree will be shallower etc. Do you have any advice on the minimum polygons per leaf? Is 1 too low, and what would you consider to be too many? The "levels" this tree will be converting will typically consist of an outdoor scene with grass, roads and some builds, perhaps a few open windows with a room inside.
Thanks again for your help,
Chris
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
