One note. If all you have is vertices, and you have not prescribed certain edges as being the boundary, then there is NO unique concave polygon that contains the points. There is, however, a unique minimal convex hull, which would be found by using a standard Delaunay triangulation of a 2D point cloud. The most efficient technique here would probably be the divide and conquer algorithm described in detail by Guibas and Stolfi, though efficient incremental and sweepline algorithms also exist. The incremental algorithm is easiest.

If you desire a concave boundary, then you will have to either specify the boundary edges explicitly (which would give you a polygon that can feed Siedel's algorithm), or come up with a set of rules for deciding which edges will become the boundary. I'm not aware of any specific rule set for reconstructing concave objects from point clouds, but you might look at Hughes Hoppe's web page at research.microsoft.com. He's done work on reconstruction of concave meshes (not polygons per say) in 3D.

Hey Matt,

The ear-clipping method is a good way to map a concave polygon into so-called "monotone" pieces that can individually be triangulated using a convex triangulation method, then stitch them back together. This is certainly appropriate.

You are correct that a true Delaunay triangulation would not work. Unfortunately, constrained Delaunay is FAR from easy to implement. I would steer you away from trying to implement that; however, you may find Jonathan Shewchuk's code, Triangle, is available as source code for free and supports constrained Delaunay using the divide and conquer technique. You still need to *know* which edges are boundary here, as those edges become the constraints.

Jonathan Shewchuk's Home Page

As for gluNewTess.. I think you're just not interpreting the input correctly. You specify a series of vertices, but those vertices are in a certain order that explicitly defines the boundary edges (each vertex in the list creates an edge back to the prevous vertex). Probably, gluNewTess expects the vertices to be listed in an order that defines the polygon counterclockwise.

Note that if gluNewTess can deal with 3D polygons, internally it actually does a 2D triangulation. It does this by computing the normal vector to the polygon, creating a coordinate system with 2 axes in that plane, then projects the points into the plane. Once the points are in the plane, it treats the vertices as 2D, and uses a 2D approach. My prior post (the one lost due to timeout---GRRRR, bad gamedev!) went into this process in detail. gluNewTess *may* be able to deal with nonplanar polygons (any "polygon" in 3D with more than 3 vertices might not actually be perfectly planar, and in fact might be far from planar). BUT, nonplanar polygons can cause difficulties depending on how the projection plane for the 2D mapping is chosen.

I am not going to have time to show you all the math for mapping a 3D polygon into 2D. It is unfortunate my prior post was lost, since I did give all the math you need. But, here is a summary:

1) Choose one vertex of the polygon to be the local origin, O = (O.x, O.y, O.z).

2) Create a unit vector from O to the next vertex along an edge connected to O. Call the unit vector X = (X.x, X.y, X.z). This will be the direction of the X axis in the 2D plane in which you will be doing the triangulation

3) Find a unit normal vector to the polygon by taking X and any other edge that is not parallel to X and doing a cross product. (See articles here at gamedev or do a forum search to learn how to do a cross product). Call the normal Z = (Z.x, Z.y, Z.z).

4) Do another cross product, Y = Z cross X, and normalize it for good measure. (We need to make sure it has length 1.0).

5) Now, X and Y are the two directions that define the plane in which you will do the triangulation.

6) Form a 3 x 3 rotation matrix:

    [X.x X.y X.z]R = |Y.x Y.y Y.z|    [Z.x Z.y Z.z]

This is the so-called "world to object" rotation matrix, which maps vectors in world space into the coordinate system of interest, e.g., it converts vectors in world space into the coordinate system given by X, Y, and Z. The transpose of R is the object to world rotation matrix, which takes vectors in the object's space and maps them to the world. (The tranpose rules is only true if R contains no scaling factors...this one does not, since we made sure X, Y, and Z all had length 1.0).

7) Now, map all your polygon vertices:

V_mapped = R * (V_world_space - O)

8) Now that all your vertices are mapped, your V_mapped vectors *are* the 2D vertices you need! Just drop the Z coordinate!

So, except for telling you how to do the matrix and vector math in the formula for V_mapped, that is all the math to do the 3D to 2D conversion! Articles here on gamedev should give you all the matrix & vector math you need to carry it out!

I think gluNewTess probably doesn't do generalized ear-clipping. I think it uses a plane sweep to divide the triangle into trapezoids, which are easily triangulated. Similar to ear-clipping, and easy enough to implement.

Posting now. Here goes nothing!