• Advertisement
Sign in to follow this  

Triangle Splitting

This topic is 4820 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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.x, vFront.y, vFront.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.x, vFront.y, vFront.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.x, vBack.y, vBack.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.x, vBack.y, vBack.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
Advertisement
Sign in to follow this  

  • Advertisement