Page 204 - Geometric Modeling and Algebraic Geometry

11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 207

If p 1 and p 2 are on the same connected component of the level set f(x)= f 0
(where f 0 = f(p 1 )= f(p 2 ))in U, then g reaches the same value at p 1 and p 2 on
this level set, so that by Role’s theorem, there exists a point p ∈ U in-between p 1
)(p)= t x (p)=0. By hypothesis, this is impossible.
and p 2 , such that Jac(Φ x 0
Thus p 1 and p 2 belongs to two different connected components of f(x)= f 0 in
U. Consequently the value f 0 is reached at 4 distinct points of ∂U, which implies
that f has at least 4 extrema on ∂U.

Now note that up to a change of variable z = a 2 − z, we can assume that
∂ z f> 0 on both y = a 1 ,y = b 1 faces. Then if ∂ y f< 0 on z = a 2 ,wehave
f(x 0 ,a 1 ,b 2 ) >f(x 0 ,a 1 ,a 2 ) >f(x 0 ,b 1 ,a 2 ) and (a 2 ,a 3 ) is not a local extrema.
Otherwise ∂ y f> 0 and (b 1 ,a 2 ) is not a local extrema. In both cases, we do not have
is injective and that the intersection of C with the
4 extrema, which proves that ϕ x 0
plane x = x 0 in D is at most one point. So by proposition 5, we deduce that C is
regular in D.

For more details on the injectivity properties, see [16]. Here also, a similar crite-
rion applies by symmetry, exchanging the roles of the x, y, z coordinates.
If one of these criteria applies with t i (x) =0 on D (for i = x, y, z), we will say
that C is i-regular on D.
From a practical point of view, the test that t i (x) =0 or ∂ i (h) for i = x, y
or z, h = f or g, is replaced by the stronger condition that their coefficients on
the Bernstein basis of D have a constant sign, which is straightforward to check.
Similarly, such a property on the faces of D is also direct, since the coefficients of
a polynomial, with a minimal (resp. maximal) x-indices (resp. y-indices, z-indices)
are its Bernstein coefficients on the corresponding face.
In addition to these tests, we also test whether both surfaces penetrate the cell,
since a point on the curve must lie on both surfaces. This test could be done by
looking at the sign change of the Bernstein coefficients of the surfaces with regards
to that cell. If no sign change occurs, we can rule out the possibility that the cell
contains any portion of the curve C, hence terminate the subdivision early. In this
case, we will also say that the cell is regular.
The regularity criterion is sufficient for us to uniquely construct the topologi-
cal graph g of C within D. Without loss of generality, we suppose that the curve C
is x-regular in D. Hence, there is no singularity of C in D. Furthermore, this also
guarantees that there is no ‘turning-back’ of the curve tangent along x-direction, so
the mapping of C onto the x axis is injective. Intuitively, the mapped curve should
be a series of non-overlapping line segments, of which the ends correspond to the
intersections between the curve C and the cell, and such mapping is injective.
This property leads to a unique way to connect those intersection points, once
they are computed (see section 11.3.3), in order to obtain a graph representing the
topology of C. Here is how this graph is computed in practice: suppose C is i-regular
in the domain D, and that we have computed the set of intersection points V = {v j }
of the curve with the boundary of D. First, we sort the elements in V comparing