Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
594 Chapter 11 Intersection in 3D
The pseudocode is as follows:
ComputeCurve(S, P, u0, v0, u1, v1, p0, p1)
{
Calculate:
u0’ = u’(u0, v0), v0’ = v’(u0, v0) and
u1’ = u’(u1, v1), v1’ = v’(u1, v1)
as described in the text
// Compute tangent vectors for R(t)
d0 = sSubU(u0, v0) * u’(u0, v0) + sSubV(u0, v0) + v’(u0, v0);
d1 = sSubU(u1, v1) * u’(u1, v1) + sSubV(u1, v1) + v’(u1, v1);
Calculate midpoint (uMid, vMid) of
parameter-space curve p: { (u0, v0), (u1, v1), (u0’, v0’), (u1’, v1’) }
// Calculate 3D image of p(uMid, vMid)
pMid = S(uMid, vMid);
recurse = false;
// Check if we’ve met convergence criteria, both 2D and 3D
if (pMid is not ‘‘close enough’’ to plane P) {
// Intersect curve to find split point
pMid = IntersectCurve(S, P, uMid, vMid);
recurse = true;
} else if (pMid is not ‘‘close enough’’ to 3D curve { p0, p1, d0, d1 } {
recurse = true;
}
if (recurse) {
// Recursively call function on split curve
ComputeCurve(S, P, u0, v0, p0, uMid, vMid, pMid);
ComputeCurve(S, P, uMid, vMid, pMid, u1, v1, p1);
} else {
// Found curve
curve = { p0, p1, d0, d1 }
}
}
A bit of explanation of the “IntersectCurve” function is in order: this computes
the intersection of the plane P with an isoparametric curve S(u
0
, v) or S(u, v
0
) in a
neighborhood of (uMid, vMid), returning a new (uMid, vMid).
11.9 Quadric Surfaces 595
The third part of the algorithm takes all the Hermite (sub)curves and joins them
to produce the totality of the intersection curves proper. Note that the end points of
the subcurves should exactly match, providing the intersections of adjacent bound-
aries of subpatches are intersected with the plane in a consistent fashion.
11.8.5 Implementation Notes
As Lee and Fredricks point out, it is possible for a patch to intersect the plane, yet
no border of the patch intersects. A reasonable approach for implementation is to
compute a bounding volume for the patch (an axis-aligned or oriented bounding
box) and test for intersections of the box with the plane. If no intersections are found,
then the patch itself does not intersect the plane; otherwise, recursively split the patch
and test the bounding boxes against the plane, until the bounding volumes no longer
intersect the plane or a subpatch is found whose boundaries intersect the plane. If
the patch is represented in B
´
ezier or B-spline basis, the bounding and splitting can be
quite efficiently done.
11.9 Quadric Surfaces
The intersection of two quadric surfaces can take one of several forms:
A point—for example, two spheres touching at their poles
A line—for example, two parallel cylinders, just touching along their sides
A single curve—for example, two partially intersecting spheres meeting in a circle
Two curves—for example, a plane and a double cone meeting in two parabolic
curves
A fourth-degree nonplanar space curve—for example, two cones intersecting
Generally speaking, the first four of these cases are relatively straightforward, as we
saw in Section 11.7.3, for example, and will see in the next section, which covers
the intersection of two ellipsoids: all of the curves are conic sections. Generation of
parametric representations of these conic section curves is possible, and this is advan-
tageous for many applications (e.g., rendering the intersection curve efficiently, etc.).
Miller and Goldman (1995) describe geometric algorithms for detecting when two
quadric surfaces intersect in a conic section, and for calculating such intersections
when they exist.
It is also possible to represent the nonplanar space curves exactly and paramet-
rically, as shown by Levin (1976, 1979, 1980) and Sarraga (1983). Miller (1987)
presents an approach for the so-called natural quadrics—the sphere, cone, and
cylinder—that is based entirely on geometric (rather than algebraic) techniques and
that results in a parameterized curve representation.
596 Chapter 11 Intersection in 3D
11.9.1 General Intersection
In this section we discuss general methods for intersecting quadric surfaces. There
are two different types of representations for quadric surfaces: An algebraic one uses
a general implicit equation in x, y, and z:
Ax
2
+ By
2
+ Cz
2
+ 2Dxy + 2Eyz + 2Fxz+ 2Gx + 2Hy + 2Jz+ K = 0
The specific type of surface (sphere, cone, etc.) is encoded in the “patterns” of values
of the coefficients (e.g., a sphere has A = 1, B = 1, C =1, and K =−1).
Quadrics can also be represented in matrix form
P QP
T
= 0
where
P =
[
xyz1
]
and
Q =
ADFG
DBEH
FECJ
GH J K
Linear combinations of two quadric surfaces Q
0
and Q
1
:
Q = Q
0
− λQ
1
define a family of quadric surfaces called the pencil of surfaces. Where Q
0
and Q
1
intersect, every quadric in the pencil of the two surfaces intersects the two original
quadrics in that same intersection curve.
The Algebraic Approach
Algebraic approaches exploit what Miller (1987) terms a “not intuitively obvious”
characteristic—that at least one ruled surface
4
exists in the pencil. Ruled quadric
surfaces are useful in intersection problems because they can be easily (and exactly)
parameterized.
A ruled quadric can be represented either as a rational polynomial function or
trigononometrically. The trigonometric representations describe quadrics in their
4. A ruled surface is one that can be viewed/defined as a set of straight lines, such as a cylinder
or cone.
11.9 Quadric Surfaces 597
canonical positions and orientations, and so arbitrarily located and oriented surfaces
are transformed into their canonical positions, where the intersections are calculated,
and the intersections are transformed back by the inverse operation. A cylinder in
canonical position can be represented trigonometrically as
x =r cos(θ )
y =r sin(θ )
z = s
(11.29)
while a cone with half-angle α is
x =s tan(α) cos(θ )
y =s tan(α) sin(θ)
z = s
(11.30)
Given two natural quadric surfaces Q
0
and Q
1
, one surface is determined to play
the role of the parameterization surface—the one in whose terms the intersection
curve is described. The intersection curve is defined as
a(t)s
2
+ b(t)s +c(t) = 0 (11.31)
For any particular intersection, a, b, and c are computed as follows:
1. Transform one of the surfaces into the local coordinate space of the one chosen
to be the parameterization surface.
2. Substitute either Equation 11.29 or Equation 11.30 (as appropriate) into the
implicit equation of the transformed quadric.
3. Algebraically manipulate the result so it is in the form of Equation 11.31.
The substitution in step 2 above for cylinders yields
a(t) = C
b(t) = 2Er sin(t) + 2Fr cos(t) + 2J
c(t) = Ar
2
cos
2
(t) + Br
2
sin
2
(t) + 2Dr
2
sin(t) cos(t) + 2Gr cos(t) + 2Hr sin(t) + K
and for cones yields
a(t) = A tan
2
(α) cos
2
(t) + B tan
2
(α) sin
2
(t) + C + 2D tan
2
(α) sin(t) cos t
+ 2E tan(α) sin(t) + 2F tan(α) sin(t)
b(t) = 2G tan(α) cos(t) + 2H tan(α) sin(t) + 2J
c(t) = K
(11.32)
598 Chapter 11 Intersection in 3D
For any particular configuration of intersections, the range of the parameter t
must be determined. To do this, we must determine the critical points of the curve—
locations where the curve either turns back on itself, crosses itself, or goes to infinity.
Algebraic analysis is used to find values of t that result in s going to infinity, and lo-
cations where the discriminant vanishes. The resulting partition of t-space defines
where the curve is valid. We can then traverse the valid portions of t -space, substi-
tuting t into the appropriate version of Equation 11.32. We then find s by solving
the quadratic equation (Equation 11.31). At this point we have pairs of values (s
i
, t
i
).
These pairs can then be substituted into the appropriate parametric equation (for
the cone or cylinder), yielding points of the form [
xyz
]. These points are then
transformed into world space.
While this is all relatively straightforward, all is not rosy. The algebraic (implicit)
equations for conics and quadrics are, as Miller points out, “extremely sensitive to
small perturbations in the coefficients.” The transformations common in graphics
systems (including the transformation of one quadric into the space of the other
to actually perform the intersection, as described above) will tend to perturb the
coefficients. Further, the intersection points need to be (inversely) transformed once
they are computed, and the coefficients are used to determine which object is used as
the parameterization object. Finally, in actually computing results, we must employ
a tolerance around zero, but this is quite difficult because of the difficulty of relating
the tolerance to spatial distance. For these reasons, Miller recommends a geometric
approach.
Recent work by Dupont, Lazard, and Petitjean (2001) has shown that some of the
numerical disadvantages of Levin’s approach can be significantly mitigated. First, we
define some terms.
The signature of a quadric P with matrix P is an ordered pair (p, q),wherep and
q are the numbers of positive and negative eigenvalues of P, respectively. Dupont et
al. point out that if P has signature (p, q), then −P has signature (q, p), even though
the quadric surfaces associated with P and −P are identical. Therefore, they define
the signature as the pair (p, q) where p ≥ q. The 3 ×3 upper-left submatrix of P is
denoted P
u
and called the principal submatrix of P, and its determinant is called the
principal subdeterminant. This principal subdeterminant is significant because it is
zero for simple ruled quadrics.
A quadric’s canonical form is given as
p
i=1
a
i
x
2
i
−
r
i=p+1
a
i
x
2
i
+ ξ = 0
or
p
i=1
a
i
x
2
i
−
r
i=p+1
a
i
x
2
i
+ x
r+1
= 0
11.9 Quadric Surfaces 599
Table 11.2
Parametric representation of the canonical simple ruled quadrics. After Dupont,
Lazard, and Petitjean (2001).
Quadric type Canonical equation Parameterization
(a
i
> 0) (X =[x
1
, x
2
, x
3
], u, v ∈ R)
Line a
1
x
2
1
+ a
2
x
2
2
= 0 X(u) = [0, 0, u]
Plane x
1
= 0 X(u, v) = [0, u, v]
Double plane a
1
x
2
1
= 0 X(u, v) = [0, u, v]
Parallel planes a
1
x
2
1
= 1 X(u, v) = [
1
√
a
1
, u, v]
X(u, v) = [
1
−
√
a
1
, u, v]
Intersecting planes a
1
x
2
1
− a
2
x
2
2
= 0 X(u, v) = [
u
√
a
1
,
u
√
a
2
, v]
X(u, v) = [
u
√
a
1
, −
u
√
a
2
, v]
Hyperbolic paraboloid a
1
x
2
1
− a
2
x
2
2
− x
3
= 0 X(u, v) = [
u+v
2
√
a
1
,
u−v
2
√
a
2
, uv]
Parabolic cylinder a
1
x
2
1
− x
2
= 0 X(u, v) = [u, a
1
u
2
, v]
Hyperbolic cylinder a
1
x
2
1
− a
2
x
2
2
= 0 X(u, v) = [
1
2
√
a
1
(u +
1
u
),
1
2
√
a
2
,
(u +
1
u
), v]
where a
0
> 0, ∀i, ξ ∈ [0, 1], and p ≤ r. The canonical forms for the simple ruled
quadrics are shown in Table 11.2.
Levin’s method for intersecting two quadrics P and Q can be summarized as
follows:
1. Find a ruled quadric in the pencil of P and Q. This is done by determining
the type of Q and of the quadrics R(λ) = P − λQ such that λ is a solution of
det(R
u
(λ)).
2. Compute the orthogonal transformation T that takes R to canonical form. In
that frame, R has a parametric form (as shown in Table 11.2). Compute P
=
T
−1
PT of P in that frame, and consider
X
T
P
= a(u)v
2
+ b(u)v + c(u) = 0
3. Solve the above equation for v in terms of u. Determine the domain of u over
which these solutions are defined—this is the region in which the discriminant
b
2
(u) − 4a(u)c(u) ≥0. Substitute v with its solutions in terms of u in X, yielding
a parameterization of P ∩Q = P ∩R (in the frame where R is canonical).
4. Transform the parametric intersection formula back into world space as TX(u).
600 Chapter 11 Intersection in 3D
Table 11.3 Parametric representation of the projective quadrics. After Dupont, Lazard, and
Petitjean (2001).
Signature Canonical equation (a
i
> 0) Parameterization (X = [x
1
, x
2
, x
3
, x
4
]∈ P
3
)
(4,0) a
1
x
2
1
+ a
2
x
2
2
+ a
3
x
2
3
+ a
4
x
2
4
= 0 Q =∅
(3,1) a
1
x
2
1
+ a
2
x
2
2
+ a
3
x
2
3
+ a
4
x
2
4
= 0detQ<0
(3,0) a
1
x
2
1
+ a
2
x
2
2
+ a
3
x
2
3
= 0 Q is a point
(2,2) a
1
x
2
1
+ a
2
x
2
2
− a
3
x
2
3
− a
4
x
2
4
= 0 X(u, v) = [
ut+vw
√
a
1
,
uw−vt
√
a
2
,
ut−vw
√
a
3
,
uw+vt
√
a
4
]
(2,1) a
1
x
2
1
+ a
2
x
2
2
− a
3
x
2
3
= 0 X(u, v) = [
u
2
+v
2
2
√
a
1
,
u
2
−v
2
2
√
a
2
,
uv
√
a
3
, wt]
(2,0) a
1
x
2
1
+ a
2
x
2
2
= 0 X(u, v) = [0, 0, u, v], u, v ∈ P
1
(1,1) a
1
x
2
1
− a
2
x
2
2
= 0 X(u, v) = [
u
√
a
1
,
u
√
a
2
, v, w],
X(u, v) = [
u
√
a
1
, −
u
√
a
2
, v, w], (u, v, w) ∈ P
2
(1,0) a
1
x
2
1
= 0 X(u, v) = [0, u, v, w], (u, v, w) ∈ P
2
Dupont et al. (2001) point out three sources of potential numerical problems:
In step 1, λ is the root of a cubic polynomial, potentially involving nested cubic
and square roots.
In step 2, the coefficients of T involve as many as four levels of nested roots.
In step 3, we have a square root in the solution of the polynomial equation noted
in step 2.
They propose several improvements to Levin’s method to avoid these problems. First,
they only consider the quadrics in P
3
—real projective 3-space. Levin’s method works
because there are sufficient canonical quadrics such that the substitution of step 3 re-
sults in a second-degree equation in one variable with a discriminant of degree four
in another variable. Dupont et al. provide a set of parameterizations for projective
space that share that property, with the exception of those of signature (3, 1) (ellip-
soids, hyperboloids, and elliptic paraboloids). These are shown in Table 11.3.
This approach reduces the number of times the quadric R has to be searched for
in the pencil; this search is required if and only if P and Q have signature (3, 1).
Another difference in their approach is based on a theorem: if two quadrics P and
Q both have signature (3, 1) and intersect in more than two points, then there exists
a rational number λ such that P − λQ does not have signature (3, 1). This ensures
that P and R have rational coefficients, and that λ can be computed “most of the
time” with normal floating-point arithmetic.
Finally, they use Gauss’s reduction method for quadratic forms (Lam 1973) for
transforming R into a canonical frame (in step 2). Compared to Levin’s use of an
11.9 Quadric Surfaces 601
orthogonal transformation in that step, the form of the solutions is “substantially”
simplified.
Their algorithm is summarized as follows:
1. Find quadric R in the pencil of P and Q such that det R ≥ 0 (or, find that the
intersection is of dimension 0). This is done by checking det Q:ifitisnonnega-
tive, then let R = Q; otherwise, if there is a λ such that det(P − λQ) ≥ 0, then
set R − P −λQ. Otherwise, the intersection has dimension 0.
2. If R’s signature is (4, 0) or (3, 0), then the intersection has dimension 0. Other-
wise, compute transformation T taking R into canonical form. Then, compute
P
= T
T
PT.
3. Solve X
T
P
X = 0, and determine the domains of (u, v) ∈ P
1
that are valid. Sub-
stitute (w, t), wt,orw into X in terms of (u, v) (depending on the case). If a, b,
and c all vanish for some values of (u, v), then replace (u, v) by those values in X
and let (w, t) ∈ P
1
. This gives a parametric representation of the intersection of
P and Q in R’s frame.
4. Transform the solution back into world space as TX(u, v).
The result of this algorithm is an explicit parametric representation of the inter-
section of quadrics P and Q; all the coefficients are in Q[
√
a
1
,
√
a
2
,
√
a
3
,
√
a
4
], w he re
the a
i
are the coefficients on the diagonal of T
T
RT.
The Geometric Approach
The geometric approach is so called because in it the quadric surfaces are instead
represented by points, vectors, and scalars that are specific to each type of surface.
For example, spheres are represented by a centerpoint and radius. In addition to the
more advantageous numerical characteristics, this approach is more compatible with
the definitions of such objects that you would want to use in a graphics library or
application interface.
We have already seen a geometric approach in the problem of intersecting the
sphere, cone, and cylinder with a plane (Section 11.7). As stated in the introduction
to this section, intersections may be one of several types:
A point—for example, two spheres touching at their poles
A line—for example, two parallel cylinders, just touching along their sides
A single curve—for example, two partially intersecting spheres meeting in a circle
Two curves—for example, a plane and a double cone meeting in two parabolic
curves
A fourth-degree nonplanar space curve—for example, two cones intersecting
602 Chapter 11 Intersection in 3D
Natural Quadrics Intersecting in Planar Conic Sections
Any two natural quadrics, of course, intersect in one of these types. Miller and Gold-
man (1995) note that the intersection of two natural quadrics can consist of either a
conic section (which, of course, lies in some plane and which may be degenerate, con-
sisting of a line, lines, or a point) or a fourth-degree nonplanar space curve. The con-
figurations of two natural quadrics that result in a planar conic curve intersection are
very special cases and few indeed, and their intersections can be computed by purely
geometric means, using the geometric representation of the quadrics. The algorithms
themselves are specific to the two types of quadrics involved and are similar in flavor
to those for the intersection of a plane and a natural quadric (see Sections 11.7.2,
11.7.3, and 11.7.4).
As suggested earlier, the planar intersection calculations of the natural quadrics
are similar in nature to the plane–natural quadric intersections presented earlier,
and so in Table 11.4 we only show the conditions under which two natural quadrics
intersect in a conic section (or degeneracy in the form of points or lines).
For those configurations of natural quadrics that do not result in a planar inter-
section, the result is a general fourth-degree space curve. These, too, can be computed
using purely geometric means (Miller 1987), and each algorithm is type-specific. The
papers (Miller and Goldman 1995; Miller 1987) covering the geometric algorithms
for both the planar and nonplanar intersections, respectively, of the natural quadrics
total 44 pages, and the presentation of the planar intersection is itself a summary
of two much longer technical reports that provide the details (Miller and Goldman
1993a, 1993b). Even with this extensive coverage, including also the paper covering
the plane–natural quadric intersection (Miller and Goldman 1992), only the natu-
ral quadrics’ intersections are covered; you could, of course, make the argument that
these are by far the most useful subset, but in any case, intersections of arbitarary
quadric surfaces must either be treated with the approach of Levin (1976, 1979, 1980)
or modifications thereof (Dupont, Lazard, and Petitjean 2001) or be treated as gen-
eral surface-surface intersection (SSI) problems.
Nonplanar Quadric-Quadric Intersections
Because of the lengthy development and case-by-case treatment required for the ge-
ometric intersection of quadrics that result in nonplanar fourth-degree space curves,
we present only a sketch of the approach and point the reader to Miller’s exhaustive
coverage (Miller 1987) for details and implementation.
The geometric approach shares with the algebraic approach the ideas of selecting
one surface as the parameterization surface and transforming the other into its local
space, and using the pencil of the two quadrics to parameterize the intersection curve.
However, the representations for the objects differ: for the parameterization quadric,
a coordinate-free parametric representation is used, while for the other surface, an
object-type-specific version of the implicit equation is used. Because the parametric
definition for the parameterization surface is based on geometrically meaningful
11.9 Quadric Surfaces 603
Table 11.4
Conditions under which natural quadric surfaces intersect in planar conic curves.
After Miller and Goldman (1995).
Surface pair Geometric conditions Results
Sphere-sphere All Empty, one tangent point, or
one circle
Sphere-cylinder Center of sphere on axis of
cylinder
Empty, one tangent circle, or
two circles
Sphere-cone Center of sphere on axis of
cone
Empty, one tangent circle,
one circle and a vertex, or two
circles
Cylinder-cylinder Parallel axes Empty, one tangent line, or
two lines
Intersecting axes and equal
radii
Two ellipses
Cylinder-cone Coincident axes Two circles
Axes intersect in a point at
distance d =
r
sin α
from the
vertex of the cone
Two ellipses (same or opposite
halves of cone) or one ellipse
and one tangent line
Cone-cone Parallel axes, same half-angle Ellipse, shared tangential
ruling, or hyperbola
Coincident axes Two circles or single vertex
Axes intersect at point I such
that d
1
sin α
1
= d
2
sin α
2
,
where d
1
is the distance from
vertex i to I
Various combinations of pairs
of conics, or a tangent line
plus a conic, or 1–4 lines if the
vertices coincide
entities, the functions a(t), b(t), and c(t) in Equation 11.31 have a more direct
geometric interpretation.
We can rewrite Equations 11.29 and 11.30 in coordinate-free terms. Define a
cylinder as consisting of a base point B,radiusr, and axis ˆw. As well, we need an
additional two vectors ˆu and ˆv to parameterize the cylinder—these, together with ˆw
and B, form an orthonormal basis. Our equation is then
P(s, t) = B + r(cos(t ) ˆu + sin(t ) ˆv) + s ˆw (11.33)
A cone can be given a similar treatment:
P(s, t) = B + s(tan(α)(cos(t) ˆu + sin(t) ˆv) (11.34)