# Triangulate Concave Shape

This topic is 3474 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am looking for a "good" way to triangulate a closed concave shape of vertices and edges. The basic principles I'm interested in are: 1) It must minimize "sliver" triangles that are very thin and contain really small angles. 2) It 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): If the mesh was convex, a good strategy would be Delaunay triangulization, but I want to deal with potentially very concave shapes that you would get out of a modeling program. Also, if someone knows a fast way to find the "worst possible" triangle among a sub-shape, then I have some ideas related to branch and bound algorithms that might work. I thought about this approach for a while but had no luck.

##### Share on other sites
You can start with any triangulation (CGAL has a function to do that, or you can roll your own) and then try to use flips to get rid of sliver triangles.

[Edited by - alvaro on March 16, 2009 9:46:58 PM]

##### Share on other sites
Is your problem 2D or 3D? In 2D it is much easier as a vertex only has 2 neighbours and you can work around the shape, and a vertex is either convex or concave. In 3D things are much trickier because the mesh is a complex network and vertices may be convex in one direction and concave in another.

##### Share on other sites

I guess ear clipping may not be what you're looking for, but this paper on that references some alternatives that sound useful.

##### Share on other sites
Newton physics engine is capable of performing re-triangulation of convex and concave treecollisions to remove redundant faces when the mesh is finished with optimization flag on.

You can get the geometry output back in newton by using NewtonCollisionForEachPolygonDo.

Unfortunately you will lose all UV mapping and normals when using this, but it works very well.

1. 1
2. 2
Rutin
22
3. 3
4. 4
frob
18
5. 5

• 33
• 13
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
632566
• Total Posts
3007107

×