Graphics Reference
In-Depth Information
One way to find g(t) is to differentiate the equation in condition (2). This shows
that g(t) must satisfy
Jtt
d
dt
g
∂
∂
h
t
(
()
)
( )
+
(
()
)
=
g
,
t
g
tt
,
0
(13.26)
where J(
x
,t) is the Jacobian matrix
∂
∂
h
x
Ê
Á
ˆ
˜
i
j
()
=
()
Jt
x
,
x
,
t
.
If the rank of J(
x
,t) is n for all values t, then the implicit function theorem will guar-
antee that g(t) exists. We are left with the problem of solving the system of ordinary
differential equations defined by (13.26) and can use any of the well-known ways to
solve such equations.
A second way to find g(t) is to use a standard root finding method like the Newton-
Raphson method to the equation in condition (2) above.
We mention two potential problems with using the homotopy method. In general
terms, what sets the homotopy method apart from previous iterative schemes is the
fact that it replaces a “local convergence” approach with a “global convergence” one.
With the homotopy method we already have some knowledge about certain initial
zeros (if our initial guess for a zero is poor when using a standard Newton-Raphson
method then we may have extreme difficulty in converging to a zero) and we can use
them to iterate to
all
of the zeros of our function. Nevertheless, we are still dealing
with an iterative process and one big problem with the type of iterative methods that
are used is that when relevant Jacobian matrices have singularities, then it is very
hard to guarantee the convergence to a desired solution. It took a lot of work to over-
come the singular Jacobian matrix problem and make the homotopy method work
and be reasonably efficient.
Another problem that caused great inefficiencies in the homotopy method initially
was the choice of a start function g(
x
). The original approach was to use Bézout's
theorem and choose a polynomial function g(
x
) of total degree d that was the product
of the degrees of the polynomials in f(
x
). In practice, however, the number of zeros
of f(
x
) was often much smaller than d and so a lot of computation effort was wasted
in generating curves g(t) that diverged to • as t Æ 1. It was important to find a better
bound on the number of zeros of f(
x
). This can be done in the case of
sparse polyno-
mials
, that is, polynomials that have a relatively small number of monomial terms.
One gets a more efficient homotopy method when f(
x
) is a sparse polynomial. See,
for example, the paper [VeVC94], which concentrates on sparse polynomial systems.
13.5.4
Surface Recursive Subdivision Methods
The general idea of using recursive subdivision (divide-and-conquer) in computer
graphics is an old one. Display algorithms in early papers, such as [Catm74] and
[LCWB80], made use of it. The first suggestion that it might be useful for intersection
problems can be found in [LanR80]. Bézier and B-spline surfaces with their control
