Triangulating non-planar polygons

Question

I would like to triangulate a non-planar polygon (i.e. the vertices do not lie in the same 3D plane). The polygon consists of many points (hundreds). The triangulated surface does not have to be smooth. In fact, the denser it is, the better.

My initial ideas were:

• NURBS
• Generating additional points "within the polygon" and applying 3D Delaunay triangulation.
• Just putting one(or few) more vertices "in the middle" and connecting them with the contour vertices.

I am not sure which of these ideas is applicable to my situation, or maybe there are even better ways?

More details: Even though the points on the contours are hundreds, they can be grouped in 3 to ~10 subsets, so that every subset closely approximates a line. The so-generated lines still don't lie in the same plane though. One can think about it as a flock of birds, which fly in a polygon, but not exactly on the same vertical height.

Answer 1

I ended up doing the following:

1. Fit a plane to the points.
2. Project the points to the plane fit.
3. Transform the points into the coordinate system of the plane fit, so that every point has a 2D coordinate (x, y) and a depth z
4. Compute the boundary of the point cloud.
5. Generate additional 2D points within the boundary (one can use either equidistant points or distorted points, with whatever density one likes).
6. Run a 2D Delaunay triangulation on all points (boundary + generated points).
7. Interpolate the depth values of the generated inner points based on the boundary depth values. Any kind of interpolation can be used - i used MATLAB's triscatteredinterp() which worked quite well.
8. Translate all points back using the inverse transform from (3)
9. Use the triangulation from (6) and the points obtained in (8).

You can see the result here: http://www.youtube.com/watch?v=4AqHxKsM7Iw&feature=g-upl