Triangle splitting and polygon triangulation

Triangle splitting

The first problem I needed to solve was how to split a mesh (at least a convex one) in two with a plane. This will hopefully be a helpful tool for severing arms, legs and heads 🙂

1
A simple cube and a split plane

I started by splitting all the mesh triangles that intersect the splitting plane. The splitting algorithm I wrote is based on two very helpful articles written by Randy Gaul:

After the split we have a bunch of triangles that are on one side of the plane and a bunch of triangles that are on the other side of the plane. One could use these triangles to output two meshes but they would be missing a face (the intersection area).

Filling ”the gap”

Intersection polygon

So both of the meshes (or ”bunch of triangles”) created have an intersection area that has to be filled. This can be done by calculating a polygon from the intersection area and triangulating that into a face.

Triangles that are ”touching” the intersection plane have vertices that are on the intersection plane. From these vertices, I calculated the longest ”streak” of vertices that are connected to each other (with an edge) trying to ”get around” the intersection area. Hopefully this forms an edge loop (first and last vertices are connected) and we have the polygon that we can fill.

Triangulation

Filling a polygon means (in this context) triangulating the polygon. I used an simple polygon ear clipping method described in Ear-clipping Based Algorithms of Generating High-quality Polygon Triangulation.

Splitting a mesh and triangulating the intersection area were my first steps in this coding adventure. The first implementation was not very robust and needed many optimizations to reduce excess triangle creation. I will try to write about them in the following articles.

2
Cube split in two (meshes)
4
Triangulated intersection area in a cylinder showing very ”thin” triangles caused by the ear clipping method