Sign in to follow this  
Maze Master

Triangulate Concave Shape

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this