views:

423

answers:

4

Does anybody know what triangulation algorithm Maya uses? Lacking that, what would be the most probable algoritms to try? I tried a few simple off the top of my head (shortest/longest resulting edges, smallest minimum angle, smallest/biggest area), but they where all wrong. Is Delaunay the most plausible algoritm?

Edit: by the way, pseudo code on how to implement Delaunay for a 2D quad in 3D space to generate two triangles are more than welcome!

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

+1  A: 

You might try looking at Voronoi and Delaunay Techniques by Henrik Zimmer. I don't know if it's what Maya uses, but the paper seems to describe some common techniques.

andand
Looks interesting, I'll check it out.
Jonas Byström
+1  A: 

I don't like to second-guess people's intentions but if you are simply trying to get out of Maya what is shown in the viewport you can extract Maya's triangulation by starting with MItMeshPolygon::getTriangles.

(The corresponding normals and vertex colours are straightforwardly accessible. UVs require a little more effort -- I don't remember the details (all my Maya code is with my ex employer) but whilst at first glance it may seem like you don't have the data, in fact it's all there, just not conveniently.)

(One further note -- if your artists try hard enough, they can create polygons that crash Maya when getTriangles is called, even though they render OK and can be manipulated with the UI. This used to happen every few months, so it's worth bearing in mind but probably not worth worrying about too much.)

If you don't want to use the API or Python, then running polyTriangulate before exporting, then undo afterwards (to get back the original polygons) would let you examine out the triangulated mesh. (You may want or need to save the scene to a temp file, then reload it afterwards and use file to give it its old name back, if your export process does stuff that is difficult or impossible to undo.)

This is a bit hacky, but you're guaranteed to get the exact triangulation Maya is using. Rather easier than writing your own triangulation code, and almost certainly a LOT easier than trying to work out whatever Maya does internally...

brone
Unfortunately I have mel, but no access to the C api (tool chain nearly done, I'm not replacing it). Sheesh, I'm getting increasingly annoyed by Maya's internals, since I sorta took the path of the reverse engineering idiot many months back. :)
Jonas Byström
I take it this IS what you're trying to do then? If you can't use the Python bindings to the C++ API, then maybe something like "polyTriangulate, export, undo" would help. (Alternatively, save scene to temp file, triangulate, export, reload, use "file" to give it its old name, in case your export does some random stuff that mucks with the undo queue.) A bit hacky, but rather easier than writing your own triangulation code, and I'm willing it bet it would be a LOT easier than trying to work out whatever Maya does internally...
brone
Of course you're right. It took me two days and one night of trial-and-error to realize that. Thanks for the good advice anyway. :)
Jonas Byström
I've updated the answer so it includes the gist of my comment, for future searchers...
brone
A: 

Here you can find an applet that demonstrates the Incremental, Gift Wrap, Divide and Conquer and QuickHull algorithms computing the Delaunay triangulation in 3D. Pointers to each algorithm are provided.

belisarius
+1  A: 

Jonathan Shewchuk has a very popular 2D triangulation tool called Triangle, and a 3D version should appear soon. He also has a number of papers on this topic that might be of use.

Suresh
Fwiw, his triangle.c (2005) is 16k lines, including 1k help; enjoy
Denis