Now let us denote the implicit algebraic surface
of total
degree
by
(5.78)
By substituting
, where
,
,
and
are all of maximum degree
in
and
in
into (5.78) and multiplying by
leads to an algebraic curve
(5.79)
of maximum degree
and
in
, respectively.
Consequently, the
problem of intersection reduces to the problem of
tracing
without omitting any special features of
the curve, e.g. small loops, singularities, and accurately computing
all its branches. This is a fundamental problem in algebraic geometry
[437] and much work has been done to understand its
solution. In the context of algebraic geometry the coefficients of
are integers. In the context of CAD and computer
implementation, the coefficients of
, and
are floating point numbers. Therefore, if
the above substitution is performed in floating point arithmetic the
coefficients of
involve error, which may considerably
modify the problem being solved. To avoid such error, rational
arithmetic may be used for robustness. These issues are discussed in
the Chap. 4.
Figure 5.18:
Parameter space of
and resulting algebraic
curve
The algebraic curve
(5.80)
can be reformulated in terms of Bernstein polynomials using
(4.18) as follows:
(5.81)
where
.
As an example, consider a plane in an implicit form
(5.82)
and a rational Bézier patch of degree
in
,
in
(5.83)
where
and weights
.
The resulting algebraic curve is of the form of
equation (5.81) with
(5.84)
In fact the power basis form of
need not be computed at
all, if polynomial arithmetic for Bernstein polynomials, described in Sect.
1.3.2, is used (see also
[106]).
The advantage of the Bernstein form is the higher numerical stability
of the roots in comparison to the power basis and
the convex hull property. If
or
for all
,
there is no solution and the two surfaces do not intersect. More
precisely, the entire algebraic surface
does not
intersect the surface patch
for
. Obviously, when all
the two surfaces
coincide in their entirety. A somewhat complex algebraic curve
is shown in Fig. 5.18 involving various branches
(from border to border), internal loops, and singularities.
Next: 5.8.1.2 Tracing method
Up: 5.8.1 Rational polynomial parametric/implicit
Previous: 5.8.1 Rational polynomial parametric/implicit
Contents Index
December 2009