Merge overlapping triangles into a polygon

Question

I've got a bunch of overlapping triangles from a 3D model projected into a 2D plane. I need to merge each island of touching triangles into a closed, non-convex polygon.

The resultant polygons shouldn't have any holes in them (since the source data doesn't).

Many of the source triangles share (floating point identical) edges with other triangles in the source data.

What's the easiest way to do this? Performance isn't particularly important, since this will be done at design time.

Answer 1

Try gpc, or the General Polygon Clipper Library.

Answer 2

Imagine the projection onto a plane as a "view" of the model (i.e. the direction of projection is the line of sight, and the projection is what you see). In that case, the borders of the polygons you want to compute correspond to the silhouette of the model.

The silhouette, in turn, is a set of edges in the model. For each edge in the silhouette, the adjacent faces will have normals that either point away from the plane or toward the plane. You can check this be taking the dot product of the face normal with the plane normal -- look for edges whose adjacent face normals have dot products of opposite signs with the projection direction.

Once you have found all the silhouette edges you can join them together into the boundaries of the desired polygons.

Generally, you can find more about silhouette detection and extraction by googling terms like mesh silouette finding detection. Maybe a good place to start is here.