Thread: [Algorithms] Cutting Ears Algorithm
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Johan G. <spi...@gm...> - 2009-01-27 20:27:39
|
I have implemented the cutting ears algorithm for polygon triangulation but have run into a problem. The algorithm will cycle thru all vertices of the polygon and determine if the given vertex makes an ear (triangle that does not contain any other point), if a vertex is determined to be an ear a triangle will be created and the vertex is removed from the search space. The problem is when a vertex that is an ear is shared between other vertices that cannot become an ear by themselves, consider a triangle fan where the first vertex fans out to 4 other vertices on a straight line, the first vertex will be considered an ear and create the first triangle but the algorithm will remove it from the search space and the remaining 4 vertices cannot make another ear causing a valid simple polygon to fail the triangulation. My questions are, is the algorithm uncapable of handling this scenario or have I simply implemented it incorrectly? Any idea how I would go about modifiying the algorithm to handle this case? |
|
From: Bill B. <wb...@gm...> - 2009-01-27 20:45:24
|
On Wed, Jan 28, 2009 at 5:27 AM, Johan Gustafsson <spi...@gm...> wrote: > I have implemented the cutting ears algorithm for polygon triangulation > but have > run into a problem. The algorithm will cycle thru all vertices of the > polygon and > determine if the given vertex makes an ear (triangle that does not > contain any other > point), if a vertex is determined to be an ear a triangle will be > created and the > vertex is removed from the search space. The problem is when a vertex > that is > an ear is shared between other vertices that cannot become an ear by > themselves, > consider a triangle fan where the first vertex fans out to 4 other > vertices on a > straight line, the first vertex will be considered an ear and create the > first triangle but > the algorithm will remove it from the search space and the remaining 4 > vertices > cannot make another ear causing a valid simple polygon to fail the > triangulation. > > My questions are, is the algorithm uncapable of handling this scenario > or have I > simply implemented it incorrectly? > > Any idea how I would go about modifiying the algorithm to handle this case? The problem is that you need to extend your "triangle contains any other point" test to also include points that are exactly on the edge from vertex i-1 to i+1. Of course you will then run into numerical issues with testing such things in your case above, so you need to use exact arithmetic, or introduce some evil tolerances. Or what you might try is to pick the ear that maximizes the signed distance from the i-1, i+1 edge to all other vertices. Since you're guaranteed that there are always 2 genuinely valid ears, this should always find you a decent ear to clip. --bb |
|
From: Johan G. <spi...@gm...> - 2009-01-27 21:00:25
|
Yes thank you bill, I had forgot to include the edge case in my point-triangle intersection test and once added it seems the algorithm will handle even this case without any modifications. |
|
From: Simon F. <sim...@po...> - 2009-01-28 15:24:30
|
Bill Baxter wrote: > On Wed, Jan 28, 2009 at 5:27 AM, Johan Gustafsson > <spi...@gm...> wrote: >> I have implemented the cutting ears algorithm for polygon >> triangulation but have run into a problem. The algorithm will cycle > The problem is that you need to extend your "triangle contains any > other point" test to also include points that are exactly on the edge > from vertex i-1 to i+1. Of course you will then run into numerical > issues with testing such things in your case above, so you need to > use exact arithmetic, or introduce some evil tolerances. I just wanted register my vote for using exact maths. I initially tried using epsilons in my triangulation code (which handled self-intersections) but it did not turn out well. I rewrote it using exact mathematics and it was much cleaner. Cheers Simon |
|
From: Graham R. ARA/S. <gr...@ar...> - 2009-01-27 21:23:32
|
The standard ear-clipping algorithm can be problematic when you have some vertices that are collinear. You can play with more robust predicates to test to see if points are on the boundary edge of the ear, but my suggestion is to change the ear test such that instead of testing to see if any points lie inside the candidate ear triangle, test to see if any points lie inside the circumcircle of candidate ear triangle. This is a Delaunay constraint, and it will yield much better results, e.g., fewer slivers or degenerate triangles. In your example case, the circumcircle is much larger than the triangle. All of the collinear points (except the two end ones) will be inside the circumcircle, and because of this that first candidate ear will fail. You'll move to the next point, which will more than likely pass the test and you'll be able to remove that ear. But, I wonder if you are thinking about the problem incorrectly? You mentioned that you have a triangle fan. That's already triangles. Why are you triangulating it? To triangulate this...I suppose, you would find the boundary polygon, which is not a triangle fan, then triangulate the boundary polygon using ear-clipping... Graham -----Original Message----- From: Johan Gustafsson [mailto:spi...@gm...] Sent: Tuesday, January 27, 2009 3:27 PM To: Game Development Algorithms Subject: [Algorithms] Cutting Ears Algorithm I have implemented the cutting ears algorithm for polygon triangulation but have run into a problem. The algorithm will cycle thru all vertices of the polygon and determine if the given vertex makes an ear (triangle that does not contain any other point), if a vertex is determined to be an ear a triangle will be created and the vertex is removed from the search space. The problem is when a vertex that is an ear is shared between other vertices that cannot become an ear by themselves, consider a triangle fan where the first vertex fans out to 4 other vertices on a straight line, the first vertex will be considered an ear and create the first triangle but the algorithm will remove it from the search space and the remaining 4 vertices cannot make another ear causing a valid simple polygon to fail the triangulation. My questions are, is the algorithm uncapable of handling this scenario or have I simply implemented it incorrectly? Any idea how I would go about modifiying the algorithm to handle this case? ------------------------------------------------------------------------ ------ This SF.net email is sponsored by: SourcForge Community SourceForge wants to tell your story. http://p.sf.net/sfu/sf-spreadtheword _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t |
|
From: Jon W. <jw...@gm...> - 2009-01-27 22:57:04
|
Johan Gustafsson wrote: > vertex is removed from the search space. The problem is when a vertex > that is > an ear is shared between other vertices that cannot become an ear by > themselves, > consider a triangle fan where the first vertex fans out to 4 other > vertices on a > straight line, the first vertex will be considered an ear and create the > first triangle but > the algorithm will remove it from the search space and the remaining 4 > vertices > cannot make another ear causing a valid simple polygon to fail the > triangulation. > > My questions are, is the algorithm uncapable of handling this scenario > or have I > simply implemented it incorrectly? > The algorithm works fine. I don't understand why you think that the remaining 4 vertices couldn't make triangles that make ears? Even if it's concave, it will have at least 2 ears, unless it's also self-intersecting and/or flips winding. Sincerely, jw |
|
From: Bill B. <wb...@gm...> - 2009-01-28 00:23:09
|
On Wed, Jan 28, 2009 at 7:56 AM, Jon Watte <jw...@gm...> wrote: > Johan Gustafsson wrote: >> vertex is removed from the search space. The problem is when a vertex >> that is >> an ear is shared between other vertices that cannot become an ear by >> themselves, >> consider a triangle fan where the first vertex fans out to 4 other >> vertices on a >> straight line, the first vertex will be considered an ear and create the >> first triangle but >> the algorithm will remove it from the search space and the remaining 4 >> vertices >> cannot make another ear causing a valid simple polygon to fail the >> triangulation. >> >> My questions are, is the algorithm uncapable of handling this scenario >> or have I >> simply implemented it incorrectly? >> > > The algorithm works fine. I don't understand why you think that the > remaining 4 vertices couldn't make triangles that make ears? Even if > it's concave, it will have at least 2 ears, unless it's also > self-intersecting and/or flips winding. > In the situation he's describing he's left with just 4 collinear vertices because of his initial choice of ear to snip. --bb |
|
From: Jon W. <jw...@gm...> - 2009-01-28 01:12:01
|
Bill Baxter wrote: > In the situation he's describing he's left with just 4 collinear > vertices because of his initial choice of ear to snip. > Great! He's done! Unless he wants to avoid T junctions. In that case, he'll need slivers. Whether you want slivers plus a big triangle, or a number of small triangles, probably depend on a bunch of situation-specific parameters, though. The naive ear clipping can generate these slivers for him, too (by relaxing the "no zero area triangles" rule when there is no other ear to clip). Sincerely, jw |
|
From: Bill B. <wb...@gm...> - 2009-01-28 01:30:00
|
On Wed, Jan 28, 2009 at 10:11 AM, Jon Watte <jw...@gm...> wrote: > Bill Baxter wrote: >> In the situation he's describing he's left with just 4 collinear >> vertices because of his initial choice of ear to snip. >> > > Great! He's done! > > Unless he wants to avoid T junctions. In that case, he'll need slivers. > Whether you want slivers plus a big triangle, or a number of small > triangles, probably depend on a bunch of situation-specific parameters, > though. The naive ear clipping can generate these slivers for him, too > (by relaxing the "no zero area triangles" rule when there is no other > ear to clip). Good point. Some algorithms are perfectly happy to accept degenerate tris as input. --bb |
|
From: Johan G. <spi...@gm...> - 2009-01-28 13:59:51
|
Thanks for the feedback and even though I think the algorithm will work for my current needs I would like to get some information on certain subjects you have all brought to the table. First I'd like to define my problem and the reason why I'm triangulating (even shapes that are already triangles fans) I'm working on an editor that works in 2D space where the user creates shapes (simple polygons) and inorder to render the created polygons I triangulate the shapes and send them off as triangle lists to the renderer. Performance is not a primary concern since the number of vertices and shapes are relatively low. Since the user input can indeed be already defined triangles, like the trianglefan previously mentioned the algorithm will still process it. At the moment the editor seems to run just fine but I get scared when I hear words like sliver since I dont even know what a sliver is (english is not my 1st language), if someone could explain what a sliver is and how one could occur or methods to avoid it please amuse me. Further you guys mention degenerate triangles, I presume the algorithm can only cause a degenerate triangle to occur if the user inputs 3 colinear vertices or the point in triangle test fails to include border cases (my triangle fan example). The first case is simple to avoid but the second case might be harder to avoid because of numerical stabilities during the point in triangle test. Have I understood it correctly that exchanging the point in triangle to use a Delanuay constraint will solve this problem? I'm having a hard time visualising this. |
|
From: Graham R. ARA/S. <gr...@ar...> - 2009-01-28 16:33:35
|
Hi, I'll try to answer a couple of your questions. First, a "sliver" is a triangle that is slender, e.g., if you look at it, it is long in one dimension but short in the other dimension. Another way to look at it is that the ratio of the triangle area to the circumference is small....it is nearly but not quite degenerate. The Delaunay constraint will greatly reduce the occurrence of slivers and degeneracies. In practice, it also tends to *reduce* the need for "robust predicates" (e.g., the exact math point-in-triangle tests that some have mentioned in this thread). In particular, if you have several collinear points as in your example case, the use of the Delaunay constraint would generally prevent the algorithm from choosing that first large ear...it would instead lead you to remove vertices along the collinear grouping first, rather than removing the vertex on the opposite side. You would in that case never create any degenerate triangles. We had a need, a couple of years ago, to triangulate some very, very strange polygons that on one side have several *hundred* non-uniformly spaced but collinear points and on the other side highly irregular, non-collinear points. The traditional point-in-ear test fails miserably (slivers, degeneracies, T-intersections that we could not accept), but the Delaunay constraint test has proven to be extremely robust and gives us high quality tessellations that rarely have slivers and never have degeneracies. There is a caveat with the Delaunay constraint: sometimes none of the candidate ears will be able to satisfy this constraint (for example, if you have more than 3 points on a circular arch). So, therefore, if you add the Delaunay constraint you have to also have the point-in-ear test, which you will use to choose an ear if you aren't able to find a Delaunay ear. (A 4th, 5th, 6th, n-th point on a circular arch will be outside the triangular ear so will allow you to find those ears using the traditional test.) I will also note that while for the Delaunay method you have compute and store the circumcircle information, the point-in-circumcircle test is much faster than the point-in-ear test, so the final computational cost is not really much different for either test. Graham -----Original Message----- From: Johan Gustafsson [mailto:spi...@gm...] Sent: Wednesday, January 28, 2009 9:00 AM To: Game Development Algorithms Subject: Re: [Algorithms] Cutting Ears Algorithm Thanks for the feedback and even though I think the algorithm will work for my current needs I would like to get some information on certain subjects you have all brought to the table. First I'd like to define my problem and the reason why I'm triangulating (even shapes that are already triangles fans) I'm working on an editor that works in 2D space where the user creates shapes (simple polygons) and inorder to render the created polygons I triangulate the shapes and send them off as triangle lists to the renderer. Performance is not a primary concern since the number of vertices and shapes are relatively low. Since the user input can indeed be already defined triangles, like the trianglefan previously mentioned the algorithm will still process it. At the moment the editor seems to run just fine but I get scared when I hear words like sliver since I dont even know what a sliver is (english is not my 1st language), if someone could explain what a sliver is and how one could occur or methods to avoid it please amuse me. Further you guys mention degenerate triangles, I presume the algorithm can only cause a degenerate triangle to occur if the user inputs 3 colinear vertices or the point in triangle test fails to include border cases (my triangle fan example). The first case is simple to avoid but the second case might be harder to avoid because of numerical stabilities during the point in triangle test. Have I understood it correctly that exchanging the point in triangle to use a Delanuay constraint will solve this problem? I'm having a hard time visualising this. ------------------------------------------------------------------------ ------ This SF.net email is sponsored by: SourcForge Community SourceForge wants to tell your story. http://p.sf.net/sfu/sf-spreadtheword _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t |
