Page 143 - Geometric Modeling and Algebraic Geometry

144 F. Cazals et al.
allows a global characterization of ridges [18, Chapter 11] as a 1 dimensional smooth
sub-manifold in a 7 dimensional space. But this characterization is not amenable to
algorithmic developments.
Shifting from this seven-dimensional space to the parametric space, the theory of
algebraic invariants has been used to derive the equation of the ridge curve as the zero
set of an invariant function [8]. The ensuing strategy consists of defining invariants
as functions of the fundamental forms and their derivatives. The equation of ridges
is given in this setting. If one further specializes this equation for a surface given by
a parameterization, the result matches, up to a constant factor, our implicit encoding
P =0 [3]. The point of view of our approach is to work from the beginning on a
parametrized surface. The definition of ridges involves principal curvatures and prin-
cipal directions of curvature which are independent of the given parametrization, but
we explicit all these invariants wrt the parametrization and its derivatives. Hence, for
polynomial parametric surfaces, we end with a polynomial with integer coefficients
whose variables are the partial derivatives of the parametrization up to the third order.
This polynomial is the same for any other parametrization.

Reporting the topology of an algebraic curve. In the case of a polynomial paramet-
ric surface, we recast the problem of approximating ridges into the field of algebraic
geometry. We recall that the standard tool to compute a graph encoding the topology
of a 2-D or 3-D curve is the Cylindrical Algebraic Decomposition (CAD) [7, 9].

8.1.3 Contributions and paper overview

Let Φ(u, v) be a smooth parameterized surface over a domain D⊂ R . We wish to
2
report a certified approximation of its ridges, which subsumes a solution for all the
difficulties enumerated in section 8.1.1.
The first step in providing a certified approximation of the ridges of Φ consists
of computing an implicit equation P =0 encoding these ridges. The derivation of
this equation is presented in the companion paper [3], which also contains a detailed
discussion of our implicit encoding of ridges wrt previous work.
The equation P =0 being taken for granted, the contribution developed in this
paper is to exploit as far as possible the geometry of P encoded in P =0,soas
to develop the first algorithm able to compute the ridges topology of a polynomial
parametric surface. Our algorithm avoids the main difficulties of CAD methods:
(i) singular and critical points are sequentially computed directly in 2D; (ii) no
generic assumption is required, i.e. several critical or singular points may have
the same horizontal projection; (iii) no computation with algebraic numbers is
involved. Because algorithms based on the Cylindrical Algebraic Decomposition are
not effective for our high degree curves such as P =0, our algorithm is to the best
of our knowledge the only one able to certify properties of the curve P =0.
The paper is organized as follows. The implicit equations for ridges and its singu-
larities are recalled in section 8.2. The algorithm to compute the topology of the ridge
curve is described in section 8.3. Section 8.4 provides illustrations on two B´ ezier sur-
faces.