Jump to content
• Advertisement

Public Group

# Triangle Splitting

This topic is 4939 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

##### Share on other sites
Advertisement
try to google for "sutherland hodgman algorithm"

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
4. 4
frob
14
5. 5
• Advertisement

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632168
• Total Posts
3004543

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!