Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
464 Chapter 10 Distance in 3D
//
// region 3
//
lSqr += line.direction.y * line.direction.y;
delta = line.direction.x * ptMinusExtents.x
+ line.direction.y * ptPlusExtents.y
+ line.direction.z * ptPlusExtents.z;
t = -delta / lSqr;
distanceSquared +=
ptMinusExtents.x * ptMinusExtents.x
+ ptPlusExtents.y * ptPlusExtents.y
+ ptPlusExtents.z * ptPlusExtents.z
+ delta * t;
qPrime.x = box.extents.x;
qPrime.y = -box.extents.y;
qPrime.z = -box.extents.z;
}
}
}
RaytoOBB
In the case of a ray-OBB distance calculation, we first compute the distance of the
infinite line in which the ray lives to the OBB. If the parameter t of the closest point
on the ray is less than zero, then we have to compute the distance from the ray’s point
of origin to the OBB.
The pseudocode is
real RayOBBDistanceSquared(Ray ray, OBB box)
{
Line line;
line.origin = ray.origin;
line.direction = ray.direction;
distanceSquared = LineOBBDistanceSquared(line, box, t);
if(t<0){
distanceSquared = PointOBBDistanceSquared(ray.origin, box);
}
return distanceSquared;
}
10.10 Line to Quadric Surface 465
Line Segment to OBB
In the case of a line segment-OBB distance calculation, we first compute the distance
of the infinite line in which the line segment lives to the OBB. If the parameter t of
the closest point on the line segment is not within [0, 1], then we need to find the
distance from the point at the start of the line segment (if t<0), or the distance from
the point at the end of the line segment (if t>1).
The pseudocode is
real LineSegmentOBBDistanceSquared(Segment seg, OBB box)
{
Line line;
line.origin = seg.start
line.direction = seg.end - seg.start;
distanceSquared = LineOBBDistanceSquared(line, box, t);
if(t<0){
distanceSquared = PointOBBDistanceSquared(seg.start, box);
} else if (t > 1) {
distanceSquared = PointOBBDistanceSquared(seg.end, box);
}
return distanceSquared;
}
10.10 Line to Quadric Surface
If the line intersects the quadric surface, then the distance between the two is zero. The
intersection can be tested using the parametric form for the line, X(t) =P +t
d.The
quadric surface is implicitly defined by Q(X) = X
T
AX +B
T
X +c = 0. Replacing
the line equation into the quadratic equation produces the polynomial equation
(
d
T
A
d)t
2
+
d
T
(2AP + B)t + (P
T
AP + B
T
P + c) = e
2
t
2
+ e
1
t + e
0
= 0
This equation has real-valued solutions whenever e
2
1
− 4e
0
e
2
≥ 0, in which case the
distance between the line and the surface is zero.
If the equation has only complex-valued solutions, then the line and the surface
do not intersect and the distance between them is positive. Imagine starting with a
cylinder whose axis is the line and whose radius is small enough that it does not
intersect the surface. As the radius is increased, eventually the cylinder will just touch
the surface, typically at one point but possibly along an entire line. The distance
between the surface and the line is the radius of this cylinder and corresponds to the
466 Chapter 10 Distance in 3D
distance between a surface point on the cylinder and the axis of the cylinder. If the line
is represented as the intersection of two planes ˆn
i
·X = c
i
=ˆn
i
·P for i =0, 1, where
{
d, ˆn
0
, ˆn
1
} is a set of mutually orthogonal vectors and ˆn
i
=1, then the squared
distance from X to the cylinder axis is F(X)= ( ˆn
0
· X −c
0
)
2
+ ( ˆn
1
· X −c
1
)
2
.The
problemistofindapointX on the quadric surface that minimizes F(X). This is
a constrained minimization problem that is solved using the method of Lagrange
multipliers (see Section A.9.3), as is shown next.
Define
G(X, s) = ( ˆn
0
· X − c
0
)
2
+ ( ˆn
1
· X − c
1
)
2
+ sQ(X)
where s is the parameter introduced as the multiplier. The minimum of G occurs
when ∇Q =
0 and ∂G/∂s = 0.Thefirstequationis2( ˆn
0
· X − c
0
) ˆn
0
+ 2( ˆn
1
· X −
c
1
) ˆn
1
+ s∇Q =
0, and the second equation just reproduces the constraint Q = 0.
Dotting the first equation with
d yields the condition
L(X) :=
d ·∇Q(X) = 0
a linear equation in X. Geometrically, the condition
d ·∇Q = 0 means that when
the minimum distance is positive, the line segment connecting the two closest points
must be perpendicular to both the line and the quadratic curve. See Figure 6.23 for an
illustration in the 2D setting. Now dot the first equation with ˆn
0
and with ˆn
1
to obtain
two equations involving s,2( ˆn
1
·X − c
1
) + s ˆn
0
·∇Q = 0 and 2( ˆn
0
·X − c
0
) + s ˆn
1
·
∇Q =0. In order for both linear equations to have a common solution, it is necessary
that
M(X) := ( ˆn
0
· X − c
0
) ˆn
1
·∇Q − ( ˆn
1
· X − c
1
) ˆn
0
·∇Q = 0
a quadratic equation in X.
We have a system of three polynomial equations in the three unknown compo-
nents of X. The two equations Q = 0 and M = 0 are quadratic, and the equation
L = 0 is linear. Section A.2 shows how to solve such systems. Just as in the 2D prob-
lem for computing distance between a line and an ellipse, some care must be taken
in solving the system. The equation L = 0 is degenerate when A
d =
0, in which case
the equation becomes
d · B = 0. Also notice that the equation M = 0 is rewritten as
ˆn · (2AX +B) = 0, where ˆn = ( ˆn
0
· X −c
0
) ˆn
1
− ( ˆn
1
· X −c
1
) ˆn
0
, a vector orthogo-
nal to
d.IfA ˆn =
0, the equation M = 0 degenerates to ˆn · B = 0. Either degeneracy
can occur when the quadric surface contains a line, for example, a parabolic cylinder,
hyperbolic cylinder, or a hyperboloid itself. An implementation must trap the de-
generacies and switch to the appropriate code block for computing distance between
lines.
10.11 Line to Polynomial Surface 467
An alternative approach to computing the distance between the line and the
quadric surface is to use a numerical minimizer. If the line is X(t) =P +t
d for t ∈R
and the distance between a point X and the quadric surface is F(X), the distance be-
tween the line point X(t) and the quadric surface is G(t) =F(P + t
d). A numerical
minimizer can be implemented that searches the t-domain R for those values of t
that produce the minimum for G(t). The trade-offs to be considered are twofold.
The approach that sets up a system of polynomial equations has potential numerical
problems if variables are eliminated to produce a single polynomial equation of large
degree. Both the elimination process and the root finding are susceptible to numerical
errors due to nearly zero coefficients. The approach that sets up a function to mini-
mize might be more stable numerically, but convergence to a minimum is subject to
the problem of slowness if an initial guess is not close to the minimum point or the
problem of the iterates trapped at a local minimum that is not a global minimum.
10.11 Line to Polynomial Surface
Let the line be represented by L(t) = P + t
d for t ∈ R and where
d=1. Let the
surface be represented parametrically by
X(r, s) =
n
0
i
0
=0
n
1
i
1
=0
A
i
0
,i
1
r
i
0
s
i
1
for (r, s) ∈ [r
min
, r
max
]× [s
min
, s
max
]. The squared distance between a pair of points,
one from the surface and one from the line, is
F(r, s, t) =X(r, s) −L(t)
2
The squared distance between the surface and the line is min{F(r, s, t) : (r, s, t) ∈
[r
min
, r
max
]× [s
min
, s
max
]× R}. A numerical minimizer can be applied directly to F ,
but the usual warnings apply: beware of convergence to a local minimum that is not
a global minimum. The standard calculus approach to finding the minimum is to
construct the set of critical points, evaluate F at each point in that set, and select the
minimum of the F values. The first-order derivatives of F are F
r
= 2(X − L) · X
r
,
F
s
= 2(X − L) · X
s
, and F
t
=−(X − L) ·
d,whereX
r
and X
s
are the first-order
derivatives of X. Observe that the degree of X is n
0
+n
1
and the degree of X
r
and X
s
is n
0
+ n
1
− 1. The critical points are defined below:
1. (F
r
, F
s
, F
t
)(r, s, t) = (0, 0, 0) for (r, s, t) ∈ (r
min
, r
max
) × (s
min
, s
max
) × R
2. (F
r
, F
t
)(r, s
min
, t)= (0, 0) for (r, t)∈ (r
min
, r
max
) × R
3. (F
r
, F
t
)(r, s
max
, t)= (0, 0) for (r, t)∈ (r
min
, r
max
) × R
468 Chapter 10 Distance in 3D
4. (F
s
, F
t
)(r
min
, s, t) = (0, 0) for (s, t) ∈ (s
min
, s
max
) × R
5. (F
s
, F
t
)(r
max
, s, t) = (0, 0) for (s, t) ∈ (s
min
, s
max
) × R
6. F
t
(r
min
, s
min
, t)= 0 for t ∈ R
7. F
t
(r
min
, s
max
, t)= 0 for t ∈ R
8. F
t
(r
max
, s
min
, t)= 0 for t ∈ R
9. F
t
(r
max
, s
max
, t)= 0 for t ∈ R
Item 1 in the list requires solving three equations in the three unknowns r, s, and
t. Define
(r, s) = X(r, s) − P . The equation F
t
= 0 may be solved for t =
d ·
.
Replacing this in F
r
=0 and F
s
=0 yields the polynomial equations (
−(
d ·
)
d) ·
X
r
=0 and (
− (
d ·
)
d) ·X
s
=0, the first of degree 2n
0
−1inr and 2n
1
in s, the
second of degree 2n
0
in r and 2n
1
− 1ins. Elimination theory (Wee and Goldman
1995a, 1995b) may be applied to reduce these to a single large-degree polynomial
equation in r, G(r) = 0.Foreachroot¯r of the equation, corresponding values of
¯s are found that are roots to (
− (
d ·
)
d) · X
r
= 0. For each such pair ( ¯r, ¯s), the
value
¯
t is computed and the F(¯r, ¯s,
¯
t) is evaluated. The minimum such F values is
maintained throughout the process.
Item 2 requires solving two equations in the two unknowns r and t. The equation
F
t
= 0 again is solved for t =
d ·
, except that now
varies only with r since
s = s
min
. Replacing in F
r
= 0 leads to a single polynomial equation in r of degree
2n
0
− 1.Foreachroot¯r,
¯
t is computed, F(¯r, s
min
,
¯
t) is evaluated, and the minimum
of F is updated to this new value if it happens to be smaller than the previously stored
minimum. Items 3, 4, and 5 are handled similarly.
Item 6 is simple to handle. The single equation is solved for
¯
t =
d ·
, and
F(r
min
, s
min
,
¯
t) is evaluated and used to update, if necessary, the currently stored
minimum of F . Items 7, 8, and 9 are handled similarly.
10.12 GJK Algorithm
The GJK algorithm for computing distance between two convex polyhedra has the
same theoretical foundation as its 2D equivalent for computing the distance be-
tween two convex polygons. The material in Section 6.10 was described for the n-
dimensional problem in terms of simplices contained in the convex objects and ap-
plies when n = 3. The simplices, of course, are tetrahedra for this dimension. An
implementation for a 3D collision detection system called SOLID (Software Library
for Interference Detection) is built on top of the 3D GJK algorithm and is available
at Van den Bergen (1997). The descriptions of the various algorithms used in the im-
plementation are provided in Van den Bergen (1997, 1999, 2001a). Of great interest
in this implementation is that special attention is paid to numerical issues that have
plagued many other implementations of GJK.
10.13 Miscellaneous 469
10.13 Miscellaneous
This section covers algorithms for handling some specific types of distance queries.
In particular, the queries involve (1) distance between a line and a planar curve, (2)
distance between two planar curves that do not lie in the same plane, (3) distance
between moving objects, and (4) distance between two points on a surface. The latter
query requires that the distance is calculated as the arc length of the shortest path
between the points where the path itself must lie on the surface. The path is called a
geodesic path, and the length is called geodesic distance.
10.13.1 Distance between Line and Planar Curve
Two types of methods are presented for computing the distance between a line and a
planar curve. The first method is based on a parametric representation of the curve.
The second method is based on a representation of the curve as the solution set to a
system of algebraic equations. In either case, the line is represented parametrically as
X(t) =P +t
ˆ
d,where
ˆ
d=1, and the plane of the curve is ˆn ·X =c,whereˆn=1.
Parametric Representation
Let the curve be represented parametrically as X(s) for some domain [s
min
, s
max
]. Th e
squared distance between a pair of points, one from the curve and one from the line,
is F(s, t) =X(s) − (P + t
ˆ
d)
2
. Finding the minimum distance between line and
curve requires computing a parameter pair (s, t) ∈ [s
min
, s
max
] × R that minimizes
F . A numerical minimizer can be applied directly to F , especially so if X is not
continuously differentiable in s. If derivatives do exist and are continuous, then a
calculus solution can be applied. Specifically, the minimum occurs when one of the
following conditions holds:
i. ∇F(s, t) =
0 for an (s, t) ∈ (s
min
, s
max
) × R
ii. ∂F(s
min
, t)/∂t = 0 for some t ∈ R
iii. ∂F(s
max
, t)/∂t = 0 for some t ∈ R
The simplest partial derivative equation to solve is ∂F /∂t = 0. The solution is
t =
ˆ
d · (X(s) − P). If working with the full gradient, the t value can be replaced in
the other derivative equation
0 =
∂F
∂s
= ((X(s) − P)− (
ˆ
d · (X(s) − P))
ˆ
d) ·X
(s)
= X
(s)
T
(I −
ˆ
d
ˆ
d
T
)(X − P) (10.16)
470 Chapter 10 Distance in 3D
The complexity of solving this equation is directly related to the complexity of the
curve itself.
Example Distance between a line and a circle. Acirclein3DisrepresentedbyacenterC,a
radius r, and a plane containing the circle, ˆn · (X − C) = 0, where ˆn is a unit-length
normal to the plane. If ˆu and ˆv are also unit-length vectors so that ˆu, ˆv, and ˆn form
an orthonormal set, then the circle is parameterized as
X(s) =C +r(cos(s) ˆu + sin(s) ˆv) =: C + r ˆw(s)
for s ∈ [0, 2π).TheX values are equidistant from C since X − C=r because
ˆw=1. They are also in the specified plane since ˆn · (X −C) = 0 because ˆu and
ˆv are perpendicular to ˆn.
Setting
=C −P , and after some algebraic steps, Equation 10.16 for this exam-
ple becomes
a
10
cos s + a
01
sin s +a
20
cos
2
s +a
11
cos s sin s +a
02
sin
2
s =0
where a
10
=
·ˆv − (
ˆ
d ·ˆv)(
ˆ
d ·
), a
01
=−
·ˆu + (
ˆ
d ·ˆu)(
ˆ
d ·
), a
20
=−r(
ˆ
d ·ˆu)
(
ˆ
d ·ˆv), a
11
=r[(
ˆ
d ·ˆu)
2
−(
ˆ
d ·ˆv)
2
], and a
02
=r(
ˆ
d ·ˆu)(
ˆ
d ·ˆv). A numerical root finder
may be applied to this equation. Each root ¯s is used to compute
¯
t =
ˆ
d · (X(¯s) − P),
and a corresponding squared distance F(¯s,
¯
t) is computed. The squared distance
between the line and the circle is the smallest F value computed over all the roots. The
amount of CPU time required to compute the distance in this manner is probably no
less than the amount needed to minimize F directly using a numerical solver. In both
cases, evaluation of the trigonometric functions is the main expense in time.
Algebraic Representation
Let the curve be defined as the intersection of its containing plane and a surface
defined implicitly by the polynomial equation F(X)= 0. It is assumed that ∇F and
the plane normal ˆn are never parallel—a reasonable assumption since the surface
should transversely cut the plane to form the curve. The perpendicular distance
from a point X to the line is the length of the line segment S(X) = (X − P)−
(
ˆ
d ·(X −P))
ˆ
d). This segment is the projection of X −P onto a plane orthogonal to
ˆ
d.TheproblemistocomputeapointX for which the squared distance S(X)
2
is minimized subject to the constraints ˆn · X = c and F(X) = 0.Themethodof
Lagrange multipliers discussed in Section A.9.3 can be applied to solve this. Observe
that
S
2
= (X − P)
T
(I −
ˆ
d
ˆ
d
T
)(X − P)= (X − P)
T
A(X − P)
10.13 Miscellaneous 471
where A = I −
ˆ
d
ˆ
d
T
. Define
G(X, u, v) = (X − P)
T
A(X − P)+ u( ˆn · X − c) + vF (X)
The parameters u and v are the Lagrange multipliers. The function G has a
minimum when ∂G/∂X =
0, ∂G/∂u = 0, and ∂G/∂v = 0. The notation ∂G/∂X
denotes the 3-tuple of first-order partial derivatives of G with respect to the three
components of X. The last two equations are just a restatement of the constraints that
define the object. By assumption, ˆn ·∇F =
0, so dotting the X derivative equation
by this vector and dividing by 2 yields the scalar equation constraint
H(X) :=ˆn ×∇F · A(X −P)= 0
The candidate points X for minimizing the distance are solutions to the system of
polynomial equations: ˆn · X =c, F(X)= 0, and H(X)= 0.
Example Distance between a line and a circle. Consider the same example discussed previ-
ously. Many choices may be made for F . For example, F can define a sphere of radius
r centered at C.OrF can define a cylinder whose axis contains circle center C, has
direction ˆn, and has radius r. The sphere provides a simpler equation, so we use it:
F(X)=X − C
2
− r
2
and ∇F = 2(X − C). The function H(X) is a quadratic
polynomial. Elimination theory applied to the one linear and two quadratic equa-
tions results in a polynomial of large degree. Instead of solving all three, the planar
coordinates can be used. Let X = C + u ˆu + v ˆv,where{ˆu, ˆv, ˆn} is an orthonormal
set. This representation of X automatically satisfies the plane equation ˆn · X = c,
where c =ˆn · C. Replacing X into F = 0 and H = 0 produces two quadratic equa-
tions f(u, v) = 0 and h(u, v) = 0 in the two unknowns u and v. Elimination of v
leads to a single quartic equation g(u) = 0.Foreachroot ¯u, two values ¯v are com-
puted by solving the quadratic equation f(¯u, v) = 0. The squared distance for each
pair ( ¯u, ¯v) is computed, and the minimum squared distance is selected from the set
of squared distances.
10.13.2 Distance between Line and Planar Solid Object
The previous method computed distance between a line and a curve. If the distance
is required between a planar solid object whose boundary is a specified curve, the
algorithm must be slightly modified. If the line intersects the plane at a point inside
the solid object, then the distance is zero. If the line intersects the plane, but does
not intersect the solid object, then the point in the solid object closest to the line
must be a point on the object boundary. The argument is simple. If the closest point
is an interior point, it must be obtained from the closest line point by a projection
onto the plane of the object. A sufficiently small step along the line starting at the
closest line point and in the direction toward the plane leads to a new line point,
472 Chapter 10 Distance in 3D
its projection being another interior point of the object, and this new pair of points
attains smaller distance than the previous pair, a contradiction to the previous pair
attaining minimum distance. Finally, if the line is parallel to the plane, then the closest
points on the object to the line may be selected from the object boundary. Thus, the
algorithm amounts to determining if the line intersects the object. If so, the distance
is zero; if not, the distance is computed from line to object boundary.
10.13.3 Distance between Planar Curves
If two planar curves lie on the same 3D plane ˆn · (X −C) = 0, the distance between
them can be calculated by using planar coordinates, effectively reducing the problem
to one in two dimensions. That is, if ˆn is unit length and if ˆu and ˆv are unit-length
vectors such that {ˆu, ˆv, ˆn} is an orthonormal set, then any point on the plane is
represented by X =C +r ˆu + s ˆv + t ˆn for some choice of scalars r, s, and t. Distance
calculations are made within the plane by projecting out the normal component.
The projected points are C +r ˆu + s ˆv. The two-dimensional distance algorithms are
applied to points (r, s). In 3D, the point C corresponds to the origin (0, 0) of the 2D
system.
An application might require distance calculations between planar curves that do
not lie in the same plane. In this case the problem requires calculations in the full
three-dimensional space. We present two types of methods for handling such curves.
One method applies if the planar curves are represented in some parametric form.
The other method applies if the sets of points for the planar curves are represented as
solution sets to systems of algebraic equations.
Parametric Representation
Let the curves be represented parametrically as X(s) for some domain [s
min
, s
max
]
and Y(t) for some domain [t
min
, t
max
]. The squared distance between a pair of
points, one on each curve, is F(s, t) =X(s) − Y(t)
2
. Finding the minimum dis-
tance between the curves requires computing a parameter pair (s, t) ∈ [s
min
, s
max
]×
[t
min
, t
max
] that minimizes F . A numerical minimizer can be applied directly to F ,
especially if either X or Y is not continuously differentiable. If both curves are con-
tinuously differentiable, then a calculus solution can be applied. Specifically, the
minimum occurs either at an interior point of the domain where ∇F =
0orata
boundary point of the domain. Each edge of the boundary provides a minimization
problem in one less dimension. The set of points (s, t) for which F is evaluated and
the minimum chosen from all such evaluations consists of these critical points:
1. ∇F(s, t) =
0 for (s, t)∈ (s
min
, s
max
) × (t
min
, t
max
)
2. ∂F(s
min
, t)/∂t = 0 for t ∈ (t
min
, t
max
)
3. ∂F(s
max
, t)/∂t = 0 for t ∈ (t
min
, t
max
)
10.13 Miscellaneous 473
4. ∂F(s, t
min
)/∂s = 0 for s ∈ (s
min
, s
max
)
5. ∂F(s, t
max
)/∂s = 0 for s ∈ (s
min
, s
max
)
6. (s
min
, t
min
), (s
min
, t
max
), (s
max
, t
min
), (s
max
, t
max
)
The complexity of solving the partial derivative equations is directly related to the
complexity of F(s, t).
Algebraic Representation
Let the planes of the two curves be ˆn
0
· X = c
0
and ˆn
1
· Y = c
1
,whereX denotes any
point on the first curve and Y denotes any point on the second curve. We assume that
the normal vectors are unit length and that the two planes are distinct. This does allow
for the curves to be on parallel planes. Suppose that the first curve is the intersection
of its containing plane and a surface defined implicitly by the polynomial equation
P
0
(X) = 0. We can assume that ˆn
0
and ∇P
0
are not parallel since P
0
can be chosen
so that the implicit surface intersects the plane transversely. Similarly let the second
curve be the intersection of its containing plane and a surface defined implicitly by
the polynomial equation P
1
(Y ) = 0, where ˆn
1
and ∇P
1
are not parallel. For each pair
of points (X, Y), one from the first curve and one from the second curve, the squared
distance is X −Y
2
. The distance between the two curves is attained by a pair (X, Y)
that minimizes X − Y
2
subject to the four algebraic constraints.
The minimization is accomplished by using the method of Lagrange multipliers
discussed in Section A.9.3. Define
G(X, Y , s
0
, t
0
, s
1
, t
1
) =X − Y
2
+ s
0
ˆn
0
· (X − C
0
) + t
0
P
0
(X)
+ s
1
ˆn
1
· (Y − C
1
) + t
1
P
1
(Y )
Observe that G : R
10
→ R. The derivative ∂G/∂X denotes the 3-tuple of first-order
partial derivatives with respect to the components of X. The derivative ∂G/∂Y is de-
fined similarly. The minimum of G occurs when ∂G/∂X =
0, ∂G/∂Y =
0, ∂G/∂s
0
=
0, ∂G/∂t
0
= 0, ∂G/∂s
1
= 0, and ∂G/∂t
1
= 0. The last four derivative equations are
just a restatement of the four constraints that define the two curves. The X and Y
partial derivative equations are
∂G
∂X
= 2(X − Y)+ s
0
ˆn
0
+ t
0
∇P
0
(X) =
0 and
∂G
∂Y
= 2(Y − X) + s
1
ˆn
1
+ t
1
∇P
1
(
T)=
0
Dotting these with ˆn
0
×∇P
0
and ˆn
1
×∇P
1
, respectively, yields ˆn
0
×∇P
0
(X)·
(X − Y) = 0 and ˆn
1
×∇P
1
(Y ) · (Y − X) = 0. Combining these with the four