Page 207 - Geometric Modeling and Algebraic Geometry

210 C. Liang et al.
Computing the topology of the curve C:
INPUT:f(x) and g(x) polynomials ∈ Q[x, y, z], a tolerance and a list of bounding domain
∈ R).
D 0 ← [a 0,b 0] × [a 1,b 1] × [a 2,b 2] (a i,b i
• Step 0: (initialization step) domain list D← D 0; vertex list V ← NIL; connectivity list
E ← NIL;
• Step 1: compute t ← (f) ∧ (g) given by Eq. (11.7);
• Step 2: convert f, g and t into Bernstein basis representation;
• Step 3: while D is not empty, pick a D in D:
– Step 3.1: compute V the set of intersection points between the boundary of the domain
D and the curve C;
– Step 3.2: if the size of D is larger than :
· if the curve C within the domain D is regular (see section 11.3.2):
· sort and connect the points v ∈ V ; the connectivities are stored in E;
· else if the domain D is not regular:
· subdivide D and append the subdivided domains into the domain list D
– else if the size of D is not larger than :
· add the domain D as a ’box’ vertex into V ;
· this vertex is connected with all intersections v ∈ V of D; these connectivities
are also appended to E;
– Step 3.4: remove D from D and repeat Step 3;

OUTPUT: The graph represented by a set of vertices V , which are either 3D points or boxes
(with size less than ) bounding the singularities, and a set of connections E that are repre-
senting the edges of the resulting graph.

points). Notice that a pure algebraic approach, exploiting the specificity of problem
and with a very efficient Gr¨ obner engine takes about 10 minutes to certify the topol-
ogy (see [3]).
The second example is a projection of a self-intersection curve of bicubic patch,
computed by resultant techniques (see [9]). The input polynomial is of total degree
76, of multidegree (44, 44) with 1905 monomials. The coefficients are integers of at
most 288 bits. It takes 5 seconds, for this example with the same precision =10 −3 .

11.4.2 Intersection curves of implicit surfaces

This set of examples are from [8]. The computational time accompanied is measured
up to milliseconds (see Fig. 11.2):

1) f(x)=0.85934x +0.259387xy +0.880419y +0.524937xz − 0.484008yz +
2
2
0.510242z − 1
2
g(x)=0.95309x +0.303149xy +0.510242y − 0.200075xz +0.64647yz +
2
2
0.786669z − 1
2
time: 80 msec
2) f(x)= −0.125x − 0.0583493xy +0.493569y +0.966682xz − 1.5073yz −
2
2
0.368569z − 0.865971x − 0.433067y − 0.250095z
2