1 Introduction

Non-uniform rational B-splines (NURBS) has been widely used in the designing of free-form surface, as it can offer an exact uniform representation of analytical shapes as well as free-form parametric curves and surfaces [1, 2]. However, as a kind of parametric curve, there is no analytic relationship between its parameter u and the corresponding arc length, so it is difficult to design a high accurate and real-time interpolator with small feedrate fluctuation.

Therefore, NURBS interpolator is always a research hotspot in the last decades, and many interpolation algorithms have been proposed in order to get better performance [3,4,5], which can be divided into three categories: approximation method, fitting method, and feedback method.

Approximation is first proposed by Koren et al., where time-based Taylor’s expansion is used to approximate the NURBS curve [3]. Different algorithms are developed based on this idea after that [6,7,8]. Runge-Kutta [9] and Adams-Bashforth [10] methods are also used in order to improve the approximation accuracy. However, truncation errors are inevitable for these methods in practice, so feedrate fluctuations are also inevitable, although high-order terms can improve the accuracy, which means more computational load and worse real-time performance.

Fitting method can also be called remapping method, and Cheng et al. employs a high-order polynomial spline to fit the relationship of arc length and the curve parameter u [11]. Liu et al. proposed a quartic equation-based interpolation algorithm, which can reduce the feedrate fluctuation for NURBS curves to satisfy the command feedrate [12]. This method can get a direct relationship between the parameter and arc length, but the fitting operation is time-consuming, and large amount memory is required, so it is not suitable for real-time interpolation.

Feedback parametric interpolation is an improvement of the approximation method proposed by Lo [13], which employs an iterative way to approximate a desired point. Cheng et al. proposed a real-time predictor–corrector interpolator, the feedrate command error can fall within the specified tolerance with a predicted initial value and iteration [14]. Zhao et al. proposed a feedback interpolator with arc-length compensation and the feedback correction, good efficiency and accuracy can be achieved with their method [15]. These feedback methods can get desired feedrate fluctuation with enough times of iteration, but the iteration time is uncertain, so it is also not suitable for real-time interpolator [16].

In Summary, there is always a tradeoff between the computational load and the desired performance. An interpolator with high accuracy, high efficiency, and small feedrate fluctuation is still a big challenge for motion control systems in practice [17].

Therefore, an interpolation method based on Taylor’s expansion with arc length prediction and feedback correction is proposed in this paper. Firstly, a NURBS curve is split into several continuous segments, and the velocity profile is generated based on the arc length of every segment. Secondly, a prediction model is derived from the relationship of the previous arc length and the corresponding feed length in one interpolation interval. As derivative and curvature of NURBS curves used in CAD/CAM system are continuous, the arc length can be predicted with this model and the command feed length. Finally, the value of parameter u is calculated with Taylor’s expansion method and corrected by iteration, so that the target position with small feedrate fluctuation can be achieved from the parametric equations.

The rest of this paper is organized as follows. Section 2 is the introduction of Taylor’s expansion-based NURBS interpolation and the analysis of feedrate fluctuation. Section 3 is the details of the proposed online interpolation method. The simulation results are given in Section 4. Conclusions are summarized in Section 5.

2 Interpolation of NURBS curve

As a non-uniform rational B-spline curve, NURBS curve C(u) can be expressed as in Eq. (1)

$$ C(u)=\frac{\sum \limits_{i=0}^n{N}_{i,p}(u){P}_i{w}_i}{\sum \limits_{i=0}^n{N}_{i,p}(u){P}_i},u\in \left[0,1\right] $$
(1)

where the index i=0, 1, …, n, Pi is the set of control point, wi is the set of corresponding weight of Pi , (n+1) is the number of the control points, and p is the degree of the NURBS curve. Ni,p(u) is the B-spline basis function defined on the non-uniform knot vector U={u0 ,u1 ,⋯,un+p+1}. The B-spline basic function Ni,p(u) is defined as

$$ {\displaystyle \begin{array}{c}{N}_{i,0}(u)=\left\{\begin{array}{c}0\kern0.5em if\ {u}_i<u\le {u}_{i+1}\\ {}1\kern0.5em otherwise\end{array}\right.\\ {}{N}_{i,p}(u)=\frac{u-{u}_i}{u_{i+p}-{u}_i}{N}_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-{u}_{i+1}}{N}_{i+1,p-1}(u)\end{array}} $$

The interpolation of NURBS curve can be divided into two stages: pre-processing and online interpolation. In pre- processing, a NURBS curve is split into several continuous segments based on its degree and control points. In online interpolation stage, the parameter u is derived with Taylor’s expansion or other interpolation algorithms, and then the position of the target interpolation points can be obtained. The process is in Fig. 1.

Fig. 1
figure 1

interpolation process of NURBS curve

Full size image

2.1 Pre-processing of NURBS curve interpolation

NURBS curve is the linear combination of a series of B-spline basis functions, so it is (p-k) times continuously differentiable at a knot of multiplicity k for a p degree curve [14]. The continuity degree of the curve at each knot can be achieved by its degrees and knot vector. So that an NURBS curve can be divided into several separate segments of infinitely differentiable spline base on the orders of its continuity and number of control points.

Two examples with repeated knot vector values and multiple control points are shown in Fig. 2 where P={P1,P2,…P7} are control points of the NURBS curve. Both of these two curves are second degree. In Fig. 2 (a), knot vector is U=[0, 0, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1, 1], and in Fig. 2 (b), control points P3=P4. These two curves both can be split into two smooth segments with the abovementioned method.

Fig. 2
figure 2

Division of second-degree NURBS, (a) NURBS curve with repeated knot vector elements, (b) NURBS with multiple control points

Full size image

It is necessary to get the accurate arc length of the split continuous segments first before velocity scheduling and interpolation. The arc length of the NURBS curve between [a, b] can be expressed as in Eq. (2)

$$ s={\int}_a^b\left\Vert {C}^{\prime }(u)\right\Vert du $$
(2)

where ‖ ∗ ‖ denotes the vector norm and ‖C′(u)‖ is the norm of the first-order derivative of C′(u).

However, there is no analytical relation between the arc length and its parameter for NURBS curve, as in the case of lines and circles, so a numerical integration method Simpsons rule is adopted considering the computational accuracy and load. The approximate arc length s(a, b) of a segment of NURBS curve on the interval [a, b] can be expressed as

$$ s\left(a,b\right)=\left[C(a)+4C\left(\frac{a+b}{2}\right)+C(b)\right]\frac{\left(b-a\right)}{6} $$

For a specified tolerance ε, if the condition in Eq. (3) is satisfied, then the approximation is within the given tolerance of the true arc length.

$$ \frac{\mid s\left({a}_1,{b}_1\right)+s\left({a}_2,{b}_2\right)-s\left(a,b\right)\mid }{10}<\varepsilon $$
(3)

where [a1 ,b1] and [a2 ,b2] are the intervals split from [a, b]. If the condition in Eq. (2) cannot be satisfied, the subintervals should be further refined.

2.2 Interpolation based on Taylor’s expansion

Arc length of NURBS is in a nonlinear relationship with its parameter u, so its interpolation algorithm is much more complex than linear and circle interpolation. The interpolation of NURBS is a process of computing a proper parameter value u to satisfy that the feed length in an interpolation interval is equal to the command velocity.

The feedrate V(t) of can be defined as

$$ V(t)=\left\Vert \frac{dC(u)}{dt}\right\Vert $$

where u(t) is a monotone increasing function of time in the NURBS interpolation, then the equation as in Eq. (4) can be derived

$$ V(t)=\left\Vert \frac{dC(u)}{dt}\right\Vert =\left\Vert \frac{dC(u)}{du},\cdot, \frac{du}{dt}\right\Vert =\left\Vert \frac{dC(u)}{du}\right\Vert \cdot \frac{du}{dt} $$
(4)

therefore, the first-order derivatives of u(t) can be achieved as in Eq. (5).

$$ \frac{du}{dt}=\frac{V(t)}{\left\Vert \frac{dC(u)}{du}\right\Vert } $$
(5)

the second-order derivatives of u(t) can be achieved as in Eq. (6).

$$ \frac{d^2u}{d{t}^2}=\frac{V_k^2\left\langle \frac{dC(u)}{du},\frac{d^2C(u)}{d{u}^2}\right\rangle }{{\left\Vert \frac{dC(u)}{du}\right\Vert}^4} $$
(6)

The algorithm based on the first- or second-order Taylor’s expansion method is one of the most used methods to obtain the value of parameter u. Therefore uk+1 can be calculated with Taylor’s expansion.

$$ {u}_{k+1}={u}_k+T\left(\frac{du}{dt}\right){\left|{}_{u={u}_k}+\frac{T^2}{2}\left(\frac{d^2u}{d{t}^2}\right)\right|}_{u={u}_k}+o\left({T}^3\right) $$
(7)

where T is the interpolation interval. Substituting Eq. (5) into (7), then uk+1 can be derived. If the interpolation interval is small enough, the higher order infinitesimal in Taylor’s expansion can be neglected, and the first-order Taylor’s expansion can be derived as in Eq. (6)

$$ {u}_{k+1}\approx {u}_k+\frac{V_kT}{\left\Vert \frac{dC\left({u}_k\right)}{du}\right\Vert } $$
(8)

More accurate result can be achieved with second- or even higher-order Taylor’s expansion, and the-second order Taylor’s expansion is shown in Eq. (9).

$$ {u}_{k+1}\approx {u}_k+\frac{V_kT}{\left\Vert \frac{dC\left({u}_k\right)}{du}\right\Vert }+\frac{{\left.{\left({V}_kT\right)}^2\Big\langle \frac{dC(u)}{du},\frac{d^2C(u)}{d{u}^2}\Big\rangle \right|}_{u={u}_k}}{{\left\Vert \frac{dC(u)}{du}\right\Vert}_{u={u}_k}^4} $$
(9)

Therefore, the next interpolation point can be achieved by C(uk+1), where the feed arc length of current interpolation interval is expressed as VkT.

2.3 Feedrate fluctuation analysis

The interpolation point C(uk+1) on the curve can be achieved with uk+1, so that the resultant displacement of the motion can be achieved

$$ {l}_k={\hat{V}}_kT=\left\Vert C\left({u}_{k+1}\right)-C\left({u}_k\right)\right\Vert $$
(10)

There are two problems need to be noticed. Firstly, VkT is the arc length of current curve as shown in Eq. (11), which is different from the chord length \( {\hat{V}}_kT \) in Eq. (10).

$$ {s}_k={V}_kT={\int}_{u_k}^{u_{k+1}}\left\Vert \frac{dC(u)}{du}\right\Vert du $$
(11)

Secondly, the high-order term of Taylor’s expansion is neglected. Although the higher-order Taylor’s expansion can achieve better precision, truncation errors are still inevitable. These two factors lead to the difference of desired and actual feed length in an interpolation interval as in Fig. 3. In another words, the feedrate fluctuation ε from the difference of the actual velocity \( {\hat{V}}_k \) and the desired velocity Vk is unavoidable as in Eq. (12).

$$ \varepsilon =\left|\frac{V_k-{\hat{V}}_k}{V_k}\right|\times 100\% $$
(12)
Fig. 3
figure 3

Desired and actual feed in an interval

Full size image

In order to achieve smaller feedrate fluctuation, another interpolation target point B’ as in Fig. 3 needs to be found, so that the actual feed length |AB’| could be equal to the arc length AB, and feedrate fluctuation can be eliminated. So how to get the target point B’ to insure that the chord length |AB’| is equal to its arc length AB is the target of this paper.

3 Interpolation with online arc length prediction and correction

The proposed online interpolation method can be divided into two stages. Firstly, a prediction model is derived based on the relationship of the arc length and chord length of previous interpolation results, and then target arc length AB’ is predicted based on the desired feed length and the derived model. Secondly, target parameter u of the curve is derived with Taylor’s expansion and corrected by iteration, so the position of the target interpolation points can be obtained. The whole process is as shown in Fig. 4.

Fig. 4
figure 4

Flowchart of the arc length predictor and correction algorithm

Full size image

3.1 Arc length predictor

Mark the arc length between uk and uk+1 as sk, and its corresponding chord length as lk. When the arc length is small enough, it can be approximated with a circle of same curvature as shown in Fig. 5

Fig. 5
figure 5

relationship of chord length, curvature and arc length

Full size image

Therefore, the arc length sk can be expressed as a function of the chord length lk and the radius of curvature 1/Rk, as shown in Eq. (13).

$$ {s}_k=f\left({R}_k,{l}_k\right)\approx 2{R}_k\cdotp \mathit{\sin}\frac{l_k}{2{R}_k} $$
(13)

The chord length lk is the actual feed length in an interpolation interval, which is computed in the feedrate scheduling stages. It can be seen that the arc length sk is a function of the its curvature 1/Rk and the chord length lk. In another word, if the curvature of the spline is continuous, the arc length sk corresponding to the given chord length lk will change continuously with the curvature of the spline.

$$ {\displaystyle \begin{array}{c}\underset{\theta \to 0}{\lim }{s}_k=\underset{\theta \to 0}{\lim }2{R}_k\cdotp \mathit{\sin}\frac{l_k}{2{R}_k}\\ {}=2{R}_k\cdotp \frac{l_k}{2{R}_k}\\ {}={l}_k\end{array}} $$
(14)

When the chord length tends to zero, it will be equal to the arc length. Take the quotient of arc length sk and chord length lk as λ, then λ can be expressed as in Eq. (15).

$$ \lambda =\frac{s}{l}=\frac{\int_{u_k}^u\left\Vert \frac{dC(u)}{du}\right\Vert du}{\left\Vert C,(u),-,C,\left({u}_k\right)\right\Vert } $$
(15)

A polynomial is employed to approximate this relationship in an interpolation interval. It is known that cubic spline is most used in CAD/CAM, whose derivative and curvature are continuous, so λ is continuous. Arc length λk+1 can be interpolated based on the previous value λk, λk-1 and λk-2. Here Newton’s divided difference interpolation polynomial is employed to get the correction factor.

$$ {\lambda}_k={\lambda}_0+\sum \limits_{k=1}^n\frac{\varDelta^k{\lambda}_k}{k!}s\left(s-1\right)\cdots \left(s-k+1\right),\kern0.5em 0\le s\le n $$

The divided differences table is shown in Table 1.

Table 1 Newton backward difference formula
Full size table

Then the target arc length sk+1 corresponding to the desired feed length VkT can be derived as in Eq. (16).

$$ {s}_{k+1}={l}_{k+1}\cdotp {\lambda}_{k+1}={V}_kT\cdotp {\lambda}_{k+1} $$
(16)

Different orders of the divided quotient can be employed to get desired precision. When abovementioned algorithm is implemented, arc length and chord length are unknown at first, so a buffer is needed. Only when the buffer is full with historic data, the Newton’s divided difference interpolation polynomial can start working.

3.2 Feed-length correction

$$ {u}_{k+1}^1\approx {u}_k+\frac{V_kT{\lambda}_{k+1}}{{\left.\sqrt{{\left(\frac{dx}{du}\right)}^2+{\left(\frac{dy}{du}\right)}^2+{\left(\frac{dz}{du}\right)}^2}\right|}_{u={u}_k}} $$
(17)

Taylor’s expansion is employed to get the value of parameter u as shown in Eq. (8) and Eq. (9). Given the computational load of second-order Taylor's expansion, firs order is employed here.

As the feed length in an interpolation interval is the predicted with Eq. (16), then another target position B1 as in Fig. 7 is obtained, then uk+1 can be derived as shown in Eq. (17).

The actual feed length in this interpolation interval can also be achieved as in Eq. (18).

$$ {l}_{k+1}^1=\sqrt{{\left.{\left({x}_{k+1}-{x}_k\right)}^2+{\left({y}_{k+1}-{y}_k\right)}^2+{\left({z}_{k+1}-{z}_k\right)}^2\right|}_{u={u}_{k+1}^1}} $$
(18)

Take Δlk + 1 as the difference between the feed displacement and chord length, when the value is 0 means the feedrate fluctuation is 0. So that an iterative formula can be derived as in Eq. (19).

$$ \left\{\begin{array}{c}{\left.{u}_{k+1}^{i+1}={u}_{k+1}^i+\frac{\varDelta {l}_{k+1}^i}{\sqrt{{\left(\frac{dx}{du}\right)}^2+{\left(\frac{dy}{du}\right)}^2+{\left(\frac{dz}{du}\right)}^2}}\right|}_{u={u}_{k+1}^i}\\ {}\varDelta {l}_{k+1}^i={V}_kT-{l}_{k+1}^i\end{array}\right. $$
(19)

An ideal value of feedrate fluctuation can be obtained with enough times of iteration; the process is shown in Fig. 6.

Fig. 6
figure 6

Process of getting target feedrate fluctuation

Full size image

4 Simulation and verification

A segment of 2D cubic curve as in Eq. (20) is interpolated with the velocity V=1.5m/min, interpolation interval T=0.001s.

$$ \Big\{{\displaystyle \begin{array}{c}x=-140{u}^3+90{u}^2+90u\\ {}y=-90{u}^2+90u\kern1.00em \end{array}} $$
(20)

The contour shape and velocity profile of this curve are shown in Fig. 7. The feedrate fluctuation performance of traditional Taylor’s expansion method and the proposed prediction model based algorithm is shown in Fig. 8.

Fig. 7
figure 7

The tested cubic polynomial curve, (a) Shape of the curve, (b) Velocity profile

Full size image
Fig. 8
figure 8

Feedrate fluctuation comparison of different methods, (a) 1st order Taylor’s expansion, (b) 2nd order Taylor’s expansion (c)1st order Taylor’s expansion with 3rd order polynomial predictor, (d) 1st order Taylor’s expansion with 3rd order polynomial predictor and twice iteration

Full size image

The maximum feedrate fluctuation of first-order Taylor’s expansion interpolation method is about 0.35%, as shown in Fig. 8(a). When second-order Taylor’s expansion is employed, better performance can be achieved, and the feedrate fluctuation can be reduced to 3×10-3 %, as shown in Fig. 8(b). The feedrate fluctuation of arc length predictor model is only one thousandth of second-order Taylor’s expansion as in Fig. 8(c), and better performance can be achieved when iteration is applied as in Fig. 8(d).

For the curve in Eq. (20), even second-order Taylor’s expansion based interpolator can get the desired feedrate fluctuation. The interpolation of a more complicated butterfly shape NURBS curve in Fig. 9(a) is used to verify the performance of proposed method, where Fig. 9(b) is the velocity profile. The feedrate fluctuation of these methods is shown in Fig. 10, and the sum of feedrate fluctuation in the whole interpolation process is shown in Table 2.

Fig. 9
figure 9

The tested cubic polynomial curve, (a) shape of the curve, (b) velocity profile

Full size image
Fig. 10
figure 10

Feedrate fluctuation comparison of different methods, (a) 1st order Taylor’s expansion, (b) 2nd order Taylor’s expansion, (c) 1st order Taylor’s expansion with 3rd polynomial predictor, (d) 1st order Taylor’s expansion with 3rd polynomial predictor and twice iteration

Full size image
Table 2 Sum of feedrate fluctuation in the whole interpolation process
Full size table

The interpolation results show that, although the biggest feedrate fluctuation of second-order Taylor’s expansion method in Fig. 10(b) is smaller than arc length predictor model in Fig. 10(c), its sum feedrate fluctuation is bigger as in Table 2. Besides, the computational load of second-order Taylor’s expansion method is also larger than third-order polynomial. When the predictor and iteration method are combined together, the feedrate fluctuation can reduce hundreds times, and high performance can be achieved as in Fig. 10(d) and Table 2.

5 Conclusion

Feedrate fluctuation in NURBS interpolation is analyzed, and a novel interpolator is proposed to get small feedrate fluctuation. A polynomial based prediction model is derived based on the continuous relationship of the interpolated chord length and its corresponding arc length, so that an accurate interpolation arc-length with small feedrate fluctuation can be achieved with this model. Then the target parameter u in every interpolation cycle is calculated with Taylor’s expansion and corrected by iteration, so the desired feedrate fluctuation can be achieved. Performance of the proposed algorithm is tested with two segments of curve, and the simulation results show that the proposed algorithm can get smaller feedrate fluctuation with fewer times of iteration than traditional Taylor’s expansion method.