Graphics Reference
In-Depth Information
Figure 13.8.
Multiple-curve
intersections.
Figure 13.8 shows an example of multiple intersections, which lead to such situations.
Therefore, the suggested solution for the problem is the following recursive subdivi-
sion step: If Bézier clipping does not reduce the parameter range of each of the curves
by at least 20%, then subdivide the curve with the largest remaining parameter
interval and do a Bézier clip of the other curve with the two halves. Although this
solves our convergence problem, if curves are almost tangent or two intersections
are very close, then the algorithm reduces to a divide-and-conquer binary search
type algorithm in the neighborhood of those points. There is a very efficient way to
handle that situation, but we refer the reader to [SedN90] for the details. This finishes
our discussion of the Sederberg-Nishita Bézier clipping algorithm. Timing compar-
isons in [SedN90] show that for curves of degree less than five, the implicitization
algorithm in [SedP86] runs typically between 1 and 3 times faster than the Bézier clip
algorithm, which in turn is between 2 and 10 times faster than the algorithms from
[LanR80] and [KopM83]. For higher-degree curves, the Bézier clipping algorithm
seems to win. [Rock90] also has a comparison of various divide-and-conquer methods
for curves.
13.3.5
Curve Algebraic Methods
[SedP86] describes an algorithm for computing the intersection of two rational curves.
By implicitizing one of the curves and substituting the parameterization of the other
into the equation for the first one ends up having to solve a set of homogeneous linear
equations. Another approach combining elimination theory and matrix computations
is described in [ManD94] and [ManK97]. An algorithm for finding the intersection of
two algebraic curves is described in [Sede89].
In general, depending on how smooth curves are presented, earlier comments
imply that the intersection problem can be reduced to finding the roots of an equa-
tion of one or two variables. The interesting case is the two-variable case that involves
solving a polynomial equation of the form
(
)
= 0
fuv
,
,
like equation (13.6). This is the type of problem that algebraic geometry can help solve
and is really part of the more general problem of computing implicitly defined objects
about we have more to say in the next chapter.
Sometimes one wants not only the points in the plane that constitute the inter-
section of two parameterized curves but the parameter values at the points of inter-
section. If one used an implicitization approach to find the intersection, then the
parameter variables would have disappeared. This means that after finding an
