Graphics Reference
In-Depth Information
triangulate
nonconvex faces: decomposing them into a set of triangles. All faces can
be triangulated, often in many different ways. Another alternative is to partition the
faces into as few convex pieces as possible, thus reducing the number of faces to be
tested.
The following sections describe two methods: one for triangulation of nonconvex
faces and one for decomposition of nonconvex faces into a small number of convex
pieces. Last, the problem of decomposing nonconvex polyhedra into convex pieces
is discussed.
12.5.1
Triangulation by Ear Cutting
Various algorithms have been invented for the triangulation of polygons, ranging from
slow but easy-to-implement algorithms to algorithms that although theoretically
optimal are so complicated they are unimplementable in practice! One popular and
quite straightforward triangulation algorithm proceeds by a process known as
ear
cutting
(or
ear clipping
).
The triangle formed by a polygon vertex
V
i
and its immediate predecessor and
successor vertices
V
i
−
1
and
V
i
+
1
is said to be an
ear
if the diagonal between
V
i
−
1
and
V
i
+
1
is contained in its entirety in the polygon. The vertex
V
i
is said to be the
ear tip
.
The ear is commonly referred to by the ear tip vertex alone. It can be shown that every
simple nontriangle polygon has at least two nonoverlapping ears [Meisters75]. Thus,
all such polygons can be triangulated by the repeated identification and removal (or
cutting) of ears. It follows that a triangulation of a simple polygon with
n
vertices
consists of exactly
n
2 triangles. Figure 12.17 shows a simple polygon with two ears
and one possible triangulation of the polygon.
For a simple polygon an equivalent test for three consecutive vertices
V
i
−
1
,
V
i
, and
V
i
+
1
forming an ear
E
is to make sure
V
i
is convex and that no other polygon vertex
lies inside
E
.
V
i
is convex if
E
has the same winding as the polygon itself. Specifically,
for a counterclockwise polygon
V
i
is convex if
E
is counterclockwise.
Now consider the process of triangulation by repeated ear cutting. Initially, a
polygon will have some number
n
of ears,
n
−
2. As an ear is cut,
n
may decrease,
increase, or stay the same. The change in number of ears depends on the ear tip-ness
of the vertices
V
i
−
1
and
V
i
+
1
after the cutting. In other words, the change of ear-ness
only happens locally to the vertices where the ear is cut.
A polygon can therefore be triangulated by looping counterclockwise (say) around
the polygon boundary, visiting the vertices sequentially one after one, testing them
for ear-ness. As ears are encountered, they are cut. To make sure both vertices where
an ear is cut are revisited, the vertex previous to the (removed) ear tip vertex is set as
the next vertex to visit after a cut.
Figure 12.18 illustrates the first steps of a triangulation using this method. Starting
at
V
0
, vertex
V
5
is found to be inside the ear triangle during ear verification, and thus
V
0
is not an ear. The algorithm therefore proceeds to the next vertex
V
1
.
V
1
is also
≥
