Page 202 - Geometric Modeling and Algebraic Geometry

11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 205
Proposition 3. If ∂ y f(x, y) =0 (resp. ∂ x f(x, y) =0) in a domain D =[a 0 ,b 0 ] ×
[a 1 ,b 1 ] ⊂ R , the curve C is regular on D.
2
Proof. Suppose that ∂ y f(x, y) =0 in D. Then C is smooth, since its normal vector
is defined everywhere, and has no vertical tangents in D. By the implicit function
◦
theorem, the connected components of C∩ D are the graph of functions of the form
y = ϕ(x). The closure of such a connected component is called hereafter a branch
of C in D.As ∂ y f(x, y) =0 in D,foragiven x ∈ [a 0 ,b 0 ] there is at most one
◦
branch of C in D above x. Consequently, the connected components of C∩ D project
bijectively onto non-overlapping open intervals of [a 0 ,b 0 ].
Moreover, as there is no vertical tangent, each of these branches starts and ends
at a point on the border ∂D of D. Notice that two branches may share a starting or
ending point, when the curve is tangent (with even multiplicity) to ∂D.
Thus, computing the points of C∩∂D, repeating a point if its multiplicity is even,
sorting them by lexicographic order such that x>y ((x 0 ,y 0 ) > (x 1 ,y 1 ) if x 0 >x 1
or x 0 = x 1 and y 0 >y 1 ), we obtain a sequence of points p 1 ,p 2 ,...,p 2 s−1 ,p 2 s
such that the curve C in D is isotopic to the union of the non-intersecting segments
[p 1 ,p 2 ],..., [p 2s−1 ,p 2s ]. In other words, the topology of C is uniquely determined
from its intersection points with ∂D and C is regular on D.
If ∂ y f =0 on D (resp. ∂ x f =0), we will say that C is x-regular (resp. y-regular). A
sufficient condition for f to be x-regular (respectively y-regular) is that the Bernstein
coefficients of the first derivative of f against y (respectively x) maintains a constant
sign (see also [1]). By Descartes’ law, this statement implies that the sign variation
in this direction should be at most 1.
To put it in another way, by solely studying the sign variations of the tangential
gradient vector of the curve (represented in Bernstein basis), i.e. (∂ y f(x), −∂ x f(x)),
we are able to detect when the curve is regular on D and to determine uniquely the
topological graph.

3D case:

The 2D approach can be generalized to the 3D case where the tangential gradient
vector of the curve C defined by the intersection of two algebraic surfaces, namely
f(x, y, z)=0 and g(x, y, z)=0,isgiven by t = %(f) ∧%(g) (see Eh. (11.7)).
Similar to the 2D case, we can represent each component of t in the Bernstein basis
for a given domain (in cube shape) D =[a 0 ,b 0 ]×[a 1 ,b 1 ]×[a 2 ,b 2 ]. The sign change
of the resulting Bernstein coefficients enables a simple regularity test with minimal
computation effort.
We describe a first and simple regularity criterion:
Proposition 4. The 3D spatial curve C defined by f =0 and g =0 is regular on D,
if

• t x (x) =0 on D, and
• ∂ y h =0 (or ∂ z h =0)on D,for h = f or h = g.