Graphics Reference
In-Depth Information
n
n
Â
( (
)
=
[
(
)
+
]
Bui n u uu u
1
-
=
.
in
,
i
=
0
Figure 13.6(b) shows the graph of D(u) for the example in Figure 13.6(a). Clearly, if
()
£
()
≥
Du
d
or Du
d
max
,
min
then p(u) will not lie on the curve q(u). Therefore one can trim away those parts of
p(u). Actually, we shall only trim away parts at the ends of the curve. Let u
min
and
u
max
be the largest and smallest u so that the convex hull of the
D
i
misses the fat line
Y
between y = d
min
and y = d
max
over the intervals [0, u
min
] and [u
max
,1], respectively.
For the example in Figure 13.6(b) it turned out that u
min
= 0.25 and u
max
= 0.75. We
now subdivide the Bézier curve p(u) at u
min
and u
max
using the de Casteljau algorithm
and only keep the part over [u
min
,u
max
]. That part is then reparameterized to [0,1].
Note that we are being conservative here and we could have trimmed a little more.
As Figure 13.6(b) shows, the curve D(u) meets the fat line
Y
over an interval smaller
than [u
min
,u
max
].
After clipping p(u) against q(u), we repeat this process, this time clipping q(u)
against the fat line associated to the clipped p(u). We alternate back and forth between
clipping against p(u) and q(u) until we arrive at our intersection point. This is the
basic idea behind the Bézier clipping algorithm for finding curve intersections, but
there are some important details that need to be added.
The first observation is that we can use any fat line for the clipping. The choice
above is usually effective, but another choice that is sometimes better is to use a fat
line orthogonal to the line containing
p
0
and
p
n
. An example of that is shown in Figure
13.7. The fat line between
L
1
and
L
2
is a better choice when clipping q(u) against p(u)
than using one that is parallel to the line containing the endpoints
A
and
B
of
the curve p(u). The extra time used in checking which choice is better seems to be
worth it.
Another point that has not been addressed is whether or not the above algorithm
actually converges. In fact, it may not if we only clip little if anything at each stage.
Figure 13.7.
An alternative fat line.
