×

Representing rational curve segments and surface patches using semi-algebraic sets. (English) Zbl 1439.65024

In the work for generating surfaces by (piecewise) rational curves or surfaces, the representation of the surfaces (or curves) using semi-algebraic sets is an important tool. Such surfaces have many useful applications and there are also other methods to define them, such as radial basis functions. In this particular approach, rational curves or surfaces defined by tensor-products of rational curves are used. The main idea is the generation of globally defined functions whose local parts (segments) the desired surfaces are (in other words, the parts of the surfaces we really need are sections of the unbounded ones). They are defined implicitly by semi-algebraic sets, and the provided algorithms for computing the surfaces work well unless there are singularities in the rational function. These singularities need to be identified, and this is achieved by creating boxes about the singularities where the curves are generated within a certain numerical error (by contrast, there is no error if there is no singularity). Many numerical examples are provided to show the success of the methods.

MSC:

65D10 Numerical smoothing, curve fitting
65D17 Computer-aided design (modeling of curves and surfaces)
65D12 Numerical radial basis function approximation

Software:

Implicit
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersson, L. E.; Peters, T.; Stewart, N., Selfintersection of composite curves and surfaces, Comput. Aided Geom. Des., 15, 507-527 (1998), URL: · Zbl 0996.65023
[2] Barton̆, M.; Elber, G.; Hanniel, I., Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests, Comput. Aided Des., 43, 1035-1044 (2011), URL:
[3] Buchberger, B., Groebner-bases: an algorithmic method in polynomial ideal theory, (Bose, N., Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems. Copyright (1985), Reidel Publishing Company: Reidel Publishing Company Dordrecht - Boston - Lancaster, the Netherlands). (Bose, N. K., Multidimensional Systems Theory and Application (2003), Kluwer Academic Publisher), 89-128, Chapter 6 · Zbl 0587.13009
[4] Buhmann, M. D., Radial Basis Functions: Theory and Implementations (2003), Cambridge University Press · Zbl 1038.41001
[5] Busé, L., Implicit matrix representations of rational Bézier curves and surfaces, Comput. Aided Des., 46, 14-24 (2014), 2013 {SIAM} Conference on Geometric and Physical Modeling
[6] Carr, J. C.; Beatson, R. K.; Cherrie, J. B.; Mitchell, T. J.; Fright, W. R.; McCallum, B. C.; Evans, T. R., Reconstruction and representation of 3D objects with radial basis functions, (Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (2001), ACM: ACM New York, NY, USA), 67-76, URL:
[7] Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer-Verlag: Springer-Verlag Wien · Zbl 0906.03033
[8] Chen, F.; Cox, D. A.; Liu, Y., The \(μ\)-basis and implicitization of a rational parametric surface, J. Symb. Comput., 39, 689-706 (2005), URL: · Zbl 1120.14054
[9] Chen, X.; Riesenfeld, R. F.; Cohen, E.; Damon, J., Theoretically based robust algorithms for tracking intersection curves of two deforming parametric surfaces, (Kim, M. S.; Shimada, K., Geometric Modeling and Processing - GMP 2006 (2006), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 101-114 · Zbl 1160.68614
[10] Chen, F.; Wang, W., The \(μ\)-basis of a planar rational curve—properties and computation, Graph. Models, 64, 368-381 (2002), URL: · Zbl 1055.68117
[11] Cheng, J. S.; Gao, X. S.; Li, J., Topology determination and isolation for implicit plane curves, (Proceedings of the 2009 ACM Symposium on Applied Computing (2009), ACM: ACM New York, NY, USA), 1140-1141, URL:
[12] Cheng, J. S.; Jin, K., A generic position based method for real root isolation of zero-dimensional polynomial systems, J. Symb. Comput., 68, 204-224 (2015), URL: · Zbl 1304.13048
[13] Chionh, E. W., Rectangular corner cutting and Dixon \(A\)-resultants, J. Symb. Comput., 31, 651-669 (2001), URL: · Zbl 0987.65044
[14] Cohen-Or, D.; Kaufman, A., Fundamentals of surface voxelization, Graph. Models Image Process., 57, 453-461 (1995), URL:
[15] Eigenwillig, A.; Kerber, M.; Wolpert, N., Fast and exact geometric analysis of real algebraic plane curves, (Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (2007), ACM: ACM New York, NY, USA), 151-158, URL: · Zbl 1190.14062
[16] Elber, G.; Grandine, T.; Kim, M. S., Surface self-intersection computation via algebraic decomposition, Comput. Aided Des., 41, 1060-1066 (2009), URL:
[17] Elkadi, M.; Mourrain, B., Residue and implicitization problem for rational surfaces, Appl. Algebra Eng. Commun. Comput., 14, 361-379 (2004), URL: · Zbl 1058.14073
[18] Galligo, A.; Pavone, J. P., A sampling algorithm computing self-intersections of parametric surfaces, (Elkadi, M.; Mourrain, B.; Piene, R., Algebraic Geometry and Geometric Modeling (2006), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 185-204 · Zbl 1107.65310
[19] Jia, X.; Goldman, R., \(μ\)-bases and singularities of rational planar curves, Comput. Aided Geom. Des., 26, 970-988 (2009), URL: · Zbl 1205.14033
[20] Krishnan, S.; Manocha, D., An efficient surface intersection algorithm based on lower-dimensional formulation, ACM Trans. Graph., 16, 74-106 (1997), URL:
[21] Laine, S., A topological approach to voxelization, Comput. Graph. Forum, 32, 77-86 (2013), URL:
[22] Li, J.; Shen, L. Y.; Gao, X. S., Proper reparametrization of rational ruled surface, J. Comput. Sci. Technol., 23, 290-297 (2008), URL:
[23] Manocha, D.; Canny, J. F., Algorithm for implicitizing rational parametric surfaces, Comput. Aided Geom. Des., 9, 25-50 (1992), URL: · Zbl 0817.65012
[24] Mourrain, B.; Pavone, J., Subdivision methods for solving polynomial equations, J. Symb. Comput., 44, 292-306 (2009), Polynomial System Solving in honor of Daniel Lazard · Zbl 1158.13010
[25] Pérez-Díaz, S., Computation of the singularities of parametric plane curves, J. Symb. Comput., 42, 835-857 (2007), URL: · Zbl 1138.14036
[26] Pérez-Díaz, S.; Sendra, J. R.; Villarino, C., Computing the singularities of rational surfaces, Math. Comput., 84, 1991-2021 (2015), URL: · Zbl 1318.14056
[27] Sagraloff, M.; Mehlhorn, K., Computing real roots of real polynomials, J. Symb. Comput., 73, 46-86 (2016), URL: · Zbl 1330.65072
[28] Sederberg, T. W.; Chen, F., Implicitization using moving curves and surfaces, (Proceedings of the 22Nd Annual Conference on Computer Graphics and Interactive Techniques (1995), ACM: ACM New York, NY, USA), 301-308, URL:
[29] Shen, L. Y.; Cheng, J. S.; Jia, X., Homeomorphic approximation of the intersection curve of two rational surfaces, Comput. Aided Geom. Des., 29, 613-625 (2012), URL: · Zbl 1256.65022
[30] Shen, L. Y.; Goldman, R., Implicitizing rational tensor product surfaces using the resultant of three moving planes, ACM Trans. Graph., 36, 1-14 (2017), URL:
[31] Shen, L. Y.; Goldman, R., Combining complementary methods for implicitizing rational tensor product surfaces, Comput. Aided Des., 104, 100-112 (2018), URL:
[32] Shen, L. Y.; Yuan, C. M., Implicitization using univariate resultants, J. Syst. Sci. Complex., 23, 804-814 (2010), URL:; 2019-11-09 05:31:49 <sb:reference id=“bib5368656E32303130s2”><sb:host><sb:e-host><ce:inter-ref xlink:href=“doi:10.1007/s11424-010-7218-6” id=“inf0280”>https://doi.org/10.1007/s11424-010-7218-6</ce:inter-ref></sb:e-host></sb:host></sb:reference> · Zbl 1213.14093
[33] Yao, S.; Feng, Y.; Jia, X.; Shen, L. Y., A package to compute implicit equations for the rational curves and surfaces, (The 44th International Symposium on Symbolic and Algebraic Computation (2019), ACM: ACM Beijing, China. URL)
[34] Zapata, J. L.G.; Martín, J. C.D., Finding the number of roots of a polynomial in a plane region using the winding number, Comput. Math. Appl., 67, 555-568 (2014), URL: · Zbl 1350.65042
[35] Zhao, X. Y.; Zhu, C. G., Injectivity conditions of rational Bézier surfaces, Comput. Graph., 51, 17-25 (2015), International Conference Shape Modeling International
[36] Zhao, X. Y.; Zhu, C. G.; Wang, H., Geometric conditions of non-self-intersecting NURBS surfaces, Appl. Math. Comput., 310, 89-96 (2017), URL: · Zbl 1426.65029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.