Page 198 - Geometric Modeling and Algebraic Geometry
P. 198
11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 201
The application of subdivision methods for handling higher dimensional objects
is not so well developed. In [12] a method which subdivides up to some precision
level, and applies dual marching cube approach to connect points on the curve or
to mesh a surface is described. The variety is covered by boxes of a given size, and
the connectivity of these cells is used to deduce the piecewise linear approximation.
In [1], a subdivision approach exploiting the sign variation of the coefficients in the
Bernstein basis in order to certify the topology of the surface in a cell, is used for the
purpose of polygonalizing an implicit algebraic surface.
The work of this paper is in the spirit of this former approach. We apply a sub-
division approach also exploiting the properties of the Bernstein polynomial rep-
resentation. We describe a simple regularity test extending the criterion of [1] to
curves, which allows us to detect easily when the topology of the curve in a cell is
uniquely determined from its intersection with the border of the cell. This provides
an efficient test for stopping earlier the subdivision process and branching to path
following methods if we are interested in a good geometrical approximation of the
curve.
We address the same question as in [8], but with this new methods, we are able
to solve the following problems already identified in this paper:
• To achieve higher numerical stability by operating on Bernstein basis instead of
monomial basis;
• Through subdivision on three principle directions, i.e. x, y, z (or x, y, z), to iso-
late the domain containing the singularities from those containing regular curve
segments. This divide-and-conquer approach, in principle, should simplify the
graph building algorithm adopted in [8] where the whole domain has to be con-
sidered.
However, for the treatment of singular points, we have to introduced a threshold
to stop the subdivision. Contrarily to [8], we do not certify the topology at singular
points, but computed boxes of size , containing these singularities.
On the contrary, we show that our approach is able to handle implicit curves
with large equation (of total degree about 80 with coefficients of bit-size 200), which
resultant-based techniques are not able to treat.
This paper is organized as follows: in Section 11.2, we will review some of the
relevant concepts and theorem required by our proposed algorithm; Section 11.3 is
devoted to outlining our proposed algorithms and the details about how the essential
steps in our algorithm are handled. We will show the experiment results in Section
11.4 and conclude in Section 11.5 with the problems and possible improvements
over the currently proposed algorithm.
11.2 Fundamental ingredients
This section introduces the theoretical background of Bernstein polynomial represen-
n
tation and how it is related to the problem we want to solve. For a domain D ⊂ R ,
◦
we denote by D its interior, by D its closure. For a box D =[a 0 ,b 0 ] × [a 1 ,b 1 ] ×