Page 197 - Geometric Modeling and Algebraic Geometry

200 C. Liang et al.
One major obstacle for adopting implicit representations instead of parametric
representations concerns the piecewise linear approximation of such curves or sur-
faces for visualization purposes. A brute force approach would be an exhaustive
evaluation for approximating the zero level set, which is obviously very inefficient.
A typical alternative scenario is to adopt a divide-and-conquer approach. Larger un-
determined domains are broken down to smaller predictable domains in which the
topological feature and eventually, the curve/surface itself can be inferred efficiently.
An objective of this paper is to describe an efficient method, which allows us to cap-
1
ture the topology of an implicit curve, when this curve is smooth , but also to localize
the singular points if they exist.
The problem of computing the topology of curves has been approach in different
ways. A first family of methods is based on a sweeping approach. For 2D planar al-
gebraic curves, such approach has been studied in [7] and [10]. It was later extended
by Gatellier et al. in [8] to the 3D spatial curves resulting from the intersection
of two algebraic surfaces. See also [2]. These methods use a conceptual sweeping
line/plane perpendicular to some projection axis, and detect the critical topological
events, such as tangents to the sweeping planes and singularities. The final output of
these methods are a graph of connected vertices complying to the topology of the
original curves. A notable problem of aforementioned approaches is that they relies
of the computation of sub-resultant sequences, which can be a bottleneck in many
examples with large degree and large coefficients (see Section 11.4.1).
Another family of methods are the subdivision based techniques, which uses a
simple criterion to remove domains which do not contain the roots. A crucial prob-
lem involved here is how to efficiently and reliably deduce the root information in
a given interval (or a bounding box). In these methods, instead of using monomial
representation, we represent the equations using Bernstein basis [6]. Among early at-
tempts, Sederberg [17] converted an algebraic curve in to piecewise triangular Bern-
stein basis. See also [13] combining symbolic and numeric techniques to compute
the topology of 2D curves. The approach of [11] for computing the curves of in-
tersection of two parameterised surfaces is also combining subdivision techniques
with regularity criterion, exploiting the properties of the intersection curve in the 2D
parameter domains.
The first problem of computing roots of univariate polynomials has been ana-
lyzed for instance in [15], where root information tests are by based on Descartes’
Law of Sign and its variant in the Bernstein basis. This approach has been extended
to the approximation of isolated roots of multivariate systems. In [18], the author
used tensor product version of Bernstein basis and integrated domain reduction tech-
niques to speed up the convergence and reduce the number of subdivisions. In [4],
the emphasis is put on the subdivision process, and stopping criterion based on the
normal cone to the surface patch. In [14], this approach has been improved by intro-
ducing pre-conditioning and univariate-solver steps. The complexity of the method
is also analyzed in terms of intrinsic differential invariants.

The tangent vector space exists at every points
1