Berberich et al. introduce an algorithm for computing the topology of a surface in three-dimensional (3D) space, implicitly represented by a polynomial in three unknowns of arbitrary degree N. For any given polynomial shape, the algorithm produces a finite structure representing the topology (and some other geometric characteristics, such as singularities) of the considered surface, allowing, for example, one to determine very easily if the surface is connected or not, if it is bounded or not, and to compute the number of its connected components.
The proposed algorithm is based on an adaptation to this particular case of the classical cylindrical algebraic decomposition (CAD), introduced by George Collins in the 1960s, to deal with the quantifier elimination problem over the reals. This algorithm goes a step beyond recent progress, showing how to efficiently use in practice algebraic techniques to deal with particular instances of geometrical problems, like the one considered here, that are very relevant to computer-aided geometric design. These adaptations are usually based on adequately mixing the aforementioned algebraic techniques (subresultants, Sturm-Habicht sequences, and symbolic real root solving) with numerical, combinatorial, or geometrical information coming from the particular problem considered.
The proposed method is projection based: the topology of the considered surface is obtained by projecting it on the plane, and then analyzing the topology of the obtained curve arrangement that is later lifted to the 3D space in order to obtain the searched topology. One of the main advantages of the proposed algorithm is that it does not require any special hypothesis for the projection to be considered--a very typical restriction of the algorithms dealing with the analysis of geometrical entities defined implicitly.
The authors also report the implementation in C++ of the presented algorithm (to be included in a future release of the Computational Geometry Algorithms Library (CGAL)), showing very good performance for surfaces defined by polynomials of low degree (up to degree six in any of the three considered variables).
This paper is very clearly written; despite some technicalities difficult to avoid, it can be easily understood by anyone interested in using this algorithm to analyze the topology of a surface in 3D space, presented implicitly.