Graphics Reference
In-Depth Information
•f
F
1
(
X
)
<
0 then
outside
•f
F
2
(
X
)
<
0 then
outside
•f
F
3
(
X
)
<
0 then
outside
•E e
inside
.
Notice that this sequence of tests does early rejection: If
X
is on the wrong side
of one edge, we don't bother computing whether it's on the right or wrong side of
the others.
Building these functions
F
i
is similar to what we just did in Section 7.9.2. The
function for testing against edge
AB
in that case would be a dot product of
X
(a)
−
A
with the vector
AB
⊥
, for example.
For a triangle in 3-space specified with three vertices,
P
0
,
P
1
, and
P
2
, the nor-
mal is
(
P
1
−
(b)
P
0
)
, normalized. What happens if we re-order the ver-
tices? We get one of two answers, depending on whether we do an even or an odd
permutation. Every triangle therefore has two orientations; we'll stick with the
convention above that the vertices of a triangle are always named
in some order,
and that this order determines the normal vector that you mean. When we build
solid objects from collections of triangles, we'll make a policy that the normals
always point “to the outside.”
P
0
)
×
(
P
2
−
(c)
(d)
A polygon is a shape like the ones shown in Figure 7.18; we typically describe a
polygon by listing its vertices in order. Some polygons are non-self-intersecting
((a), (b), (d)); these are called
simple
polygons. Among these, some are
convex,
in the sense that a line segment drawn between any two points on the edge (like
the dashed gray horizontal line shown in (a)) lies entirely inside the polygon. In
the case of nonsimple polygons like (c) and (e), the angles at the vertices may all
be nonzero, or they may, like the angle at the upper right in (e), be zero; such a
point is sometimes called a reflex vertex.
(e)
Figure 7.18: Polygons (a), (b),
and (d) are simple, while (c) and
(e) are not. Polygon (e) has a
reflex vertex, (i.e., one with vertex
angle zero) at the upper right.
A polygon in the plane, in classic geometry, was simply a shape like the ones in
Figure 7.18; because we attach an
order
to the vertices, we have slightly more
structure. This allows us to define
inside
and
outside
for a larger class of poly-
gons. Suppose that
(
P
0
,
P
1
,
,
P
n
)
is a polygon. The line segments
P
0
P
1
,
P
1
P
2
,
etc., are the
edges
of the polygon; the vectors
v
0
=
P
1
−
...
P
0
,
v
1
=
P
2
−
P
1
,
P
n
are the
edge vectors
of the polygon.
5
For each edge
P
i
P
i
+
1
,the
inward edge normal
is the vector
...
v
n
=
P
0
−
v
i
.For
a convex polygon whose vertices are listed in counterclockwise order, the inward
edge normals point toward the interior of the polygon, and the outward edge nor-
mals point toward the unbounded exterior of the polygon, corresponding to our
ordinary intuition. But if the vertices of a polygon are given in clockwise order,
×
v
i
;the
outward edge normal
is
−×
5. It's convenient to write
v
i
=
P
i
+
1
−
P
i
,
i
=
0,
...
,
n
; unfortunately, this formula fails
at
i
=
n
because
P
n
+
1
is undefined. Henceforth, it will be understood that in cases like
this,
P
n
+
1
=
P
0
,
P
n
+
2
=
P
1
, etc. In other words, we continue the labeling cyclically;
the same goes for indices less than zero:
P
−
1
=
P
n
.
