Game Development Reference
In-Depth Information
A modeling system may produce a list of polygons that might be convex or
concave. After static world geometry has been processed by performing welding
and T-junction elimination, any polygon may also contain several vertices that
are collinear (or at least nearly collinear) with some of its other vertices. This
prevents us from using a simple fanning approach that might ordinarily be used
to triangulate a convex polygon. We are instead forced to treat the polygon as
concave.
The algorithm that we describe takes as input a list of n vertices wound in a
counterclockwise direction and produces a list of
triangles. At each itera-
tion, we search for a set of three consecutive vertices for which the corresponding
triangle is not degenerate, is not wound in the wrong direction, and does not con-
tain any of the polygon's remaining vertices. The triangle formed by such a set of
three vertices is called an ear . Once an ear is found, a triangle is emitted, and the
middle vertex is disqualified from successive iterations. The algorithm repeats
until only three vertices remain. This process of reducing the size of the triangu-
lation problem by removing one ear at a time is called ear clipping .
In order to determine whether a set of three vertices is wound in a counter-
clockwise direction, we must know beforehand the normal direction
n
2
N of the
plane containing the polygon being triangulated. Let P ,
P , and P represent the
(
)
(
)
positions of the three vertices. If the cross product
PP PP points in
the same direction as the normal N , then the corresponding triangle is wound
counterclockwise. If the cross product is near zero, then the triangle is degener-
ate. Thus, two of our three requirements for a triangle are satisfied only if
−× −
2
1
3
1
(
)
(
)
PP PPN
−× −⋅
0 ε
>
(9.41)
2
1
3
1
for some small value ε (typically,
).
Our third requirement is that the triangle contains no other vertices belonging
to the polygon. We can construct three inward-facing normals
0.001
ε
N ,
N , and
N
corresponding to the three sides of the triangle, as follows.
(
)
NN PP
N NPP
NN PP
=× −
=× −
=×−
1
0
2
1
(
)
2
0
3
2
(
)
(9.42)
3
0
1
3
As shown in Figure 9.15, a point Q lies inside the triangle formed by P ,
P , and
(
)
P if and only if
.
Since we have to calculate the normals given by Equation (9.42) for each
triangle, we can save a little computation by replacing the condition given by
N
QP
− >−
i ε
for
i
{
1, 2, 3
}
i