Graphics Reference
In-Depth Information
or
(
)
(
)
s =
AP
•
N
¢
AB
•
N
¢
.
(6.7)
Of course, s and t may not be defined if the denominators in (6.6) and (6.7) are zero,
but this happens precisely when
L
and
L
¢ are parallel.
This leads to the following solution to Problem 6.5.1:
Case 1.
[
A
,
B
] and [
P
,
Q
] are not parallel.
In this case, use equations (6.6) and (6.7) to compute s and t. If
0
££
st
,
1
,
then the segments [
A
,
B
] and [
P
,
Q
] intersect in the point
IP PQ
=+t
.
Case 2.
[
A
,
B
] and [
P
,
Q
] are parallel.
There are two steps in this case.
(1) Check to see if
L
and
L
¢ are the same line. This can be done by simply checking
if they have a point in common. For example, if
AP
·
N
= 0, then they do and
L
=
L
¢. If
L
is not the same line as
L
¢, then the segments will not intersect.
(2) If
L
=
L
¢, then we still need to check if the segments intersect. One can reduce
this to a problem of segments in
R
, because the problem is equivalent to asking
if the segments [0,|
AB
|] and [|
AP
|,|
AQ
|] intersect.
Unfortunately, although the two steps in Case 2 are a straightforward solution to
the mathematical problem, implementing this in a way that produces correct results
on a computer is not easy because of round-off errors.
One other issue must still be addressed before we leave the solution to Problem
6.5.1. How does one get the normal vectors
N
and
N
¢. Since we are in the plane, this
is easy. If
V
= (a,b) is a vector, then (-b,a) is a vector perpendicular to
V
. Finally, for
a solution that is concerned with minimizing the number of arithmetic operations
needed to solve the problem see [Pras91].
6.5.2 Problem.
Find the intersection
I
of a line
L
and a plane
X
in
R
3
. Assume that
L
is defined by two distinct points
P
and
Q
and that
X
contains a point
O
and has
normal vector
N
.
Solution.
Since
I
lies on
L
we can again express
I
in the form
IP PQ
=+t
,
(6.8)
for some t. Furthermore,
OI
must be orthogonal to
N
. Therefore,
