I have been working on a BSP-Tree implementation. It works in simple cases but in more complicated cases the BSP-Tree fails because of rounding errors. I use single floating point precision.
The problem lies in the classification of the polygon:
BSPNode::classifyFace(Polygon* face, Polygon* newFrontFace, Polygon* newBackFace) {
vector<Vertex3f> *vec = face->getVertices();
for(int i = 0; i < face->numOfVertices(); i++) {
Vertex3f v = (*vec);
float res = plane.a*v.X + plane.b*v.Y + plane.c*v.Z + plane.d;
res = isZero(res) ? 0.0f : res;
.
.
.
Description:
v will be tested against the plane equation (ax + by + cz + d = 0) of the polygon. If res < 0 then on one side, if res > 0 then on other side, else on plane. I use a function isZero() to test if the result is near zero (epsilon = 10^-5) to avoid problems near zero. So far so good.
Now the problem is that res sometimes has wrong values. I've added a screenshot to show what I mean. On the screenshot one can clearly see that there is an intersection between the polygons.
But res value for v1, v2 and v3 are very small negative numbers and will be rounded to zero by isZero() function. That is clearly not correct. What could be a solution to deal with those floating point rounding problems?
Thanks!