Page 153 - Geometric Modeling and Algebraic Geometry

154 F. Cazals et al.
below the next fiber. Hence there is only one way to perform connections with non-
intersecting straight segments. More precisely, vertices of the graph are the centers
of isolation boxes, and edges are line-segments joining them.
Notice that using the intermediate fibers v = δ i is compulsory if one wishes to
get a graph G isotopic to P. If not, whenever two branches have common starting
points and endpoints, the embedding of the graph G obtained is not valid since two
arcs are identified.
The algorithm is illustrated on Fig. 8.3. In addition
• If a singular point box have width δ, then the distance between the singular point
and the vertex representing it is less than δ.
• One can compute the sign of the function Sign ridge (definition 2) for each reg-
ular point of each intermediate fiber. This defines the color of the ridge branch
it belongs to. Then one can assign to each edge of the graph the color of its end
point which is on an intermediate fiber.

8.4 Illustration

We provide the topology of ridges for two B´ ezier surfaces defined over the domain
D =[0, 1] × [0, 1].
The first surface has control points
⎛ ⎞
[0, 0, 0] [1/4, 0, 0] [2/4, 0, 0] [3/4, 0, 0] [4/4, 0, 0]
⎜ [0, 1/4, 0] [1/4, 1/4, 1] [2/4, 1/4, −1] [3/4, 1/4, −1] [4/4, 1/4, 0] ⎟
⎜ ⎟
⎜ [0, 2/4, 0] [1/4, 2/4, −1] [2/4, 2/4, 1] [3/4, 2/4, 1] [4/4, 2/4, 0] ⎟
⎜ ⎟
⎝ [0, 3/4, 0] [1/4, 3/4, 1] [2/4, 3/4, −1] [3/4, 3/4, 1] [4/4, 3/4, 0] ⎠
[0, 4/4, 0] [1/4, 4/4, 0] [2/4, 4/4, 0] [3/4, 4/4, 0] [4/4, 4/4, 0]
Alternatively, this surface can be expressed as the graph of the total degree 8 poly-
nomial h(u, v) for (u, v) ∈ [0, 1] :
2
h(u, v) = 116u v − 200u v + 108u v − 24u v − 312u v + 592u v − 360u v
3 2
4 4
4 2
3 4
4 3
3 3
4
+80u v+252u v −504u v +324u v −72u v−56uv +112uv −72uv +16uv.
3
2
4
2 2
2
2 3
3
2 4
The computation of the implicit curve has been performed using Maple 9.5 and re-
quires less than one minute (see [3]). It is a bivariate polynomial P(u, v) of total
degree 84,ofdegree 43 in u, degree 43 in v with 1907 terms and coefficients with
up to 53 digits. Figure 8.4 displays the topological approximation graph of the ridge
curve in the parametric domain D computed with the algorithm of section 8.3. There
are 19 critical points, 17 purple points and 8 umbilics, 3 of which are 3-ridge and 5
are 1-ridge.
We have computed the subsets S u , S p and S c by using the software FGB and
RS (http://fgbrs.lip6.fr). The RUR can be computed as shown in [19] or
alternatively, Gr¨ obner basis can be computed first using [5] or [6]. We tested both