Abstract
An algorithm is proposed to determine the topology of an implicit real algebraic surface in ℝ3. The algorithm consists of three steps: surface projection, projection curve topology determination and surface patches composition. The algorithm provides a curvilinear wireframe of the surface and the surface patches of the surface determined by the curvilinear wireframe, which have the same topology as the surface. Most of the surface patches are curvilinear polygons. Some examples are used to show that our algorithm is effective.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arnborg, S., Feng, H.: Algebraic decomposition of regular curves. J. Symbolic Comput. 5(1,2), 131–140 (1988)
Arnon, D.S., Collins, G., McCallum, S.: Cylindrical algebraic decomposition I: the basic algorithm. In: Buchberger, B., Collins, G.E. (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 136–151. Springer, Heidelberg
Arnon, D.S., McCallum, S.: A polynomial-time algorithm for the topological type of a real algebraic curve. J. Symbolic Comput. 5(1,2), 213–236 (1988)
Bajaj, C., Hoffmann, C.M., Lynch, R.E., Hopcroft, J.E.H.: Tracing surface intersection. Computer Aided Geometric Design 5, 285–307 (1988)
Bajaj, C., Xu, G.L.: Spline approximations of real algebraic surfaces. J. Symbolic Comput. 23, 315–333 (1997)
Basu, S., Pollack, R., Roy, M.-F.: Algorithms in real algebraic geometry. In: Algorithms and Computat. in Mathematics, vol. 10, Springer, Heidelberg (2003)
Feng, H.: Decomposition and computation of the topoplogy of plane real algebraic curves, PhD Thesis, The Royal Institute of Technology, Stockholm, Sweden (1992)
Fortuna, E., Gianni, P., Parenti, P., Traverso, C.: Algorithms to compute the topology of orientable real algebraic surfaces. J. Symbolic Comput. 36, 343–364 (2003)
Gao, X.S., Li, M.: Rational quadratic approximation to real algebraic curves. Computer Aided Geometric Design 21, 805–828 (2004)
Gatellier, G., Labrouzy, A., Mourrain, B., Técourt, J.P.: Computing the topology of three dimensional algebraic curves. In: Computational Methods for Algebraic Spline Surfaces, pp. 27–44. Springer, Heidelberg (2004)
Geismann, N., Hemmer, M., Schömer, E.: Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually. In: Symposium on Computational Geometry, pp. 264–273 (2001)
Gianni, P., Traverso, C.: Shape determination for real curves and surfaces. Ann. Univ. Ferrara Sez. VII(N.S.) 29, 87–109 (1983)
Gonzalez-Vega, L., El Kahoui, M.: An improve upper complexity bound for the topology computation of a real algebraic plane curve. J. Complexity 12, 527–544 (1996)
Gonzalez-Vega, L., Necula, I.: Efficient topology determination of implicitly defined algebraic place curves. Computer Aided Geometric Design 19, 719–743 (2002)
Hart, J.C.: Morse theory for implicit surface modeling. In: Hege, H.-C., Polthier, K. (eds.) Mathematical Visualization, pp. 257–268. Springer, Heidelberg (1998)
Hong, H.: An efficient method for analyzing the topology of plane real algebraic curves. Math. Comput. Simulation 42(4-6), 571–582 (1996)
Johnson, J.R.: Algorithms for polynomial real root isolation. Ph.d. Thesis. The Ohio state University (1991)
Keyser, J., Culver, T., Krishnan, S.: Efficient and exact manipulation of algebraic points and curve. Computer Aided Design 32(11), 649–662 (2000)
Massey, W.S.: A basic course in algebraic topology. Springer, Heidelberg (1991)
Ni, X.L., Garland, M., Hart, J.C.: Fair morse functions for extracting topological structure of a surface mesh. In: Proc. SIGGRAPH 2004 (2004)
Sakkalis, T.: The topological configuration of a real algebraic curve. Bull. Australian Math. Soc. 43(1), 37–50 (1991)
Stander, B.T., Hart, J.C.: Guaranteeing the topology of an implicit surface polygonization for interactive modeling. In: Proc. SIGGRAPH 1997, pp. 279–286 (1997)
Walker, R.J.: Algebraic curves. Springer, Heidelberg (1978)
Wu, W.T.: Mathematics Mechanization. Science Press/Kluwer, Beijing (2000)
Yang, L., Zhang, J.Z., Hou, X.R.: Nonlinear Algebraic Equation System and Automated Theorem Proving. Shanghai Scientific and Technological Education Publishing House, Shanghai (1996)
Zhang, S.G., Liu, D.Z., Feng, G.C.: Computer Mathematics: an introduction (in Chinese). Jilin University Press (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheng, JS., Gao, XS., Li, M. (2005). Determining the Topology of Real Algebraic Surfaces. In: Martin, R., Bez, H., Sabin, M. (eds) Mathematics of Surfaces XI. Lecture Notes in Computer Science, vol 3604. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11537908_8
Download citation
DOI: https://doi.org/10.1007/11537908_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28225-9
Online ISBN: 978-3-540-31835-4
eBook Packages: Computer ScienceComputer Science (R0)