Graphics Reference
In-Depth Information
For larger polyhedra, a faster approach is to construct, as a precomputation, a
hierarchy over the parts of the polyhedron. Utilizing a preconstructed hierarchy
allows the closest point to be located in logarithmic time. An example of such a
hierarchy is the Dobkin-Kirkpatrick hierarchy, described in Chapter 9. Chapter 9
also describes other approaches that can efficiently locate the closest point on the
polyhedra (such as the GJK algorithm).
5.1.8
Closest Points of Two Lines
Whereas a pair of lines in two dimensions always intersect unless they are parallel, a
pair of lines in three dimensions almost never intersect. Furthermore, even if two 3D
lines intersect in exact real arithmetic, under floating-point arithmetic they are quite
likely not to, due to rounding errors. Thus, to be able to robustly test the intersection
of two 3D lines it is best to assume that the lines might not intersect but only come
sufficiently close to each other. The intersection test then becomes determining the
distance between the lines and checking whether this distance is less than a given
threshold value.
The closest points of two lines can be determined as follows. Let the lines
L
1
and
L
2
be specified parametrically by the points
P
1
and
Q
1
and
P
2
and
Q
2
:
L
1
(
s
)
=
P
1
+
s
d
1
,
d
1
=
Q
1
−
P
1
=
+
=
−
L
2
(
t
)
P
2
t
d
2
,
d
2
Q
2
P
2
For some pair of values for
s
and
t
,
L
1
(
s
) and
L
2
(
t
) correspond to the closest points
on the lines, and
v
(
s
,
t
)
L
2
(
t
) describes a vector between them (Figure 5.8).
The points are at their closest when
v
is of minimum length. The key realization is
that this happens when
v
is perpendicular to both
L
1
and
L
2
. To see this, consider that
the shortest distance between a point
P
and a line
L
is the length of a straight line
=
L
1
(
s
)
−
L
1
(
s
) =
P
1
+
s
d
1
,
d
1
=
Q
1
-
P
1
Q
2
P
1
v
(
s
,
t
) =
L
1
(
s
) -
L
2
(
t
)
P
2
L
2
(
t
) =
P
2
+
t
d
2
,
d
2
=
Q
2
-
P
2
Q
1
Figure 5.8
The vector
v
(
s
,
t
) connecting the two closest points of two lines,
L
1
(
s
) and
L
2
(
t
),
is always perpendicular to both lines.
