Graphics Reference
In-Depth Information
We begin with some general observations that are the basis for all the algorithms
that find the distance between two parameterized objects
O
1
and
O
2
in
R
n
. Let
A
Õ
R
s
,
B
Õ
R
t
, and assume that p :
A
Æ
O
1
and q :
B
Æ
O
2
are parameterizations of
O
1
and
O
2
, respectively. Define h :
A
¥
B
Æ
R
by
(
)
=
(
()
-
()
)
(
(
)
-
()
)
h
uv
,
p
uv
q
•
p
uv
q
.
(14.1)
Finding the points of
O
1
and
O
2
that are closest is equivalent to finding the minima
of h(
u
,
v
). If p(
u
) and q(
v
) are closest points on
O
1
and
O
2
, respectively, then (
u
,
v
) must
satisfy one of the following two properties:
(1) (
u
,
v
) is a critical point of h in the interior of
A
¥
B
.
(2) (
u
,
v
) ζ(
A
¥
B
), that is,
u
is on the boundary of
A
and/or
v
is in the bound-
ary of
B
.
Finding the minima of h is therefore a two-step process. First, the critical points of h
are found by searching for zeros of the derivative of h. (We will always assume that
functions are as differentiable as needed.) If we are not lucky to have formulas for
these zeros, then any method that finds zeros of functions, such as the Newton-
Raphson method, can be used here. We shall see in our examples below that having
the derivative of h zero at some point (
u
,
v
) corresponds geometrically to the saying
that the vector p(
u
) - q(
v
) is orthogonal to the tangent planes of
O
1
and
O
2
at p(
u
)
and p(
v
), respectively. This is intuitively what we would expect to have happen at two
closest points. It generalizes the fact that the vector between two closest points on
two lines is orthogonal to both of the lines. Of course, do not forget the possible special
case where the objects intersect. The zero vector is orthogonal to everything.
Now the derivative of h is defined by the Jacobian matrix, which in turn is defined
by the partials of p(
u
) and q(
v
). The exact form they take depends on the specific func-
tions. Next, after having found any closest points on the interior of
A
¥
B
, we have to
compare them with those on the boundary of
A
¥
B
. This is basically another problem
of the same type but of one lower dimension.
Point-curve Distance.
To find the distance between a point
p
and a parameterized
curve q : [c,d] Æ
R
3
we need to solve the equation
(
()
)
¢
()
=
p
-
qv
•
q v
0
(14.2)
for v. The left-hand side of equation (14.2) is what the derivative of the function h in
equation (14.1) reduces to here. There may be more than one solution. For example,
in Figure 14.1 both points
q
1
and
q
2
satisfy equation (14.2). Therefore, after finding
all the solutions we need to check which of the solutions that lie in [c,d] correspond
to the closest point. Finally, we need to compare the distance of that closest point to
the distances from
p
to q(c) and q(d), the endpoints of the curve. Note how q(d) is
actually the closest point on the curve in Figure 14.1.
Curve-curve Distance.
Assume that two curves are parameterized by functions p(u)
and q(u), respectively. To find points on these curves that are closest to each other we
