Look-ahead interpolation of short line segments using B-spline curve fitting of dominant points

Abstract

In this study, a real-time look-ahead interpolation methodology with B-spline curve fitting technique using the selected dominant points is proposed. First, an improved scheme for selecting the dominant points is proposed to reduce the numbers of control points and iterations. Second, a point-to-curve distance function is defined, and its Taylor’s expansion is investigated for curve fitting. Finally, a real-time look-ahead interpolation function, which consists of spline fitting, feedrate scheduling and parametric interpolation modules, is developed to obtain smooth tool path and feedrate profile simultaneously. Experiments on an X-Y-Z platform are conducted with a three-dimensional tool path, and the results demonstrate the feasibility and efficiency of the present algorithms.

Keywords

B-spline fitting point-to-curve distance function dominant point look-ahead interpolation parametric interpolator

Introduction

Nowadays, short line segments, or G01 blocks, are still the most widely utilized representation form for the tool paths in the computer numerical control (CNC) machining. However, due to the tangency and curvature discontinuities, frequent feedrate fluctuation and acceleration variation may occur at the junctions of adjacent segments during the linear interpolation, which inevitably deteriorate the machining efficiency and quality. Many studies show that the parametric interpolation methods can realize high-feedrate and high-accuracy machining.^1–3 Thus, a solution for the aforementioned problem is to convert the short line segments to B-spline curves in a real-time manner and apply parametric interpolation method in the CNC system. In such case, there are two major concerns related to the curve fitting: (1) selection of the discrete points and (2) B-spline curve fitting to the selected points.

There are two approaches to convert the linear segments to parametric splines, that is, the interpolation method and the approximation method. For the interpolation method,^4–8 the resultant number of the control points equals that of the discrete points. If numerous line segments are involved, the storage requirement and computational load for the curve fitting process are considerably huge. Compared with the interpolation method, the approximation method can describe the fitted B-spline curve with fewer control points,^9–12 which means the curve information can be compressed significantly. Some commercial CNC systems already provide curve approximation functions, such as nano smoothing in FANUC 32i¹³ and COMPCAD in Siemens 840D.¹⁴ However, because the required number of the control points is unknown in advance, the aforementioned approximation methods should select some arbitrary points and then adopt an iterative process to adjust both the number and locations of the control points for the fitted curve. Thus, the number of the control points and iterations may be large, which requires considerable computational efforts. To solve this problem, the technology such as feature recognition can be adopted.^15,16 Recently, Park and Lee¹⁷ proposed a novel dominant point selection scheme, which chooses the feature points of the curve for B-spline curve fitting. With this method, better curve approximation can be achieved with far fewer control points. Park¹⁸ then expanded the idea of dominant points and proposed a B-spline surface fitting method according to the dominant columns along two directions. However, the existing dominant selection schemes merely consider the curvature factor. In their practical applications, numerous iterations are required to add new dominant points, which degrade the real-time performance.

Based on the selected discrete points, the approximation algorithm using the least-square (LS) optimization technique is usually adopted to generate the fitted B-spline curves. The aforementioned studies employed point distance minimization (PDM) method to approximate the discrete points, which minimizes the squared distance between the discrete point and the point on the fitted curve. Actually, the target of the approximation method is to pursue a B-spline curve and keep the distance between the line segments and the fitted spline curve within a specified tolerance. Obviously, the traditional PDM method may lead to unsatisfied approximation results. To solve this issue, Blake and Isard¹⁹ defined the distance from the discrete point to the tangential line at the corresponding point as the point-to-curve distance and proposed a tangent distance minimization (TDM) method. Wang et al.²⁰ proposed a curvature-based quadratic approximant of squared distance between the point and the fitted curve and employed the distance in the squared distance minimization (SDM) method. However, the existing TDM and SDM methods only apply to planar curves.

In this study, a new selection scheme for dominant points and a new SDM method based on the point-to-curve distance function are proposed, which can apply to spatial line segments and produce a fitted B-spline curve with fewer control points and higher convergence rate. The remainder of this article is organized as follows. In section “Cubic B-spline curve fitting,” a novel dominant point selection scheme is presented to reduce the number of control points and iterations. Also, a point-to-curve distance function is defined and its differential property is investigated, and then its Taylor’s expansion is used for SDM optimization. Moreover, the Hausdorff distance is adopted as a criterion for the approximation accuracy, and an accuracy control method is presented. In section “Real-time look-ahead interpolation with spline fitting,” a real-time look-ahead interpolation program, which consists of spline fitting, feedrate scheduling and parametric interpolation modules, is presented. Experiments are conducted in section “Experimental validations,” and the conclusions are given in section “Conclusion.”

Cubic B-spline curve fitting

Selection of dominant points

The proposed dominant point selection scheme takes three steps: selection of local curvature maximum (LCM) points and two end points, determination of the points where the bending direction of the curve changes and selection of the chordal points. The curvature provides useful information to characterize the shape of the curved path. Thus, it is natural to use the discrete curvature information to determine the dominant points^15,16 for the line segments, which can be estimated by the curve fitting methods.^21–23 In such case, the curvature may fluctuate because of the trajectory discretization and the curvature evaluation error, as shown in the dashed box in Figure 1, where $κ$ denotes the discrete curvature and $n$ the number of the discrete points. If the LCM points are chosen without filtering the noisy points,¹⁵ numerous dominant points will be selected in the dashed boxes.

Figure 1.

Dominant point selection based on the curvature information.

To solve this problem, an improved selection scheme for the LCM points is proposed. First, given a set of ordered discrete points $q_{i} = (x_{i}, y_{i}, z_{i}) \in ℝ^{3}$ , $i = 0, 1, \dots, n$ , as shown in Figure 2, the discrete curvatures at the junctions are evaluated as²⁰

| κ_{i} | = \frac{2 \sin α_{i}}{‖ q_{i + 1} - q_{i - 1} ‖}, i = 1, \dots, n - 1

(1)

where

α_{i} = arc \cos \frac{(x_{i + 1} - x_{i}) (x_{i} - x_{i - 1}) + (y_{i + 1} - y_{i}) (y_{i} - y_{i - 1}) + (z_{i + 1} - z_{i}) (z_{i} - z_{i - 1})}{‖ q_{i + 1} - q_{i} ‖ \cdot ‖ q_{i} - q_{i - 1} ‖}

(2)

Figure 2.

Discrete curvature for the short line segments.

Then, the two end points $q_{0}$ and $q_{n}$ are selected as dominant points. Different from Li et al.,¹⁵ point $q_{i}$ is chosen as the dominant point if the following two conditions are satisfied: $| κ_{i} | > | κ_{f} |$ and $| κ_{i} | > | κ_{l} |$ hold, where $κ_{f}$ and $κ_{l}$ are the local curvature minimum values before and behind point $q_{i}$ ; $| κ_{i} | - | κ_{f} | \geq δ_{f}$ or $| κ_{i} | - | κ_{l} | \geq δ_{f}$ , where $δ_{f}$ is the filtering parameter. As shown in Figure 3, the proposed scheme has capability of eliminating numerous dominant points at the regions with slight curvature changes, which benefits the fast convergence for the curve fitting.

Figure 3.

Proposed LCM point searching scheme: (a) curvature profile and (b) the details in the dashed box of the left sub-figure.

The sign of the discrete curvature changes as the bending direction of the curve changes. The corresponding points are denoted as curvature-passing-zero (CPZ) points. Obviously, point $q_{i}$ is determined as the CPZ point if $κ_{i - 1} κ_{i} > 0$ and $κ_{i} κ_{i + 1} < 0$ hold. The CPZ points are then stored into the buffer but not chosen as dominant points. In the following, the chordal points are selected between the adjacent points including the dominant points and CPZ points.

Although the LCM points can reflect the sharp regions of the linear curved path, these points fail to cover the total shape of the curve. Taking the dolphin curve as an example, as shown in Figure 4, no dominant points are selected within the dashed boxes because the curvatures vary slightly. Clearly, the chosen dominant points cannot reflect the curve shape in such regions. To guarantee the fitting process to converge, new dominant points need to be added iteratively. To decrease the iteration number, dominant points in such regions are also required. In the following, the chordal points, which are selected as another kind of dominant points, are searched according to the chord scanning.

Figure 4.

Reason for the selection of the chordal points.

As shown in Figure 5, $q_{i}$ to $q_{i + 4}$ are five adjacent points among all the discrete points, where $q_{i}$ and $q_{i + 4}$ are two adjacent points among the points obtained in the above two steps, which means $q_{i} / q_{i + 4}$ is the LCM point or the CPZ point. The chordal point selection scheme can be summarized in the following two steps.

Figure 5.

Selection scheme for chordal points: (a) chord scanning and (b) iterative subdivision.

Procedure 1

Selection of the chordal points:

Step I. Calculate the chordal deviation $d_{i + 1}$ to $d_{i + 3}$ from points $q_{i + 1}$ to $q_{i + 3}$ to the line $q_{i} q_{i + 4}$ , respectively, and compare the maximum distance with the fitting accuracy $δ$ . As shown in Figure 5(a), assuming $d_{i + 2}$ is maximal and $d_{i + 2} > δ$ holds, point $q_{i + 2}$ is then chosen as dominant point;

Step II. Calculate the curvature of point $q_{i + 2}$ , that is, $κ_{i + 2}$ . If $| κ_{i + 2} | > κ_{c}$ , where $κ_{c} (κ_{c} > 0)$ is a specified threshold to identify that the point lies in the sharp regions, perform Step I within points $q_{i}$ to $q_{i + 2}$ and $q_{i + 2}$ to $q_{i + 4}$ iteratively, as shown in Figure 5(b); otherwise, finish.

By employing the proposed scheme, the dominant points are also selected at the flat regions of the curve. In addition, the dominant points are thicker at the sharp regions, which can describe the curve more accurately in such regions.

Point-to-curve distance function and its application to spline fitting

Zhu et al.²⁴ defined a signed point-to-surface distance function and applied its second-order Taylor’s expansion to the approximation for the target surface. By expanding the idea, this study defines a point-to-curve distance function and investigates its differential properties as well. Taylor’s expansion of the distance function is then utilized in the B-spline curve approximation.

Definition 1 (point-to-curve distance function)

Given a regular smooth curve $r (w) \in ℝ^{3}$ , where $w$ denote the curve parameters, and a point $q \in ℝ^{3}$ , there exists at least one closest point $p \in r (w)$ , termed as foot point, such that

‖ q - p ‖ = min_{x \in r (w)} ‖ q - x ‖

where $‖ \cdot ‖$ stands for the Euclidean norm on $ℝ^{3}$ . The distance from point $q$ to curve $r (w)$ is defined as

d (q, w) = ‖ q - p ‖

(3)

As shown in Figure 6, $\vec{pq}$ lies in the normal plane at the point $p$ ; $C^{p}$ denotes the unit vector corresponding to the vector $\vec{pq}$ ; $N^{p}$ and $T^{p}$ are the principal unit normal vector and the unit tangential vector, respectively, and then equation (3) can be rewritten as

d (q, w) = (q - p) \cdot C^{p}

(4)

Figure 6.

Point-to-curve distance function.

and $C^{p}$ can be calculated by

\begin{matrix} T^{p} = r' (s_{p}), N^{p} = \frac{r " (s_{p})}{‖ r " (s_{p}) ‖}, B^{p} = T^{p} \times N^{p} \\ C^{p} = \frac{[(\vec{pq} \cdot N^{p}) \cdot N^{p} + (\vec{pq} \cdot B^{p}) \cdot B^{p}]}{‖ (\vec{pq} \cdot N^{p}) \cdot N^{p} + (\vec{pq} \cdot B^{p}) \cdot B^{p} ‖} \end{matrix}

(5)

where $B^{p}$ denotes the binormal vector of the normal plane, $s_{p}$ the arc-length at point $p$ and bold dot $\cdot$ the inner product operator.

For the point-to-curve distance function $d (q, w)$ , if $w$ is fixed, the simplified distance function $d (q)$ represents the orthogonal deviation from point $q$ to curve $r (w)$ . In such situation, the distance function can be utilized for contour error estimation in the contour-following application.²⁵ On the other hand, if point $q$ is fixed, another simplified distance function $d (w)$ is obtained. The shape parameter vector $w$ can be adjusted to approximate a sequence of discrete points. In such situation, the distance function can be applied for curve approximation. The major concern of this study is B-spline curve fitting; thus, the differential property of $d (w)$ is investigated in the following.

Proposition 1. Let $p = r (w)$ , and the first-order Taylor’s expansion of $d (w)$ is

\bar{d} (w + Δ w) = d (w) - {[C^{p} \cdot r_{w_{1}}, C^{p} \cdot r_{w_{2}}, \dots, C^{p} \cdot r_{w_{m}}]}^{T} Δ w + o^{2} (‖ Δ w ‖)

(6)

where $r_{w_{i}} (i = 1, \dots, m)$ are the derivatives at the curve parameters, respectively.

Proposition 2. For the regular smooth curve $r (w)$ , $d (w)$ is the second-order differentiable and the elements of its Hessian matrix can be expressed as

{[\nabla^{2} d (w)]}_{ij} = - C_{w_{j}}^{p} \cdot r_{w_{i}} - C^{p} \cdot r_{w_{i} w_{j}}

(7)

where $C_{w_{j}}^{p}$ are the derivatives of $C^{p}$ at the curve parameters.

The proofs of both propositions are given in Appendix 1. According to equations (6) and (7), the second-order Taylor’s expansion of $d (w)$ is

\begin{matrix} d (w + Δ w) = d (w) - {[C^{p} \cdot r_{w_{1}}, C^{p} \cdot r_{w_{2}}, \dots, C^{p} \cdot r_{w_{m}}]}^{T} Δ w \\ + Δ w^{T} [\nabla^{2} d (w)] Δ w / 2 + o^{3} (‖ Δ w ‖) \end{matrix}

(8)

For planar curves, equations (6) and (8) can be rewritten as

d (w + Δ w) = d (w) - {[N^{p} \cdot r_{w_{1}}, N^{p} \cdot r_{w_{2}}, \dots, N^{p} \cdot r_{w_{m}}]}^{T} Δ w + o^{2} (‖ Δ w ‖)

(9)

and

\begin{matrix} d (w + Δ w) = d (w) - {[N^{p} \cdot r_{w_{1}}, N^{p} \cdot r_{w_{2}}, \dots, N^{p} \cdot r_{w_{m}}]}^{T} Δ w \\ + Δ w^{T} [\nabla^{2} d (w)] Δ w / 2 + o^{3} (‖ Δ w ‖) \end{matrix}

(10)

Clearly, the value of $d (w)$ denotes the point-to-curve distance; thus, it can be used for B-spline approximation. Given a set of ordered discrete points $q_{i} \in ℝ^{3}$ ( $i = 0, 1, \dots, n$ ) and the control points $w$ for the fitted B-spline, the fitted problem can be expressed as the following LS minimization problem

min_{w \in ℝ^{3}} \sum_{i = 0}^{n} {[d_{q_{i}} (w)]}^{2}

(11)

where $d_{q_{i}} (w)$ denotes the distance from point $q_{i}$ to the fitted curve. Equation (11) is a nonlinear LS problem. To solve it, equation (6) can be utilized to linearize the term $d_{q_{i}} (w)$ , and then the Gauss–Newton method can be applied to solve it. The readily obtained linear LS problem can be expressed as

min_{w, Δ w \in ℝ^{3}} \sum_{i = 0}^{n} {d_{q_{i}} (w) - {[C^{p_{i}} \cdot r_{w_{1}}, C^{p_{i}} \cdot r_{w_{2}}, \dots, C^{p_{i}} \cdot r_{w_{m}}]}^{T} Δ w}^{2}

(12)

where $p_{i}$ is the foot point of $q_{i}$ , and $Δ w$ are treated as the increments for the control points.

Equation (12) is the proposed SDM method in this study. Furthermore, the distance between the given point set $q_{i}$ and the fitted curve, which is denoted as $d_{q_{i}} (w)$ in equation (12), can be evaluated by two methods: (1) search the foot point on the parametric curve iteratively²⁶ and evaluate the distance by definition and (2) estimate the distance using the contour error estimation method.²³

Note that if the discrete points are far away from the fitted curve, the proposed method inevitably introduces huge approximation error. Thus, a proper initial B-spline fitting curve is necessary. The traditional PDM technique can be utilized to obtain such an initial B-spline curve

min f = \frac{1}{2} \sum_{i = 1}^{n} ‖ q_{i} - {r (w) |}_{t = t_{q_{i}}} ‖^{2}

(13)

where ${r (w) |}_{t = t_{q_{i}}}$ denotes the corresponding point of point $q_{i}$ on the fitted curve. Its meaning can be explained as follows: perform parameterization and determine the parameter $t = t_{q_{i}}$ for the point $q_{i}$ , then substitute this parameter into the fitted curve $r (w)$ and yield the corresponding point ${r (w) |}_{t = t_{q_{i}}}$ . Two steps are involved in the proposed SDM method; the details of which are summarized as follows.

Procedure 2

The proposed SDM method:

Step I. Given a set of discrete points $q_{i} \in ℝ^{3}$ ( $i = 0, 1, \dots, n$ ) and the specified fitting accuracy tolerance $δ$ , the traditional PDM method is performed to obtain an initial B-spline curve $r (w^{k})$ (let the initial value of k be 0).

Compute the parameter values of all the discrete points by performing chord length parameterization²⁷

{\begin{matrix} {\bar{u}}_{0} = 0, {\bar{u}}_{n} = 1 \\ {\bar{u}}_{k} = {\bar{u}}_{k - 1} + \frac{\sqrt{‖ q_{k} - q_{k - 1} ‖}}{\sum_{i = 0}^{n - 1} \sqrt{‖ q_{i + 1} - q_{i} ‖}}, k = 1, \dots, n - 1 \end{matrix}

(14)

Select the initial dominant points according to the scheme introduced in section “Point-to-curve distance function and its application to spline fitting.”

Perform knot placement. The knots are determined by averaging the parameters of the dominant points, which can be expressed as²⁵

{\begin{matrix} u_{0} = \dots = u_{p} = 0, u_{m - p} = \dots = u_{m} = 1 \\ u_{j + p} = \frac{1}{p} \sum_{i = j}^{j + p - 1} {\bar{u}}_{i}, j = 1, \dots, n - p \end{matrix}

(15)

where ${\bar{u}}_{i}$ are the knot parameters of the dominant points.

The PDM method (equation (13)) is utilized to approximate the dominant points, and a fitted B-spline curve $r (w^{k})$ is obtained.

Step II. Update the initial B-spline curve to get the target fitted curve.

5. Check the deviation between the fitted curve $r (w^{k})$ and the linear tool path. If the maximal deviation $ξ_{k} > δ$ , then go to step 6; otherwise, finish.

6. Solve the following problem to determine the differential increment of the control points $Δ w$

min_{w, Δ w \in ℝ^{3}} \sum_{i = 0}^{n} {d_{q_{i}} (w^{k}) - [{C^{p_{i}} \cdot r_{w_{1}}, C^{p_{i}} \cdot r_{w_{2}}, \dots, C^{p_{i}} \cdot r_{w_{m}}]}^{T} Δ w}^{2}

(16)

7. Update the control points

w^{k + 1} = w^{k} + Δ w, k = k + 1

(17)

8. Check the deviation again, if $ξ_{k} > δ$ , then go to step 9; otherwise, finish.

9. If the fitting accuracy is not satisfied within some regions defined by two adjacent dominant points, choose the point with the maximum error as the new dominant point. Subsequently, perform knot placement according to the updated dominant points, and go to step 3.

The flowchart of the proposed SDM method is shown in Figure 7. The accuracy control method in the spline fitting process is presented in the following.

Figure 7.

Flowchart for B-spline curve fitting.

Accuracy control in spline fitting

The B-spline fitting method should keep the distance between the linear segments and the fitted B-spline curve within a specified tolerance. The Hausdorff distance is usually adopted as a criterion for the resultant approximation quality, which is defined as follows.

Definition 2 (Hausdorff distance)

Given two non-empty subsets A and B of a metric space, their Hausdorff distance is defined as H(A, B) = max(h(A, B), h(B, A)), where $h (A, B) = max_{a \in A} min_{b \in B} ‖ a - b ‖$ , $h (B, A) = max_{b \in B} min_{a \in A} ‖ b - a ‖$ .

Obviously, it is difficult to compute the Hausdorff distance directly. Thus, the verification process is simplified according to the following definition and proposition.

Definition 3 (Hausdorff envelope)

As shown in Figure 8(a), the Hausdorff envelope (HE) of the line segment $\bar{q_{i} q_{i + 1}}$ , denoted as $HE (\bar{q_{i} q_{i + 1}}, δ)$ , is the envelope body including two semi spheres and a cylinder, whose centerline is the line segment.

Figure 8.

Accuracy control for B-spline curve fitting: (a) Hausdorff envelope for line segment and (b) accuracy control for the fitted control.

Proposition 3. As shown in Figure 9, let the foot points of $q_{i}$ and $q_{i + 1}$ on the fitted curve $r (w)$ are $r (w^{q_{i}})$ and $r (w^{q_{i + 1}})$ , respectively, if the curve $\overset{⌢}{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ is included in $HE (\bar{q_{i} q_{i + 1}}, δ)$ , then the Hausdorff distance satisfies $H (r (w), \overset{⌢}{q_{1} q_{n}}) < δ$ . The proof of Proposition 3 is given in Appendix 2.

Figure 9.

Line segment and its Hausdorff envelope.

Actually, the control points mainly affect the shape of the fitted curve. Thus, to verify that the fitted curve $\overset{⌢}{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ is contained in $HE (\bar{q_{i} q_{i + 1}}, δ)$ , the chordal deviation and the distances from the two ending points to the curve are employed here for fitting accuracy verification. Note that it is difficult to estimate the chordal deviation, $‖ \vec{qt} ‖$ as shown in Figure 9 is utilized for approximation. The verification scheme for $‖ \vec{qt} ‖$ is described as follows: let points $s$ and $t$ be the center points of $\bar{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ and $\hat{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ , respectively, search point $q$ such that $sq ⊥ \bar{q_{i} q_{i + 1}}$ , and then $‖ \vec{qt} ‖ \leq ‖ st ‖ + ‖ sq ‖ < δ$ if $‖ st ‖ + ‖ sq ‖ < δ$ . The Hausdorff distance verification for the line segment $\bar{q_{i} q_{i + 1}}$ is presented as follows.

Procedure 3

Hausdorff distance verification:

Step I. Calculate the foot points $r (w^{q_{i}})$ and $r (w^{q_{i + 1}})$ for $q_{i}$ and $q_{i + 1}$ , respectively, which can be evaluated by solving the following equations

[q_{i} - r (w^{q_{i}})] \cdot r' (w^{q_{i}}) = 0, [q_{i + 1} - r (w^{q_{i + 1}})] \cdot r' (w^{q_{i + 1}}) = 0

(18)

Step II. Check if $‖ q_{i} r (w^{q_{i}}) ‖ < δ$ and $‖ q_{i + 1} r (w^{q_{i + 1}}) ‖ < δ$ hold, if not, finish, which means the fitting accuracy is not satisfied; otherwise, go to Step III.

Step III. Evaluate the center points of $\bar{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ and $\overset{⌢}{r (w^{q_{i}}) r (w^{q_{i + 1}})}$ , which are denoted as points $s$ and $t$ . Search point $q$ that $sq ⊥ \bar{q_{i} q_{i + 1}}$ holds, and check if $‖ \vec{qt} ‖ \leq ‖ st ‖ + ‖ sq ‖ < δ$ holds, if not, finish; otherwise, the current B-spline curve is included in the HE, which means the fitting accuracy is satisfied.

Real-time look-ahead interpolation with spline fitting

In this section, an interpolator with real-time look-ahead interpolation function is proposed, which consists of three modules: spline fitting, feedrate scheduling and parametric interpolation modules. Figure 10 illustrates the flowchart of the look-ahead interpolation and motion control. Considering the CPU’s capability, the look-ahead period is set to be 4 ms to guarantee that the spline fitting and feedrate scheduling can be finished within one sampling interval.

Figure 10.

Flowchart of the look-ahead interpolator and motion controller based on B-spline approximation.

Spline fitting module

Note that the most time-consuming part of the approximation task is to solve the linear optimization problem, which is expressed in equation (16). If too many dominant points are involved within one look-ahead period, the considerable computational load of the fitting process may exceed the processor’s capability. To guarantee the real-time performance of the look-ahead interpolation, a floating window is employed to determine the number of the line segments handled in one look-ahead period. At the beginning of every look-ahead timer interrupt response routine, N dominant points are detected and then the involved line segments are applied for curve fitting.

In every floating window, a B-spline curve is generated. To avoid variation at the junctions of two adjacent fitted B-spline curves, the condition of C ⁰ continuity is added into the fitting algorithm. Thus, by utilizing the PDM method to yield the initial B-spline, equation (13) is rewritten as

\begin{matrix} min \sum_{i = j}^{k} ‖ q_{i} - {r (w) |}_{u = u_{q_{i}}} ‖^{2} \\ s . t . {r (w) |}_{u = 0} = q_{j} \\ {r (w) |}_{u = 1} = q_{k} \end{matrix}

(19)

where $q_{j}, q_{j + 1}, \dots q_{k}$ are the dominant points; ${r (w) |}_{u = 0}$ and ${r (w) |}_{u = 1}$ are the start and end points for the fitted curve, respectively.

Then, using the proposed SDM method to update the B-spline, equation (16) is rewritten as

\begin{matrix} min_{w, Δ w \in ℝ^{3}} \sum_{i = 0}^{n} {d_{q_{i}} (w^{k}) - {[C^{p_{i}} \cdot r_{w_{1}}, C^{p_{i}} \cdot r_{w_{2}}, \dots, C^{p_{i}} \cdot r_{w_{m}}]}^{T} Δ w}^{2} \\ s . t . {r (w) |}_{u = 0} = q_{j} \\ {r (w) |}_{u = 1} = q_{k} \end{matrix}

(20)

In one look-ahead period, the geometric information of the B-spline curve in the next period is unknown in advance. Thus, in this study, only C ⁰ continuity rather than the higher-order continuity is employed.

Feedrate scheduling and parametric interpolation modules

Four steps are involved in the feedrate scheduling and parametric interpolation modules, the details of which are summarized as follows.

Procedure 4

Feedrate scheduling and parametric interpolation:

Step I: curve scanning. In the first step, the fitted curve is scanned to obtain the initial feedrate limitation profile. During the curve scanning process, pre-interpolation is performed, and the feedrate constraint at each scanning step is determined by

V (u_{k}) = min {\frac{2}{T_{s}} \sqrt{\frac{2 δ_{c}}{κ (u_{k})} - δ_{c}^{2}}, \sqrt{\frac{A_{max}}{κ (u_{k})}}, \sqrt[3]{\frac{J_{max}}{κ {(u_{k})}^{2}}}, F}

(21)

where $T_{s}$ denotes the interpolation period, $κ (u_{k})$ the curvature in the current step, $δ_{c}$ the confined chord error, $A_{\max} / J_{max}$ the maximal tangential acceleration/jerk and F the minimum value of the feedrate command and the feedrate that are restricted by axes’ capabilities.

Then, the second-order Taylor’s expansion with respect to the time can be employed to approximate the curve parameter

u_{k + 1} = u_{k} + \frac{V (u_{k}) T_{s} + (T_{s}^{2} / 2) A (u_{k})}{‖ C' (u_{k}) ‖} - \frac{{(V (u_{k}) T_{s})}^{2} C' (u_{k}) \cdot C " (u_{k})}{2 ‖ C' (u_{k}) ‖^{4}}

(22)

where

A (u_{k}) = \frac{V (u_{k + 1}) - V (u_{k})}{T_{s}}

(23)

The feedrate minimum points, whose curvatures satisfy the following expression, are treated as the junctions of acceleration and deceleration blocks

κ (u_{k}) > min {κ_{cbc}, \frac{A_{\max}}{F^{2}}, \sqrt{\frac{J_{\max}}{F^{3}}}}

(24)

where $κ_{cbc}$ denotes the curvature threshold to avoid feedrate fluctuation.²⁸ Then, the length of each block is calculated by applying adaptive Simpson’s method.

Note that the feedrate limitations within a look-ahead window can be evaluated by equation (21), but those at the junctions of adjacent fitted B-spline curves cannot use this concept because the curvature is not continuous. To solve this problem, the tangential lines of the two B-spline curves are used to approximate the splines, as shown in Figure 11. The feedrate limitation is determined by

V = min {\frac{A_{max} T_{s}}{2 \sin (θ / 2)}, F}

(25)

Figure 11.

Connection of two fitting curves in two look-ahead floating windows.

Step II: Bidirectional acceleration. In the second step, bidirectional acceleration is implemented within the floating look-ahead window. The aim is to correct the feedrate constraints at the junctions of the acceleration and deceleration blocks. Considering the constraints of tangential acceleration and jerk, S-shape acceleration is performed in both the forward and backward directions, and the feedrate limitations are corrected. Readers can refer to Zhao et al.²⁹ for detailed description about the bidirectional acceleration.

Step III: Acceleration/deceleration (ACC/DEC) planning. With respect to the obtained feedrate limitation profile, a jerk limited S-shape feedrate profile is planned to avoid shock or vibration at the sharp corners or positions without continuous curvature. Readers can refer to Lin et al.² for more detailed descriptions about the feedrate scheduling.

Step IV: Parametric interpolation. Finally, with the feedrate profile obtained from the look-ahead function, the interpolator performs parametric interpolation to generate the reference position commands and sends them to the motion controller for position feedback control. The traditional Taylor’s expansion is adopted as the interpolation method, as shown in equation (22).

Experimental validations

To demonstrate the proposed B-spline curve fitting method, experiments are conducted on a triaxial platform, as illustrated in Figure 12. The experimental system contains three main parts: a PC, which is employed to perform the look-ahead interpolation; a custom motion control card, which is equipped with a fixed-point TMS320F2812 DSP to perform closed-loop position control and an X-Y-Z table, which is driven by three YASKAWA SGDV series servo drivers and SGMJV motors. The built-in incremental encoder for each motor is used for position feedbacks. The resolution of the encoder is 10,000 pulses/rev. The lead of the ball screws for the X-Y-Z table is 10 mm/rev.

Figure 12.

Layout of the experimental platform.

A three-dimensional (3D) pigeon-shaped linear tool path with 1270 line segments, which is generated by UGNX, is applied to validate the proposed dominant selection scheme and SDM method. The maximal acceleration $A_{\max}$ and jerk $J_{\max}$ are set to be 3000 mm/s² and 60000 mm/s³, respectively. The approximation error tolerance $δ$ , the filtering parameter $δ_{f}$ and the curvature threshold $κ_{c}$ are set to be 0.05 mm, 0.0005 mm⁻¹ and 0.1 mm⁻¹, respectively. The periods of the interpolation and the control loop are fixed to 0.5 and 0.1 ms, respectively.

Three steps are involved in the experiments. First, two dominant point selection schemes, including the proposed method and Park’s method, are performed for the linear tool path. Figure 13(a)–(d) illustrates the distribution of dominant points on the original line segments and curvature profiles, respectively. From Figure 13(a), it can be found that the dominant points determined by the proposed method are adaptively selected more at the complicated regions but fewer at the flat regions. In addition, the proposed method can characterize both the sharp and flat shapes simultaneously. On the contrary, without filtering the discrete curvatures, numerous dominant points are selected at the regions where the points have almost the similar curvatures using Park’s method, as shown in Figure 13(b) and (d).

Figure 13.

Distribution of the dominant points on the curved path and curvature profile using the two methods: (a) result of the proposed method, (b) result of Park’s method, (c) result of the proposed method and (d) result of Park’s method.

Second, the proposed SDM method is applied on the basis of the selected dominant points with above two methods. In this study, the dominant point number specified in one look-ahead window is 30. Figure 14 illustrates the fitting results using the proposed dominant point selection scheme and the proposed SDM method.

Figure 14.

Fitting result using the proposed dominant point selection scheme and SDM fitting method: (a) layout of the control points and (b) fitting result.

Table 1 summarizes the detailed numerical results of three different B-spline curve fitting methods: Park’s dominant point selection scheme with the proposed SDM method, commercial software tool UGNX and the proposed dominant point selection scheme with the proposed SDM method. It can be seen that compared with Park’s method, the proposed one can reduce the control points by 25.82% with only two iterations. Compared with UG, the proposed method can reduce the control points by 19.39% using cubic B-spline, which can achieve C ² continuity. In addition, compared with the original linear tool path, the fitted curve can describe the profile with 158 control points, which indicates that the curve information is compressed significantly.

Table 1.

Comparison of the fitting results using three methods.

Approximation method	B-spline order	Dominant point number	Iteration number
Park	4	213	4
UG	3	196	N/A
Proposed	4	158	2

N/A: the iteration number for the commercial software UG is unavailable.

Then, the proposed dominant selection scheme and the PDM method are applied for B-spline curve fitting. The resultant numbers of control points and iteration are 182 and 3, respectively. From Table 1, it can be seen that the proposed SDM method can reduce control points by 13.19% and iteration by 1 time compared with the PDM method. Thus, the proposed SDM method can not only reduce the control points effectively but also increase the convergence rate.

Third, curve scanning, bidirectional acceleration and ACC/DEC planning are performed with respect to the fitted B-spline curves. Figure 15 shows the generated feedrate scheduling profiles for the original tool path and the fitted curve. Compared with the original linear curved path, it can be found that the fitted curve significantly increases the machining efficiency. The elapsed time for the interpolation with two methods is 19.17 and 7.48 s, respectively. This means the parametric interpolation improves the productivity by 60.98% as compared with the original linear interpolation method.

Figure 15.

(a) Feedrate limitation and (b) scheduled profiles for the original linear tool path and the fitted tool path.

Conclusion

In this article, a real-time look-ahead interpolation with B-spline curve approximation technique for short line segments is proposed. Compared with the traditional approximation methods, the proposed method has the following advantages: (1) an adaptive dominant point selection scheme is proposed, which can reduce the number of the control points and the iteration for the fitting procedure and (2) a point-to-curve distance function is defined and utilized for SDM, which can be utilized in 3D approximation with higher convergence rate.

Experiments are conducted on an X-Y-Z table. The results demonstrate the effectiveness of the proposed method in CNC machining of 3D short line segments.

It is worth mentioning that only C ⁰ continuity is achieved at the junctions of two adjacent fitted curves, and the curve fitting method cannot be directly applied to generate dual B-spline curves for five-axis machine tools. Our future works will focus on improving the continuity and investigating the dominant point–based dual B-spline curve fitting method.

Footnotes

Appendix 1

Appendix 2 Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This work was partially supported by the National Natural Science Foundation of China under grant No. 51325502, the National Key Basic Research Program under grant No. 2011CB706804 and the Science & Technology Commission of Shanghai Municipality under grant No. 13JC1408400.

References

Lei

Wang

. Robust real-time NURBS path interpolators. Int J Mach Tool Manu 2009; 49: 625–633.

Lin

Tsai

Yau

. Development of a dynamics-based NURBS interpolator with real-time look-ahead algorithm. Int J Mach Tool Manu 2007; 47: 2246–2262.

Sun

Wang

Guo

. Guide curve based interpolation scheme of parametric curves for precision CNC machining. Int J Mach Tool Manu 2006; 46: 235–242.

Yau

Wang

. Fast Bezier interpolator with real-time lookahead function for high-accuracy machining. Int J Adv Manuf Tech 2007; 47: 1518–1529.

Liu

Yamazaki

. The design of a NURBS pre-interpolator for five-axis machining. Int J Adv Manuf Tech 2008; 36: 927–935.

Tsai

Nien

Yau

. Development of a real-time look-ahead interpolation methodology with spline-fitting technique for high-speed machining. Int J Adv Manuf Tech 2010; 47: 621–638.

Wang

Yau

. Real-time NURBS interpolator: application to short linear segments. Int J Adv Manuf Tech 2009; 41: 1169–1185.

Zhang

Yan

Yuan

. Curve fitting and optimal interpolation on CNC machines based on quadratic B-splines. Sci China Inform Sci 2011; 54: 1407–1418.

Yau

Kuo

. NURBS machining and feed rate adjustment for high-speed cutting of complex sculptured surfaces. Int J Prod Res 2001; 39: 21–41.

10.

Langeron

Duc

Lartigue

. A new format for 5-axis tool path computation, using Bspline curves. Comput Aided Design 2004; 36: 1219–1229

11.

Lin

Ueng

Lai

. CNC codes conversion from linear and circular paths to NURBS curves. Int J Adv Manuf Tech 2008; 39: 760–773.

12.

Yeh

. Implementation of online NURBS curve fitting process on CNC machines. Int J Adv Manuf Tech 2009; 40: 531–540

13.

FANUC. 5-axis machining features FANUC series 30i-model a/31i-model A5. Japan: FANUC Ltd, 2006.

14.

Siemens. Milling with SINUMERIK: 5-axis machining manual. Germany: Siemens Ltd, 2009.

15.

Ding

Mou

. Feature recognition technology for aircraft structural parts based on holistic attribute adjacency graph. Proc IMechE, Part B: J Engineering Manufacture 2010; 224: 271–278.

16.

Wang

. Feedback method from inspection to process plan based on feature mapping for aircraft structural parts. Robot Cim: Int Manuf 2012; 28: 294–302.

17.

Park

Lee

. B-spline curve fitting based on adaptive curve refinement using dominant points. Comput Aided Design 2007; 39: 439–451.

18.

Park

. B-spline surface fitting based on adaptive knot placement using dominant columns. Comput Aided Design 2011; 43: 258–264.

19.

Blake

Isard

. Active contours. Berlin: Springer Verlag, 1998.

20.

Wang

Pottmann

Liu

. Fitting B-spline curves to point clouds by curvature-based squared distance minimization. ACM T Graphic 2006; 25: 214–238.

21.

Hamann

Chen

. Data point selection for piecewise linear curve approximation. Comput Aided Geom D 1994; 11: 289–301.

22.

Liu

Wong

Zhang

. Adaptive fairing of digitized data with discrete curvature. Comput Aided Design 2002; 34: 309–320.

23.

Park

Kim

Lee

. A method for approximate NURBS curve compatibility based on multiple curve refitting. Comput Aided Design 2000; 32: 237–252.

24.

Zhu

Zhang

Ding

. Geometry of signed point-to-surface distance function and its application to surface approximation. J Comput Inf Sci Eng 2010; 10: 041003.

25.

Zhu

Zhao

Ding

. Real-time contouring error estimation using second-order approximation. Int J Mach Tool Manu 2013; 68: 75–80.

26.

Zhou

Sherbrooke

Patrikalakis

. Computation of stationary points of distance functions. Eng Comput 1993; 9: 231–246.

27.

Piegl

Tiller

. The NURBS book. Berlin: Springer Verlag, 1997.

28.

Chen

Feng

. Performance evaluation of a real-time interpolation algorithm for NURBS curves. Int J Adv Manuf Tech 2002; 20: 270–276.

29.

Zhao

Zhu

Ding

. A real-time look-ahead interpolation methodology with curvature-continuous B-spline transition scheme for CNC machining of short line segments. Int J Mach Tool Manu 2013; 65: 88–98.