Page 164 - Geometric Modeling and Algebraic Geometry

166 S. Chau et al.
≥ 0 (the tolerance). Following [12], the approximate implicitization problem con-
sists in finding a non–zero polynomial P ∈ R[x, y, z] of degree d such that
∀(u, v) ∈ [0, 1] ,P (x(u, v)+ α(u, v) g(u, v)) = 0 (9.9)
2
with |α(u, v)|≤ and ||g(u, v)|| 2 =1. Here, α is the error function and g is the
direction for error measurement, e.g., the unit normal direction of the surface patch.

9.4.2 Approximate implicitization of a biquadratic surface

The main question of the approximate implicitization problem is how to choose the
degree. A key ingredient for this choice seems to be the topology, especially if the ini-
tial surface has self–intersections. The use of degree 4 was suggested by Tor Dokken;
after several experiments he concluded that the algebraic surfaces of degree 4 pro-
vide sufficiently many degrees of freedom to approximate most cases encountered in
practice. In the case of a biquadratic surface, where the exact implicit equation has
degree 8, using degree 4 seems to be a reasonable trade-off.
We describe two methods for approximate implicitization by a quartic for a bi-
quadratic surface. The approximate implicit equation is

4−i 4−i−j
4

i j k
P(x, y, z)= b ijk x y z (9.10)
i=0 j=0 k=0
with the unknown coefficients b =(b 000 ,b 100 ,...,b 004 ) ∈ R . Let β(u, v) be the
35
vector formed by the tensor–product Bernstein polynomials of bidegree (8,8).
Dokken’s method.

This method, which is described in more detail in [12], proceeds as follows:
T
1. Factorize P(x(u, v)) = (Db) β(u, v) where D is a 81 × 35 matrix.
2. Generate a singular values decomposition (SVD) of D.
3. Choose b as the vector corresponding to the smallest singular value of D.
Note that this method is general and does not use the fact that we have a biquadratic
surface. Hereafter, we use an adapted method based on the geometry of the surface
of bidegree (2,2). Also, the computation of the singular value decomposition needs
floating point numbers.

Geometric method using evaluation:

This approach consists in constructing some pertinent geometrical constraints to give
a linear system of equations (with the unknowns b 000 ,b 100 ,...,b 004 ), and then solv-
ing the resulting system by a singular values decomposition. In our method, we char-
acterize some conics, especially the four border conics and two interior conics: