Title sums it up. I'm looking for a simple/fast method of converting a polygon into the least number of triangles possible.

Thanks in advance.

If your polygon is simple and has N vertices, then *any* triangulation has N-2 triangles. Triangulation by ear clipping is easy to implement.

http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf ;)

WARNING! The Chazelle algorithm that quasar3d posted is notoriously complex and AFAIK has never been correctly implemented! Probably best to try something else first

The ear clipping algorithm is simple to implement on paper, but producing a reliable method of triangulating concave polygons with floating point coordinates is another story. I found that the difference between comparing floats with < and <= would often be the difference between the algorithm working perfectly or producing mess. You've also got to worry about self-intersecting polygons, which I've found is an issue with all concave polygon algorithms, as the difference between concave and self-intersecting can lie inside floating point tolerance.

Alright I've read through the Ear Clipping paper and I think I understand what's going on here. I do have one question though:



The paper is talking about "A reflex vertex is one for which the interior angle formed by the two edges sharing it is larger than 180 degrees. A convex vertex is one for which the interior angle is smaller than 180 degrees." Say I'm looking at triangle 4, 1, 2. Iterating through all my vertex's shows that 4-1-2 has no other vertex's in it so it would pass initial ear triangle tests. But 4-1-2 is not part of the actual polygon. How do I test my potential ear triangles to determine if they're reflex or convex?

You have to categorise the polygon as either clockwise or counterclockwise. First, you find a vertex which you can guarantee is convex. The best way of doing this is to choose the vertex with the minimum x coord, and minimum y coord if there are ties. Now you do a convexity check on the triangle around that vertex, which can be done by calculating the triangle's signed area. If area > 0, the triangle is counterclockwise. Area < 0 = clockwise.

Once you have the winding of a known convex vertex, you can determine if any vertex is convex, as all convex verties have the same winding, and all concave vertices have the opposite winding.

Alright, A long time getting back to this, Busy with school. Ugh.

So I've found the following (http://2000clicks.com/MathHelp/GeometryTriangleAreaVector3.aspx):

In the x-y coordinate plane, the signed areas are given by
A[sub]1[/sub] = (x[sub]3[/sub] y[sub]2[/sub] - x[sub]2[/sub] y[sub]3[/sub])/2
A[sub]2[/sub] = (x[sub]1[/sub] y[sub]3[/sub] - x[sub]3[/sub] y[sub]1[/sub])/2
A[sub]3[/sub] = (x[sub]2[/sub] y[sub]1[/sub] - x[sub]1[/sub] y[sub]2[/sub])/2

So that's in X-Y. I can't find a good example of what it would be in X-Y-Z.

The trick to solving most 3D planar problems is to just ignore one of the coordinates and treat the problem as a 2D one. Consider the normal to the plane the vertices lie in, and discard the axis with the greatest absolute value. For example, if the normal is (0,1,0), you discard the y axis and work in the x,z plane. Alhough you could actually discard any axis as long as it's normal component is not on, or close to zero.

Keep in mind if the plane is not axis aligned (and it usually isn't), then measurements in the 2D plane are different than in 3D. So when you calculate the area of the triangle around your vertices in 2D, it's not the actual area in 3D space, but it still retains all it's important properties. (For determining winding, etc).

Being able to address vectors with an array subscript is useful here. So in 2D, a 3D point is given by (P[iX], P[iY]), where iX,iY = 1,2 (x axis ignored), 2,0 (y axis ignored) or 0,1 (z axis ignored).
Or you could just copy your vertices in memory first. I actually employ a 2D iterator object that can be constructed from an array of 3D points and a normal.


float Signed_Area(vec3 Vec1, vec3 Vec2, vec3 Vec3)
{
return (float)(0.5 * (-Vec2.x * Vec1.y + Vec3.x * Vec1.y + Vec1.x * Vec2.y - Vec3.x * Vec2.y - Vec1.x * Vec3.y + Vec2.x * Vec3.y));
}


I got the idea for this here Wolfram.com. obviously it's not checking to see if anything is zero. I'll figure something out for that.