Fill hole of mesh after clipping against plane

Question

I wrote a simple algorithm which clips an arbitrary 3D object against a plane:

The algorithm roughly works like this:

1) Iterate all triangles

2) Iterate all edges for each triangle

3) If the edge intersects with the plane, either 1 or 2 new triangles are generated, old triangle is discarded

4) If no edges intersect, the triangle is either kept intact or discarded (Depending on which side of the plane it is on)

Of course, this leaves a hole on the mesh where the plane cut through it. What would be a fast way to generate a new mesh to fill the hole? For convex geometry I could just use one of the new vertices on the plane as starting point and connect it to all other new points and generate the triangles that way, however the object isn't necessarily convex.

Answer 1

If a triangle is intersected by the plane during clipping, then two of its edges are necessarily intersected and each intersected edge generate one new vertex so two new vertices are generated for this triangle (ignoring the cases where the plane intersects exactly with the triangle vertices). For every new vertex, one should then keep track of the two other new vertices created in the two triangles adjacent to the edge of the initial new vertex. Then by simply traversing all the different chains of such adjacent new vertices, one can reconstruct (possibly non-convex) filling polygons needed to close the holes of the clipped mesh. To get convex polygons or simple triangles from these polygons, apply a convex decomposition or polygon triangulation algorithm (see Polygon triangulation). This assumes that the input mesh was watertight, with proper triangle edges (one edge is only shared by two triangles) and ignores issues related to vertex / plane intersection.

In practice: whenever a new vertex is created in one triangle, keep track of the index of the other new vertex created in the same triangle (and vice-versa). Each new vertex ID thus ends up being mapped to two new vertex IDs, the one created to the "left", and the one created to the "right" of the new vertex. The "left" / "right" orientation is derived from the plane orientation and the relative orientation of the two adjacent new vertices. Once the clipping is done, pick one new vertex in the mapping, traverse the mapping in the same direction (left or right) to extract an entire polygonal chain and once this chain is closed (getting back to the first selected vertex), a new hole-filling polygon can be added to the clipped mesh. Continue selecting unused new vertices in the mapping and traversing the mapping until all the new vertices have been used in hole-filling polygons.