Graphics Reference
In-Depth Information
look up those sorts of details, insofar as they are available, in the references to spe-
cific algorithms. Some general references that give an overview of intersection algo-
rithms and compare some of the methods used in these algorithms are [PraG86],
[SedP86], [Luka89], [DoSY89], [Hoff89], [AzBB90], [BarK90], [SedN90], [Boen91],
[Patr92], [Patr93], and [HosL93]. We conclude with a brief summary in Section 13.6.
A few general comments are in order before we get started. The problem of finding
the intersection of two smooth objects is invariably reduced to the problem of finding
the roots of an equation. The exact nature of this equation is determined by how the
two objects
O
1
and
O
2
are presented, that is, whether they are defined parametrically
or implicitly via equations. In the discussion below assume that
O
1
and
O
2
are m-
dimensional objects in
R
n
, that
x
Œ
R
n
, and that
s
,
t
Œ
R
m
are variables used to para-
meterize the objects. (For the curves and surfaces of interest to us, m will be 1 or 2,
respectively, and n will be 2 or 3.)
Implicit/parametric Intersection.
This is the easiest case. Suppose that
O
1
is
defined by an equation
f
()
= 0,
(13.1)
and that
O
2
is parameterized by a function p(
t
) = (p
1
(
t
),p
2
(
t
),..., p
n
(
t
)). The inter-
section
O
1
«
O
2
can be obtained by solving the equation
()
=
(
()
()
()
)
=
Ff pp
t
t
,
t
,...,
n
t
0
,
(13.2)
1
2
which defines an implicit object in
R
m
.
Implicit/implicit Intersection.
Suppose that
O
1
and
O
2
are defined by equations
f
()
= 0
and
g
()
= 0,
respectively. One needs to solve
()
=
(
() ()
)
=
(
)
=
F
x
f
x
,
g
x
00
,
0
.
Parametric/parametric Intersection.
Suppose that
O
1
and
O
2
have parameteriza-
tions p(
s
) and q(
t
), respectively. We need to solve
(
)
=
()
-
()
=
F
st
,
p
s
q
t
0
.
(13.3)
Because the implicit/parametric case is the easiest case, one often tries to convert
to this case. This is one way how algebraic geometry enters the picture. Converting
the parametric/parametric case means that we would use algebraic geometry to
convert one of the parameterizations to an implicit representation. This is always pos-
