×

Certified approximation of parametric space curves with cubic \(B\)-spline curves. (English) Zbl 1251.65014

Approximating complex curves with simple parametric curves is widely used in CAGD, CG, and CNC. This paper presents an algorithm to compute a certified approximation to a given parametric space curve with cubic \(B\)-spline curves. By certified, we mean that the approximation can approximate the given curve to any given precision and preserve the geometric features of the given curve such as the topology, singular points, etc. The approximated curve is divided into segments called quasi-cubic Bézier curve segments which have properties similar to a cubic rational Bézier curve. And the approximate curve is naturally constructed as the associated cubic rational Bézier curve of the control tetrahedron of a quasi-cubic curve.
A novel optimization method is proposed to select proper weights in the cubic rational Bézier curve to approximate the given curve. The error of the approximation is controlled by the size of its tetrahedron, which converges to zero by subdividing the curve segments. As an application, approximate implicit equations of the approximated curves can be computed. Experiments show that the method can approximate space curves of high degrees with high precision and very few cubic Bézier curve segments.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)

Software:

ISOLATE
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M.; Šír, Z.; Jüttler, B., Evolution-based least-squares fitting using Pythagorean hodograph spline curves, Comput. Aided Geom. Design, 24, 310-322 (2007) · Zbl 1171.65315
[2] Alcázar, J. G.; Sendra, J. R., Computation of the topology of real algebraic space curves, J. Symbolic Comput., 39, 6, 719-744 (2005) · Zbl 1120.14049
[3] Alcázar, J. G.; Díaz-Toca, G. M., Topology of 2D and 3D rational curves, Comput. Aided Geom. Design, 27, 7, 483-502 (2010) · Zbl 1210.65031
[4] Chen, J.; Zhang, S.; Bao, H.; Peng, Q., \(G^3\) continuous curve modeling with rational cubic Bézier spline, Process Nat Sci, 12, 217-221 (2002) · Zbl 1039.65011
[5] Chen, X. D.; Ma, W.; Paul, J. C., Cubic B-spline curve approximation by curve unclamping, Computer-Aided Design, 42, 6, 523-534 (2010)
[6] Chen, Y.; Shen, L. Y.; Yuan, C. M., Collision and intersection detection of two ruled surfaces using bracket method, Comput. Aided Geom. Design, 28, 2, 114-126 (2011) · Zbl 1210.65054
[7] Cheng, J.S., Gao, X.S., Li, J., 2009. Topology determination and isolation for implicit plane curves. In: Proc. ACM Symposium on Applied Computing, pp. 1140-1141.; Cheng, J.S., Gao, X.S., Li, J., 2009. Topology determination and isolation for implicit plane curves. In: Proc. ACM Symposium on Applied Computing, pp. 1140-1141.
[8] Cheng, J. S.; Gao, X. S.; Yap, C.-K., Complete numerical isolation of real roots in zero-dimensional triangular systems, J. Symbolic Comput., 44, 7, 768-785 (2009) · Zbl 1169.13017
[9] Chuang, J. H.; Hoffmann, C. M., On local implicit approximation and its applications, ACM Trans. Graph., 8, 4, 298-324 (1989) · Zbl 0746.68091
[10] Cox, D. A.; Sederberg, T. W.; Chen, F., The moving line ideal basis of planar rational curves, Comput. Aided Geom. Design, 15, 8, 803-827 (1998) · Zbl 0908.68174
[11] Daouda, D.N., Mourrain, B., Ruatta, O., 2008. On the computation of the topology of a non-reduced implicit space curve. In: ISSACʼ08: Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, pp. 47-54.; Daouda, D.N., Mourrain, B., Ruatta, O., 2008. On the computation of the topology of a non-reduced implicit space curve. In: ISSACʼ08: Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, pp. 47-54. · Zbl 1238.14046
[12] Degen, W. L.F., High accurate rational approximation of parametric curves, Comput. Aided Geom. Design, 10, 3-4, 293-313 (1993) · Zbl 0781.65008
[13] Degen, W. L.F., Geometric Hermite interpolation: in memoriam Josef Hoschek, Comput. Aided Geom. Design, 22, 7, 573-592 (2005) · Zbl 1100.41002
[14] Deng, J., Chen, F., Shen, L.Y., 2005. Computing \(μ\); Deng, J., Chen, F., Shen, L.Y., 2005. Computing \(μ\) · Zbl 1360.14141
[15] Dokken, T., 2001. Approximate implicitization. In: Mathematical Methods for Curves and Surfaces: Oslo 2000, pp. 81-102.; Dokken, T., 2001. Approximate implicitization. In: Mathematical Methods for Curves and Surfaces: Oslo 2000, pp. 81-102. · Zbl 0989.65019
[16] Farin, G., Geometric Hermite interpolation with circular precision, Computer-Aided Design, 40, 4, 476-479 (2008)
[17] Forrest, A., The twisted cubic curve: a computer-aided geometric design approach, Computer-Aided Design, 12, 4, 165-172 (1980)
[18] Gao, X. S.; Li, M., Rational quadratic approximation to real algebraic curves, Comput. Aided Geom. Design, 21, 8, 805-828 (2004) · Zbl 1069.65518
[19] Ghosh, S.; Petitjean, S.; Vegter, G., Approximation by conic splines, Math. Comput. Sci., 1, 39-69 (2007) · Zbl 1127.41002
[20] Hijllig, K.; Koch, J., Geometric Hermite interpolation, Comput. Aided Geom. Design, 12, 6, 567-580 (1995) · Zbl 0875.68851
[21] Hoschek, J.; Lasser, D., Fundamentals of Computer Aided Geometric Design (L. Schumaker, Trans.) (1993), A. K. Peters, Ltd.: A. K. Peters, Ltd. Natick, MA, USA · Zbl 0788.68002
[22] Kong, V. P.; Ong, B. H., Shape preserving approximation by spatial cubic splines, Comput. Aided Geom. Design, 26, 8, 888-903 (2009) · Zbl 1205.65051
[23] Li, M.; Gao, X. S.; Chou, S. C., Quadratic approximation to plane parametric curves and its application in approximate implicitization, Vis. Comput., 22, 9, 906-917 (2006)
[24] Li, Y. M.; Cripps, R. J., Identification of inflection points and cusps on rational curves, Comput. Aided Geom. Design, 14, 5, 491-497 (1997) · Zbl 0896.65014
[25] Liang, C., Mourrain, B., Pavone, J.P., 2009. Subdivision methods for the topology of 2d and 3d implicit curves. In: Geometric Modeling and Algebraic Geometry, pp. 199-214.; Liang, C., Mourrain, B., Pavone, J.P., 2009. Subdivision methods for the topology of 2d and 3d implicit curves. In: Geometric Modeling and Algebraic Geometry, pp. 199-214. · Zbl 1132.14335
[26] Manocha, D.; Canny, J. F., Detecting cusps and inflection points in curves, Comput. Aided Geom. Design, 9, 1, 1-24 (1992) · Zbl 0757.65012
[27] Pelosi, F.; Farouki, R. T.; Manni, C.; Sestini, A., Geometric Hermite interpolation by spatial Pythagorean-hodograph cubics, Adv. Comput. Math., 22, 325-352 (2005) · Zbl 1065.68103
[28] Piegl, L.; Tiller, W., The NURBS Book (1997), Springer-Verlag: Springer-Verlag New York, Inc., New York, NY, USA · Zbl 0868.68106
[29] Pottmann, H. Leopoldseder, S. Hofer, M., Approximation with active B-spline curves and surfaces. In: PGʼ02: Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, vol. 8 2002.; Pottmann, H. Leopoldseder, S. Hofer, M., Approximation with active B-spline curves and surfaces. In: PGʼ02: Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, vol. 8 2002.
[30] Rababah, A., High accuracy Hermite approximation for space curves in \(R^d\), J. Math. Anal. Appl., 325, 2, 920-931 (2007) · Zbl 1111.68731
[31] Renka, R. J., Shape-preserving interpolation by fair discrete \(G^3\) space curves, Comput. Aided Geom. Design, 22, 8, 793-809 (2005) · Zbl 1120.65311
[32] Rouillier, F.; Zimmermann, P., Efficient isolation of polynomialʼs real roots, J. Comput. Appl. Math., 162, 1, 33-50 (2004) · Zbl 1040.65041
[33] Rubio, R.; Serradilla, J. M.; Vélez, M. P., Detecting real singularities of a space curve from a real rational parametrization, J. Symbolic Comput., 44, 5, 490-498 (2009) · Zbl 1159.14036
[34] Wang, H.; Jia, X.; Goldman, R., Axial moving planes and singularities of rational space curves, Comput. Aided Geom. Design, 26, 3, 300-316 (2009) · Zbl 1205.14077
[35] Wu, Z. K.; Lin, F.; Soon, S. H., Topology preserving voxelisation of rational Bézier and NURBS curves, Computers & Graphics, 27, 1, 83-89 (2003)
[36] Xu, L.; Shi, J., Geometric Hermite interpolation for space curves, Comput. Aided Geom. Design, 18, 9, 817-829 (2001) · Zbl 0984.68163
[37] Yang, X., Curve fitting and fairing using conic splines, Computer-Aided Design, 36, 5, 461-472 (2004) · Zbl 1206.68329
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.