Calculation of Space NURBS Curve Interpolation Error

Liangji Chen, Fei Gao, Bo Zhao, Longfei Ma

School of Mechanical Engineering, Tiangong University, Tianjin, China.

DOI: 10.4236/jcc.2020.86001                

Abstract

Aiming at the problem of low accuracy of interpolation error calculation of existing NURBS curves, an approximate method for the distance between a point and a NURBS interpolation curve is proposed while satisfying the accuracy of the solution. Firstly, the minimum parameter interval of the node vector corresponding to the data point under test in the original data point sequence is determined, and the parameter interval is subdivided according to the corresponding step size, and the corresponding parameter value is obtained. Secondly, the distance from the measured point to the NURBS curve is calculated, and the nearest distance is found out. The node interval is subdivided again on one side of the nearest distance. Finally, the distance between the data point to be measured and each subdivision point is calculated again, and the minimum distance is taken as the interpolation error between the point and the NURBS curve. The simulation results of actual tool position data show that this method can more accurately obtain the error of spatial NURBS interpolation curve.

Keywords

Computer-Aided Design, NURBS Interpolation Curve, Interpolation Error, Approximation Solution

1. Introduction

NURBS curve and surface interpolation technology has a broad application prospect in Computer-Aided Design, and has become the most popular mathematical expression as early as the 1980s [1] [2] [3]. In the design and production process in the field of numerical control machining, it is necessary to seek the optimal NURBS curve and surface expression from a large number of original cutter point data [4]. Gofuku et al. [5] proposed a technique to interpolate B-spline curves through geometric algorithm, which has a compact representation and does not need to be given the size of the tangent vector and the normal vector. Yoshimoto et al. [6] proposed a genetic algorithm based on real number coding, which can achieve a better fitting effect when dealing with smooth data. Park et al. [7] proposed a B-spline curve approximation method based on error adaptive control, which can obtain the minimum control point curve satisfying the preset fitting accuracy without the given number of control points.

The interpolation error is an important basis for measuring the distance between the spatial uninvolved interpolation data points and the NURBS interpolation curves. The above scholars have given corresponding interpolation error calculation models for the interpolation error calculation problem, and the quality of the error calculation model directly affects the number of iterations of the NURBS interpolation curve and the number of interpolation data points, and finally affects the efficiency in the actual processing process. In addition to the above scholars, Hu et al. [8] proposed a method to calculate the minimum distance between a point and a curve by using the projection method. This method has a fast convergence rate, but strict requirements on the selection of initial values in the iterative process. Stakhov [9] proposed a golden section method to calculate the minimum distance from the point to the curve. The method has a slow convergence speed and uncertain direction. Shopova et al. [10] and Vallex et al. [11] proposed genetic algorithm and particle swarm optimization algorithm respectively. These methods can obtain the global optimal solution, but the algorithm is complex and the calculation takes a long time. Theoretically, the interpolation error value is the radius of the circular arc tangent to the NURBS curve at the data point to be measured. The radius value is taken as the theoretical interpolation error value. Due to the complexity of the calculation of this method, most scholars have not adopted this method for calculation. Currently, the most extensive deviation calculation method is to carry out parametric calculation on all data points to be tested, calculate the corresponding points of each parameter value on the NURBS curve, and take the distance between the data points and the corresponding points on the NURBS curve as the actual interpolation error value [12]. In view of the above calculation method, it is easy to produce the problem of low accuracy and poor reliability, which will greatly increase the number of iterations and the selection of interpolation data points.

Based on the above analysis, this article will elaborate on the following four parts. In the first part, the method steps of interpolating the global curve of a given data point are introduced in detail. In the second part, this paper proposes a new method for calculating spatial NURBS curve interpolation error, and explains the calculation process of this method in detail. In the third part, the error calculation method is compared with the existing method to show the superiority of accuracy in error calculation. The fourth part summarizes the whole paper and explains the application value of the NURBS curve error calculation method.

2. NURBS Curve Interpolation

2.1. A Basic Definition of a NURBS Curve

A p-degree NURBS curve is defined as [13]

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

In Equation (1), $\left\{P_i\right\}$ is the control point of NURBS curve. The number of control points is n + 1, and the lines of all control points $\left\{P_i\right\}$ constitute the control polygon of NURBS curve. $\left\{{\omega }_i\right\}$ is the weight factor value of the corresponding control point $\left\{P_i\right\}$ ; $N_{i,p}\left(u\right)$ is the pth B-spline basis function.

The B-spline basis function is defined in the node vector

$U=\left(u_0,u_1,\cdots ,u_m\right)$

(where: $m=n+p+\text{1}$, and the number of nodes is m + 1). B-spline basis function can be obtained by de Boor-Cox recurrence formula

$\{\begin{array}{l}{N}_{i,0}\left(u\right)=\{\begin{array}{l}1,\text{if}{u}_i\le u\le u_{i+1}\\ 0,\text{else}\end{array}\\ N_{i,p}\left(u\right)=\frac{u-u_i}{u_{i+p}-u_i}{N}_{i,p-1}\left(u\right)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}{N}_{i+1,p-1}\left(u\right)\\ \begin{array}{cc}\text{let}& \frac{\text{0}}{\text{0}}=\text{0}\end{array}\end{array}$. (2)

2.2. Calculation of NURBS Curve

For the data point set of NURBS curve interpolation, the following interpolation calculation method can be used to calculate the NURBS curve interpolation.

2.2.1. Parametric Calculation of Feature Points

First, we need to parameterize the set of data points participating in the interpolation. In this paper, the most commonly used string length parameterization method is used to parameterize the feature data points.

For data point set $\left\{Q_j\right\}\left(j=0,1,2,\cdots ,n\right)$, let the total chord length be D, then there will be

$D={\displaystyle \underset{j=1}{\overset{n}{\sum }}\left|Q_j-Q_{j-1}\right|}$ (3)

Then, the parameters corresponding to each data point $\left\{Q_j\right\}\left(j=0,1,2,\cdots ,n\right)$ can be represented as

$\begin{array}{l}{\bar{u}}_0=0\\ {\bar{u}}_j={\bar{u}}_{j-1}+\frac{\left|Q_j-Q_{j-1}\right|}{D},j=1,2,\cdots ,n-1\\ {\bar{u}}_n=1\end{array}$. (4)

2.2.2. Node Vector Calculation

Let the node vector be $U=\left(u_0,u_1,\cdots ,u_m\right)$. In order to make the node vector reflect the distribution of ${\bar{u}}_j$ well, this paper adopts the method of taking the average value, namely

$\begin{array}{l}{u}_0=\cdots =u_p=0\\ u_{i+p}=\frac{1}{p}{\displaystyle \underset{j=i}{\overset{i+p-1}{\sum }}{\bar{u}}_j}\left(i=1,2,\cdots ,n-p\right)\\ u_{m-p}=\cdots =u_m=1\end{array}$ (5)

where U is equal to $\left(\underset{p+1}{\underset{︸}{0,\cdots ,0}},u_{p+1},\cdots ,u_{m-p-1},\underset{p+1}{\underset{︸}{1,\cdots ,1}}\right)$.

2.2.3. The Calculation of Control Points

In order to simplify the calculation, all the weight factor values ${\omega }_i$ are set as 1 in this paper, and ${\displaystyle {\sum }_{i=0}^n{N}_{i,p}\left(u\right)=1}$ can be known from the normalization of the NURBS curve. At this point, Equation (1) can be simplified to

$C\left(u\right)={\displaystyle \underset{i=0}{\overset{n}{\sum }}{N}_{i,p}\left(u\right)P_i}$ (6)

Establish the following system of linear Equations for the control point $P_i$

$\begin{array}{cc}{Q}_j=C\left({\bar{u}}_j\right)={\displaystyle \underset{i=0}{\overset{n}{\sum }}{N}_{i,p}\left({\bar{u}}_j\right)P_i}& \left(j=0,1,\cdots ,n\right)\end{array}$ (7)

In Equation (7), ${\displaystyle {\sum }_{i=0}^n{N}_{i,p}\left({\bar{u}}_j\right)}$ is the matrix of $\left(n+1\right)\times \left(n+1\right)$ coefficients. The parameter ${\bar{u}}_j$ and the node vector $U$ can be obtained by using Equations (3)-(5). The B-spline basis function can be obtained by using Equation (2), and the following linear equations can be obtained by substituting into Equation (7)

$\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ N_{0,3}\left({\bar{u}}_1\right)& N_{1,3}\left({\bar{u}}_1\right)& N_{2,3}\left({\bar{u}}_1\right)& \cdots & N_{n,3}\left({\bar{u}}_1\right)\\ N_{0,3}\left({\bar{u}}_2\right)& N_{1,3}\left({\bar{u}}_2\right)& N_{2,3}\left({\bar{u}}_2\right)& \cdots & N_{n,3}\left({\bar{u}}_2\right)\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right]\cdot \left[\begin{array}{c}{P}_0\\ P_1\\ P_2\\ ⋮\\ P_n\end{array}\right]=\left[\begin{array}{c}{Q}_0\\ Q_1\\ Q_2\\ ⋮\\ Q_n\end{array}\right]$ (8)

After solving the control point set $\left\{P_i\right\}\left(i=0,1,2,\cdots ,n\right)$ in Equation (8), A NURBS interpolation curve about the feature data point $\left\{Q_j\right\}\left(j=0,1,2,\cdots ,n\right)$ participating in the interpolation can be uniquely determined.

3. Interpolation Error Calculation of NURBS Curve

An initial NURBS interpolation curve is constructed according to the calculation method of the NURBS interpolation curve calculated in Section 2. However, for data point set $\left\{Q_s\right\}\left(s=0,1,\cdots ,t-n-1\right)$ in the original data point set $\left\{Q_i\right\}\left(i=0,1,\cdots ,t\right)$ that does not belong to interpolation data point set $\left\{Q_j\right\}\left(j=0,1,\cdots ,n\right)$ and does not participate in NURBS curve interpolation, interpolation error ${\epsilon }_s$ at all data points $Q_s$ should be calculated to verify whether the constraint condition that ${\epsilon }_s$ is not greater than the preset interpolation error $\epsilon$ is satisfied. In order to calculate the interpolation error ${\epsilon }_s$ at each data point $Q_s$, an approximate solution method for the distance from the following point to the NURBS interpolation curve is proposed in this paper.

The first step is to determine the minimum parameter node interval $\left(u_a,u_b\right)$ of the node vector corresponding to the data point $Q_s$ in the original data point sequence, as shown in Figure 1.

The parameter node interval $\left(u_a,u_b\right)$ is divided by step h for R (where R is the number of data points not involved in interpolation between two adjacent characteristic data points), and $u_r=u_a+rh$ $\left(r=0,1,2,\cdots ,R\right)$ is taken, where the calculation formula of step h is

$h=\frac{u_b-u_a}{R}$ (9)

Calculate the distance between $Q_s$ and $C\left(u_r\right)$, ${\epsilon }_r$, take the minimum value in ${\epsilon }_r$ as ${\epsilon }_c$, and the point on the curve corresponding to ${\epsilon }_c$ as $C\left(u_c\right)$, as shown in Figure 2(a). The calculation formulas of ${\epsilon }_r$ and ${\epsilon }_c$ are respectively

${\epsilon }_r=\left|Q_s-C\left(u_r\right)\right|\text{,}{u}_a\le u_r\le u_b$ (10)

${\epsilon }_c=\underset{0\le r\le R}{\min }\left|Q_s-C\left(u_r\right)\right|$ (11)

Take parameter $u_c$ as the center, and take parameter $u_{c-}$ and $u_{c+}$ on each side (where $u_{c-}=u_c-h$, $u_{c+}=u_c+h$ ). Calculate the distance $L_{c-}$ and $L_{c+}$ from data points $Q_s$ to two points $C\left(u_{c-}\right)$ and $C\left(u_{c+}\right)$ respectively, and take the smaller value of the two as $L_{\min }$.

Figure 1. The node interval corresponding to the point.

(a) (b)

Figure 2. The node interval corresponding to the point. (a) Calculate the shortest distance from the first point to the curve projection; (b) Calculate the shortest distance from the second point to the curve projection.

On the side where $L_{\min }$ is obtained (may as well be set as $C\left(u_{c+}\right)$ ), W parameter nodes are taken to form the parameter interval of $\left(u_c,u_{c+W}\right)$ (The satisfactory accuracy can be obtained if W is 3). The data point $Q_s$ is projected to the NURBS curve segment from $C\left(u_c\right)$ to $C\left(u_{c+3}\right)$, and the projection point is set as $C\left(u_w\right)$ ( $w=0,\text{1},\text{2,}\cdots$ ), calculate the distance ${\epsilon }_w$ between $Q_s$ and $C\left(u_w\right)$, take the minimum value in ${\epsilon }_w$ as ${\epsilon }_s$, and the point on the curve corresponding to ${\epsilon }_s$ as $C\left(u_d\right)$, as shown in Figure 2(b).

In the parameter node interval $\left(u_c,u_{c+W}\right)$, $R^{\prime }$ ( $R^{\prime }=10W$ ) is divided by step $h^{\prime }$, and $u_w=u_c+wh$ $\left(w=0,1,2,\cdots ,R^{\prime }\right)$ is taken, where the calculation formula of step $h^{\prime }$ is

$h^{\prime }=\frac{u_{c+W}-u_c}{R^{\prime }}$ (12)

The calculation formulas of the distance between data point $Q_s$ and $C\left(u_w\right)$, ${\epsilon }_w$ and ${\epsilon }_s$ can be respectively calculated as

${\epsilon }_w=\left|Q_s-C\left(u_w\right)\right|\text{,}{u}_c\le u_w\le u_{c+W}$ (13)

${\epsilon }_s=\underset{0\le w\le R^{\prime }}{\min }\left|Q_s-C\left(u_w\right)\right|$ (14)

Now, the specific algorithm steps of the approximate solution method for interpolation error can be summarized as follows:

l Search the minimum parameter node interval $\left(u_a,u_b\right)$ in the node vector corresponding to the data point $Q_s$ in the original data point sequence, divide the parameter interval by the step length h calculated by Equation (9) into R equal parts, and obtain the value of each parameter at the equal point respectively.

l The distance ${\epsilon }_r$ between $Q_s$ and various points on the curve corresponding to parameter $u_r$ is calculated by using Equation (10), and the minimum distance ${\epsilon }_c$ is obtained by combining Equation (11). Meanwhile, the point $C\left(u_c\right)$ and parameter $u_c$ on the curve corresponding to ${\epsilon }_c$ are determined.

l Taking parameter $u_c$ as the center, one parameter $u_{c-}$ and $u_{c+}$ are taken on each side before and after, to calculate the distance $L_{c-}$ and $L_{c+}$ between $Q_s$ and two points $C\left(u_{c-}\right)$ and $C\left(u_{c+}\right)$, and to determine the smaller value $L_{\min }$.

l On the side where $L_{\min }$ is obtained, the parameter interval $\left(u_c,u_{c+W}\right)$ is obtained, and the $R^{\prime }$ bisection is performed by using Equation (12), and the value $u_w$ $\left(w=0,1,2,\cdots ,R^{\prime }\right)$ at the same bisection point of each parameter is obtained, respectively. ${\epsilon }_w$ and ${\epsilon }_s$ are calculated by using Equation (13) and Equation (14).

4. Actual Data Calculation Results and Comparative Analysis

In order to verify the accuracy and feasibility of the interpolation error calculation method proposed in this paper, firstly, $\left\{Q_j\right\}$ set of data points to be interpolated and a measurement point $Q$ outside the data points are given in this paper. The coordinate of the measurement point $Q$ outside the data points is $Q=\left(\text{11}\text{.3929,5}\text{.6180,6}\text{.8010}\right)$, and the spatial position coordinates of each point are shown in Table 1.

The NURBS curve interpolation method in Section 2 is used to interpolate $\left\{Q_j\right\}$, and the relationship between the interpolated NURBS curve, the interpolated data point $\left\{Q_j\right\}$ and the measured point $Q$ is shown in Figure 3.

Using the interpolation error calculation method proposed in this paper, the distance between the measured point $Q$ and the NURBS interpolation curve is calculated by using the existing neighborhood comparison method [12] and the stepwise scanning method [14] respectively. The calculation results and calculation time of various methods are listed in Table 2. The theoretical distance in Table 2 is calculated by using UG/NX software.

Table 1. Data points used to be interpolated to the NURBS curve.

Figure 3. Error calculation diagram.

Table 2. The results of the three methods are compared.

As can be seen from Table 2, the approximate error solutions can be obtained by the three calculation methods. Among them, the minimum distance calculated by the stepwise scanning method is 0.0115 mm larger than the theoretical minimum distance, but the calculation time is the shortest. The minimum distance calculated by the neighborhood comparison method is 0.0010 mm larger than the theoretical minimum distance, and the calculation time is much longer than that by the neighborhood comparison method. The minimum distance calculated by the method in this paper is 0.0007 mm larger than the theoretical minimum distance and takes the longest time to calculate. However, the actual distance calculated by the method in this paper is closer to the theoretical distance calculated by using UG/NX software, which can more accurately express the error results of NURBS curve interpolation. Therefore, the interpolation error calculation method proposed in this paper is effective in the actual interpolation error calculation process.

5. Conclusion

Solution space for NURBS curve point to the curve of minimum distance problem, this paper puts forward a new type of computing space discrete data points to NURBS curve distance method, and the correctness of the method through examples, and compared with other existing methods, the calculation precision of the method is higher, to reflect the NURBS curve interpolation error and improve the efficiency of iteration has good application value.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Lasemi, A., Xue, D. and Gu, P. (2010) Recent Development in CNC Machining of Freeform Surfaces: A State-of-the-Art Review. Computer-Aided Design, 42, 641-654. https://doi.org/10.1016/j.cad.2010.04.002
[2]	Jahanpour, J., Motallebi, M. and Porghoveh, M. (2016) A Novel Trajectory Planning Scheme for Parallel Machining Robots Enhanced with NURBS Curves. Joumal of Intelligent & Robotic Systems, 82, 257-275. https://doi.org/10.1007/s10846-015-0239-6
[3]	Ruben, S. and Ettore, B. (2014) NURBS Distance Fields for Extremely Curved Cracks. Computational Mechanics, 54, 1431-1446. https://doi.org/10.1007/s00466-014-1067-4
[4]	Galvez, A. and Iglesias, A. (2013) Firefly Algorithm for Explicit B-Spline Curve Fitting to Data Points. Mathematical Problems in Engineering, 2013, Article ID: 528215. https://doi.org/10.1155/2013/528215
[5]	Gofuku, S., Tamura, S. and Maekawa, T. (2009) Point-Tangent/Point-Normal B-Spline Curve Interpolation by Geometric Algorithms. Computer-Aided Design, 41, 412-422. https://doi.org/10.1016/j.cad.2009.02.005
[6]	Yoshimoto, F., Harada, T. and Yoshimoto, Y. (2003) Data Fitting with a Spline Using a Real-Coded Genetic Algorithm. Computer-Aided Design, 35, 751-760. https://doi.org/10.1016/S0010-4485(03)00006-X
[7]	Park, H. and Lee, J.-H. (2006) B-Spline Curve Fitting Based on Adaptive Curve Refinement Using Dominant Points. Computer-Aided Design, 39, 439-451. https://doi.org/10.1016/j.cad.2006.12.006
[8]	Hu, S.-M. and Wallner, J. (2004) A Second Order Algorithm for Orthogonal Projection onto Curves and Surfaces. Computer Aided Geometric Design, 22, 251-260. https://doi.org/10.1016/j.cagd.2004.12.001
[9]	Stakhov, A. (2005) The Golden Section, Secrets of the Egyptian Civilization and Harmony Mathematics. Chaos, Solitons and Fractals, 30, 490-505. https://doi.org/10.1016/j.chaos.2005.11.022
[10]	Shopova, E.G. and Vaklieva-Bancheva, N.G. (2006) BASIC—A Genetic Algorithm for Engineering Problems Solution. Computers and Chemical Engineering, 30, 1293-1309. https://doi.org/10.1016/j.compchemeng.2006.03.003
[11]	Valle, Y., Venayagamoorthy, G.K. and Mohagheghi, S. (2008) Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems. IEEE Transaction on Evolutionary Computation, 12, 171-195. https://doi.org/10.1109/TEVC.2007.896686
[12]	Jiang, B.C., Han, J. and Xia, L. (2015) Accurate Solution Algorithm of B-Spline Curve Approximation Deviation. Manufacturing Technology and Machine Tools, No. 7, 67-71.
[13]	Piegl, L. and Tller, W. (2012) The NURBS Book. Springer Science & Business Media, Berlin.
[14]	He, G.Y. (2002) Visual C++ Common Numerical Algorithm Set. Science Press, Beijing, 528-529.