A certified cubic B-spline interpolation with tangential direction constraints

HE Shi-Tao, SHEN Li-Yong, WU Qin, YUAN Chun-Ming

Journal of Systems Science & Complexity ›› 0

PDF(6084 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(6084 KB)
Journal of Systems Science & Complexity ›› 0

A certified cubic B-spline interpolation with tangential direction constraints

  • HE Shi-Tao1, SHEN Li-Yong1, WU Qin1,2, YUAN Chun-Ming1,2
Author information +
History +

Abstract

Curve interpolation with B-spline is widely used in various areas. This problem is classic and recently raised in application scenario with new requirements such as path planning following the tangential vector field under certified error in CNC machining. This paper proposes an algorithm framework to solve Hausdorff distance certified cubic B-spline interpolation problem with or without tangential direction constraints. The algorithm has two stages: the first stage is to find the initial cubic B-spine fitting curve which satisfies the Hausdorff distance constraint; the second stage is to set up and solve the optimization models with certain constraints. Especially, the sufficient conditions of the global Hausdorff distance control for any error bound are discussed, which can be expressed as a series of linear and quadratic constraints. A simple numerical algorithm to compute the Hausdorff distance between a polyline and its B-spline interpolation curve is proposed to reduce our computation. Experimental results are presented to show the advantages of our algorithms.

Key words

Cubic B-spline / Hausdorff distance / Interpolation / Tangential direction

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
HE Shi-Tao, SHEN Li-Yong, WU Qin, YUAN Chun-Ming. A certified cubic B-spline interpolation with tangential direction constraints. Journal of Systems Science and Complexity, 0

References

[1] Thévanaz P, Blu T, Unser M. Interpolation Revisited. IEEE Transactions on Medical Imaging 2000; 19(7): 739-758.
[2] Lehmann TM, Gönner Claudia, Spitzer Klaus. Addendum: B-Spline Interpolation in Medical Image Processing. IEEE Transactions on Medical Imaging 2001; 20(7): 660-665.
[3] Maekawa T, Noda T, Tamura S, et al. Curvature continuous path generation for autonomous vehicle using B-spline curves. Computer-Aided Design 2010; 42(4):350-359.
[4] Behroo M, Banazadeh A. Near-optimal trajectory generation, using a compound B-spline in-terpolation and minimum distance criterion with dynamical feasibility correction. Robotics and Autonomous Systems 2015; 74:79-87.
[5] Piegl L, Tiller W. The NURBS book. 2nd ed. New York: Springer-Verlag; 1997.
[6] Farin G. Curves and surfaces for CAGD: A practical guide. Morgan Kaufmann Publishers Inc; 2001.
[7] Hu LC, Shou HH, Fang SF. A PIA optimization algorithm for non-uniform B-spline curves and surfaces. International Journal of Modelling and Simulation 2017; 37(3):167-177.
[8] Idais H, Yasin M, Pasadas M, González P. Optimal knots allocation in the cubic and bicubic spline interpolation problems. Mathematics and Computer in Simulation 2019; 164:131-145.
[9] Shao MZ, Hu LC, Shou HH, Shen J. A novel adaptive GA-based B-spline curve interpolation method. Recent Patents on Engineering 2019; 13(3):289-304.
[10] Hu LC, Zhang WS. NSGA-II approach for proper choice of nodes and knots in B-spline curve interpolation. Computer-Aided Design 2020; 127.
[11] Park H, Lee JH. B-spline curve fitting based on adaptive curve refinement using dominant points. Computer-Aided Design 2007; 39(6):439-451.
[12] Xiao QB, Wan M, Qin XB, et al. Real-time smoothing of G01 commands for five-axis machining by constructing an entire spline with the bounded smoothing error. Mechanism and Machine Theory 2021; 161, 104307.
[13] Huang J, Du X, Zhu LM. Real-time local smoothing for five-axis linear toolpath considering smoothing error constraints. International Journal of Machine Tools and Manufacture 2018; 124:67-79.
[14] Li GX, Liu HT, Liu SJ, et al. A general C2 continuous toolpath corner smoothing method for a 5-DOF hybrid robot. Mechanism and Machine Theory 2022; 169, 104640.
[15] He SS, Yan CY, Deng YC, et al. A tolerance constrained G2 continuous path smoothing and interpolation method for industrial SCARA robots. Robotics and Computer Integrated Manufacturing 2020; 63, 101907.
[16] Shahzadeh A, Khosravi A, Robinette T, Nahavandi S. Smooth path planning using biclothoid fillets for high speed CNC machines. International Journal of Machine Tools and Manufacture 2018; 132:36-49.
[17] Gofuku S, Tamura S, Maekawa T. Point-tangent/point-normal B-spline curve interpolation by geometric algorithms. Computer-Aided Design 2009; 41(6):412-422.
[18] Okaniwa S, Nasri A, Lin HW, et al. Uniform B-spline curve interpolation with prescribed tangent and curvature vectors. IEEE Transactions on Visualization and Computer Graphics 2012; 18(9):1474-1487.
[19] Chen XD, Ma WY. Geometric point interpolation method in R3 space with tangent directional constraint. Computer-Aided Design 2012; 44(12):1217-1228.
[20] Chiou CJ, Lee YS. A machining potential field approach to tool path generation for multi-axis sculptured surface machining. Computer-Aided Design 2002; 34(5):357-371.
[21] Li Z, Tang K. Partition-based five-axis tool path generation for freeform surface machining using a non-spherical tool. Journal of Manufacturing Systems 2021; 58: 248–262.
[22] Liu X, Li Y, Ma S, Lee CH. A tool path generation method for freeform surface machining by introducing the tensor property of machining strip width. Computer-Aided Design 2015; 66: 1–13.
[23] Kumazawa GH, Feng HY, Barakchi Fard MJ, Preferred feed direction field: A new tool path generation method for efficient sculptured surface machining. Computer-Aided Design 2015; 67-68: 1-12.
[24] Su C, Jiang X, Huo GY, et al. Initial tool path selection of the iso-scallop method based on offset similarity analysis for global preferred feed directions matching. The International Journal of Advanced Manufacturing Technology 2020; 106(7-8):2675-2687.
[25] Zou Q. Length-optimal tool path planning for freeform surfaces with preferred feed directions based on Poisson formulation. Computer-Aided Design 2021; 139(9), 103072.
[26] Gorden WJ, Riesenfled RF. B-spline curves and surfaces. Computer Aided Geometric Design 1974:95-126.
[27] Lee ETY. Choosing nodes in parametric curve interpolation. Computer-Aided Design 1989; 21(6):363-370.
[28] Foley TA, Nielson GM. Knot selection for parametric spline interpolation. Computer Aided Geometric Design 1989: 261-71.
[29] He ST, Shen LY. A Class of Parameterization Method of Accumulated Average Arc Length for Parametric Curves. Journal of Jilin University (Science Edition) 2021; 59(2):286-294.
[30] http://cvxr.com/cvx/
[31] Yang Z, Shen LY, Yuan CM, Gao XS. Curve fitting and optimal interpolation for CNC machining under confined error using quadratic B-splines. Computer-Aided Design 2015; 66:62-72.
[32] Lin FM, Shen LY, Yuan CM, Mi ZP. Certified space curve fitting and trajectory planning for CNC machining with cubic B-splines. Computer-Aided Design 2018; 106:13-29.

Funding

This research is partially supported by the National Key Research and Development Program of China under Grant 2020YFA0713703, Beijing Natural Science Foundation under Grant Z190004, NSFC (Nos. 11688101, 61872332, 12271516) and Fundamental Research Funds for the Central Universities. . . . .
PDF(6084 KB)

Accesses

Citation

Detail
Sections
Recommended

/

〈 〉