# A Novel Approach for NURBS Interpolation with Minimal Feed Rate Fluctuation Based on Improved Adams-Moulton Method

Authors: Junquan Peng; Xinhua Liu; Lei Si; Jingjing Liu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

In order to reduce the feed rate fluctuation of interpolation, a novel approach for NURBS interpolation with minimal feed rate fluctuation based on improved Adams-Moulton (IAM) method is proposed. At first, the representation and calculation of NURBS curve interpolation are described. Then, the constraints of feeding step length are firstly given out to calculate the minimal hoping feeding step length and the detailed IAM method of NURBS curve interpolation is presented. Finally, simulations and experiments are carried out to verify the feasibility and applicability of proposed IAM method.


---

## Body

## 1. Introduction

Along with rapid progress and development of science, technology, and social economy, the machining accuracy of CNC machine tools is increasingly demanding [1]. Just because of this condition, conventional linear and circular interpolation cannot fit the requirement of machining in modern CNC systems. However, NURBS method offers a common mathematical form for the precise representation of standard analytical shapes as well as free-form curves and surfaces [2–4]. Since NURBS curve has lots of advantages in designing complicated shapes compared with conventional linear and circular, its interpolation methods have been developed in CAD/CAM applications [5, 6].Although many approximation methods connected with NURBS interpolation have been proposed to obtain efficient machining, feed rate fluctuation is an important challenge. To the best of our knowledge, the problem of NURBS interpolation for CNC machines has almost not been dealt with.Recent publications relevant to this paper are mainly summarized. Farouki and Tsai [7] proposed PH curve interpolation which could give rational analytical relations between arc length and parameters as well as effectively reducing the interpolation output feed rate fluctuation. Tsai and Chung [8] reduced the interpolation output feed rate fluctuation through iterative methods, especially in curve curvature at the output of the feed rate fluctuation. Yong and Narayanaswami [9] proposed a spline curve interpolation algorithm based on the second-order Taylor expansion method. Yeh and Hsu [10] proposed a speed-controlled interpolator by incorporating a compensatory parameter to minimize the feed rate fluctuation. Erkorkmaz and Altintas [11, 12] adopted quintic polynomial for interpolation with minimal feed rate fluctuation. Zhiming et al. [13] proposed a real-time parametric interpolation technique. Cheng et al. [14] compared different NURBS interpolation algorithms on the basis of computing time, interpolation accuracy, and feed rate fluctuation. Tikhon et al. [15] proposed a NURBS curve interpolation device based on the adaptive feed rate control. Lei et al. [16] proposed an inverse length function method which cubic/quintic Hermite spline was used to achieve very low feed rate fluctuation in non-real-time processes. Lin et al. [17] proposed a dynamics-based interpolator with real-time look-ahead algorithm to generate a smooth and jerk-limited acceleration/deceleration feed rate profile. Jia et al. [18] presented a NURBS interpolation method based on Adams algorithm which ensured the real-time of the algorithm through reasonable simplification and approximation. Wu et al. [19, 20] presented a nonuniform rational B-spline interpolation algorithm with compensatory parameter to minimize feed rate fluctuation and contour error by improving the inverse length function method with the usage of biarc guide curve. Sun et al. [21] proposed a novel adaptive federate interpolation method for NURBS tool path with drive constraints which can acquire smooth feed rate profile. Liu et al. [22] proposed a double secant interpolation algorithm and a fast calculation and derivation algorithm of NURBS to solve the problem of feed rate fluctuation. Liu et al. [23] proposed a new NURBS interpolation method with minimal feed rate fluctuation for CNC machine tools to obtain the sampling curve parameter.Although many approaches for NURBS interpolation have been proposed in above literature, they have some common disadvantages summarized as follows. Firstly, most of researchers presented their methods for NURBS interpolation with the second-order Taylor expansion method. However, the second-order Taylor expansion method referred to second derivative of NURBS curve and it was complicated. Secondly, some researchers considered the problem of feed rate fluctuation. Nevertheless, results of feed rate fluctuation were very high and unsatisfactory.In order to solve the above problems, a novel approach for NURBS interpolation with minimal feed rate fluctuation based on improved Adams-Moulton method is applied and the rest of this paper is organized as follows. In Section2, representation and calculation of NURBS curve interpolation are presented. The improved predictor-corrector formula of NURBS curve interpolation is proposed in Section 3. In Section 4, simulations with the trident and butterfly NURBS curves are conducted to verify the feasibility of the proposed method. Experimental verification is conducted in Section 5. Our conclusions are summarized in Section 6.


## 2. Representation and Calculation of NURBS Curve Interpolation

Suppose thatCu represents a NURBS curve and is given by [2, 24, 25]:(1)Cu=∑i=0nNi,puwiPi∑i=0nNi,puwi,where Pi are the control points, wi are the weights of Pi, (n+1) are the number of the control points, and p is the degree of NURBS curve. Ni,pu is the pth-degree B-spline basis function and can be calculated using the recursive formulas given as follows:(2)Ni,0u=1ifui≤u≤ui+10otherwiseNi,pu=u-uiui+p-uiNi,p-1u+ui+p+1-uui+p+1-ui+1Ni+1,p-1u,where u0,u1,…,un+p+1 represents the knot vectors and u is the interpolation parameter.The node vector in parameter coordinates is not uniformly distributed for NURBS curve interpolation in general, so the value of the B-spline basis function is not the same and it is necessary to obtain all the B-spline basis functions, respectively. In addition, the weight factor value of NURBS curve interpolation needs to be obtained and this makes the computation more time-consuming. However, because of the simple expression and high derivative evaluation efficiency, the matrix expression of the NURBS curve can be used to solve the complicated calculation problem in the pretreatment process.Due to the fact that the NURBS curve of degree 3 is used widely, the following example is used to be illustrated. If NURBS curve control polygon[P0,P1,…,Pn], weights w0,w1,…,wn, and node vectors u0,u1,…,un+p+1 are given, then NURBS curve of degree 3 can be expressed as follows [18]:(3)Ct=∑j=i-3iwjPjNj,3u∑j=i-3iwjNj,3u=1,t,t2,t3Miwi-3Pi-3wi-2Pi-2wi-1Pi-1wiPi1,t,t2,t3Miwi-3wi-2wi-1wi,where i=3,4,…,n,t∈0,1,t=u-ui/ui+1-ui=u-ui/∇i1, ∇i1=ui+1-ui,∇i2=ui+2-ui+1,∇i3=ui+3-ui+2, especially, ∇i0=0, and the expression of Mi is as follows:(4)Mi=m11m12m13m14m21m22m23m24m31m32m33m34m41m42m43m44=∇i12∇i-12∇i-231-m11-m13∇i-112∇i-12∇i-130-3m113m11-m233∇i-11∇i1∇i-12∇i-1303m11-3m11-m333∇i12∇i-12∇i-130-m11m11-m43-m44-13m33+m44+∇i12∇i2∇i-13∇i12∇i2∇i3.Here, the expression of parameters is as follows:(5)B0=m11wi-3Pi-3+m12wi-2Pi-2+m13wi-1Pi-1+m14wiPi.B1=m21wi-3Pi-3+m22wi-2Pi-2+m23wi-1Pi-1+m24wiPiB2=m31wi-3Pi-3+m32wi-2Pi-2+m33wi-1Pi-1+m34wiPiB3=m41wi-3Pi-3+m42wi-2Pi-2+m43wi-1Pi-1+m44wiPiB0′=m11wi-3+m12wi-2+m13wi-1+m14wiB1′=m21wi-3+m22wi-2+m23wi-1+m24wiB2′=m31wi-3+m32wi-2+m33wi-1+m34wiB3′=m41wi-3+m42wi-2+m43wi-1+m44wi,When (4) and (5) are substituted into (3), the new expression of NURBS curve is as follows:(6)Ct=∑j=i-3iwjPjNj,3u∑j=i-3iwjNj,3u=B0+B1t+B2t2+B3t3B0′+B1′t+B2′t2+B3′t3,t∈0,1,i=3,4,…,n.According to (6), molecular coefficients B0,B1,B2,B3 and denominator coefficients B0′,B1′,B2′,B3′ have little to do with parameter t. Therefore, it is able to avoid the repeated calculation of the real-time interpolation process with condition that the numerical value of these coefficients is obtained. That is improvement of interpolation speed is promoted.


## 3. Improved Adams-Moulton Method of NURBS Curve Interpolation

### 3.1. Constraints of Feeding Step Length

In this subsection, the system architecture of proposed IAM method is established in Figure1, which is utilized to implement CNC control tasks.Figure 1
The system architecture of proposed NURBS interpolation method.


### 3.2. Constraints of Feeding Step Length

Normally, estimating feed step length of trajectory space is calculated as (7) and based on constraints of the maximum feed rate, chord error, normal acceleration, and jerk. Therefore, constraint equations of the maximum feed rate, chord error, normal acceleration, and jerk are given as formulas (8), (9), (10), and (11), respectively:(7)ΔL^i=Cu^m+1-Cu^m≈8·δ·ρi(8)ΔLi1=Fmax·T(9)ΔLi2=8·ρi·δmax·T(10)ΔLi3=Amax·ρi·T(11)ΔLi4=Jmax·ρi3·T,where Fmax, δmax, Amax, Jmax are the maximum feed rate, chord error, normal acceleration, and jerk, respectively. T, ρi, δ are sample time, the radius of curvature at the parameter value ui, and the chord error, respectively.However, the chord error involves the curvature calculation, so (12) is adopted to calculate the curvature:(12)δ=Cum+um+12-Cum+Cum+12.In addition, to avoid the curvature calculation, formulas (9), (10), and (11) can be expressed as formulas (13), (14), and (15), respectively:(13)ΔLi2=δmaxδ·ΔL^i(14)ΔLi3=T2·aNmax2·δmax·ΔLi2(15)ΔLi4=T4·Jmax·ΔLi2δmax23·ΔLi2.In summary, hoping feeding step length should be satisfied with the following formula:(16)ΔLi=min⁡ΔLi1,ΔLi2,ΔLi3,ΔLi4


### 3.3. Improved Adams-Moulton Method

To implement NURBS interpolation, the Adams-Moulton (AM) method is adopted here. Using the AM method, the curve approximation up is given as follows [18]:(17)um+1=um+T249fk+1+19fk-5fk-1+fk-2fk=dudtt=tm=VumC′um,where Vum, T, and C′um denote the feed rate, the sampling time, and the first derivatives of the NURBS curve, respectively.Although the second-order derivative operation is avoided by AM method, an implicit is introduced and it is also needed to solve first-order derivative. Therefore, the forward-center-backward difference is used to replace the differential to improve AM method so that the operation time of interpolation algorithm can be shortened and the real-time performance is able to be ensured. The three different forward-center-backward differences are as in formulas (18), (19), and (20), respectively:(18)um+1′=um+1-umTBackward  differenceum′=um+1-umTForward  differenceum-1′=um-um-22TCentral  differenceum-2′=um-1-um-2TForward  difference(19)um+1′=um+1-umTBackward  differenceum′=um-um-1TBackward  differenceum-1′=um-um-22TCentral  differenceum-2′=um-1-um-2TForward  difference(20)um+1′=um+1-umTBackward  differenceum′=um+1-um-12TCentral  differenceum-1′=um-um-1TForward  differenceum-2′=um-1-um-2TForward  difference.When (18), (19), and (20) are substituted into (17), the improved AM method is as in formulas (21), (22), and (23), respectively:(21)um+10=18·13um-2um-1-3um-2(22)um+11=110·21um-12um-1+um-2(23)um+22=111·20um-7um-1-2um-2.Due to the slow convergence rate of the traditional correction formula, the Inverse Quadratic Interpolation (IQI) is adopted to calculate the estimated parameteru~m+1. When parameters um+10, um+11, um+12 are substituted into  (7), estimated feed step lengths ΔLm+10, ΔLm+11, ΔLm+12 are obtained, respectively. So, the estimated parameter u~m+1 calculation formula is as follows [26]:(24)u~m+1=um+12-r·r-q·um+12-um+11+1-r·s·um+12-um+10q-1·r-1·s-1,where q=ΔLm+10/ΔLm+11, r=ΔLm+12/ΔLm+11, s=ΔLm+12/ΔLm+10.Theoretically, sampling step size should satisfy the following equation:(25)Cu~m+1-Cu~m=Vu~m·THowever, truncation errors and the discrepancy errors between machining trajectory and the demand curve will make (25) dissatisfied; that is, feed rate fluctuation existed. So, feed rate fluctuation ε should be considered and it can be defined as follows:(26)ε=Vu~m·T-Cu~m+1-Cu~mVu~m·T·100%.


## 3.1. Constraints of Feeding Step Length

In this subsection, the system architecture of proposed IAM method is established in Figure1, which is utilized to implement CNC control tasks.Figure 1
The system architecture of proposed NURBS interpolation method.


## 3.2. Constraints of Feeding Step Length

Normally, estimating feed step length of trajectory space is calculated as (7) and based on constraints of the maximum feed rate, chord error, normal acceleration, and jerk. Therefore, constraint equations of the maximum feed rate, chord error, normal acceleration, and jerk are given as formulas (8), (9), (10), and (11), respectively:(7)ΔL^i=Cu^m+1-Cu^m≈8·δ·ρi(8)ΔLi1=Fmax·T(9)ΔLi2=8·ρi·δmax·T(10)ΔLi3=Amax·ρi·T(11)ΔLi4=Jmax·ρi3·T,where Fmax, δmax, Amax, Jmax are the maximum feed rate, chord error, normal acceleration, and jerk, respectively. T, ρi, δ are sample time, the radius of curvature at the parameter value ui, and the chord error, respectively.However, the chord error involves the curvature calculation, so (12) is adopted to calculate the curvature:(12)δ=Cum+um+12-Cum+Cum+12.In addition, to avoid the curvature calculation, formulas (9), (10), and (11) can be expressed as formulas (13), (14), and (15), respectively:(13)ΔLi2=δmaxδ·ΔL^i(14)ΔLi3=T2·aNmax2·δmax·ΔLi2(15)ΔLi4=T4·Jmax·ΔLi2δmax23·ΔLi2.In summary, hoping feeding step length should be satisfied with the following formula:(16)ΔLi=min⁡ΔLi1,ΔLi2,ΔLi3,ΔLi4


## 3.3. Improved Adams-Moulton Method

To implement NURBS interpolation, the Adams-Moulton (AM) method is adopted here. Using the AM method, the curve approximation up is given as follows [18]:(17)um+1=um+T249fk+1+19fk-5fk-1+fk-2fk=dudtt=tm=VumC′um,where Vum, T, and C′um denote the feed rate, the sampling time, and the first derivatives of the NURBS curve, respectively.Although the second-order derivative operation is avoided by AM method, an implicit is introduced and it is also needed to solve first-order derivative. Therefore, the forward-center-backward difference is used to replace the differential to improve AM method so that the operation time of interpolation algorithm can be shortened and the real-time performance is able to be ensured. The three different forward-center-backward differences are as in formulas (18), (19), and (20), respectively:(18)um+1′=um+1-umTBackward  differenceum′=um+1-umTForward  differenceum-1′=um-um-22TCentral  differenceum-2′=um-1-um-2TForward  difference(19)um+1′=um+1-umTBackward  differenceum′=um-um-1TBackward  differenceum-1′=um-um-22TCentral  differenceum-2′=um-1-um-2TForward  difference(20)um+1′=um+1-umTBackward  differenceum′=um+1-um-12TCentral  differenceum-1′=um-um-1TForward  differenceum-2′=um-1-um-2TForward  difference.When (18), (19), and (20) are substituted into (17), the improved AM method is as in formulas (21), (22), and (23), respectively:(21)um+10=18·13um-2um-1-3um-2(22)um+11=110·21um-12um-1+um-2(23)um+22=111·20um-7um-1-2um-2.Due to the slow convergence rate of the traditional correction formula, the Inverse Quadratic Interpolation (IQI) is adopted to calculate the estimated parameteru~m+1. When parameters um+10, um+11, um+12 are substituted into  (7), estimated feed step lengths ΔLm+10, ΔLm+11, ΔLm+12 are obtained, respectively. So, the estimated parameter u~m+1 calculation formula is as follows [26]:(24)u~m+1=um+12-r·r-q·um+12-um+11+1-r·s·um+12-um+10q-1·r-1·s-1,where q=ΔLm+10/ΔLm+11, r=ΔLm+12/ΔLm+11, s=ΔLm+12/ΔLm+10.Theoretically, sampling step size should satisfy the following equation:(25)Cu~m+1-Cu~m=Vu~m·THowever, truncation errors and the discrepancy errors between machining trajectory and the demand curve will make (25) dissatisfied; that is, feed rate fluctuation existed. So, feed rate fluctuation ε should be considered and it can be defined as follows:(26)ε=Vu~m·T-Cu~m+1-Cu~mVu~m·T·100%.


## 4. Simulation Study

In this section, two NURBS curves of degree 3 named trident and butterfly shown in Figure2 are used as examples to test the feasibility of the developed interpolation scheme and the command generator programs are written by Matlab and are executed on a personal computer with Intel(R) Core(TM) i5-2450M 2.50 GHz CPU. According to Figure 2, the trident and butterfly curves parameters are given in Appendix and the interpolation conditions for two NURBS curves of degree 3 are listed in Table 1.Table 1
The interpolation conditions for two third-degree NURBS curves.
Parameters
Symbols
Units
Namely feed rate
F
80 mm/s
Maximum acceleration
A
m
a
x
1200 mm/s2
Maximum jerk
J
m
a
x
25000 mm/s3
Maximum chord error
δ
m
a
x
0.001 mm
Sampling time
T
0.001 sFigure 2
NURBS curves for simulations.
(a)
The trident contour
(b)
The butterfly contourIn this section, feed rate precision is only considered and feed rate scheduling [27] is applied as shown in Figures 3 and 4. The AM method and IAM method are compared based on feed rate precision. Finally, simulation results of the trident and butterfly NURBS curve are shown in Figures 5 and 6, respectively. In addition, important data of simulations are given in Table 2.Table 2
Simulation results of two interpolation methods.
Interpolation algorithm
The maximum federate fluctuation ratio (%)
Interpolation time (s)
Trident
Butterfly
Trident
Butterfly
AM method
0.0017
0.023
1.800
5.808
IAM method
0.0008
0.0033
1.908
5.910Figure 3
Feed rate scheduling results of the trident NURBS curve.
(a)
The feed rate profile
(b)
The acceleration profile
(c)
The jerk profileFigure 4
Feed rate scheduling results of the butterfly NURBS curve.
(a)
The feed rate profile
(b)
The acceleration profile
(c)
The jerk profileFigure 5
Simulation results of the trident NURBS curve.
(a)
The AM method
(b)
The IAM methodFigure 6
Simulation results of the butterfly NURBS curve.
(a)
The AM method
(b)
The IAM methodFrom Figure5, it can be seen that the maximum feed rate fluctuation of the AM method is about 0.0017%. The maximum feed rate fluctuation of the IAM method is about 0.0008% and it is almost close to zero. Overall, the proposed IAM method is suitable for other simple third-degree NURBS curves. In Figure 6, it can be seen that the maximum feed rate fluctuation of the AM method is about 0.023%. The maximum feed rate fluctuation of the IAM method is about 0.0033%. Feed rate fluctuation is reduced about 14 times with the IAM method. From above all, the proposed IAM method is suitable for other complex third-degree NURBS curves and it is satisfied for modern CNC machining. From Table 2, it can be seen that the interpolation time of trident and butterfly NURBS curve based on the AM method is lower than the proposed IAM method, but gap is very small. In summer, the proposed IAM interpolation method in this paper has better flexibility than the AM method.


## 5. Experimental Verification

The CNC platform is developed for verifying the proposed IAM method experimentally. The hardware and software structures are as follows:(i)
CPU: Intel(R) Core(TM) i5-2450M 2.50 GHz(ii)
Servo system
(a)
x-/y-axis: Panasonic MBDKT2510E (driver) + Panasonic MHMJ042G1U (motor)(iii)
Drive system: ball screws, 5 mm screw pitch(iv)
Software
(a)
OS: 32-bit Windows 7(b)
Real-time core: motion control card based on DSP+FPGA, including linear, circular and NURBS interpolator, and other basic modules, the sampling time being 1 msThe butterfly NURBS curve is represented and machined by the CNC platform. The maximum feed rate is 4800 mm/min. The machining result is shown in Figure7. In Figure 7(b), there are bulges at positions 1 and 3. However, interpolation lines are continuous at positions 1 and 3 from Figure 7(c). In Figure 7(b), the break point is sunken and unsmooth at position 2. Nevertheless, transition of the break point is smooth at position 2 from Figure 7(c). From above all, the final experimental results show the proposed IAM method is more feasible than AM method.Figure 7
The machining of the butterfly curve.
(a)
Hardware and software of the host computer
(b)
The machining result of AM method
(c)
The machining result of IAM method


## 6. Conclusions

In this paper, an improved Adams-Moulton method for NURBS interpolation with minimal feed rate fluctuation has been proposed. The main conclusions of the study are as follows:(i)
The theoretical model of the proposed IAM method is built based on the derived analytic relations between the kinematic characteristics and the parameters of path curve as well as feed rate profile.(ii)
The proposed IAM method has been validated by simulations and experimental tests. It is effective and reliable for the feed rate interpolation of geometrically simple and complex NURBS curves of degree 3 and smaller feed rate fluctuation based on the proposed IAM method can be obtained compared with the AM method.



---

*Source: 8718760-2017-03-22.xml*