I have a love-hate relationship to all kinds of triangulations. They are super useful tools for many problems, but at the same time they are super annoying to get robust. I have been pounding my head to the wall trying to get one Delaunay triangulator to work properly.Bourke's code is broadly used and seems quite robust too, but it fails to deliver one feature, convex hull, which is really important for my use. This seems to be common problem with Delaunay triangulators which rely on super triangle as the initial state of the triangulator.
After browsing through countless of other implementations and papers I finally found a O(n^2) algorithm last night, which seems to suit my need very well (I'm talking about the O(N^2) algorithm of the Java applet). I'm not sure which algorithm it is, it does not look like any of the usual suspects. But it does not require super triangle, and there is a case which handles the hull too. Even better, the algorithm behaves well even if manually set the hull edges myself. And finally as an added bonus, the idea of the algorithm is easy to understand visually, hence, I'm able to debug it myself too when I run into problems with it again.
Most (if not all) of the existing Delaunay triangulation implementations I could find out there fail sooner or later if you have points in your input data which are along the same line. That is a condition which majority of my input points satisfies.
I'm yet to do full set of test, but so far it looks good. The Java implementation has a couple of bugs in it, especially how it handles face labels.
Looks like I can finally move the detail mesh generation off the TODO list...
[EDIT] The algorithm in question seems to be a gift wrapping variant of Delaunay triangulation. See A Comparison of Sequential Delaunay Triangulation Algorithms, the papers that paper refers to seem to be pretty hard to find.
What is the purpose of the Delaunay triangulation in recast ? Shouldn't you use constrained Delaunay triangulation ?
ReplyDeleteWhen additional points are added to the detail meshes of the navigation polygons, I use Delaunay triagulation to create trimesh of all the points within the polygon.
ReplyDeleteA few months ago I was also looking for some triangulation stuff for an idea and put up this proto test from some reference I found, proto made in Processing:
ReplyDeletehttp://jet.ro/tmp/triangulation/
At least with simple click-around-testing it felt somewhat robust already. However I didn't use that for any further stuff. If I remember correctly it was because that one didn't easily list the result as triangles, but only as edges instead.
I remember also looking at triangulation code from the geometrictools.com site, I thought it looked like robust and very usable code, but I didn't actually do any own tests with it:
http://tinyurl.com/wm4cg
LOL, I just realized that reference code I had used is exactly the same you was already talking about, after I peeked at the processing test code and found a note about the original code! My intention was to give you another pointer to a potentially usable reference. Well, at least I included the link to the other site, heh.
ReplyDeleteJetro, heh :) Thanks for the pointers. As much I like Geometric Tools stuff, their license is GPL or LGPL, which make the code unusable in some cases. Plus I find his code really hard to debug. But as you said, their code is usually robust and well behaving.
ReplyDeleteHave you seen Poly2tri?
ReplyDeletehttp://code.google.com/p/poly2tri/
@zzzzrrr, I have and it seems really good! It does have a couple of robustness problems with parallel edges (that is, magic epsilon issues :)) but other than that it seems great. I'm tempted to write a int/fixed point version of it.
ReplyDelete