curved 3d surface triangulation

Hmmm, how much Information on the surface do you have? Any chance of treating it as manifold? Then you could use geodesic lines as Scan Lines to determin convex/concave and still use a modified ear-clipping algorithm.

I have no information about the order of the vertices.. I just know that they are stored as a ccw chain, but absolutely no idea which point is the start..

These two sentences confuse me. First you say you know nothing about the order; then you say they're stored as a CCW chain. Which is it? When you say you know nothing about the order, do you simply mean that you have "no idea which point is the start?" But how is a "start" in a loop meaningful?

I'm going to assume that you have a sequence of vertices x[sub]0[/sub], x[sub]2[/sub], ..., x[sub]N-1[/sub] in R[sup]3[/sup], and that the i-th vertex is connected by a line segment to the vertices with indices mod(i-1,N) and mod(i+1,N).

Then, I'd think about the problem in the following way: I'd look for a smooth real-valued function on R[sup]3[/sup] such that
1.) it's zero at the vertices and on the line segments connecting them
and
2.) its gradient is nonzero everywhere.
Then, the zero-level set of this function will be a "membrane" across this closed loop; you can draw it with e.g. marching cubes/tetrahedra. The reason I've included condition (2) is that I want to make sure that the zero-level set is two-dimensional.

What this leaves is how to compute such a function. My first impulse is to use the heat equation. You'd have some sort of mixed boundary conditions... let's see... how about the mixed Dirichlet/Neumann conditions,
1.) f(x) = 0 for all x in B (B is a subset of R[sup]3[/sup]; it's the image of the closed curve described by the vertex sequence)
2.) grad f(x) = g(x) for all x in B
where g is a function specifying the gradient on the boundary. In particular, I guess a reasonable way to define g is as the binormal to the curve at each point (i.e., the vector perpendicular to both the normal (centrifical force vector), and tangent vectors; get it through a cross product).

There might be better ways to do this though... in particular, I'm not thrilled with the idea of manually specifying the gradient... Still, I think that this is on the right track...

(EDIT: This paper looks promising... In particular, see Fig. 28; that's exactly what I was picturing... I also realized that "soap film" is a good search term.... One intro to level set methods for curvature flow can be found here; in general this author (Sethian) is the guy to go to for level-set methods.)

--- EDIT:

triangulate a single quasi-rectangular (convex and slighlty concave vertices) U-shaped face (2xn 3d points)..

In this case, I think I have an answer. If you know a-priori that your loop is a "quasi-rectangle," then you can also a-priori build a 2d grid with the given vertices on its boundary. Then, interpolate x, y, and z coordinates separately across this grid. The plain old heat equation in 2d with Dirichlet boundary conditions gives a way to do this.

--- EDIT 2:

I don't know how much sense it even makes to try to come up with a robust solution that "always works." Clearly there are closed curves that are not the boundaries of 2-manifolds-with-boundary -- just consider knots. I suppose you could look for a method that works for all curves that are knot-equivalent to the circle... but this seems hard...

...all of which makes a parametric/Lagrangian approach (as suggested in EDIT 2) actually look more attractive to me. It's extremely straightforward: The x, y, and z coordinates, respectively, can each be thought of as scalar values specified at points on the boundary of a square/rectangle/disc in the plane; then you can use the interpolation method of your choice -- e.g., heat equation, radial basis functions, etc -- to interpolate between them in the interior of the square/rectangle/disk. The nonexistence of self-intersections is not guaranteed, but, hey, trying to avoid that itself opens up a whole can of worms, so maybe we should just accept that... Then you just map a regular grid in 2d through this parametrization, and you're done. In the end, this is a pretty straightforward approach..

(And I hope the "brainstorming aloud" style I've used here hasn't been too confusing.)

WOAH.. Emergent you have my respect..

and I guess you really got the point.. I will look into your answer more deeply in the next days, but for sure you gave me some good tracks..
thank you

The question I have is...do you have an equation for the curved 3D face? For example, is the surface itself a sphere? Does the boundary you describe merely represent a trim curve applied to some otherwise known surface shape? For example, you could triangulate a sphere (geodesic tesselation mentioned by Kayzaks for example), then clip the triangulation according to the boundary curve. An outline, for the case that you already have some kind of analytic surface equation for the *surface* shape would be something like:

1) Tessellate the surface, ignoring the boundary curve. Pay attention to error, e.g., tessellate so that the flat triangles are close to the actual analytic surface. (A whole post could talk about this, but you could just do it experimentally.)
2) "Draw" or project the tessellated triangles into the parameter space of the surface. (For example, if the surface is a perfect sphere, your parameter space would be based on spherical coordinates. If the surface of a cylinder, then cylindrical coordinates. If a bicubic spline, then there are two parametric orthogonal directions, often designated u and v, and so the parametric space would be uv space.)
3) Project your boundary curve into that same parametric space.
4) Trim the surface triangulation (in parameter space) by clipping against the projected boundary curve and for any triangle that is no longer a triangle, triangulate that using ear clipping (for example). This would not introduce new points (other than the points on the boundary). It would only introduce new triangles.
5) The result will give you triangles that define the triangulated 3D surface, and exactly matching a polyline loop that connects the trim points together. Just point the triangle corner indices at the 3D, unprojected version of your vertices instead of the parameter space projected coordinates.

I know a picture would help, but hopefully that makes sense. This, to me, is intuitive. Kind of messy to implement, but workable, and if you can easily determine a parametric space for the surface shape it should work for any surface.

If your surface (apart from the boundaries) is defined by points also, then you'd have to fit a surface somehow.

If you look at the way hardware tessellation works (e.g., DirectX 11), you'll find that it is not unlike what I describe in that tessellation is basically done in a 2D parameter space (the projection from your 3D input into the 2D parameter space being done with a "hull shader") and generates triangles in parameter space that conform to a prescribed boundary, then with the final 3D surface triangles being determined in a "domain shader" that maps from the 2D parameter space triangles back into 3D. The hull and domain shaders basically do exactly what I was trying to describe above when talking about the analytic surface. Hardware tessellation happens to be way constrained, e.g., surfaces are "patches" that are pre-trimmed to the boundary, and there are fixed tesselation rules for the way the boundary is treated that avoid the need to ear clip boundary polygons (the tessellation rules produce only triangles, though they aren't necessarily high quality, low aspect ratio triangles). But it does strongly resemble what I described above.

To follow up, the real search term I think you're looking for is minimal surface. (Though, grhodes and I have interpreted your question quite differently from one another.)