Graphics Reference
In-Depth Information
Figure 13.3.
Bounding curves for a Bézier curve.
one on either side of the actual curve. Turner called the region between the two curves
a
curve-bounding area
. This idea easily generalizes to any curves defined by control
points. In general, one can define two bounding curves associated to a curve, which
have the property that the region between them contains the original curve. If the
curve-bounding areas of two curves do not intersect, then the curves will not inter-
sect. If they intersect, then a subdivision process is applied to get a new set of two
curves so that the region between them is a closer fit to the original curve. Turner
describes steps that one can take to make sure that the intersection algorithm based
on this idea provides correct answers in the presence of singularities.
The next three sections discuss more direct approaches to the smooth curve inter-
section problem. For an approach based on interval arithmetic see [HMSP96].
13.3.3
A Curve Newton-Raphson Method
To find the intersection of two smooth curves parameterized by functions p(u) and
q(u) amounts to solving an equation of the form
(
)
=
()
-
()
= 0
fu v
,
pu
qv
.
(13.6)
We describe an approach discussed in [HosL93]. Let p(u) = (p
1
(u),p
2
(u)) and q(v) =
(q
1
(v),q
2
(v)).
(1) Pick a point
p
0
= (x
0
,y
0
) = p(u
0
) on the curve p(u).
(2) Find the intersection of the tangent line
L
0
to p(u) at
p
0
with the curve q(u).
Since this tangent line is defined by
p
0
+ t p¢(u
0
) and has equation
(
)
¢
()
--
(
)
¢
()
=
xxpu
-
yypu
01 0
0,
02 0
the equation we need to solve is
(
()
-
)
¢
()
-
(
()
-
)
¢
()
=
qv xp u
q v yp u
0
,
1
0
2
0
2
0
1
0
or
()
¢
()
-
()
¢
()
-
(
¢
()
-
¢
()
)
=
qvp u
qvpu
xp u
ypu
010
0
.
(13.7)
1
20
2
10
020
