Graphics Reference
In-Depth Information
sible for a rational parameterization. For the implicit/implicit case, we would use
algebraic geometry to convert one of the implicit representations to a parametric one,
although this is
not
always possible. See Sections 10.9 and 10.15 in [AgoM05].
Another comment we would like to make here is with regard to the Newton-
Raphson method. This method, whose mathematics is described in more detail in
Section 4.7 in [AgoM05], will be referred to over and over again because it gets used
in many of the algorithms described in this chapter. Therefore, to ensure that the
reader knows what is involved when it is mentioned, it is probably helpful to review
the idea behind it in general terms before we get started. The Newton-Raphson
method is an approach to solving an equation of the form
()
=
f
x0
.
(13.4)
One starts with an initial guess
x
0
and then generates a sequence of points
x
i
that,
hopefully, converge to a solution
p
0
of equation (13.4). If
S
is the set defined by equa-
tion (13.4), then this process is often referred to as
relaxing
x
0
to
p
0
in
S
. Given
x
i
, one
gets the next point
x
i+1
by using the first few terms of the Taylor expansion for f about
x
i
as an approximation for f and solving for its zeros. Strictly speaking, the Newton-
Raphson method uses the linear approximation
()
=
()
+
()
-
(
)
,
hf
xx
f
xxx
i
i
i
which uses the first two terms. The solution to the linear system h (
x
) =
0
then becomes
the next point
x
i+1
. Using the Moore-Penrose inverse matrix to solve for
x
i+1
we get
(
)
-
=+
()
¢
()
¢
()
¢
()
1
(
)
T
T
xxx xx x
f
f
f
f
.
(13.5)
i
+
1
i
i
i
i
i
where f¢(
z
) is the Jacobian matrix of f at
z
. The solution
p
0
may only be one point of
a curve segment that belongs to the entire solution set
S
of equation (13.4). In that
case, one generates a sequence of solutions
p
i
that become the vertices of a polygo-
nal curve that approximates a curve segment of
S
. One gets
p
i+1
from
p
i
by starting
with a guess
x
0
=
p
i
+ d for some appropriate small d and relaxing that point to
S
in
the manner described above. If one is careful, then one can use this technique to gen-
erate an approximation to the entire solution set
S
, but one needs a starting guess for
every component of
S
.
A major problem for algorithms that compute intersections is that one has to cope
with potentially complicated intersections and situations where objects intersect in
singular ways. For example, two surfaces may intersect in a surface, in isolated points,
or in a curve that has cusps, self-intersections, and consists of several disconnected
pieces. The nicest situation is where objects meet transversally, but even there prob-
lems arise in practice if points are too close to a singularity, such as where the objects
are close to intersecting or almost tangent. As we indicated in our comments at the
beginning of this section, there is a constant worry about numerical instability.
Another issue that comes up with surface intersections is the question of how the
intersection should be represented. Some ways to represent the intersection curve are
