I am looking for a "good" way to triangulate a closed concave shape of vertices and edges.

"good" is quite a vague term, but the basic principles I'm interested in are:

1) Minimize "sliver" triangles that are very thin and contain really small angles.

2) Must be reasonable to compute. Ideally it would take less than a day to compute the triangulization for a mesh with ~10,000 vertices on a standard computer (so complete brute force is out).

Here is a diagram (initial shape in black):

http://img394.imageshack.us/img394/3077/concavetriangle.png [Broken]

If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation [Broken] method could work well if I had a fast way of finding the worst possible triangle among a subset of the shape, but I'm having no luck there.

"good" is quite a vague term, but the basic principles I'm interested in are:

1) Minimize "sliver" triangles that are very thin and contain really small angles.

2) Must be reasonable to compute. Ideally it would take less than a day to compute the triangulization for a mesh with ~10,000 vertices on a standard computer (so complete brute force is out).

Here is a diagram (initial shape in black):

http://img394.imageshack.us/img394/3077/concavetriangle.png [Broken]

If the mesh was convex, a good strategy would be http://en.wikipedia.org/wiki/Delaunay_trianglulation [Broken] method could work well if I had a fast way of finding the worst possible triangle among a subset of the shape, but I'm having no luck there.

Last edited by a moderator: