Graphics Reference
In-Depth Information
Figure 6.12.
Finding the intersection of two
segments.
Faces are usually defined by listing their vertices in some order. This ordering
defines an orientation and normal vector in a unique way. These are called the
induced
orientation
and
induced normal vector
, respectively. For example, if the face is defined
by
p
0
,
p
1
,...,
p
k
, then the induced normal vector is
p
0
p
1
¥
p
1
p
2
(assuming that
p
0
,
p
1
,
and
p
2
are noncollinear). Conversely, an orientation or normal vector for a face defines
a unique ordering of its vertices called the
induced ordering
.
All this extends to the case of an (n - 1)-dimensional face
F
of an n-dimensional
solid
S
in
R
n
, in particular, to the case n = 2 and edges of polygons in the plane.
Finally, if one has a set of either all outward- or all inward-pointing normals for
a polygon, then another way to test for its convexity is to take successive cross prod-
ucts of the edges and their normals and see if the vectors we get all point the same
way.
6.5
Simple Intersection Algorithms
6.5.1
Problem.
Find the point
I
that is the intersection of two planar segments
[
A
,
B
] and [
P
,
Q
].
Solution.
Let
L
and
L
¢ be the lines determined by
A
,
B
and
P
,
Q
, respectively. See
Figure 6.12. Since
I
, if it exists, must belong to both
L
and
L
¢, we can express
I
in the
form
I
=+
A
s
AB
=+
P
t
PQ
,
(6.5)
for some s and t. Assume that
N
and
N
¢ are two vectors which are perpendicular to
L
and
L
¢, respectively. It follows that
(
)
(
)
+
(
)
A
•
N
=+
A
s
AB
•
N
=+
P
t
PQ
•
N
=
P
•
N
t
PQ
•
N
,
or
t =
(
) (
)
PA
•
N
PQ
•
N
.
(6.6)
Similarly,
(
)
(
)
(
)
P
•
N
¢=
P
+
t
PQ
•
N
¢=
A
+
s
AB
•
N
¢=
A
•
N
¢+
s
AB
•
N
¢
.
