Re: [Algorithms] Cutting Ears Algorithm

[Graham R. ARA/S. <gr...@ar...>]

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