Three-dimensional triangle algorithm

Question

Does anyone know which Maya triangulation algorithm uses? If this is not done, then what are the most likely algorithms? I tried a few simple ones from the top of my head (shortest / longest resulting edges, minimum minimum angle, smallest / largest area), but they are all wrong. Is Delaunay the most plausible algorithm?

Edit: By the way, the pseudo-code on how to implement Delaunay for 2D quad in 3D to create two triangles is more than welcome!

Edit 2: Unfortunately, this is not an answer in 3D space (applicable only in 2D).

Answer 1

I don’t like to intrude on people's intentions, but if you just try to get out of Maya, which is shown in the viewport, you can extract the Mayan triangulation by starting with MItMeshPolygon::getTriangles .

(Corresponding normals and vertex colors are simply available. UV requires a little more effort - I don’t remember the details (all my Maya code is with my former employer), but at first glance this may seem to you to have no data, in fact everything is there, just not conveniently.)

(One more note: if your artists try their best, they can create polygons that break Maya when calling getTriangles , even if they display OK and can be controlled using the user interface. This happened every few months, so keep in mind but probably don't worry about too much.)

If you do not want to use the API or Python, then before exporting polyTriangulate , then undo (to return the original polygons) will allow you to examine the triangulated mesh. (You may want to, or need to save the scene in a temporary file, then reload it and use file to return its previous name if your export process does things that are difficult or impossible to undo.)

This is a bit hacky, but you are guaranteed to get the exact triangulation that Maya uses. It is rather easier to write your own triangulation code and almost certainly LOT is easier than trying to work out what Maya does internally ...

Answer 2

You can try to take a look at the Voronoi and Delaunay Techniques from Henrik Zimmer. I don't know if this uses maya, but the document describes some common methods.

Answer 3

Jonathan Shelchuk has a very popular 2D triangulation tool called Triangle, and a 3D version is due to appear shortly. He also has a number of articles on this topic that may be useful.

Answer 4

Here you can find an applet that demonstrates the algorithms of incremental, gift wrapping, separation and subjugation and QuickHull, which calculate Delaunay triangulation in 3D. Pointers to each algorithm are indicated.