Page 206 - Geometric Modeling and Algebraic Geometry

11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 209
We assume that the input equations are given with exact (large) rational (or inte-
ger) numbers (even if the input is given with floating point numbers, we will consider
it as an exact input). In order to compute the topology of C in a domain D, we convert
its representation in the Bernstein basis of D, using exact rational arithmetic.
Once this conversion is done, we normalize the equation, by dividing by the
coefficient of maximal norm. For each resulting rational coefficient c, we compute
the smallest interval [c, c] represented with floating point numbers and containing c.
Then, the subdivision process is performed, using interval arithmetic. The reg-
ularity criterion, which reduces to sign evaluations, is applied on these interval co-
efficients. We use the following convention: a interval is < 0 (resp. > 0) if all its
elements are < 0 (resp. > 0). If the interval contains 0, we say that its sign is inde-
terminate.
If the regularity test fails,

• either the sign of all the coefficients of the polynomial are indeterminate, and
we re-convert the exact polynomial to its representation on the corresponding
sub-domain and restart the approximation process.
• or we subdivide the domain, as in the usual case.

11.3.5 Outline of the algorithm

The proposed algorithm for 3D curves is outlined as follows:
We do not describe the algorithm for 2D curves, which is basically a specializa-
tion of this one.

11.4 Experiments

Our proposed algorithm is implemented as a part of SYNAPS (SYmbolic Numeric
2
APplicationS) library . The experiments have been carried out on a 3.4GHz PC,
under Linux.

11.4.1 Planar curves of high degree with large coefficients

In this section, we report on the application of the 2d algorithm, in the case of large
integer coefficients. The first example is about ridge curve. Ridge curves correspond
to local extrema of curvature taken in the principal direction of the surface, after
some algebraic manipulations they can be obtained as implicit curve (see [3]). See
also [19] and [20] for other related approaches. In the example it corresponds to a
bicubic surface, the input polynomial is of total degree 84, of multidegree (43, 43)
with 1907 monomials. The coefficients are integers encoded on at most 65 bits. For
the precision =10 −3 which controls the singularity localization, it takes 30 sec-
onds. The topology is certified except in tiny boxes (which contains the singularity

http://www-sop.inria.fr/galaad/software/synaps/
2