Computing knots by quadratic and cubic polynomial curves

Fan Zhang^{1,}^{2,}(✉)(),Jinjiang Li^{1,}^{2}(),Peiqiang Liu^{1,}^{2}(),Hui Fan^{1,}^{2}()

^{1}School of Computer Science and Technology, Shandong Technology and Business University, Yantai264005, China ^{2}Co-Innovation Center of Shandong Colleges andUniversities: Future Intelligent Computing, Yantai264005, China

A new method is presented to determine parameter values (knot) for data points for curve and surface generation. With four adjacent data points, a quadratic polynomial curve can be determined uniquely if the four points form a convex polygon. When the four data points do not form a convex polygon, a cubic polynomial curve with one degree of freedom is used to interpolate the four points, so that the interpolant has better shape, approximating the polygon formed by the four data points. The degree of freedom is determined by minimizing the cubic coefficient of the cubic polynomial curve. The advantages of the new method are, firstly, the knots computed have quadratic polynomial precision, i.e., if the data points are sampled from a quadratic polynomial curve, and the knots are used to construct a quadratic polynomial, it reproduces the original quadratic curve. Secondly, the new method is affine invariant, which is significant, as most parameterization methods do not have this property. Thirdly, it computes knots using a local method. Experiments show that curves constructed using knots computed by the new method have better interpolation precision than for existing methods.

Received: 30 March 2020
Published: 30 November 2020

Fund: National Natural Science Foundation of China(Grant Nos. 61602277 and 61772319);Natural Science Foundation of Shandong Province(Grant Nos. ZR2016FQ12 and ZR2018BF009);Key Research and Development Program of Yantai City(Grant No. 2017ZH065);CERNET Innovation Project(Grant No. NGII20161204);Science and Technology Innovation Program for Distributed Young Talents of Shandong Province Higher Education Institutions(Grant No. 2019KJN042)

Corresponding Authors:
Fan Zhang
E-mail: zhangfan51@sina.com;lijinjiang@gmail.com;liupq@126.com;fanlinw@263.net

About author: Fan Zhang received his B.S. and Ph.D. degrees in computer science from Shandong University in 2009 and 2015, respectively. From 2012 to 2014, he visited the Department of Computer Science, University of Kentucky, USA, as a joint-training Ph.D. student. He is currently an associate professor with the School of Computer Science and Technology, Shandong Business and Technology University. His research interests include image processing, computer vision, computer graphics, and CAGD.|Jinjiang Li received his B.S. and M.S. degrees in computer science from Taiyuan University of Technology, China, in 2001 and 2004, respectively, and his Ph.D. degree in computer science from Shandong University, Jinan, China, in 2010. From 2004 to 2006, he was an assistant research fellow with the Institute of Computer Science and Technology, Peking University. From 2012 to 2014, he was a post-doctoral fellow with Tsinghua University, Beijing. He is currently a professor with the School of Computer Science and Technology, Shandong Technology and Business University. His research interests include image processing, computer graphics, computer vision, and machine learning.|Peiqiang Liu received his Ph.D. degree in computer software and theory from Shandong University in 2013. He is currently a professor at Shandong Technology and Business University. His research interests include algorithms and complexity theory, and computational biology.|Hui Fan received his B.S. degree in computer science from Shandong University in 1984 and his Ph.D. degree in computer science from Taiyuan University of Technology in 2007. From 1984 to 2001, he was a professor at the Computer Department of Taiyuan University of Technology. He is currently a professor at Shandong Technology and Business University. His research interests include computer aided geometric design, computer graphics, information visualization, virtual reality, and image processing.

Table 1Maximum errors of ${E}_{1}?(k,t)$ for $\lambda =0.15$

${E}_{2}?(k,t)$

New

M0

M1

M2

M3

M4

M5

M6

$K=1$

2.23e-5

4.18e-5

7.87e-5

2.24e-4

8.09e-4

2.15e-5

1.26e-4

7.60e-4

$K=2$

4.58e-5

5.49e-5

1.01e-4

2.76e-4

8.83e-4

4.64e-5

1.57e-4

8.32e-4

$K=3$

7.15e-5

7.69e-5

1.24e-4

3.31e-4

9.53e-4

7.37e-5

1.78e-4

9.01e-4

$K=4$

9.99e-5

1.03e-4

1.63e-4

3.88e-4

1.02e-3

1.06e-4

1.90e-4

9.64e-4

$K=5$

1.33e-4

1.33e-4

2.06e-4

4.45e-4

1.07e-3

1.51e-4

2.30e-4

1.02e-3

$K=6$

1.31e-4

1.67e-4

2.47e-4

4.99e-4

1.12e-3

1.85e-4

2.66e-4

1.06e-3

$K=7$

1.82e-4

2.05e-4

2.83e-4

5.49e-4

1.14e-3

1.93e-4

2.97e-4

1.09e-3

$K=8$

2.09e-4

2.45e-4

3.76e-4

5.90e-4

1.15e-3

2.49e-4

3.24e-4

1.10e-3

$K=9$

3.34e-4

2.86e-4

4.92e-4

6.58e-4

1.12e-3

5.03e-4

3.46e-4

1.07e-3

$K=10$

3.16e-4

3.33e-4

6.39e-4

7.23e-4

1.04e-3

4.18e-4

3.97e-4

1.01e-3

$K=11$

3.49e-4

3.97e-4

9.32e-4

7.76e-4

9.93e-4

5.09e-4

4.70e-4

9.73e-4

$K=12$

4.44e-4

4.50e-4

1.35e-3

8.06e-4

1.03e-3

5.78e-4

5.54e-4

1.02e-3

$K=13$

3.84e-4

6.19e-4

1.88e-3

7.97e-4

1.04e-3

5.42e-4

6.48e-4

1.04e-3

$K=14$

4.99e-4

8.43e-4

2.50e-3

7.23e-4

9.85e-4

8.13e-4

7.48e-4

9.79e-4

Table 2Maximum errors of ${E}_{2}?(k,t)$ for $\lambda =0.15$

Fig. 5Error curves for six methods.

${F}_{1}?(t)$

New

M0

M1

M2

M3

M4

M5

M6

$\lambda =0.05$

4.28e-5

1.56e-4

4.15e-4

2.87e-4

3.87e-4

5.29e-5

2.80e-4

5.46e-4

$\lambda =0.10$

4.51e-5

1.64e-4

4.25e-4

4.52e-4

6.09e-4

5.68e-5

3.08e-4

1.03e-3

$\lambda =0.15$

4.82e-5

1.73e-4

4.32e-4

6.19e-4

9.59e-4

6.05e-5

3.39e-4

1.58e-3

$\lambda =0.20$

5.75e-5

1.82e-4

4.36e-4

8.46e-4

1.36e-3

6.38e-5

3.71e-4

2.17e-3

$\lambda =0.25$

7.27e-5

1.90e-4

4.37e-4

1.13e-3

1.82e-3

6.68e-5

4.09e-4

2.83e-3

Table 3Maximum errors of ${F}_{1}?(t)$

[1]

Ahlberg, J. H.; Nilson, E.; Walsh, J. L. The Theory of Splines and Their Applications. Academic Press, 1967.

[2]

Boor, C. D. A Practical Guide to Splines. Springer-Verlag New York, 1978.

[3]

Brodlie, K. W. A review of methods for curve and function drawing. In: Mathematical Methods in Computer Graphics and Design. London: Academic Press, 33-37, 1980.

[4]

Faux, I. D.; Pratt, M. J. Computational Geometry for Design and Manufacture. Halsted Press, 1979.

[5]

Su, B. Q.; Liu, D. Y. Computational Geometry: Curve and Surface Modeling. Academic Press, 1989.

[6]

Li, W. S.; Xu, S. H.; Zheng, J. M.; Zhao, G. Target curvature driven fairing algorithm for planar cubic B-spline curves. Computer Aided Geometric Design Vol. 21, No. 5, 499-513, 2004.

[7]

Lü, W. Curves with chord length parameterization. Computer Aided Geometric Design Vol. 26, No. 3, 342-350, 2009.

[8]

Farin, G. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, 1988.

[9]

Lee, E. T. Y. Choosing nodes in parametric curve interpolation. Computer-Aided Design Vol. 21, No. 6, 363-370, 1989.

[10]

Jeong, S. Y.; Choi, Y. J.; Park, P. Parametric interpolation using sampled data. Computer-Aided Design Vol. 38, No. 1, 39-47, 2006.

[11]

Yuksel, C.; Schaefer, S.; Keyser, J. Parameterization and applications of Catmull-Rom curves. Computer-Aided Design Vol. 43, No. 7, 747-755, 2011.

[12]

Fang, J. J.; Hung, C. L. An improved parameterization method for B-spline curve and surface interpolation. Computer-Aided Design Vol. 45, No. 6, 1005-1028, 2013.

[13]

Lim, C. G. A universal parametrization in B-spline curve and surface interpolation. Computer Aided Geometric Design Vol. 16, No. 5, 407-422, 1999.

[14]

Zhang, C. M.; Cheng, F. H. F.; Miura, K. T. A method for determining knots in parametric curve interpolation. Computer Aided Geometric Design Vol. 15, No. 4, 399-416, 1998.

[15]

Zhang, C. M.; Wang, W. P.; Wang, J. Y.; Li, X. M. Local computation of curve interpolation knots with quadratic precision. Computer-Aided Design Vol. 45, No. 4, 853-859, 2013.

[16]

Hartley, P. J.; Judd, C. J. Parametrization and shape of B-spline curves for CAD. Computer-Aided Design Vol. 12, No. 5, 235-238, 1980.

[17]

Marin, S. P. An approach to data parametrization in parametric cubic spline interpolation problems. Journal of Approximation Theory Vol. 41, No. 1, 64-86, 1984.

[18]

Li, X. M.; Zhang, F.; Chen, G. N.; Zhang, C. M. Formula for computing knots with minimum stress and stretching energies. Science China Information Sciences Vol. 61, No. 5, Article No. 052104, 2017.

[19]

Lin, F. M.; Shen, L. Y.; Yuan, C. M.; Mi, Z. P. Certified space curve fitting and trajectory planning for CNC machining with cubic B-splines. Computer-Aided Design Vol. 106, 13-29, 2019.

[20]

Yang, Z. Y.; Shen, L. Y.; Yuan, C. M.; Gao, X. S. Curve fitting and optimal interpolation for CNC machining under confined error using quadratic B-splines. Computer-Aided Design Vol. 66, 62-72, 2015.

[21]

Floater, M. S.; Reimers, M. Meshless parameterization and surface reconstruction. Computer Aided Geometric Design Vol. 18, No. 2, 77-92, 2001.

[22]

Gotsman, C.; Gu, X. F.; Sheffer, A. Fundamentals of spherical parameterization for 3D meshes. In: Proceedings of the ACM SIGGRAPH 2003 Papers, 358-363, 2003.

[23]

Gu, X. F.; Yau, S. T. Global conformal surface parameterization. In: Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 127-137, 2003.

[24]

Xie, H.; Qin, H. A novel optimization approach to the effective computation of NURBS knots. International Journal of Shape Modeling Vol. 7, No. 2, 199-227, 2001.

[25]

Farin, G. Rational quadratic circles are parametrized by chord length. Computer Aided Geometric Design Vol. 23, No. 9, 722-724, 2006.

[26]

Bastl, B.; Jüttler, B.; Lávi?ka, M.; Schicho, J.; ?ír, Z. Spherical quadratic Bézier triangles with chord length parameterization and tripolar coordinates in space. Computer Aided Geometric Design Vol. 28, No. 2, 127-134, 2011.

[27]

Bastl, B.; Jüttler, B.; Lávi?ka, M.; ?ír, Z. Curves and surfaces with rational chord length parameterization. Computer Aided Geometric Design Vol. 29, No. 5, 231-241, 2012.

[28]

Tsuchie, S.; Okamoto, K. High-quality quadratic curve fitting for scanned data of styling design. Computer-Aided Design Vol. 71, 39-50, 2016.

[29]

Han, X. L. A class of general quartic spline curves with shape parameters. Computer Aided Geometric Design Vol. 28, No. 3, 151-163, 2011.

[30]

Bashir, U.; Abbas, M.; Ali, J. M. The G2 and C2 rational quadratic trigonometric Bézier curve with two shape parameters with applications. Applied Mathematics and Computation Vol. 219, No. 20, 10183-10197, 2013.

[31]

Antonelli, M.; Beccari, C. V.; Casciola, G. High quality local interpolation by composite parametric surfaces. Computer Aided Geometric Design Vol. 46, 103-124, 2016.