Page 146 - Geometric Modeling and Algebraic Geometry

8 Ridges and Umbilics of Polynomial Parametric Surfaces 147
In addition, the classification of an umbilic as 1-ridge or 3-ridges from P 3 goes
as follows:
• If P 3 is elliptic, that is the discriminant of P 3 is positive (δ(P 3 ) > 0), then the
umbilic is a 3-ridge umbilic and the 3 tangent lines to the ridges at the umbilic
are distinct.
• If P 3 is hyperbolic (δ(P 3 ) < 0) then the umbilic is a 1-ridge umbilic.

8.2.1 Polynomial surfaces

A fundamental class of surface used in Computer Aided Geometric Design con-
sists of polynomial surfaces like B´ ezier and splines. We first observe that if Φ is a
polynomial, all its derivatives are also polynomials. Thus in the polynomial case
the equation of ridges, which is a polynomial wrt to these derivatives, is alge-
braic. Hence the set of all ridges and umbilics is globally described by an algebraic
curve. Notice that the parameterization can be general, in which case Φ(u, v)=
(x(u, v),y(u, v),z(u, v)), or can be a height function Φ(u, v)=(u, v, z(u, v)).
As a corollary of Thm. 3, one can give upper bounds for the total degree of the
polynomial P wrt that of the parameterization. Distinguishing the cases where Φ is a
general parameterization or a height function (that is Φ(u, v)=(u, v, h(u, v))) with
h(u, v) and denoting d the total degree of Φ, P has total degree 33d−40 or 15d−22
for a height function.
In the more general case where the parameterization is given by rational fractions
of polynomials, P is a rational function of the surface parameters too. The denom-
inator of P codes the points where the surface is not defined and away from these
points, the numerator codes the ridges and umbilics.

8.3 Certified topological approximation

In this section, we circumvent the difficulties of the Cylindrical Algebraic Decom-
position (CAD) and develop a certified algorithm to compute the topology of P.
Consider a parameterized surface Φ(u, v), the parameterization being polynomial
with rational coefficients. Let P be the curve encoding the ridges of Φ(u, v).Weaim
at studying P on the compact box domain D =[a, b] × [c, d].
Given a real algebraic curve, the standard way to approximate it consists of re-
sorting to the CAD. Running the CAD requires computing singular points and criti-
cal points of the curve — points with a horizontal tangent. Theoretically, these points
are defined by zero-dimensional systems. Practically, because of the high degree of
the polynomials involved, the calculations may not go through. Replacing the bot-
tlenecks of the CAD by a resolution method adapted to the singular structure of P,
we develop an algorithm producing a graph G embedded in the domain D, which is
isotopic to the curve P of ridges in D. Key points are that:
1. no generic assumption is required, i.e. several critical or singular points may
have the same horizontal projection;
2. no computation with algebraic numbers is involved.