Jump to content
  • Advertisement
Sign in to follow this  
Maze Master

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.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!