Leafy BSP Tree Compilation

[Adrian M]

During the bsp tree compilation there happens sometimes that a polygon would be split so much until it becomes very thin with an area almost 0. This polygon would further be split and thus obtaining degenerate triangles. The problem is that the construction fails when fed this kind of polygons and full leaves(all polygons used as splitter) arive in back nodes. When clipping triangles or classifying them i used a small epsilon to compare to 0. Lowering this epsilon does not help, actually often, it causes more problems. I have 3 small-medium sized levels(~500 tri - ~6000 tri) that are compiled flawessely without introducing degenerate triangles. How can i go around avoiding degenerate triangle creation, how can these be handled? Is it the sole duty of the artist to avoid such cases?

 

[GeLeTo]

You shouldn't get triangles with zero-sized area if your epsilon calculations are correct.
In order to split an almost zero-sized polygon - you need to have some of it's verts in front (at >epsilon distance) of the plane and some of it's verts behind. How is this possible if the polygon is almost zero-sized?

 

[Adrian M]

You shouldn't get triangles with zero-sized area if your epsilon calculations are correct.
In order to split an almost zero-sized polygon - you need to have some of it's verts in front (at >epsilon distance) of the plane and some of it's verts behind. How is this possible if the polygon is almost zero-sized?

Well, the triangle could be almost like a long line. This way it can be possible to be further split.

 

[Cryect]

Have you tried using as criteria for the weight in choosing what split plane to use the number of polygon splits that will occur if you use this plane as well increased weighting for every time a polygon has already been split? As well, if you are only considering a single split consider if you choose this split what the result of the next N splits would be as well and then going with the split that is lowest overall weight for the future.

 

[Adrian M]

Have you tried using as criteria for the weight in choosing what split plane to use the number of polygon splits that will occur if you use this plane as well increased weighting for every time a polygon has already been split? As well, if you are only considering a single split consider if you choose this split what the result of the next N splits would be as well and then going with the split that is lowest overall weight for the future.

I'm using a heuristic for tree balancing and minimization of the number of new polygons created, it's like this:

abs(FrontPolygons-BackPolygons) + Splits * 3.

Where FrontPolygons represents the number of polygons completely in front of the current split plane, BackPolygons are the polygons completely behind and Splits is the number of the polygons that are spanned by the split plane.