BSP Tree problems
Author
I am making a BSP tree in OpenGL. Everything works fine except when I split polygons the texture coordinates don't split right for some polygons. I am so getting sick of this so can someone help me by telling me a formula you used to split the texture coords.
All I am looking for is a code snippet showing how to calculate the right texture coordinates for split polygons. Thanks.
Can you show us how you're currently calculating the texture coordinates at the split points? And perhaps you could also tell us how the resulting texture coordinates are wrong.
Author
Basically I am using this to get the tex coords
float tu = texCoords[current].tu - texCoords.tu;
float tv = texCoords[current].tv - texCoords.tv;
tu = texCoords.tu + (tu * dist);
tv = texCoords.tv + (tv * dist);
With dist being the scalar used to split the polygon. What makes the tex coords wrong is the output I am getting. I have a room with 4 walls, a floor, and a ceiling as well as another wall in the middle left of the room. If I don't render using the BSP I can clearly see all of the polygon data and tex coords are correct. The problem lines in the polygon split function. Here is the entire splitting function. Keep in mind I was hacking at this for a few days so there might be some unused variables and things might be a little sloppy.
float tu = texCoords[current].tu - texCoords.tu;
float tv = texCoords[current].tv - texCoords.tv;
tu = texCoords.tu + (tu * dist);
tv = texCoords.tv + (tv * dist);
With dist being the scalar used to split the polygon. What makes the tex coords wrong is the output I am getting. I have a room with 4 walls, a floor, and a ceiling as well as another wall in the middle left of the room. If I don't render using the BSP I can clearly see all of the polygon data and tex coords are correct. The problem lines in the polygon split function. Here is the entire splitting function. Keep in mind I was hacking at this for a few days so there might be some unused variables and things might be a little sloppy.
void CPolygon::ClipPolygon(CPlane &plane, CPolygon *fP, CPolygon *bP){ int frontCount = 0, backCount = 0, current = 0, f = 0, b = 0; int resultIndex[10]; CVector4 frontList[10]; CTexCoord tCFList[10]; CVector4 backList[10]; CTexCoord tCBList[10]; CVector4 p1, p2, pHit; if(!fP && !bP) return; for(int i = 0; i < 3; i++) { resultIndex = plane.ClassifyPoint(vertices); switch(resultIndex) { case FRONT_PLANE: f++; break; case BEHIND_PLANE: b++; break; default: break; } } if(!f) { backCount = 3; backList[0] = vertices[0]; backList[1] = vertices[1]; backList[2] = vertices[2]; } if(!b) { frontCount = 3; frontList[0] = vertices[0]; frontList[1] = vertices[1]; frontList[2] = vertices[2]; } tCFList[0] = texCoords[0]; tCFList[1] = texCoords[1]; tCFList[2] = texCoords[2]; tCBList[0] = texCoords[0]; tCBList[1] = texCoords[1]; tCBList[2] = texCoords[2]; if(f && b) { for(int i = 0; i < 3; i++) { current = (i + 1) % 3; switch(resultIndex) { case FRONT_PLANE: frontList[frontCount++] = vertices; break; case ON_PLANE: case CLIPPED_PLANE: frontList[frontCount++] = vertices; backList[backCount++] = vertices; continue; break; default: backList[backCount++] = vertices; break; } if(resultIndex[current] == ON_PLANE || resultIndex[current] == resultIndex) continue; CVector4 v1(vertices.x, vertices.y, vertices.z, 1); CVector4 v2(vertices[current].x, vertices[current].y, vertices[current].z, 1); CVector4 v3(vertices[0].x, vertices[0].y, vertices[0].z, 1); CVector4 dir = v2 - v1; CVector4 dir2 = v3 - v1; CVector4 pNormal(plane.a, plane.b, plane.c, plane.d); int result = 1; float dist = 0; float dp2 = 0; float dp = pNormal.DotProduct3(dir); if(fabs(dp) < 0.001f) result = 0; else { dp2 = pNormal.DotProduct3(dir2); dist = dp2 / dp; if(dist < 0 || dist > 1) result = 0; else { pHit = v1 + dir * dist; } } dist = (pHit - v1).GetLength() / dp; frontList[frontCount] = pHit; backList[backCount] = pHit; float tu = texCoords[current].tu - texCoords.tu; float tv = texCoords[current].tv - texCoords.tv; tu = texCoords.tu + (tu * dist); tv = texCoords.tv + (tv * dist); tCFList[frontCount].tu = tu; tCFList[frontCount].tv = tv; tCBList[backCount].tu = tu; tCBList[backCount].tv = tv; frontCount++; backCount++; } } if(fP) { fP->vertices[0] = frontList[0]; fP->vertices[1] = frontList[1]; fP->vertices[2] = frontList[2]; fP->flag = flag; fP->normal = normal; fP->texCoords[0] = tCFList[0]; fP->texCoords[1] = tCFList[1]; fP->texCoords[2] = tCFList[2]; } if(bP) { bP->vertices[0] = backList[0]; bP->vertices[1] = backList[1]; bP->vertices[2] = backList[2]; bP->flag = flag; bP->normal = normal; bP->texCoords[0] = tCBList[0]; bP->texCoords[1] = tCBList[1]; bP->texCoords[2] = tCBList[2]; }}
Ok, had a quick look through your code. I can't quite tell what you're doing towards the middle there, where you find the intersection point. I didn't look at it too carefully, but at first glance the code doesn't look right, and may be the source of your problems. In any case, whether or not it's correct, I think you're working too hard there - the intersection points can be found with considerably less effort.
The first thing to consider is that your ClassifyPoint() function most likely finds the signed distance from the point to the plane, and then returns a constant based on the sign of the result, e.g. a positive distance is 'in front', a negative distance is 'behind', and so on.
The fact is, these signed distances give you all the information you need to find the points of intersection, but you're just throwing the information away. Then, later, you're doing a bunch of additional work to try to re-create the point of intersection.
Here's how I do it in my clipping code. Instead of calling a ClassifyPoint() function, I call a DistanceToPlane() function, and keep the result in an array. I also have a frontCount and backCount, like you do, and increment them as appropriate based on the distance to the plane for each vertex.
If and when it comes time to clip the polygon, the distances from the vertices to the planes (which you saved from your distance tests) tell you a) if an edge spans the plane and needs to be clipped, and b) where the parametric point of intersection is.
Anyway, that's it for me for tonight, but if you're still struggling with this tomorrow I'll be glad to post some code.
The first thing to consider is that your ClassifyPoint() function most likely finds the signed distance from the point to the plane, and then returns a constant based on the sign of the result, e.g. a positive distance is 'in front', a negative distance is 'behind', and so on.
The fact is, these signed distances give you all the information you need to find the points of intersection, but you're just throwing the information away. Then, later, you're doing a bunch of additional work to try to re-create the point of intersection.
Here's how I do it in my clipping code. Instead of calling a ClassifyPoint() function, I call a DistanceToPlane() function, and keep the result in an array. I also have a frontCount and backCount, like you do, and increment them as appropriate based on the distance to the plane for each vertex.
If and when it comes time to clip the polygon, the distances from the vertices to the planes (which you saved from your distance tests) tell you a) if an edge spans the plane and needs to be clipped, and b) where the parametric point of intersection is.
Anyway, that's it for me for tonight, but if you're still struggling with this tomorrow I'll be glad to post some code.
Here is some sample code for you to look at:
I tested it and it seems to work fine. I didn't include texture coordinates, but you should be able to interpolate them using 't' the same way the vertices are interpolated.
If anything isn't clear, feel free to ask.
void SplitPolygon( const std::vector<Vector3>& p, // Input polygon std::vector<Vector3>& pf, // Front poly after split std::vector<Vector3>& pb, // Back poly after split const Vector3& n, // Plane normal float d, // Plane distance (may need to be negated first) float epsilon) // Tolerance for point-on-plane{ if (p.empty()) return; std::vector<float> dist(p.size()); std::vector<int> side(p.size()); int numFront = 0; int numBack = 0; enum {ON, FRONT, BACK, SPANNING}; for (int i = 0; i < p.size(); ++i) { dist = p.Dot(n) - d; if (dist > epsilon) { side = FRONT; ++numFront; } else if (dist < -epsilon) { side = BACK; ++numBack; } else side = ON; } pf.clear(); pb.clear(); if (!numBack) pf = p; else if (!numFront) pb = p; else { for (int i = 0; i < p.size(); ++i) { if (!(side & BACK)) pf.push_back(p); if (!(side & FRONT)) pb.push_back(p); int j = (i + 1) % p.size(); if ((side | side[j]) == SPANNING) { float t = dist / (dist - dist[j]); Vector3 v = (1.0f - t) * p + t * p[j]; pf.push_back(v); pb.push_back(v); } } }}I tested it and it seems to work fine. I didn't include texture coordinates, but you should be able to interpolate them using 't' the same way the vertices are interpolated.
If anything isn't clear, feel free to ask.
Author
Thanks pal. You helped me a lot. Things are clear now and I was able to get things working right.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
