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.

Search Nedrilad ::

Custom Search