# Real-Time NURBS Interpolation under Multiple Constraints

Authors: Mingxing Nie; Yaping Wan; Aijun Zhou
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

NURBS interpolation is superior to traditional linear or circular interpolation in terms of code size, surface quality, and machining efficiency. However, with the increasing demands for high-accuracy and efficient machining, NURBS interpolation has faced a growing number of challenges. Many researchers are actively involved in this field with great interest. Due to the special form of NURBS curve, there is a nonlinear relationship between its curve and arc length; feed fluctuations and mechanical shocks which are caused during the interpolation process will seriously affect the surface accuracy and quality of machined parts. To solve these problems, a real-time NURBS interpolation is proposed under multiple constraints (RNIC) in this paper. First, the formulas of the constrained feedrate under geometric errors, kinematic constraints, drive constraints, and contour errors are given. Then, the two stages for the proposed interpolation are established. The former stage is offline preprocessing stage, which aims to quickly find feedrate sensitive areas (FSAs), while the latter online stage is the real-time interpolation, which is responsible for smoothing the velocity. In the preprocessing stage, we utilized FSA scan module and feedrate adjustment module to detect the FSAs and adjust the feedrate at the start/end of each subsegment by a bidirectional scanning algorithm. Each segment contains acceleration and deceleration (some contains uniform speed) stages, which can be well matched with the processing process of acceleration and deceleration. Finally, according to the proposed method and the adaptive speed adjustment method, the simulation of a “butterfly-shaped” NURBS curve using the S-shaped ACC/DEC algorithm is carried out, which verifies the reliability and effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

As one of the international industrial standards of CAD system, NURBS curves play an increasing role in the application fields of computer-aided geometric design (CAGD) with the wide application of this geometric model. Profiting from the ability of changing the shape of local contours and describing complex contours by low-order equations, NURBS interpolations have been increasingly developed in CNC machining. NURBS interpolation is superior to traditional linear and circular interpolation in terms of code size, surface quality, and machining efficiency. However, there are still some challenges in building a successful NURBS interpolator. First, the feedrate along the machining path may be limited by many factors including geometrical, kinematic, and axis dynamics constraints in large curvature areas; these constraints should be reasonably and smoothly adjusted to ensure good machining quality and accuracy. Second, abrupt curvature change will cause ACC/DEC and jerk out of tolerance. Last, there is no mathematical expression between the NURBS curve parameters and displacement, which inevitably leads to a fluctuation between the expected and actual feedrates.In order to improve machining accuracy and efficiency, Yeh and Hsu [1] adaptively adjust the feedrate considering the constrained chord error, which improves the contour accuracy of parametric curve interpolation. Yong and Narayanaswami [2] proposed the concept of feedrate sensitive corners to confine acceleration and deceleration in offline processing. Nam and Liu [3, 4] further limited the effect of jerk on machining in NURBS interpolation. While these efforts are effective, many key constraints are overlooked; various advanced algorithms have been further developed by many researchers. For example, Sencer et al. [5] solved the analytical solution of feedrate in the form of cubic B-spline, but the calculation efficiency of this process is low. Sun et al. [6] proposed a feedrate scheduling method based on drive constraints. Xavier et al. [7] developed a velocity profile optimization method based on iterative calculation of intersection points with given constraints. However, this method ignores the influence of contour accuracy. Jia et al. [8] proposed a NURBS interpolator under kinetic characteristics and contour error constraints, in which the feedrate remained constant in most areas and only changed smoothly in areas with large curvature, but the production efficiency was degraded when utilizing a constant low feedrate without making full use of the motion performance in this method. Ma et al. [9] also considered, from the perspective of axis restriction, maintaining constant feedrate in the sensitive area and smooth transition in the non-sensitive area. Liu et al. [10] used a linear mathematical model to explore the relationship between feedrate and geometric constraints. Liu et al. [11] also developed a new feedrate optimization method under multiple constraints and finally fitted to the smooth spline curve. However, these two methods only considered the influence of geometric and axis dynamics errors. Zhong et al. [12] further limited the axial velocity, axial acceleration, jerk, and contour errors through a look-ahead module.Moreover, to mitigate the feed fluctuation to further improve the machining accuracy, many methods have been proposed for NURBS interpolation. Liu et al. [13] proposed a NURBS interpolation using approximation errors, but the calculation coefficient polynomial equation is time-consuming. Liu et al. [14] proposed a highly accurate interpolation method by establishing an improved quartic equation related to the curve parameter increment to reduce the feedrate fluctuation caused by approximation errors. However, this method obtains a quartic equation by ignoring the higher-order term (order >4), which has limited adaptability. Ni et al. [15] proposed a round-off error-free feedrate scheduling method. However, this method limits the feedrate to meet the various constraints by increasing the interpolation time, which is not efficient. Song et al. [16] compensates the interpolation parameters in order to improve the calculation accuracy of the parameters for the next interpolation point. Jiang et al. [17] presented an iterative feedback interpolator that consists of estimator and corrector stages to restrain the feedrate fluctuation. Chen et al. [18] developed a NURBS interpolation method for deriving parametric curves based on Steffensen’s iterative method to avoid unnecessary feedrate fluctuations. Ji et al. [19] calculated the interpolation point parameters through iterative correction to obtain the accurate position and reduce the federate fluctuates. However, these methods have difficulty guaranteeing convergence when using iterative methods. To reduce feedrate fluctuations, Wang et al. [20] developed a bi-interpolation algorithm using two second-order Taylor expansions in one interpolation cycle. However, the time cost of this algorithm is relatively large.In addition, much effort has been made to develop feedrate optimization techniques, and many fruitful feedrate scheduling methods have been proposed. The feedrate profile of the linear acceleration and deceleration algorithm [21–23] is not smooth, and machine vibration will inevitably occur during the movement. In the early days, NURBS interpolation was realized by using the speed adaptive adjustment methods [1, 24], but these methods could not meet the tolerance limits of chord error, acceleration, and jerk. Du et al. [25] developed a complete S-shaped NURBS interpolation under confined jerk, acceleration limits, which adopted compensate on strategies to make the federate more continuous and the arc increment more precise. Lin et al. [26] used a look-ahead module to generate smooth feedrate profile to accommodate NURBS curve dynamics. Liu et al. [27] proposed the idea of NURBS curve segmentation to construct a new NURBS interpolator to improve contour error accuracy. Sun et al. [28] optimize short-line segmented machining using S-shaped ACC/DEC algorithm and time optimization function to obtain better machining accuracy and efficiency. Liu and Leng [14, 29] proposed a cubic polynomial NURBS interpolation. However, the cubic polynomial ACC/DEC algorithm is inefficient, and the jerk profile is discontinuous, which will impact the machine tool. Liu et al. [30] further improved and proposed the jerk-continuous NURBS interpolation method, which improved the contour machining accuracy and improved the low flexibility at small curvature sharp corners. However, these methods only consider the influence of the geometric characteristics of the curve and ignore the influence of the dynamic performance and contour error. Ni et al. [31] proposed a jerk-continuous NURBS interpolation. However, the computational load of this method is high, as the algorithm needs to deal with the coexistence of trigonometric functions and polynomial functions at the same time. Zhao et al. [32] applied a jerk-limited method to smooth the sharp corners of the final feedrate profile, which improved the feed correction polynomial to reduce the feed fluctuation. Furthermore, to address the problem of feedrate curve fluctuations in regions of large curvature, Su et al. [33] made full use of the local geometric information and adopted the method of sliding arc tube to optimize the target feedrate.Traditional method is to subsegment the curve and then perform acceleration and deceleration processing based on local geometric information. In fact, when the arc length is less than the shortest requisite ACC/DEC distance, there are many types of ACC/DEC involved, and the processing is very complicated, which is not conducive to the realization of real-time interpolation. This article innovatively proposes a novel bidirectional scanning algorithm. For the curve subsegment with shorter arc length, directly process it at a uniform speed, discarding the complicated ACC/DEC process; for the long curve subsegment, readjust the acceleration end point or deceleration start point according to the acceleration or deceleration distance to meet the S-curve ACC/DEC requirements. This method is simple and efficient to process shorter curves, which is in line with the actual processing process of the special difficult-to-machine parts of the workpiece. Therefore, it can effectively improve the indicated processing quality of the processed part without increasing the hardware cost. Although the processing time is extended to a certain extent, generally speaking, because the arc length of the curve subsegment is shorter, it is meaningful to sacrifice a certain amount of time to obtain higher real-time performance and processing effect.


## 2. The Presented Interpolation Architecture

### 2.1. NURBS Parameter Discretization

NURBS curves can be represented by parameters as follows:(1)Cu=∑i=0nNi,puωipi∑i=0nNi,puωi,u1≤u≤un+p+1.where i is the index i = 0, 1, …, n; Pi is the set of control points; ωi is the set of weights; and Ni,pu is the set of p-order B-spline basic functions defined on the non-uniform knot vector U, U=u0,u1,…,un+p+1. The B-spline basic function Ni,pu is calculated as(2)Ni,pu=u−uiui+p−uiNi,p−1u+ui+p+1−uui+p+1−ui+1Ni+1,p−1u,Ni,0u=1,ui<u<ui+1,0,otherwise,The first-order and second-order derivatives ofB-spline basic functions and NURBS curves are, respectively, given as(3)Ni,p′u=pui+p−uiNi,p−1u−pui+p+1−ui+1Ni+1,p−1u.The first derivative and second derivative of cu can be calculated as(4)C′u=∑i=0nNi,p′uωipi−cu⋅∑i=0nNi,p′ωi∑i=0nNi,pωi,C″u=∑i=0nNi,p″uωipi−2c′u⋅∑i=0nNi,p′ωi−cu⋅∑i=0nNi,p″ωi∑i=0nNi,pωi,For a pointcu on the NURBS curve, the curvature radius ρu can be calculated by(5)ρu=C′u3C′u×C″u,where ⋅ stands for the Euclidean norm and × means the exterior product.In this paper, the Adams-Bashforth-Moulton method (ABM) is adopted to discretize the parameter vector for NURBS interpolation. The ABM method is as follows:(6)um+1=um+T2455fk−59fk−1+37fk−2−9fk−3,fk=dudtt=tm=vumC′um=vumdCxum/dum2+dCyum/dum2+dCzum/dum2,where vum, T, and C′um are the velocity, the interpolation period, and the first derivatives of the NURBS curve; Cxum, Cyum, and Czum denote the parameter curve; um corresponds to each axis component of the interpolation point Cum on the curve.The NURBS interpolation process is continuously affected by geometric errors, motion errors, drive errors, and contour errors. Aiming at the above problems, in the preprocessing stage, under the premise of considering multiple constraints, a real-time NURBS interpolation under multiple constraints (RNIC) is proposed, which can accurately obtain the constrained interpolation feedrate and optimal interpolation points.


### 2.2. Architecture of RNIC NURBS Interpolation

A systematic NURBS interpolator with smoothing feedrate at the FSA under multiple constraints is developed to enhance the interpolator performance with respect to the machining precision and machining quality. The overall structure of the interpolator is shown in Figure1. The interpolator has two stages, namely, the preprocessing stage and the real-time interpolation stage. The former preprocessing stage aims to find the FSA quickly, while the latter real-time interpolation implements velocity smoothing and generation of interpolated toolpath points.Figure 1
The structure of the FSA NURBS interpolator.The interpolator comprehensively considers various constraints, breaking through the geometric constraints, kinematic feature constraints, and machine performance constraints of NURBS interpolation, including various constraints such as chord error, velocity, normal acceleration and jerk, contour error, and command feedrate. There are two modules in the preprocessing stage, namely, the FSA scan module and the segment feedrate adjustment module, which are used to obtain the geometric features required by the NURBS curve as the input for the next step of real-time interpolation.The goal of the FSA scan module is to efficiently obtain FSAs of the NURBS curve by introducing the first FSA scan algorithm, then find the critical point in each FSA in the second FSA scan algorithm and divide the FSA curve blocks into subsegments, and further get more detailed information about the geometric features of subsegments. The goal of the segment feedrate adjustment module is to optimize the feedrate profile for segments data generated by the former FSA scan module, which includes short segments processing, long segments backward scanning, and long segments forward scanning. During short segments processing, update the feedrate of the start/end point at the beginning and end of the segment to the same smaller speed, and then keep the entire short segment interpolation speed constant; during long segments processing, use backward and forward directions. In the forward scanning process, in order to simplify the processing flow, first set the start/end speed of the beginning and end to the smaller speed, and then obtain the actual maximum allowable feedrate of each segment; in the backward scanning process, the starting point of deceleration for a long segment is obtained.In the real-time interpolation stage, it is mainly to obtain the feedrate and calculate the precise coordinates of the next interpolation point. The s-shape based feedrate scheduling is adopted to achieve smooth feedrate profile which can greatly improve the accuracy of interpolation.


## 2.1. NURBS Parameter Discretization

NURBS curves can be represented by parameters as follows:(1)Cu=∑i=0nNi,puωipi∑i=0nNi,puωi,u1≤u≤un+p+1.where i is the index i = 0, 1, …, n; Pi is the set of control points; ωi is the set of weights; and Ni,pu is the set of p-order B-spline basic functions defined on the non-uniform knot vector U, U=u0,u1,…,un+p+1. The B-spline basic function Ni,pu is calculated as(2)Ni,pu=u−uiui+p−uiNi,p−1u+ui+p+1−uui+p+1−ui+1Ni+1,p−1u,Ni,0u=1,ui<u<ui+1,0,otherwise,The first-order and second-order derivatives ofB-spline basic functions and NURBS curves are, respectively, given as(3)Ni,p′u=pui+p−uiNi,p−1u−pui+p+1−ui+1Ni+1,p−1u.The first derivative and second derivative of cu can be calculated as(4)C′u=∑i=0nNi,p′uωipi−cu⋅∑i=0nNi,p′ωi∑i=0nNi,pωi,C″u=∑i=0nNi,p″uωipi−2c′u⋅∑i=0nNi,p′ωi−cu⋅∑i=0nNi,p″ωi∑i=0nNi,pωi,For a pointcu on the NURBS curve, the curvature radius ρu can be calculated by(5)ρu=C′u3C′u×C″u,where ⋅ stands for the Euclidean norm and × means the exterior product.In this paper, the Adams-Bashforth-Moulton method (ABM) is adopted to discretize the parameter vector for NURBS interpolation. The ABM method is as follows:(6)um+1=um+T2455fk−59fk−1+37fk−2−9fk−3,fk=dudtt=tm=vumC′um=vumdCxum/dum2+dCyum/dum2+dCzum/dum2,where vum, T, and C′um are the velocity, the interpolation period, and the first derivatives of the NURBS curve; Cxum, Cyum, and Czum denote the parameter curve; um corresponds to each axis component of the interpolation point Cum on the curve.The NURBS interpolation process is continuously affected by geometric errors, motion errors, drive errors, and contour errors. Aiming at the above problems, in the preprocessing stage, under the premise of considering multiple constraints, a real-time NURBS interpolation under multiple constraints (RNIC) is proposed, which can accurately obtain the constrained interpolation feedrate and optimal interpolation points.


## 2.2. Architecture of RNIC NURBS Interpolation

A systematic NURBS interpolator with smoothing feedrate at the FSA under multiple constraints is developed to enhance the interpolator performance with respect to the machining precision and machining quality. The overall structure of the interpolator is shown in Figure1. The interpolator has two stages, namely, the preprocessing stage and the real-time interpolation stage. The former preprocessing stage aims to find the FSA quickly, while the latter real-time interpolation implements velocity smoothing and generation of interpolated toolpath points.Figure 1
The structure of the FSA NURBS interpolator.The interpolator comprehensively considers various constraints, breaking through the geometric constraints, kinematic feature constraints, and machine performance constraints of NURBS interpolation, including various constraints such as chord error, velocity, normal acceleration and jerk, contour error, and command feedrate. There are two modules in the preprocessing stage, namely, the FSA scan module and the segment feedrate adjustment module, which are used to obtain the geometric features required by the NURBS curve as the input for the next step of real-time interpolation.The goal of the FSA scan module is to efficiently obtain FSAs of the NURBS curve by introducing the first FSA scan algorithm, then find the critical point in each FSA in the second FSA scan algorithm and divide the FSA curve blocks into subsegments, and further get more detailed information about the geometric features of subsegments. The goal of the segment feedrate adjustment module is to optimize the feedrate profile for segments data generated by the former FSA scan module, which includes short segments processing, long segments backward scanning, and long segments forward scanning. During short segments processing, update the feedrate of the start/end point at the beginning and end of the segment to the same smaller speed, and then keep the entire short segment interpolation speed constant; during long segments processing, use backward and forward directions. In the forward scanning process, in order to simplify the processing flow, first set the start/end speed of the beginning and end to the smaller speed, and then obtain the actual maximum allowable feedrate of each segment; in the backward scanning process, the starting point of deceleration for a long segment is obtained.In the real-time interpolation stage, it is mainly to obtain the feedrate and calculate the precise coordinates of the next interpolation point. The s-shape based feedrate scheduling is adopted to achieve smooth feedrate profile which can greatly improve the accuracy of interpolation.


## 3. Scheduling of the FSA under Multiple Constraints

This paragraph describes the scheduling method of FSA. First, determine the allowable feedrate on the NURBS curve under the constraints of geometric characteristics, dynamic characteristics, etc., and give its corresponding mathematical function formula. Then, the FSAs are detected quickly with a two-stage scanning method, which employs FSA scan and feedrate adjustment modules. The goal of the FSA scan module is to quickly find the FSA, including the maximum allowable feedrate calculation, the first scanning stage, the second scanning stage, and the FSA partition. The goal of the FSA feedrate adjustment is to optimize the start/end feedrate of the acceleration/deceleration phase, which includes intersection processing, backward scanning, and forward scanning.


### 3.1. Allowable Feedrate under Multiple Constraints

#### 3.1.1. Allowable Feedrate for Chord Error Constraint

Considering the chordCui,Cui+1¯ is a tiny segment in Figure 2, the arc approximation method can be used to calculate the chord error. In Figure 2, Pui is a point on the circle, Cui is a point on the curve, Pui and Cui are the coincident interpolation points, and the parameter vectors are both ui. Pui+1, Cui+1 are the next estimated interpolation points, and their parameter vectors are both ui+1.Figure 2
The chord error representation.ConsideringLi=Cui,Cui+1¯, we can get Pui+1−Pui=Li, the approximated feedrate vui=Li/T, and the formula for calculating chord error δ is(7)δ=ρui−ρui2−vuiT22.ρui is the curvature radius of the interpolated point Cui, and vui is the velocity during the sampling time T. The allowable feedrate vc1ρui of the interpolated point Cui for the set maximum chord error δmax is(8)vc1ρui=22ρuiδmax−δmax2T.


#### 3.1.2. Allowable Feedrate for the Normal Acceleration and Normal Jerk Constraints

Acceleration is the rate at which the speed and direction of an object are changing; it can be broken into its tangent and normal components. Here we first consider the normal acceleration; it can be expressed as(9)an=v2ρ.Therefore, the allowable feedratevc2ρui by the normal acceleration constraint is given as(10)vc2ρui=ρuian,max,where an,max is the maximum normal acceleration.The normal jerk is calculated as(11)Δan=an+−an−=2ansinΔφ2=2v2ρsinΔφ2,Δt=ρΔφv,jn=limΔt⟶0ΔanΔt=limΔφ⟶02v2/ρsinΔφ/2ρΔφ/v=v3ρ2.Hence, the allowable feedratevc3ρui for the normal jerk constrained can be derived as(12)vc3ρui=ρui2jn,max3.where jn,max is the maximum normal jerk.


#### 3.1.3. Allowable Feedrate for the Contour Error Constraint

The contour error directly affects the machining effect of the workpiece. For this reason, we include the contour error constraint in the preprocessor process to effectively limit the contour error from the source. Accurate estimation of contour errors has a significant impact on the quality of contour control. The contour error should satisfy the following formula:(13)ε<εlim,where εlim is the given contour error.The servo-lag induced contour error in real machining is considered as an additional constraint accompanied by the geometric and drive constraints during feedrate scheduling, so that the contour error can be bounded from the source. According to the literature [8], the feedrate constraint formula under the limitation of contour error is introduced as follows:(14)vc4ρui=2ρuiεmaxT,Thus, the constrained interpolation feedratevconsu can be obtained as(15)vconui=minvc1ρui,vc2ρui,vc3ρui,vc4ρui,VF.vconui is the allowable feedrate under multiple constraints. It can be seen that the constrained feedrate is only related to the curvature of the point. However, due to the continuous influence of curve curvature fluctuation, NURBS interpolation will still be affected by the tolerance of tangential acceleration and jerk in the large curvature part. Then, a novel curve subsegmentation method was proposed during the preprocessing stage using a two-stage FSA scan method to obtain sufficient geometric characteristics of the curve. Compared with the existing methods, this method not only considers the optimal speed under various constraints, but also uses the preprocessing process to obtain enough curve geometric characteristic information without adding additional hardware.


### 3.2. The Preprocessing Stage

#### 3.2.1. Curve Splitting at Breakpoints

During acceleration and deceleration on real-time interpolation of NURBS curves, the remaining curve distance needs to be calculated. The adaptive Simpson method can be used to calculate the length of the subsegment of the curve [8, 27]. But if there are breakpoints that appear to be discontinuous, C1 continuity is not satisfied which is a necessary condition for adaptive Simpson method. Therefore, the key is to find the breakpoints on the curve and segment the curve with the breakpoint as the boundary.There are roughly two types of breakpoints [3]. The first type is the points of C0 continuity. The second type is the points with C1 continuity when there are multiple corresponding control points.Then, the NURBS curve can be segmented into blocks according to these two kinds of breakpoints, and the bufferusblocki,ueblocki represented as the parameter interval of i-th block.


#### 3.2.2. The Two-Stage FSA Scan

Although NURBS curves are roughly divided into blocks according to breakpoints, the interpolation of each block will continue to be affected by the change of curve curvature. In order to realize smoothness interpolation, ACC/DEC feedrate profile needs to be adopted in the interpolation. The more geometrical characteristic obtained, the better the acceleration and deceleration effect.This paper creatively proposes a two-stage feedrate sensitive area (FSA) scanning method that can efficiently obtain sufficient geometrical characteristic without adding extra burden to real-time interpolation module. FSA represents a special area of the curve, which reflects the area where the allowable feedrate on the curve is less than the commanded feedrate.The first stage of an FSA scanning method is to obtain the FSAs of the curve, and the second stage is to get more detailed information of FSAs, such as the parameter of the start/end point, critical point, and the corresponding constrained feedrate of the FSAs.In the first stage scanning, the input data is the curve block parameter intervalusblock,ueblock which is the output of Ssection 3.1. Firstly, the parameter interval is discretized into a set of elements ui by step size Δu. Then, the constrained feedrate vconui of each point Cui is calculated according to (15). If vconui<vF, then the point Cui belongs to the feedrate sensitive area (FSA); otherwise, it belongs to the feedrate insensitive area (FIA).Therefore, the points of the curve block can be classified to FSA and FIA datasets through the first stage scanning. If the FSA set is not empty, it indicates that there are some feedrate sensitive areas in the curve block, and the constrained feedrates of the points in FSA are lower than the command feedrate. If the FIA set is not empty, it indicates that there are some feedrate insensitive areas in the curve block, and the constrained feedrates of the points in the FIA can reach the command valuevF.The step sizeΔu is important in the first stage scanning; the larger the step size is, the fewer the points are. If the step size is very large, some FSAs will be lost, and if the step size is too small, the processing time will be increased. In actual processing, the step size shall be flexibly selected according to experience and curve characteristics.After that, the second scanning stage is performed; the input data is the FSA and FIA datasets of the first stage scanning. In this stage, the curve blocks are further divided into subsegment, and it is necessary to obtain the geometrical characteristics information, such as the start/end point of the FSA.Suppose there are four pointsCua,Cub,Cui,Cuj on a curve block, where the parameters ua,ub∈FGAm , and ui,uj∈FIAm, Cua and Cub are the adjacent points. If ua<ui<uj<ub, there must exist a feedrate sensitive area in the parameter interval ua,ub. So the second stage scanning is carried out for the detailed information of the FSA.In the second stage scanning, the parameter intervalua,ub is discretized into a set of elements uii=1…n by step size Δu′, and the corresponding curve is divided into n points. The constrained velocity of each point Cui is calculated according to equation (6). If vconui−1==vF and vconui<vF, it means that the velocity of the previous point Cui−1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF, and the current point Cui is considered to be the start point of the FSA; if vconui<vF and vconui+1==vF, it means that the velocity of the next point Cui+1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF; the current point Cui is considered to be the end point of the FSA; if the velocity of point Cui is the point with the lowest velocity of all points in the parameter interval ua,ub, then point Cui is considered to be the critical point of the FSA which has the lowest velocity and minimum radius of curvature.So far, the detailed geometrical feature information of the FSA is obtained, such as the start/end point of the FSA. So the quaternion tupleus,uc,vc,ue corresponding to a FSA is got with the parameter us of the start point, the parameter uc of the critical point and its constrained feedrate vc, and the parameter ue of the end point. To obtain accurate parameter of the critical point, a smaller step size Δu′ in the second stage scanning is required, which should be much smaller than the step size Δu in the first stage scanning.The critical point has minimum radius of curvature and lowest feedrate in an FSA. Therefore, the critical point can be regarded as the start/end point of the acceleration/deceleration process in ACC/DEC feedrate profile. Between the two adjacent critical points, there is only one acceleration process and one deceleration according to the characteristics of NURBS curve. Hence, the curve block can be divided into several subsegments by critical points. This will greatly simplify feedrate planning for the feedrate profile of each subsegment has only one acceleration and one deceleration process.After the seconde stage scanning, The NURBS curve block can be partitioned into subsegments by critical points with the datasetsussegi,vsi,liseg,uesegi,vei , where ussegi , uesegi are the parameters of the start point and end point, with the corresponding feedrate vs and ve, and liseg is the arc length for the parameter interval ussegi,uesegi, which can be calculated by the adaptive simpson method [8, 27]. The flow chart of the two-stage scanning method is shown in Figure 3.Figure 3
The flow chart of the two-stage FSA scan.


### 3.3. A Bidirectional Scanning Approach for the Subsegments

The curve is divided into subsegments according to the critical point following the above method. If the arc length is not long enough, the feedrate cannot reach the command feedrate before deceleration. In addition, when the arc length is too short, even if the feedrate keeps accelerating or decelerating, it cannot reach the end velocity before reaching the endpoint of the subsegment. To deal with the short curve segments, there are seventeen types of feedrate profiles in [25], leading to the complex and time consume processing. In another paper, the authors proposed a new method that the scheduled feedrate keeps constant at most areas [8]; this method greatly simplifies the processing process, but the machining efficiency is also greatly reduced.For datasetussegi,vsi,liseg,uesegi,vei of the i-th subsegment, the requirement ACC/DEC displacements can be deduced as follows:(16)Sacc/decreqvsi,vei=Saccreqvsi,vF+SdecreqVmax,vei+nTvF,where Sacc/decreqvsi,vei is the requirement ACC/DEC displacements, Saccreqvsi,Vmax is the acceleration displacements, SdecreqVmax,vei is the deceleration displacements, and vF is the command feedrate. There will exits a constant feedrate profile between acceleration and deceleration when n > 0 for. The minimum required ACC/DEC displacement is obtained if n = 0 as follows:(17)Sacc/decminvsi,vei=Saccreqvsi,vF+SdecreqvF,vei.And if(18)liseg<Sacc/decminvsi,vei,it means that the arc length liseg is shorter than minimum required ACC/DEC displacement, and the feedrate profile of the segment cannot achieve the command federate vF during the ACC/DEC procedure. If the arc length liseg is longer than minimum required ACC/DEC displacement, the feedrate profile can accelerating from vsi to vF and decelerating from vF to vei. In this case, the start point of the deceleration should be decided precisely for the real-time interpolation.Therefore, we propose a bidirectional scanning method to further process the subsegment curve which consists of two stages: (1) forward scanning; (2) backward scanning.The forward scanning is to reduce the types of feedrate profiles and improve time efficiency for short subsegment. First, the feedrate of the start/end point of the subsegment is set to be the same value, so that all subsegment can be regarded as the superposition of acceleration and mirror deceleration processes. Without loss of generality, the acceleration distance from the start point to the end point is exactly half of the arc length of the subsegment; that is, the acceleration from the start point to the end point just reaches the actual maximum feedrate. This not only takes into account the efficiency, but all short subsegments can use the same method to simplify the processing method. After forward scanning, each subsegment updates feedrate of the start/end point and gets the maximum allowable feedrateVmax that can actually be achieved and obtains the output dataset ussegi,vsi,liseg,Vmax,uesegi,vei.The backward scanning is to obtain the deceleration start point of each subsegment. For the long subsegment, the deceleration feedrate profile is decelerating from the command velocity to the velocity of the end point, while the short subsegment is decelerating from the actual maximum velocity to the velocity of the end point. The deceleration velocity profile is just the opposite of the acceleration velocity profile. The deceleration process can be regarded as the inverse process of acceleration, so as to get the start point of the deceleration. Through the backward scanning, the deceleration starting point can be found and gets the output datasetussegi,vsi,liseg,Vmax,udec,uesegi,vei, where udec is the parameter of the start point for the deceleration process.The bidirectional scanning algorithm is mainly to adapt to the changing curvature characteristics of the NURBS curve. It uses the forward scanning to handle the feedrate at the start and end of the curve segment, as well as the actual maximum feedrate. It uses the backward scanning to get the deceleration starting point. However, the limitation of the bidirectional scanning algorithm is that if the velocities of the start and end points are different, the velocities at the convergence point of forward and backward interpolation need to be calculated, and the acceleration needs to be readjusted to make the velocity transition smoothly. In this paper, the feedrate of the start and end point of the subsegment is set to be the same value, so that all subsegments can be regarded as the superposition of acceleration and mirror deceleration processes.The pseudocode representation of the forward scanning and backward algorithm are shown in Tables1 and 2, and the specific steps are as follows.(A)
Forward scanning:Step 1. Let i = 0, i is the counter;Step 2. Get the arc lengthliseg, the starting feedrate vsi, and the ending feedrate vei of the i-th subsegment;Step 3. Calculate the minimum required ACC/DEC displacementSsegminvsi,vei of the i-th subsegment accelerating from vsi to vF (command feedrate) and decelerating from vF to vei under an S-shape ACC/DEC feedrate profile described in reference 26 with acceleration and jerk of A and J;Step 4. Ifliseg<Ssegminvsi,vei, go to Step 5; otherwise, set Vmax=vF, go to Step 7.Step 5. Updatevsi and vei by equation vsi=vei=minvsi,vei. If the velocity at the starting/ending point of the previous subsegment is updated, the velocity at the starting/ending point of the adjacent subsegment should be updated to a lower velocity by an iterative method.Step 6. Recalculate the new maximum achievable feedrateVmax−iact to satisfy Svsi,Vmax−iact=liseg/2 that accelerated from vsi to Vmax−iact and the displacement is half of the subsegment arc length, set Vmax=Vmax−iact.Step 7. If i< N, N represents the number of subsegments, set i = i+1; then go to Step 2; otherwise, end the program.(B)
Backward scanning:Step 1. Set i = N; N represents the number of subsegments.Step 2. Get the arc lengthliseg, maximum feedrate Vmax, and the end feedrate vei of the i-th subsegment from the forward scanning output.Step 3. IfVmax==vF (command Feedrate), take the velocity of the ending point as the starting velocity, and vF as ending velocity. The deceleration start point udeci calculated reversely from uei is the deceleration start point under S-shape ACC/DEC method described in reference 26; if Vmax<vF, take the velocity of the ending point as starting velocity, and Vmax as ending velocity, lsegi/2 as the displacement. Calculate the deceleration start point udeci from uei reversely.Step 4. Ifi = 1, program ends; otherwise, set i = i−1, and go to Step 2.Table 1
Forward scanning algorithm.
Forward scanning algorithmInput:ussegi,vsi,liseg,uesegi,vei, a, J, NOutput:ussegi,vsi,liseg,Vmax,uesegi,vei.1: Initialize: Set i = 02: While i < N3:  CalculateSaccreqvsi,vF,SdecreqvF,vei,Sacc/decminvsi,vei.4:  Ifliseg≥Sacc/decminvsi,vei.5:   SetVmax=vF.6:  else7:vsi=vei=minvsi,vei.8:   CalculateVmax−iact to satisfy Svsi,Vmax−iact=liseg/2.9:   SetVmax=Vmax−iact.10:i ++Table 2
Backward scanning algorithm.
Backward scanning algorithmInput:ussegi,vsi,liseg,Vmax,uesegi,vei, NOutput:ussegi,vsi,Vmax,udec,uesegi,vei.1: Initialize: Seti = 02: Whilei < N3:  IfVmax==vF.4:   Obtainedudeci according to reference 265:  else ifVmax<vF.6:sdec=lsegi/2.7:   Obtainedudeci.8:i++After bidirectional scanning, the dataset of the final preinterpolation is obtained asussegi,vsi,Vmax,udec,uesegi,vei, where ussegi and uesegi are the parameters of the start/end point for the i-th subsegment, vsi and vei are the corresponding feedrate, Vmax is the maximum achieved feedrate, and udec is the parameter of the start point of deceleration. The flow chart of the bidirectional scanning approach is shown in Figure 4.Figure 4
The bidirectional scanning method.


## 3.1. Allowable Feedrate under Multiple Constraints

### 3.1.1. Allowable Feedrate for Chord Error Constraint

Considering the chordCui,Cui+1¯ is a tiny segment in Figure 2, the arc approximation method can be used to calculate the chord error. In Figure 2, Pui is a point on the circle, Cui is a point on the curve, Pui and Cui are the coincident interpolation points, and the parameter vectors are both ui. Pui+1, Cui+1 are the next estimated interpolation points, and their parameter vectors are both ui+1.Figure 2
The chord error representation.ConsideringLi=Cui,Cui+1¯, we can get Pui+1−Pui=Li, the approximated feedrate vui=Li/T, and the formula for calculating chord error δ is(7)δ=ρui−ρui2−vuiT22.ρui is the curvature radius of the interpolated point Cui, and vui is the velocity during the sampling time T. The allowable feedrate vc1ρui of the interpolated point Cui for the set maximum chord error δmax is(8)vc1ρui=22ρuiδmax−δmax2T.


### 3.1.2. Allowable Feedrate for the Normal Acceleration and Normal Jerk Constraints

Acceleration is the rate at which the speed and direction of an object are changing; it can be broken into its tangent and normal components. Here we first consider the normal acceleration; it can be expressed as(9)an=v2ρ.Therefore, the allowable feedratevc2ρui by the normal acceleration constraint is given as(10)vc2ρui=ρuian,max,where an,max is the maximum normal acceleration.The normal jerk is calculated as(11)Δan=an+−an−=2ansinΔφ2=2v2ρsinΔφ2,Δt=ρΔφv,jn=limΔt⟶0ΔanΔt=limΔφ⟶02v2/ρsinΔφ/2ρΔφ/v=v3ρ2.Hence, the allowable feedratevc3ρui for the normal jerk constrained can be derived as(12)vc3ρui=ρui2jn,max3.where jn,max is the maximum normal jerk.


### 3.1.3. Allowable Feedrate for the Contour Error Constraint

The contour error directly affects the machining effect of the workpiece. For this reason, we include the contour error constraint in the preprocessor process to effectively limit the contour error from the source. Accurate estimation of contour errors has a significant impact on the quality of contour control. The contour error should satisfy the following formula:(13)ε<εlim,where εlim is the given contour error.The servo-lag induced contour error in real machining is considered as an additional constraint accompanied by the geometric and drive constraints during feedrate scheduling, so that the contour error can be bounded from the source. According to the literature [8], the feedrate constraint formula under the limitation of contour error is introduced as follows:(14)vc4ρui=2ρuiεmaxT,Thus, the constrained interpolation feedratevconsu can be obtained as(15)vconui=minvc1ρui,vc2ρui,vc3ρui,vc4ρui,VF.vconui is the allowable feedrate under multiple constraints. It can be seen that the constrained feedrate is only related to the curvature of the point. However, due to the continuous influence of curve curvature fluctuation, NURBS interpolation will still be affected by the tolerance of tangential acceleration and jerk in the large curvature part. Then, a novel curve subsegmentation method was proposed during the preprocessing stage using a two-stage FSA scan method to obtain sufficient geometric characteristics of the curve. Compared with the existing methods, this method not only considers the optimal speed under various constraints, but also uses the preprocessing process to obtain enough curve geometric characteristic information without adding additional hardware.


## 3.1.1. Allowable Feedrate for Chord Error Constraint

Considering the chordCui,Cui+1¯ is a tiny segment in Figure 2, the arc approximation method can be used to calculate the chord error. In Figure 2, Pui is a point on the circle, Cui is a point on the curve, Pui and Cui are the coincident interpolation points, and the parameter vectors are both ui. Pui+1, Cui+1 are the next estimated interpolation points, and their parameter vectors are both ui+1.Figure 2
The chord error representation.ConsideringLi=Cui,Cui+1¯, we can get Pui+1−Pui=Li, the approximated feedrate vui=Li/T, and the formula for calculating chord error δ is(7)δ=ρui−ρui2−vuiT22.ρui is the curvature radius of the interpolated point Cui, and vui is the velocity during the sampling time T. The allowable feedrate vc1ρui of the interpolated point Cui for the set maximum chord error δmax is(8)vc1ρui=22ρuiδmax−δmax2T.


## 3.1.2. Allowable Feedrate for the Normal Acceleration and Normal Jerk Constraints

Acceleration is the rate at which the speed and direction of an object are changing; it can be broken into its tangent and normal components. Here we first consider the normal acceleration; it can be expressed as(9)an=v2ρ.Therefore, the allowable feedratevc2ρui by the normal acceleration constraint is given as(10)vc2ρui=ρuian,max,where an,max is the maximum normal acceleration.The normal jerk is calculated as(11)Δan=an+−an−=2ansinΔφ2=2v2ρsinΔφ2,Δt=ρΔφv,jn=limΔt⟶0ΔanΔt=limΔφ⟶02v2/ρsinΔφ/2ρΔφ/v=v3ρ2.Hence, the allowable feedratevc3ρui for the normal jerk constrained can be derived as(12)vc3ρui=ρui2jn,max3.where jn,max is the maximum normal jerk.


## 3.1.3. Allowable Feedrate for the Contour Error Constraint

The contour error directly affects the machining effect of the workpiece. For this reason, we include the contour error constraint in the preprocessor process to effectively limit the contour error from the source. Accurate estimation of contour errors has a significant impact on the quality of contour control. The contour error should satisfy the following formula:(13)ε<εlim,where εlim is the given contour error.The servo-lag induced contour error in real machining is considered as an additional constraint accompanied by the geometric and drive constraints during feedrate scheduling, so that the contour error can be bounded from the source. According to the literature [8], the feedrate constraint formula under the limitation of contour error is introduced as follows:(14)vc4ρui=2ρuiεmaxT,Thus, the constrained interpolation feedratevconsu can be obtained as(15)vconui=minvc1ρui,vc2ρui,vc3ρui,vc4ρui,VF.vconui is the allowable feedrate under multiple constraints. It can be seen that the constrained feedrate is only related to the curvature of the point. However, due to the continuous influence of curve curvature fluctuation, NURBS interpolation will still be affected by the tolerance of tangential acceleration and jerk in the large curvature part. Then, a novel curve subsegmentation method was proposed during the preprocessing stage using a two-stage FSA scan method to obtain sufficient geometric characteristics of the curve. Compared with the existing methods, this method not only considers the optimal speed under various constraints, but also uses the preprocessing process to obtain enough curve geometric characteristic information without adding additional hardware.


## 3.2. The Preprocessing Stage

### 3.2.1. Curve Splitting at Breakpoints

During acceleration and deceleration on real-time interpolation of NURBS curves, the remaining curve distance needs to be calculated. The adaptive Simpson method can be used to calculate the length of the subsegment of the curve [8, 27]. But if there are breakpoints that appear to be discontinuous, C1 continuity is not satisfied which is a necessary condition for adaptive Simpson method. Therefore, the key is to find the breakpoints on the curve and segment the curve with the breakpoint as the boundary.There are roughly two types of breakpoints [3]. The first type is the points of C0 continuity. The second type is the points with C1 continuity when there are multiple corresponding control points.Then, the NURBS curve can be segmented into blocks according to these two kinds of breakpoints, and the bufferusblocki,ueblocki represented as the parameter interval of i-th block.


### 3.2.2. The Two-Stage FSA Scan

Although NURBS curves are roughly divided into blocks according to breakpoints, the interpolation of each block will continue to be affected by the change of curve curvature. In order to realize smoothness interpolation, ACC/DEC feedrate profile needs to be adopted in the interpolation. The more geometrical characteristic obtained, the better the acceleration and deceleration effect.This paper creatively proposes a two-stage feedrate sensitive area (FSA) scanning method that can efficiently obtain sufficient geometrical characteristic without adding extra burden to real-time interpolation module. FSA represents a special area of the curve, which reflects the area where the allowable feedrate on the curve is less than the commanded feedrate.The first stage of an FSA scanning method is to obtain the FSAs of the curve, and the second stage is to get more detailed information of FSAs, such as the parameter of the start/end point, critical point, and the corresponding constrained feedrate of the FSAs.In the first stage scanning, the input data is the curve block parameter intervalusblock,ueblock which is the output of Ssection 3.1. Firstly, the parameter interval is discretized into a set of elements ui by step size Δu. Then, the constrained feedrate vconui of each point Cui is calculated according to (15). If vconui<vF, then the point Cui belongs to the feedrate sensitive area (FSA); otherwise, it belongs to the feedrate insensitive area (FIA).Therefore, the points of the curve block can be classified to FSA and FIA datasets through the first stage scanning. If the FSA set is not empty, it indicates that there are some feedrate sensitive areas in the curve block, and the constrained feedrates of the points in FSA are lower than the command feedrate. If the FIA set is not empty, it indicates that there are some feedrate insensitive areas in the curve block, and the constrained feedrates of the points in the FIA can reach the command valuevF.The step sizeΔu is important in the first stage scanning; the larger the step size is, the fewer the points are. If the step size is very large, some FSAs will be lost, and if the step size is too small, the processing time will be increased. In actual processing, the step size shall be flexibly selected according to experience and curve characteristics.After that, the second scanning stage is performed; the input data is the FSA and FIA datasets of the first stage scanning. In this stage, the curve blocks are further divided into subsegment, and it is necessary to obtain the geometrical characteristics information, such as the start/end point of the FSA.Suppose there are four pointsCua,Cub,Cui,Cuj on a curve block, where the parameters ua,ub∈FGAm , and ui,uj∈FIAm, Cua and Cub are the adjacent points. If ua<ui<uj<ub, there must exist a feedrate sensitive area in the parameter interval ua,ub. So the second stage scanning is carried out for the detailed information of the FSA.In the second stage scanning, the parameter intervalua,ub is discretized into a set of elements uii=1…n by step size Δu′, and the corresponding curve is divided into n points. The constrained velocity of each point Cui is calculated according to equation (6). If vconui−1==vF and vconui<vF, it means that the velocity of the previous point Cui−1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF, and the current point Cui is considered to be the start point of the FSA; if vconui<vF and vconui+1==vF, it means that the velocity of the next point Cui+1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF; the current point Cui is considered to be the end point of the FSA; if the velocity of point Cui is the point with the lowest velocity of all points in the parameter interval ua,ub, then point Cui is considered to be the critical point of the FSA which has the lowest velocity and minimum radius of curvature.So far, the detailed geometrical feature information of the FSA is obtained, such as the start/end point of the FSA. So the quaternion tupleus,uc,vc,ue corresponding to a FSA is got with the parameter us of the start point, the parameter uc of the critical point and its constrained feedrate vc, and the parameter ue of the end point. To obtain accurate parameter of the critical point, a smaller step size Δu′ in the second stage scanning is required, which should be much smaller than the step size Δu in the first stage scanning.The critical point has minimum radius of curvature and lowest feedrate in an FSA. Therefore, the critical point can be regarded as the start/end point of the acceleration/deceleration process in ACC/DEC feedrate profile. Between the two adjacent critical points, there is only one acceleration process and one deceleration according to the characteristics of NURBS curve. Hence, the curve block can be divided into several subsegments by critical points. This will greatly simplify feedrate planning for the feedrate profile of each subsegment has only one acceleration and one deceleration process.After the seconde stage scanning, The NURBS curve block can be partitioned into subsegments by critical points with the datasetsussegi,vsi,liseg,uesegi,vei , where ussegi , uesegi are the parameters of the start point and end point, with the corresponding feedrate vs and ve, and liseg is the arc length for the parameter interval ussegi,uesegi, which can be calculated by the adaptive simpson method [8, 27]. The flow chart of the two-stage scanning method is shown in Figure 3.Figure 3
The flow chart of the two-stage FSA scan.


## 3.2.1. Curve Splitting at Breakpoints

During acceleration and deceleration on real-time interpolation of NURBS curves, the remaining curve distance needs to be calculated. The adaptive Simpson method can be used to calculate the length of the subsegment of the curve [8, 27]. But if there are breakpoints that appear to be discontinuous, C1 continuity is not satisfied which is a necessary condition for adaptive Simpson method. Therefore, the key is to find the breakpoints on the curve and segment the curve with the breakpoint as the boundary.There are roughly two types of breakpoints [3]. The first type is the points of C0 continuity. The second type is the points with C1 continuity when there are multiple corresponding control points.Then, the NURBS curve can be segmented into blocks according to these two kinds of breakpoints, and the bufferusblocki,ueblocki represented as the parameter interval of i-th block.


## 3.2.2. The Two-Stage FSA Scan

Although NURBS curves are roughly divided into blocks according to breakpoints, the interpolation of each block will continue to be affected by the change of curve curvature. In order to realize smoothness interpolation, ACC/DEC feedrate profile needs to be adopted in the interpolation. The more geometrical characteristic obtained, the better the acceleration and deceleration effect.This paper creatively proposes a two-stage feedrate sensitive area (FSA) scanning method that can efficiently obtain sufficient geometrical characteristic without adding extra burden to real-time interpolation module. FSA represents a special area of the curve, which reflects the area where the allowable feedrate on the curve is less than the commanded feedrate.The first stage of an FSA scanning method is to obtain the FSAs of the curve, and the second stage is to get more detailed information of FSAs, such as the parameter of the start/end point, critical point, and the corresponding constrained feedrate of the FSAs.In the first stage scanning, the input data is the curve block parameter intervalusblock,ueblock which is the output of Ssection 3.1. Firstly, the parameter interval is discretized into a set of elements ui by step size Δu. Then, the constrained feedrate vconui of each point Cui is calculated according to (15). If vconui<vF, then the point Cui belongs to the feedrate sensitive area (FSA); otherwise, it belongs to the feedrate insensitive area (FIA).Therefore, the points of the curve block can be classified to FSA and FIA datasets through the first stage scanning. If the FSA set is not empty, it indicates that there are some feedrate sensitive areas in the curve block, and the constrained feedrates of the points in FSA are lower than the command feedrate. If the FIA set is not empty, it indicates that there are some feedrate insensitive areas in the curve block, and the constrained feedrates of the points in the FIA can reach the command valuevF.The step sizeΔu is important in the first stage scanning; the larger the step size is, the fewer the points are. If the step size is very large, some FSAs will be lost, and if the step size is too small, the processing time will be increased. In actual processing, the step size shall be flexibly selected according to experience and curve characteristics.After that, the second scanning stage is performed; the input data is the FSA and FIA datasets of the first stage scanning. In this stage, the curve blocks are further divided into subsegment, and it is necessary to obtain the geometrical characteristics information, such as the start/end point of the FSA.Suppose there are four pointsCua,Cub,Cui,Cuj on a curve block, where the parameters ua,ub∈FGAm , and ui,uj∈FIAm, Cua and Cub are the adjacent points. If ua<ui<uj<ub, there must exist a feedrate sensitive area in the parameter interval ua,ub. So the second stage scanning is carried out for the detailed information of the FSA.In the second stage scanning, the parameter intervalua,ub is discretized into a set of elements uii=1…n by step size Δu′, and the corresponding curve is divided into n points. The constrained velocity of each point Cui is calculated according to equation (6). If vconui−1==vF and vconui<vF, it means that the velocity of the previous point Cui−1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF, and the current point Cui is considered to be the start point of the FSA; if vconui<vF and vconui+1==vF, it means that the velocity of the next point Cui+1 is exactly equal to the command velocity vF and the velocity of the current point Cui is lower than the command velocity vF; the current point Cui is considered to be the end point of the FSA; if the velocity of point Cui is the point with the lowest velocity of all points in the parameter interval ua,ub, then point Cui is considered to be the critical point of the FSA which has the lowest velocity and minimum radius of curvature.So far, the detailed geometrical feature information of the FSA is obtained, such as the start/end point of the FSA. So the quaternion tupleus,uc,vc,ue corresponding to a FSA is got with the parameter us of the start point, the parameter uc of the critical point and its constrained feedrate vc, and the parameter ue of the end point. To obtain accurate parameter of the critical point, a smaller step size Δu′ in the second stage scanning is required, which should be much smaller than the step size Δu in the first stage scanning.The critical point has minimum radius of curvature and lowest feedrate in an FSA. Therefore, the critical point can be regarded as the start/end point of the acceleration/deceleration process in ACC/DEC feedrate profile. Between the two adjacent critical points, there is only one acceleration process and one deceleration according to the characteristics of NURBS curve. Hence, the curve block can be divided into several subsegments by critical points. This will greatly simplify feedrate planning for the feedrate profile of each subsegment has only one acceleration and one deceleration process.After the seconde stage scanning, The NURBS curve block can be partitioned into subsegments by critical points with the datasetsussegi,vsi,liseg,uesegi,vei , where ussegi , uesegi are the parameters of the start point and end point, with the corresponding feedrate vs and ve, and liseg is the arc length for the parameter interval ussegi,uesegi, which can be calculated by the adaptive simpson method [8, 27]. The flow chart of the two-stage scanning method is shown in Figure 3.Figure 3
The flow chart of the two-stage FSA scan.


## 3.3. A Bidirectional Scanning Approach for the Subsegments

The curve is divided into subsegments according to the critical point following the above method. If the arc length is not long enough, the feedrate cannot reach the command feedrate before deceleration. In addition, when the arc length is too short, even if the feedrate keeps accelerating or decelerating, it cannot reach the end velocity before reaching the endpoint of the subsegment. To deal with the short curve segments, there are seventeen types of feedrate profiles in [25], leading to the complex and time consume processing. In another paper, the authors proposed a new method that the scheduled feedrate keeps constant at most areas [8]; this method greatly simplifies the processing process, but the machining efficiency is also greatly reduced.For datasetussegi,vsi,liseg,uesegi,vei of the i-th subsegment, the requirement ACC/DEC displacements can be deduced as follows:(16)Sacc/decreqvsi,vei=Saccreqvsi,vF+SdecreqVmax,vei+nTvF,where Sacc/decreqvsi,vei is the requirement ACC/DEC displacements, Saccreqvsi,Vmax is the acceleration displacements, SdecreqVmax,vei is the deceleration displacements, and vF is the command feedrate. There will exits a constant feedrate profile between acceleration and deceleration when n > 0 for. The minimum required ACC/DEC displacement is obtained if n = 0 as follows:(17)Sacc/decminvsi,vei=Saccreqvsi,vF+SdecreqvF,vei.And if(18)liseg<Sacc/decminvsi,vei,it means that the arc length liseg is shorter than minimum required ACC/DEC displacement, and the feedrate profile of the segment cannot achieve the command federate vF during the ACC/DEC procedure. If the arc length liseg is longer than minimum required ACC/DEC displacement, the feedrate profile can accelerating from vsi to vF and decelerating from vF to vei. In this case, the start point of the deceleration should be decided precisely for the real-time interpolation.Therefore, we propose a bidirectional scanning method to further process the subsegment curve which consists of two stages: (1) forward scanning; (2) backward scanning.The forward scanning is to reduce the types of feedrate profiles and improve time efficiency for short subsegment. First, the feedrate of the start/end point of the subsegment is set to be the same value, so that all subsegment can be regarded as the superposition of acceleration and mirror deceleration processes. Without loss of generality, the acceleration distance from the start point to the end point is exactly half of the arc length of the subsegment; that is, the acceleration from the start point to the end point just reaches the actual maximum feedrate. This not only takes into account the efficiency, but all short subsegments can use the same method to simplify the processing method. After forward scanning, each subsegment updates feedrate of the start/end point and gets the maximum allowable feedrateVmax that can actually be achieved and obtains the output dataset ussegi,vsi,liseg,Vmax,uesegi,vei.The backward scanning is to obtain the deceleration start point of each subsegment. For the long subsegment, the deceleration feedrate profile is decelerating from the command velocity to the velocity of the end point, while the short subsegment is decelerating from the actual maximum velocity to the velocity of the end point. The deceleration velocity profile is just the opposite of the acceleration velocity profile. The deceleration process can be regarded as the inverse process of acceleration, so as to get the start point of the deceleration. Through the backward scanning, the deceleration starting point can be found and gets the output datasetussegi,vsi,liseg,Vmax,udec,uesegi,vei, where udec is the parameter of the start point for the deceleration process.The bidirectional scanning algorithm is mainly to adapt to the changing curvature characteristics of the NURBS curve. It uses the forward scanning to handle the feedrate at the start and end of the curve segment, as well as the actual maximum feedrate. It uses the backward scanning to get the deceleration starting point. However, the limitation of the bidirectional scanning algorithm is that if the velocities of the start and end points are different, the velocities at the convergence point of forward and backward interpolation need to be calculated, and the acceleration needs to be readjusted to make the velocity transition smoothly. In this paper, the feedrate of the start and end point of the subsegment is set to be the same value, so that all subsegments can be regarded as the superposition of acceleration and mirror deceleration processes.The pseudocode representation of the forward scanning and backward algorithm are shown in Tables1 and 2, and the specific steps are as follows.(A)
Forward scanning:Step 1. Let i = 0, i is the counter;Step 2. Get the arc lengthliseg, the starting feedrate vsi, and the ending feedrate vei of the i-th subsegment;Step 3. Calculate the minimum required ACC/DEC displacementSsegminvsi,vei of the i-th subsegment accelerating from vsi to vF (command feedrate) and decelerating from vF to vei under an S-shape ACC/DEC feedrate profile described in reference 26 with acceleration and jerk of A and J;Step 4. Ifliseg<Ssegminvsi,vei, go to Step 5; otherwise, set Vmax=vF, go to Step 7.Step 5. Updatevsi and vei by equation vsi=vei=minvsi,vei. If the velocity at the starting/ending point of the previous subsegment is updated, the velocity at the starting/ending point of the adjacent subsegment should be updated to a lower velocity by an iterative method.Step 6. Recalculate the new maximum achievable feedrateVmax−iact to satisfy Svsi,Vmax−iact=liseg/2 that accelerated from vsi to Vmax−iact and the displacement is half of the subsegment arc length, set Vmax=Vmax−iact.Step 7. If i< N, N represents the number of subsegments, set i = i+1; then go to Step 2; otherwise, end the program.(B)
Backward scanning:Step 1. Set i = N; N represents the number of subsegments.Step 2. Get the arc lengthliseg, maximum feedrate Vmax, and the end feedrate vei of the i-th subsegment from the forward scanning output.Step 3. IfVmax==vF (command Feedrate), take the velocity of the ending point as the starting velocity, and vF as ending velocity. The deceleration start point udeci calculated reversely from uei is the deceleration start point under S-shape ACC/DEC method described in reference 26; if Vmax<vF, take the velocity of the ending point as starting velocity, and Vmax as ending velocity, lsegi/2 as the displacement. Calculate the deceleration start point udeci from uei reversely.Step 4. Ifi = 1, program ends; otherwise, set i = i−1, and go to Step 2.Table 1
Forward scanning algorithm.
Forward scanning algorithmInput:ussegi,vsi,liseg,uesegi,vei, a, J, NOutput:ussegi,vsi,liseg,Vmax,uesegi,vei.1: Initialize: Set i = 02: While i < N3:  CalculateSaccreqvsi,vF,SdecreqvF,vei,Sacc/decminvsi,vei.4:  Ifliseg≥Sacc/decminvsi,vei.5:   SetVmax=vF.6:  else7:vsi=vei=minvsi,vei.8:   CalculateVmax−iact to satisfy Svsi,Vmax−iact=liseg/2.9:   SetVmax=Vmax−iact.10:i ++Table 2
Backward scanning algorithm.
Backward scanning algorithmInput:ussegi,vsi,liseg,Vmax,uesegi,vei, NOutput:ussegi,vsi,Vmax,udec,uesegi,vei.1: Initialize: Seti = 02: Whilei < N3:  IfVmax==vF.4:   Obtainedudeci according to reference 265:  else ifVmax<vF.6:sdec=lsegi/2.7:   Obtainedudeci.8:i++After bidirectional scanning, the dataset of the final preinterpolation is obtained asussegi,vsi,Vmax,udec,uesegi,vei, where ussegi and uesegi are the parameters of the start/end point for the i-th subsegment, vsi and vei are the corresponding feedrate, Vmax is the maximum achieved feedrate, and udec is the parameter of the start point of deceleration. The flow chart of the bidirectional scanning approach is shown in Figure 4.Figure 4
The bidirectional scanning method.


## 4. Simulation and Results

The proposed NURBS interpolator is simulated on an Intel Core i7-8565U 1.8 GHz laptop. The butterfly-shaped curve is used for the proposed method shown in Figure5. The proposed real-time NURBS interpolation under multiple constraints (RNIC) and adaptive feedrate interpolation (AFI) are adopted for comparison. The two methods are implemented for the butterfly-shaped curves, and the parameters are shown in Tables 3 and 4.Figure 5
The butterfly-shaped curve.Table 3
The parameters of the simulation.
ParametersSymbolUnitCommand feedratevmax0.2 mm/msNormal accelerationan0.001 mm/ms2Normal jerkjn0.0001 mm/ms3Tangential accelerationAt0.001 mm/ms2Tangential jerkJt0.0001 mm/ms3Max chord errorδmax0.001 mmMax contour errorɛmax0.05 mmTable 4
The parameters of the butterfly-shaped curve.
ParametersValuesControl points{54.493, 52.139}, {55.507, 52.139}, {56.082, 49.615},{56.780, 44.971}, {69.575, 51.358}, {77.786, 58.573},{90.526, 67.081}, {105.973, 63.801}, {100.400, 47.326},{94.567, 39.913}, {92.369, 30.485}, {83.440, 33.757},{91.892, 28.509}, {89.444, 20.393}, {83.218, 15.446},{87.621, 4.830}, {80.945, 9.267}, {79.834, 14.535},{76.074, 8.522}, {70.183, 12.550}, {64.171, 16.865},{59.993, 22.122}, {55.680, 36.359}, {56.925, 24.995},{59.765, 19.828}, {54.493, 14.940}, {49.220, 19.828},{52.060, 24.994}, {53.305, 36.359}, {48.992, 22.122},{44.814, 16.865}, {38.802, 12.551}, {32.911, 8.521},{29.152, 14.535}, {28.040, 9.267}, {21.364, 4.830},{25.768, 15.447}, {19.539, 20.391}, {17.097, 28.512},{25.537, 33.750}, {16.602, 30.496}, {14.199, 39.803},{8.668, 47.408}, {3.000, 63.794}, {18.465, 67.084},{31.197, 58.572}, {39.411, 51.358}, {52.204, 44.971},{52.904, 49.614}, {53.478, 52.139}, {54.493, 52.139}Weights{0, 0, 0, 0, 0.0083, 0.0150, 0.0361, 0.0855, 0.1293, 0.1509, 0.1931, 0.2273, 0.2435, 0.2561,0.2692, 0.2889, 0.3170, 0.3316, 0.3482, 0.3553, 0.3649, 0.3837, 0.4005, 0.4269, 0.4510, 0.4660, 0.4891, 0.5000,0.5109, 0.5340, 0.5489, 0.5731, 0.5994, 0.6163, 0.6351, 0.6447, 0.6518, 0.6683, 0.6830, 0.7111, 0.7307, .7439,0.7565, 0.7729, 0.8069, 0.8491, 0.8707, 0.9145, 0.9639, 0.9850, 0.9917, 1.0, 1.0, 1.0, 1.0};Knot vector{1.0, 1.0, 1.0, 1.2, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 2.0, 1.0, 1.0, 5.0, 3.0, 1.0, 1.1, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.1, 1.0, 3.0, 5.0, 1.0, 1.0, 2.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.2, 1.0, 1.0, 1.0};The curvature of the test curve is shown Figure6. The test curve has high curvature and low curvature regions. In the low curvature area, due to the constraint of curvature, the velocity will not be able to feed at the command velocity, which can be a good verification of our proposed method.Figure 6
The curvature of the butterfly-shaped curve.Both preprocessing and online interpolation routines are developed in C. Additionally, we use MATLAB software to quantitatively analyze the actual velocity, tangential acceleration, and tangential jerk, which can be expressed as follows:(19)vactual,i=Cui+1−CuiT,aactual,i=vi+1−viT,jactual,i=ai+1−aiT.Figure5 shows FSAs detected by the proposed scheme (RNIC) indicated by asterisk and hollow circle, where the asterisk marked points are the starting/ending point of a FSA, and the hollow circle marked points are the minimum velocity point of the FSAs, called the critical points. The NURBS curve block can be partitioned into subsegments by critical points. All information of segments for the test curve is listed in Table 5. There are 21 segments on the test curve, where U_start and U_end are the parameters of starting/ending point of segment, and V_start and V_end are the velocity of starting/ending point of the segment. Required arc length is the minimum length for the complete S curve acc/dec profile from U_start to U_end at the test curve. Acture arclength is the length of the curve from the U_start to U_end at the test curve. The complete S curve profile field shows that the curve segment can complete a complete acceleration and deceleration process when the value is 1, or cannot complete when the value is 0.Table 5
Segments information of the butterfly curve.
NumberU_startU_endV_startV_endRequired_arc lengthActure_arclengthComplete S curve profileSegment10.0010.01690.0604430.07103538.3077396.10257NOSegment20.01690.1515020.0710350.13642331.20874450.677979YESSegment30.1515020.2379030.1364230.12299226.42800333.198769YESSegment40.2379030.2563030.1229920.00945735.0540087.142123NOSegment50.2563030.27530.0094570.14200632.6297767.737445NOSegment60.27530.3067960.1420060.10441427.69815313.756968NOSegment70.3067960.3362920.1044140.03619536.5968788.730752NOSegment80.3362920.355290.0361950.0350141.088129.29499NOSegment90.355290.3681880.035010.11308635.7333794.824294NOSegment100.3681880.4497770.1130860.01461336.13747831.123468NOSegment110.4497770.4999710.0146130.09111938.2705518.485075NOSegment120.4999710.5501790.0911190.01462938.27039718.501719NOSegment130.5501790.6317920.0146290.11300636.14599631.115427NOSegment140.6317920.6446950.1130060.03502135.7417184.826924NOSegment150.6446950.6636980.0350210.03619641.0877659.303009NOSegment160.6636980.6931030.0361960.10446836.5914998.716472NOSegment170.6931030.7246080.1044680.14176627.72569313.74367NOSegment180.7246080.7436110.1417660.00951732.6623887.756817NOSegment190.7436110.7622140.0095170.12523734.7863857.203535NOSegment200.7622140.8484280.1252370.13590526.22852533.126568YESSegment210.8484280.9831510.1359050.07105731.27517550.711964YESSegment220.9831511.00.071057039.8307346.435459NOThe optimized velocity profile by two methods is shown in Figures7 and 8, and the corresponding tangential acceleration/tangential jerk profiles are presented in Figures 9–12. As depicted in Figures 7 and 8, the feedrate is under the command feedrate by two methods. However, as shown in Figure 7, the starting speed of the feedrate profile in AFI method is rising directly from 0 to the command feedrate, which will cause a large feedrate vibration and affects the processing quality. A similar situation exists at the ending point in Figure 7. In the AFI method, the feedrate can meet the contour error limit adapted by the chord error, but the tangential acceleration exceeds the given tolerance at most of the time as shown in Figure 9. The maximum tangential acceleration is 0.0076 mm/s2 by AFI method, as shown in Table 5, which is seven times more than the maximum allowable value. At the same time, the fluctuation of acceleration also causes the tangential jerk to exceed the maximum allowable value. The maximum tangential jerk is 0.0382 mm/s3 by AFI, as shown in Table 6, which is 380 times more than the maximum allowable value.Figure 7
The velocity profile of the butterfly-shaped NURBS curve by AFI.Figure 8
The velocity profile of the butterfly-shaped NURBS curve by RNIC.Figure 9
The ACC profile of butterfly-shaped NURBS curve by AFI.Figure 10
The ACC profile of butterfly-shaped NURBS curve by RNIC.Figure 11
Jerk profile of butterfly-shaped NURBS curve by AFI.Figure 12
Jerk profile of butterfly-shaped NURBS curve by RNIC.Table 6
The comparison of simulation results of the two methods.
MethodStart/end speedPercentage of scheduling max tan-acc to maximum tan-acc (%)Percentage of scheduling max tan-jerk to maximum tan-jerk (%)AFI2 mm/ms76038200RNIC (proposed)0 mm/ms100100Compared with the AFI method, As shown in Figure8, the initial speed of the feedrate profile in the proposed RNIC method starts at zero and then accelerates to the command speed. Correspondingly, at the end of the feedrate profile, the speed decelerates to zero. In the feedrate scheduling process, the feedrate is optimized under multiple constraints. Therefore, from Figures 10 and 12, the tangential acceleration and tangential jerk by the FSA method can met system requirements; all tangential kinematic constraints of the proposed method are satisfied perfectly as shown in Table 6. Thus, the smoothness of the speed of the interpolation process is ensured.The proposed RNIC method comprehensively considers the constraint of chord error, normal acceleration, normal jerk, and contour error in the preprocessing stage and directly introduces S-shaped ACC/DEC to the curve segments in the real-time interpolation. Compared with the AFI method, the proposed RNIC method adds a preprocessing module, which can realize the optimal feed under various constraints. It can be seen from the simulation results that the former has a greater improvement in speed smoothness than the latter. From the perspective of real-time processing, the former arranges non-real-time tasks to be completed in the preprocessing stage which can greatly reduce the working load of the real-time interpolation module, so that high-speed and high-precision machining with a smaller interpolation period can be achieved. In this sense, the real-time performance is significantly improved.


## 5. Conclusion

In this paper, a real-time NURBS interpolation is proposed under geometric errors, normal kinematic constraints, and drive constraints. The preprocessing process is used to solve the problem that the velocity in NURBS interpolation is difficult to deal with under the condition of multiple constraints. The comparison and simulation analysis of the proposed RNIC method and the AFI method show that the proposed method has greatly improved in terms of velocity smoothness, acceleration, and jerk continuity. The simulation results show that the proposed algorithm is effective and greatly improves the real-time performance of the NURBS interpolator.



---

*Source: 7492762-2022-05-17.xml*