Game Development Reference
In-Depth Information
tween P and P . We can make this determination by measuring the projected
length t of the line segment connecting P to Q onto the edge formed by P and
P . This length is given by
t
=−
QP
1 cos
α
,
(9.39)
where α is the angle between the line segment and the edge. Using a dot product
to compute the cosine, we have
(
) (
)
QP P P
PP
−⋅
1
2
1
t
=
.
(9.40)
2
1
If t ε
PP , then the point Q does not lie within the interior of the
edge formed by P and P . Otherwise, we have found a T-junction, and a new
vertex should be added to the polygon of object A between P and P precisely at
Q 's location.
<
or
>−−
ε
t
2
1
9.6 Triangulation
Triangulation is the process by which a polygon is divided into triangles that use
the same array of vertices and collectively cover the same area. Polygons must be
triangulated before they can be passed to the graphics hardware. A polygon hav-
ing n vertices is always decomposed into
triangles. Convex polygons are
particularly easy to triangulate—we simply choose one vertex and connect edges
to every other nonadjacent vertex to form a triangle fan like the one shown in
Figure 9.14. Polygons that are not convex or possess three or more collinear ver-
tices cannot generally be triangulated in this way, so we have to employ more
complicated algorithms.
n
2
Figure 9.14. A convex polygon can be triangulated by connecting edges from one arbi-
trarily chosen vertex to every other nonadjacent vertex, creating a triangle fan.