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

Search Nedrilad ::

Custom Search