Page 152 - Geometric Modeling and Algebraic Geometry

8 Ridges and Umbilics of Polynomial Parametric Surfaces 153
the known number of branches connected to the study point. Then the intersections
are obviously in one-to-one correspondence with the branches. Second, as in [21]
for example, we reduce the height of the box again if necessary so that intersections
only occur on the top or the bottom of the box.
Counting the number of intersections reduces to solve 4 univariate polynomials
with rational coefficients. Reducing a box means refining its representation with the
RUR.

8.3.7 Step 3. Computing regular points in study fibers
We now compute the regular points in each fiber P(u, α i )=0. Computing the
regular points of each fiber is now equivalent to computing the roots of the poly-
nomials P(u, α i ) outside the intervals representing the u-coordinates of the study
points (which contain all the multiple roots of P(u, α i )).
Denote [u ; u ],j =1..m i the intervals representing the u-coordinates of the
2
1
i,j i,j
study points on the fiber of α i and [v ,v ] an interval containing (strictly) α i and no
1
2
i i
other α j ,j = i. Substituting v by any rational value q ∈ [v ,v ] in P(u, v) gives a
2
1
i i
univariate polynomial with rational coefficients P(u, q). We then isolate the (simple)
m i
roots of this polynomial P(u, q) on the domain [a, b]\∪ [u ; u ] : the algorithm
2
1
i,j
i,j
j=1
returns intervals [β ; β ],j =1 ...l i representing these roots.
1
2
i,j i,j
To summarize the information up to this point : we have, along each fiber, a
collection of points s i,j , i =1 ...s, j =1,...,m i + l i , which are either study
points or regular points of P. Each such point is isolated in a box i.e. a product of
−
intervals and comes with two integers (n ,n ) denoting the number of branches
+
i,j i,j
in D connected from above and from below.
8.3.8 Step 4. Adding intermediate rational fibers
Consider now an intermediate fiber, i.e. a fiber associated with v = δ i i =1 ...s−1,
with δ i a rational number in-between the intervals of isolation of two consecutive
values α i and α i+1 . If the fibers v = c or v = d are not fibers of study points, then
they are added as fibers δ 0 or δ s .
Getting the structure of such fibers amounts to solving a univariate polynomial
with rational coefficients, which is done using the algorithm described in section
8.3.1. Thus, each such fiber also comes with a collection of points, isolated in boxes,
for which one knows that n + = n − =1.
i,j
i,j
8.3.9 Step 5. Performing connections
We thus obtain a full and certified description of the fibers: all the intersection points
with P and their number of branches connected. We know, by construction, that the
branches of P between fibers have empty intersection. The number of branches con-
nected from above a fiber is the same than the number of branches connected from