split triangles on overlap

Question

I have a triangle (red, below). (or a 2D mesh of triangles)

How can I compute the polygons (and in turn tessellate them) that result from subtracting a second triangle (green) from the first?

(I'm using Python and I'm looking for an explanation and pseudo-code of an approach I can take, rather than recommendations for opaque libraries. (I currently use gluTess*() to do the tessellation of polygons, but an explanation of how to do the tesselltation myself would be interesting; my pressing problem is really the Boolean operation itself though.) It will be exciting to learn and understand the solution. My triangles are always counter-clockwise winding, if that makes any difference.)

Answer 1

I'm sure you can find general purpose polygon subtraction, clipping and triangulation algorithms that can be applied, but since you're limited to triangles simpler methods apply.

The basic approach is to extend the edges of the second (green) triangle, treating them as unending lines, then split the original (red) triangle up to three times, one for each green edge that intersects the red triangle, keeping the parts that are outside the red triangle. Algorithm:

resultSet := {}   // set of triangles
currentPoly := originalTriangle
for each edge E of secondTriangle:
    if E intersects currentPoly (*):
        Extend edge E to line L
        Split currentPoly by L into outerPoly and otherPoly (**)
        // outerPoly is on the side corresponding to the outside
        // of secondTriangle (right side if going CCW)
        resultSet += triangulatation of outerPoly (***)
        currentPoly := otherPoly
if resultSet is empty:
    resultSet := originalTriangle // no intersections

(*) A line segment intersects a polygon if the segment intersects any of the polygon edges or if it is completely contained in the polygon. For this algorithm, it is best to treat coincident lines as not intersecting (since no split will occur).

(**) Algorithm for splitting a convex polygon by a line

result := [[],[]]   // two empty lists of points
intersectionCount = 0
for each point P in the polygon:
    // each point is added to one of the result polygons
    result[intersectionCount % 2] += P
    E := edge between P and the next point Q
    if E intersects L at R:
       // each intersection point is added to both result polygons
       if R is not equal to P:
           result[intersectionCount % 2] += R
       intersectionCount += 1
       if R is not equal to Q:
           result[intersectionCount % 2] += R

(***) outerPoly will always be a triangle or quadrilateral and thus trivial to triangulate.

Answer 2

Let's walk through some scenarios...

Case 1: Triangles do not overlap (or they are tangent but not overlapping)

Test for this case by using a point-in-polygon algorithm to see if any of the three vertices of one of the triangles lies inside of or on the other.

If we are in Case 1, we don't need to do anything.

Case 2: Green triangle is inside of red triangle.

Test for this case by either using a point-in-polygon algorithm to see if all three of the green vertices are inside of the red triangle. Another way to test this is to see if any of the 3 line segments of the green triangle intersect with any of the 3 line segments of the red triangle; use an algorithm like this for intersection (additionally you have to also check to make sure at least one green vertex in inside the polygon - just to make sure your lack of intersecting lines isn't because you are actually running into Case 1).

Now for this case, draw a line segment from each of the green vertices to each of the red vertices (total of 9 new line segments). If any of these new line segments cross into the green triangle then remove them (you can check for this by using the line segment intersection method against each of the green triangle's sides). Now, test to see if any of the remaining new line segments intersect with each other; if any two do, then eliminate one, and retest until you have no more new line segments intersecting with each other.

Case 3: Green triangle overlaps red triangle, where two sides of the green triangle enter into the red triangle and also leave the red triangle.

Test for this case by checking to see that exactly two green sides each intersect with two red sides. Again use the line segment intersection algorithm.

Now for this case, draw a line segment from each of the intersection points (each place where a green side intersects with a red side) to each of the red vertices. If any of these line segments basically duplicate the red edges then remove them. If any of these new line segments cross into the green triangle then remove them (you can check for this by using the line segment intersection method against each of the green triangle's sides). Now, test to see if any of the remaining new line segments intersect with each other; if any two do, then eliminate one, and retest until you have no more new line segments intersecting with each other.

Case 4: Green triangle overlaps red triangle, where two sides of the green triangle enter into the red triangle but they do not leave the red triangle out another side.

Test for this case by checking to see that exactly two green sides each intersect with exactly one red side (it doesn't necessarily have to be the same side for each). Again use the line segment intersection algorithm.

Now for this case, draw a line segment from the green vertex that is inside of the red triangle (use the point-in-a-polygon algorithm to determine which green vertex is inside of the triangle) to each of the red triangle vertices.

Case 5: Green triangle overlaps red triangle, where only one side of the green triangle enter into the red triangle and where that same green side exits a different side of the red triangle.

Test for this case by checking to see that exactly one green side intersects with exactly two red sides. Again use the line segment intersection algorithm.

Now for this case, draw a line segment from each of the intersection points (each place where a green side intersects with a red side) to each of the red vertices. If any of these line segments basically duplicate the red edges then remove them. If any of these new line segments cross into the green triangle then remove them (you can check for this by using the line segment intersection method against each of the green triangle's sides). Now, test to see if any of the remaining new line segments intersect with each other; if any two do, then eliminate one, and retest until you have no more new line segments intersecting with each other.

And hopefully at this point you are done!