Sign in to follow this  
DaveMichael

Triangle Splitting

Recommended Posts

Beg your pardon, I've been coding a binary space partition tree for a project, and the code to split a triangle along a plane has been giving me fits. If anyone's interested, I've included the source for my current clipping algorithm below, but it's based on code that works with polygons with an arbitrary number of points, and it tends to fail at odd times. So what I'm really looking for now is a reliable algorithm for splitting a triangle on a plane, with the result being two or three new triangles. Thanks to anyone who can point me in the right direction. void T_Polygon::clip(const T_Plane &p, T_Polygon &front, T_Polygon &back, T_Polygon &extra) { log("Clipping polygon %i...", ID); //if(!front && !back) // return; T_Vector hit, _a, _b; T_Ray ray; T_Plane* pl = (T_Plane*)&p; int numFront = 0, numBack = 0, loop = 0, current = 0; T_Vector* vFront = new T_Vector[4]; T_Vector* vBack = new T_Vector[4]; T_Vector* points = new T_Vector[3]; points[0] = a; points[1] = b; points[2] = c; log("\tGot first point (%f,%f,%f).", points[0].x, points[0].y, points[0].z); log("\tGot second point (%f,%f,%f).", points[1].x, points[1].y, points[1].z); log("\tGot third point (%f,%f,%f).", points[2].x, points[2].y, points[2].z); switch(pl->classify(points[0])) { case FRONT: vFront[numFront++] = points[0]; log("\tSent first point to the front."); break; case BACK: vBack[numBack++] = points[0]; log("\tSent first point to the back."); break; case PLANAR: vFront[numFront++] = points[0]; vBack[numBack++] = points[0]; log("\tSent first point to the front and the back."); break; default: return; } for(loop = 1; loop <= 3; loop++) { log("\tStarting loop %i...", loop); if(loop == 3) current = 0; else current = loop; _a = points[loop - 1]; _b = points[current]; log("\t\tCurrent point is (%f,%f,%f).", _b.x, _b.y, _b.z); int classB = pl->classify(_b); int classA = pl->classify(_a); if(classB == PLANAR) { log("\t\tCurrent point is planar. Sorting to front and back."); vFront[numFront++] = points[current]; vBack[numBack++] = points[current]; } else { ray.origin = _a; ray.direction = _b - _a; float length = ray.direction.getLength(); if(length != 0.0f) ray.direction /= length; if(ray.intersects(p, false, length, 0, &hit) && classA != PLANAR) { log("\t\tCurrent point is on other side of the plane from last point."); log("\t\tGot new point at (%f,%f,%f).", hit.x, hit.y, hit.z); vBack[numBack++] = hit; vFront[numFront++] = hit; if(classB == FRONT) { if(current != 0) { log("\t\tSorted current point to front."); vFront[numFront++] = points[current]; } } else if(classB == BACK) { if(current != 0) { log("\t\tSorted current point to back."); vBack[numBack++] = points[current]; } } } else { log("\t\tCurrent point is on the same side of the plane from the last point."); if(current == 0) continue; if(classA == FRONT) { log("\t\tSorted current point to front."); vFront[numFront++] = points[current]; } else if(classA == BACK) { log("\t\tSorted current point to back."); vBack[numBack++] = points[current]; } else { log("\t\tShould not happen."); return; } } } } if(numFront == 4) { log("\t\tShould have four points on front side."); for(int i = 0; i < numFront; i++) { log("\t\t\t(%f,%f,%f)", vFront[i].x, vFront[i].y, vFront[i].z); } //if(front) //{ front.set(vFront[0], vFront[1], vFront[2]); front.setID(ID); if((front.plane.normal * plane.normal) < 0.0f) { front.plane.normal *= -1; front.plane.distance *= -1; } //} //if(extra) //{ extra.set(vFront[1], vFront[2], vFront[3]); extra.setID(ID); if((extra.plane.normal * plane.normal) < 0.0f) { extra.plane.normal *= -1; extra.plane.distance *= -1; } //} } else if(numFront == 3) { log("\t\tShould have three points on front side."); for(int i = 0; i < numFront; i++) { log("\t\t\t(%f,%f,%f)", vFront[i].x, vFront[i].y, vFront[i].z); } //if(front) //{ front.set(vFront[0], vFront[1], vFront[2]); front.setID(ID); if((front.plane.normal * plane.normal) < 0.0f) { front.plane.normal *= -1; front.plane.distance *= -1; } //} } if(numBack == 4) { log("\t\tShould have four points on back side."); for(int i = 0; i < numBack; i++) { log("\t\t\t(%f,%f,%f)", vBack[i].x, vBack[i].y, vBack[i].z); } //if(back) //{ back.set(vBack[0], vBack[1], vBack[2]); back.setID(ID); if((back.plane.normal * plane.normal) < 0.0f) { back.plane.normal *= -1; back.plane.distance *= -1; } //} //if(extra) //{ extra.set(vBack[1], vBack[2], vBack[3]); extra.setID(ID); if((extra.plane.normal * plane.normal) < 0.0f) { extra.plane.normal *= -1; extra.plane.distance *= -1; } //} } else if(numBack == 3) { log("\t\tShould have three points on back side."); for(int i = 0; i < numBack; i++) { log("\t\t\t(%f,%f,%f)", vBack[i].x, vBack[i].y, vBack[i].z); } //if(back) //{ back.set(vBack[0], vBack[1], vBack[2]); back.setID(ID); if((back.plane.normal * plane.normal) < 0.0f) { back.plane.normal *= -1; back.plane.distance *= -1; } //} } }

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this