Given an irregular polygon's vertex list, how to create internal triangles to build a flat 3D mesh efficiently?

Question

I'm using Unity, but the solution should be generic. I will get user input from mouse clicks, which define the vertex list of a closed irregular polygon. That vertices will define the outer edges of a flat 3D mesh.

To procedurally generate a mesh in Unity, I have to specify all the vertices and how they are connected to form triangles.

So, for convex polygons it's trivial, I'd just make triangles with vertices 1,2,3 then 1,3,4 etc. forming something like a Peacock tail.

But for concave polygons it's not so simple. Is there an efficient algorithm to find the internal triangles?

Answer 1

You could make use of a constrained Delaunay triangulation (which is not trivial to implement!). Good library implementations are available within Triangle and CGAL, providing efficient O(n*log(n)) implementations.

If the vertex set is small, the ear-clipping algorithm is also a possibility, although it wont necessarily give you a Delaunay triangulation (it will typically produce sub-optimal triangles) and runs in O(n^2). It is pretty easy to implement yourself though.

Since the input vertices exist on a flat plane in 3d space, you could obtain a 2d problem by projecting onto the plane, computing the triangulation in 2d and then applying the same mesh topology to your 3d vertex set.

Answer 2

I've implemented the ear clipping algorithm as follows:

1. Iterate over the vertices until a convex vertex, v is found
2. Check whether any point on the polygon lies within the triangle (v-1,v,v+1). If there are, then you need to partition the polygon along the vertices v, and the point which is farthest away from the line (v-1, v+1). Recursively evaluate both partitions.
3. If the triangle around vertex v contains no other vertices, add the triangle to your output list and remove vertex v, repeat until done.

Notes:

1. This is inherently a 2D operation even when working on 3D faces. To consider the problem in 2D, simply ignore the vector coordinate of the face's normal which has the largest absolute value. (This is how you "project" the 3D face into 2D coordinates). For example, if the face had normal (0,1,0), you would ignore the y coordinate and work in the x,z plane.
2. To determine which vertices are convex, you first need to know the polygon's winding. You can determine this by finding the leftmost (smallest x coordinate) vertex in the polygon (break ties by finding the smallest y). Such a vertex is always convex, so the winding of this vertex gives you the winding of the polygon.
3. You determine winding and/or convexity with the signed triangle area equation. See: http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm. Depending on your polygon's winding, all convex triangles with either have positive area (counterclockwise winding), or negative area (clockwise winding).
4. The point-in-triangle formula is constructed from the signed-triangle-area formula. See: How to determine if a point is in a 2D triangle?.
5. In step 2 where you need to determine which vertex (v) is farthest away from the line, you can do so by forming the triangles (L0, v, L1), and checking which one has the largest area (absolute value, unless you're assuming a specific winding direction)
6. This algorithm is not well defined for self-intersecting polygons, and due to the nature of floating point precision, you will likely encounter such a case. Some safeguards can be implemented for stability: - A point should not be considered to be inside your triangle unless it is a concave point. (Such a case indicates self-intersection and you should not partition your set along this vertex). You may encounter a situation where a partition is entirely concave (i.e. it's wound differently to the original polygon's winding). This partition should be discarded.
7. Because the algorithm is cyclic and involves partitioning the sets, it is highly efficient to use a bidirectional link list structure with an array for storage. You can then partition the sets in 0(1), however the algorithm still has an average O(n^2) runtime. The best case running time is actually a set where you need to partition many times, as this rapidly reduces the number of comparisons.

Answer 3

There is a community script for triangulating concave polygons but I've not personally used it. The author claims it works on 3D points as well as 2D.

One hack I've used in the past if I want to constrain the problem to 2D is to use principal component analysis to find the 2 axes of greatest change in my 3D data and making these my "X" and "Y".