Page 210 - Geometric Modeling and Algebraic Geometry

11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 213
11.5 Discussion

The algorithm proposed in this paper offers a generic method for computing the
topological graph of spatial curves resulting from the intersection of two algebraic
surfaces. As demonstrated in the experiments, it is rather robust despite the increase
of the complexity of the curve.
The major weakness of this approach, however, is that certain apparently sim-
ply situation could result in a lot of subdivisions, such as the curve with parallel
structures which are very close to each other.
As specified, in this method, the singular points are only isolated into small boxes
of size , and we do not certify the connection of the branches at these points. An
additional work would be necessary, to certify the singularity type. We are currently
investigating on this problem.
Another weakness of this approach is the memory consumption (as the storage
requirement is approximately cubic to the depth of the subdivision). This problem
however, can be mitigated by a divide-and-conquer approach and pure programming
techniques.

Acknowledgements:
3
We would like to thanks J. Wintz, for his very nice software AXEL for the visuali-
sation and manipulation of algebraic objects, that we used to produce the pictures of
the curves. We acknowledge the partial support of Aim@Shape (IST NoE 506766)
and ACS (IST Fet Open 006413).

References

1. L. Alberti, G. Comte, and B. Mourrain. Meshing implicit algebraic surfaces: the smooth
case. In L.L. Schumaker M. Maehlen, K. Morken, editor, Mathematical Methods for
Curves and Surfaces: Tromso’04, pages 11–26. Nashboro, 2005.
2. J. Gerardo Alc´ azar and J. Rafael Sendra. Computing the topology of real algebraic space
curves. J. Symbolic Comput., 39:719–744, 2005.
3. F. Cazals, J.-C. Faug` ere, M. Pouget, and F. Rouillier. Topologically certified approxima-
tion of umbilics and ridges on polynomial parametric surface. Technical Report 5674,
INRIA Sophia-Antipolis, 2005.
4. G. Elber and M.-S Kim. Geometric constraint solver using multivariate rational spline
functions. In Proc. of 6th ACM Symposium on Solid Modelling and Applications, pages
1–10. ACM Press, 2001.
5. G. Farin. Curves and surfaces for computer aided geometric design:apractical guide.
Comp. science and sci. computing. Acad. Press, 1990.
6. G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide,
3rd Ed. Academic Press, 1993.
7. T. Grandine and F. Klein. A new approach to the surface intersection problem. Computer
Aided Geometric Design, 14(2):111–134, 1997.
3 http://www-sop.inria.fr/galaad/software/axel/