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 ] ×
   193   194   195   196   197   198   199   200   201   202   203