Jump to content
  • Advertisement
Sign in to follow this  
Aph3x

Anyone used Magic's Delaunay2 code?

This topic is 5031 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

Found some 2d Delaunay code on magic software's site; has anyone here managed to use this code successfully? It seems to be giving me incorrect triangulations :-/ Maybe I'm not using it correctly..?

Share this post


Link to post
Share on other sites
Advertisement
To expand, given the 4 points:


2
1

0 3






Results in 3 triangles:
1: 0-3-1
2: 0-2-3
3: 3-2-1

Which AFAIK would be fine if triangle 2 wasn't generated, as point 1 is inside the circumcircle (0-2-3)

Share this post


Link to post
Share on other sites
Are your input points random or uniformly spaced? Uniformly-spaced points can give Delaunay triangulation algorithms fits. Jonathan Richard Shewchuk's code, Triangle, is probably vastly more robust and maybe faster than Magic's.

Share this post


Link to post
Share on other sites
They're 'human-random' - that is, I placed them randomly myself ;)
The redundancy in the output above is actually a smaller problem - with my full 'random' network I'm getting a nonsense triangulation.
Hmmm Triangle has some licensing attached iirc (and the source is HUGE!).
Gah, maybe I'll just try and implement my own version as you suggested in the other thread!

Actually, I'm wondering if I should look for a different partitioning scheme altogether - I need a Delaunay triangulation algorithm that will always succeed given arbitrary points - something I've not seen promised by any algorithm so far..!?

Share this post


Link to post
Share on other sites
Quote:
Original post by Aph3x
Actually, I'm wondering if I should look for a different partitioning scheme altogether - I need a Delaunay triangulation algorithm that will always succeed given arbitrary points - something I've not seen promised by any algorithm so far..!?


That's a tall order to fill. Coincidentally I recently implemented a Delaunay triangulation algorithm based on the Guibas and Stolfi algorithm. It breaks sometimes. I had messed around for literally weeks trying to do something "smarter" than Deluanay, given that I had some known structure to my data. But, the special cases and logic become unwieldy and impossible to deal with so I ultimately reverted back to general purpose Delaunay. Sadly, in terms of code that one can get ones hands one, Shewchuk's Triangle is probably the most reliable, simply because he uses his robust predicates (read exact floating point arithmetic), which precisely calculate circumcircle containment and line left-of/right-of for a point. Even his code only works on machines with true IEEE 64-bit floating point precision. Its these darned incircle and left-of/right-of tests that break Delaunay triangulations for certain cases.

Now, what you could possibly do is take Shewchuk's robust predicate code---which might be available without licensing contingencies---and use his incircle and left-of/right-of tests within your own incremental insertion algorithm. In this way, you could probably create a quite robust incremental algorithm on your own. You'd end up with something that only works on machines with IEEE 64-bit floating point---on Intel machines this requires that you disable internal 80-bit precision using a special assembly language call. The incremental algorithm is a bit more intuitive. My own preferred description for incremental insertion is by Mark de Berg et al. in their book "Computational Geometry: Algorithms and Applications" (ISBN 3-540-61270-X). I find this to be a better description than Eberly's. I believe somewhere on the web there is a powerpoint presentation for a University course that is basically verbatim the algorithm from this book. Might be a presentation from one of the co-authors.

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_work
That's a tall order to fill.


I suppose I can relax the robustness constraint a bit if I can determine if and where it goes wrong/fails (and then move the point in question).

I'll look at that predicate code some more - don't like messing with the internal stuff though - trying to make this as portable as possible.

Incidentally, do all these problems stem from the fact that the algorithms are avoiding a brute force approach - i.e. would a brute force approach work all the time albeit slowly? I've seen an O(n^4) algorithm somewhere...
My point set is only small (16 to 128) and the triangulation will be calculated before the game starts.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aph3x
I suppose I can relax the robustness constraint a bit if I can determine if and where it goes wrong/fails (and then move the point in question).


You could probably detect, robustly, when it MIGHT fail, then always move a point where it just might fail. The issue you deal with here is....where do you move the point? What if moving it causes another potential failure. With so few points, this might not be too worrisome.

Quote:
Original post by Aph3x
Incidentally, do all these problems stem from the fact that the algorithms are avoiding a brute force approach - i.e. would a brute force approach work all the time albeit slowly? I've seen an O(n^4) algorithm somewhere...
My point set is only small (16 to 128) and the triangulation will be calculated before the game starts.


The brute force approach simply does an exhaustive search for each point to find the nearest 3 points, checks the two possible circumcircles, then picks the smallest circumcircle. Very slow, but, yes, in your case possibly okay.

The problems do and they don't. Ha! With a brute force approach, yes, you could avoid the failures. But, when there are problem areas, where points are colinear or cocircular, with a brute force approach you have the possibility of generating a folding mesh, e.g., you could get overlapping triangles. To avoid the overlapping triangles even in the brute force approach, you still are faced with the robust predicate test...

I have a question for you. If your points are created manually, by an artist say, why not also manually triangulate them as part of the art asset generation for the game? Why bother doing this at runtime. Pre-triangulate, actually just pre-build a mesh in a modeling package. Avoid the need for an algorithm altogether?

Share this post


Link to post
Share on other sites
Quote:
Original post by grhodes_at_workI have a question for you. If your points are created manually, by an artist say, why not also manually triangulate them as part of the art asset generation for the game? Why bother doing this at runtime. Pre-triangulate, actually just pre-build a mesh in a modeling package. Avoid the need for an algorithm altogether?


Good question :) - it leads me to another problem I need to solve that sounds easier than I've found it to be: the random positioning of my points to conform to gameplay constraints.
It's basically an island archipelagos that requires two base islands at opposite extremities, with no islands too close or too far apart. So far I've been using a test set of 16 islands nicely hand-positioned to conform. The Delaunay triangulation is used as a graph to make various partitioning and adjacency calculations more efficient in my 'engine'.
I suppose if the problem beats me I can have a large database of pre-built maps (but conceding this would just annoy me ;)

Quote:
Original post by grhodes_at_work...with a brute force approach you have the possibility of generating a folding mesh, e.g., you could get overlapping triangles. To avoid the overlapping triangles even in the brute force approach, you still are faced with the robust predicate test...


So not inserting duplicates into the graph may be a workable solution this way :)

[Edited by - Aph3x on December 3, 2004 3:36:02 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Aph3x
(but conceding this would just annoy me ;)


I hear you! Sometimes, sometimes don't you just...FEEL that there is an elegant, robust solution? I hear you.

Quote:
Original post by Aph3xSo not inserting duplicates into the graph may be a workable solution this way :)


Hmmmm. No, but it helps. Actually, your Delaunay algorithm would need to remove duplicates anyway. They do cause problems. But its more than duplicates. Points that are colinear cause problems (any combination of 3 or more in your set). Points that are cocircular cause problems. Even if they are not dupes. Its tedious to manually...or randomly...create points that are guaranteed such that no 3 or more are colinear or cocircular. Damned limited precision math.

Share this post


Link to post
Share on other sites
I've recently had great success using the Delaunay methods in GEOMPACK++. The procedure you'll want to use is rtris2; there's also a naive O(n4) procedure included. rtris2 has a couple of wackinesses, primarily the fact that vertex indices and triangle neighbor indices returned count from 1 instead of 0, and that it takes your points and sorts them for you. (It is possible to undo this sorting; tell me if you want more info on this).

[Edited by - Sneftel on December 3, 2004 5:24:21 PM]

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!