Graphics Reference
In-Depth Information
2
x y
yx
--=
--=.
10
50
2
(13.20)
We note that the following related equations
2
x
y
-=
-=
10
50
2
(13.21)
are easily solved and the solutions to the parameterized equations
2
x txy
ytx
--=
--=
10
50
2
(13.22)
define a homotopy between the solutions to equations (13.20) and (13.21). Therefore,
to solve the equations (13.20) we compute the incremental changes to the solutions
to (13.21) as t changes from 0 to 1. One surface intersection algorithm that uses the
homotopy method can be found in [AbdY96].
Here is an overview of the general homotopy method. A good survey can be found
in [AllG90] and [Wats86]. Some other helpful papers are [GarZ79], [Morg83],
[Wrig85], and [AllG93], where one can also find many additional references.
A system of m polynomial equations in n variables corresponds to a polynomial
map f:
R
n
Æ
R
m
and an equation
()
=
f
x0
.
(13.23)
We choose another system of equations
()
=
g
x0
(13.24)
defined by a map g:
R
n
Æ
R
m
whose zeros are known and consider the homotopy h:
R
n
¥
R
Æ
R
m
between g(
x
) and f(
x
) defined by
(
)
=-
(
) ( )
+
()
ht
x
,
1
t g
x
tf
x
.
(13.25)
Let
x
0
be a zero of g(x). The object is to find a curve g(t) in the zero set of h that starts
at (
x
0
,0) and ends at a point (
x
1
,1), where
x
1
is a zero of f. More precisely, we look for
a curve
g :0
[]
Æ
RR
n
with the property that
(1) g(0) = (
x
0
,0)
(2) h(g(t)) =
0
, for all t Π[0,1], and
(3) g(1) = (
x
1
,1) , with f(
x
1
) =
0
.
