Page 150 - Geometric Modeling and Algebraic Geometry

8 Ridges and Umbilics of Polynomial Parametric Surfaces 151
Selecting only points belonging to D reduces to adding inequalities to the sys-
tems and is well managed by the RUR. According to [19], solving such systems is
equivalent to solving zero-dimensional systems without inequalities when the num-
ber of inequations remains small compared to the number of variables. The RUR of
the study points provides a way to compute a box around each study point q i which is
a product of two intervals [u ; u ]×[v ; v ]. The intervals can be as small as desired.
1
2
1
2
i
i
i
i
Until now, we only have separate information on the different systems. In order
to identify study points having the same v-coordinate, we need to cross this infor-
mation. First we compute isolation intervals for all the v-coordinates of all the study
points together, denote I this list of intervals. If two study points with the same v-
coordinate are solutions of two different systems, the gcd of polynomials enable to
identify them:
• Initialize the list I with all the isolation intervals of all the v-coordinates of the
different systems.
• Let A and B be the square free polynomials defining the v-coordinates of two
different systems, and I A ,I B the lists of isolation intervals of their roots. Let
C = gcd(A, B) and I C the list of isolation intervals of its roots. One can refine
the elements of I C until they intersect only one element of I A and one element
of I B . Then replace these two intervals in I by the single interval which is the
intersection of the three intervals. Do the same for every pair of systems.
• I then contains intervals defining different real numbers in one-to-one corre-
spondence with the v-coordinates of the study points. It remains to refine these
intervals until they are all disjoint.
Second, we compare the intervals of I and those of the 2d boxes of the study
points. Let two study points q i and q j be represented by [u ; u ] × [v ; v ] and
1
1
2
2
i
i
i
i
[u ; u ] × [v ; v ] with [v ; v ] ∩ [v ; v ] = ∅. One cannot, a priori, decide if these
2
1
1
1
2
2
1
2
i
j
j
i
j
j
j
j
two points have the same v-coordinate or if a refinement of the boxes will end with
disjoint v-intervals. On the other hand, with the list I, such a decision is straightfor-
ward. The boxes of the study points are refined until each [v ; v ] intersects only one
2
1
i
i
interval [w ; w ] of the list I. Then two study points intersecting the same interval
2
1
i
i
[w ; w ] are in the same fiber.
2
1
i
i
Finally, one can refine the u-coordinates of the study points with the same v coor-
dinate until they are represented with disjoint intervals since, thanks to localizations,
all the computed points are distinct.
Checking genericity conditions of section 8.3.2.
First, real singularities shall be the union of purple and umbilical points, this
reduces to compare the systems for singular points and for purple and umbilical
points. Second, showing that δ(P 3 ) =0 for umbilics and δ(P 2 ) > 0 for purple
points reduces to sign evaluation of polynomials at the roots of a system (see section
8.3.1).