An efficient bivariate three-point Lagrange interpolation method based on coordinate transformation

Abstract

This paper proposes a bivariate three-point interpolation method based on coordinate transformation. The transformation significantly improves computational efficiency by converting radial sampling points into interpolation nodes, while enabling high-precision computation of coordinates and normal vectors for any surface point. Numerical experiments validate the effectiveness of the bivariate three-point interpolation method based on coordinate transformation. Although its accuracy is slightly lower than that of the NURBS surface method, it still meets the requirement for high precision. In particular, the proposed method drastically reduces the computation time by more than 50% compared to the NURBS surface method. In addition, it seamlessly computes coordinates and normal vectors for any surface point. It is significantly helpful for the improvement of computational efficiency in engineering for the measurement and evaluation of aircraft radomes.

Keywords

Surface reconstruction bivariate Lagrange interpolation coordinate transformation radial sampling points aircraft radomes

Introduction

In engineering, precision is paramount when dealing with certain components, such as aircraft radomes, which often comprise nearly-tapered deep cavities. These components bear paramount significance due to their role in high-performance systems. In the initial stage of the batch testing of these components’ geometric parameters, the data points are gathered from their outer contours. Subsequent reconstruction of the outer contour surface occurs, followed by derivation of the normal vector at each measurement point. The vector guides the measurement of wall thickness in the corresponding direction. Consequently, the surface reconstruction algorithm necessitates both high accuracy and efficiency. It’s imperative to minimize contour data points to enhance efficiency while expanding the count of wall thickness measurement points – effectively enabling the theoretical determination of the normal vector at any contour point to meet practical engineering requisites.

The non-uniform rational B-spline (NURBS) method is currently employed in a multitude of engineering applications, including geometric design,^1–3 trajectory planning (especially for numerical control machining⁴ and robotics^5–8), surface reconstruction,^9,10 and others. Its accuracy and flexibility have been widely acknowledged and appreciated. Contemporary surface reconstruction algorithms in engineering predominantly rely on the NURBS surface method. In recent years, researchers have directed their efforts toward enhancing the accuracy of NURBS curves and surfaces. These optimizations include control points,^11,12 knot vectors,¹³ the parameters of data points,¹⁴ and weights.^15,16 In addition, a rapid algorithm based on Taylor expansion has been developed for the calculation of normal vectors on NURBS surfaces, as presented in Zhou et al.¹⁷ The NURBS surface method, despite its prevalence, remains a complex, time-consuming, and data-intensive approach. Calculating coordinates and normal vectors for arbitrary points on a NURBS surface poses challenges. The precise determination of the normal vector necessitates the prior acquisition of Cartesian coordinates (x, y, z). While this is straightforward for data points, it becomes intricate for non-data points with unknown coordinates. The mapping relationship between NURBS surface parameters u and v and Cartesian coordinates is influenced by the chord length of the curve formed by data points, which is not consistently uniform. Obtaining Cartesian coordinates from parameters u and v is feasible. However, when trying to deduce one of the Cartesian coordinates from the other two (e.g. solving coordinate z when x and y are known), it necessitates the prior determination of parameters u and v. This process introduces difficulties in maintaining accurate mapping, significantly impacting the precision of normal vector calculations.

Apart from the NURBS surface method, alternative interpolation methods like Lagrange interpolation and cubic spline interpolation can be applied to surface reconstruction in engineering. While these methods may not offer the same precision as the NURBS surface method, they are computationally straightforward, and the difference in accuracy and efficiency when calculating coordinates for any surface point is minimal, rendering them suitable for specific engineering scenarios. In the realm of Lagrange interpolation, many studies have focused on expanding interpolation nodes and enhancing interpolation basis functions. For example, an error analysis of high-order bivariate Lagrange interpolation using rectangles, right angles, and equilateral triangles has been delved in Luo et al.¹⁸ A six-point Shepard interpolation method derived from the extension of the three-point Shepard method has been introduced in Dell’Accio and Tommaso.¹⁹ This method can be applied to the scattered data, although it still imposes some node-related demands. A novel approach based on subset interpolation is proposed by improved Lagrange polynomials for the case of uneven distribution of rectangular grids in Chen et al.²⁰ A new format of Lagrange basis polynomials over regular schemes of chords has been introduced for surface reconstruction based on line integrals along segments of the unit disk in Georgieva and Uluchev.²¹ Additionally, novel Lagrange interpolation basis functions based on rectangular grid nodes to enhance accuracy have been introduced in Cao et al.²² and Harris.²³ Regarding cubic spline interpolation, research often centers on optimizing spline curve nodes. For instance, a method to determine optimal nodes for spline curves within a non-uniform rectangular grid has been presented in Idais et al.²⁴ An approach to expedite bi-cubic spline interpolation computations on non-uniform rectangular grids has been offered in Kacala and Torok.²⁵ In addition, a scheme for generating a bi-cubic spline surface for a regular cylinder under a cylindrical coordinate system has been devised in Sadikin et al.²⁶ A method for constructing a bi-cubic spline surface using scattered data has been introduced in Guan et al.,²⁷ although this method requires a high node density to achieve accuracy. The above methods impose specific node requirements on interpolation grids. In the case of radomes and other components with tapered deep cavities, data points are typically distributed radially, and to enhance measurement efficiency, these data points tend to be relatively sparse. Consequently, there is a scarcity of effective surface interpolation techniques for the reconstruction of surfaces of such components.

To solve these problems, this paper proposes a bivariate three-point Lagrange interpolation method based on coordinate transformations, achieving high surface reconstruction accuracy for sparsely and radially distributed points. Moreover, the proposed method enhances computational efficiency when compared to the prevalent NURBS surface methods and excels in efficiently and precisely computing coordinates and normal vectors for any surface point, aligning with engineering demands. The proposed method ensures accuracy and improves computational efficiency when used for surface measurement and evaluation. It can also be employed for other projects involving surface reconstruction, such as robot trajectory planning on curved surfaces. This enables the rapid acquisition of surface geometric information, which can then be used for subsequent trajectory planning, thereby enhancing overall efficiency.

Bivariate Lagrange interpolation method

In curve interpolation, consider an equidistant division of a given interval [a, b] as a sequence a = x₀ < x₁ < … < x_n = b, associated with function values y₀, y₁, …, y_n. It can be demonstrated that a continuous polynomial of order n, designated as P_n(x), can be identified to traverse all the data points, satisfying the conditions P_n(x_i) = y_i for i = 0, 1, …, n. This can be accomplished by utilizing the Lagrange interpolation formula.

P_{n} (x) = \sum_{i = 0}^{n} y_{i} (Π_{j \neq i}^{0 \leq j \leq n} \frac{(x - x_{j})}{(x_{i} - x_{j})})

(1)

In surface interpolation, the bivariate Lagrange surface interpolation formula can be derived through a product of the univariate Lagrange interpolation formula.

The set of bivariate Lagrange interpolation nodes exists within rectangular grid nodes, triangular grid nodes, and nodes of crossed straight lines. Among these, the interpolation formula applied to rectangular grid nodes is more widely employed.

Set the group of interpolation nodes f = {(x_i, y_j)|i = 0, 1, 2, …, m; j = 0, 1, 2, …, n}, mark:

\begin{matrix} U (x) = (x - x_{0}) \dots (x - x_{m}) \\ V (y) = (y - y_{0}) \dots (y - y_{n}) \end{matrix}

(2)

The rectangular grid nodes are shown in Figure 1.

Figure 1.

Rectangular grid nodes.

Then the fundamental polynomial for Lagrange interpolation of these nodes is as follows:

L_{ij} (x, y) = \frac{U (x)}{(x - x_{i}) U' (x_{i})} \cdot \frac{V (y)}{(y - y_{j}) V' (y_{j})}

(3)

The bivariate Lagrange interpolation formula is derived from the above set of nodes:

p (x, y) = \sum_{i = 0}^{m} \sum_{j = 0}^{n} f (x_{i}, y_{j}) L_{ij} (x, y)

(4)

The bivariate Lagrange interpolation formula on rectangular grid nodes generates a polynomial that passes through all data points which can be categorized into overall interpolation and local interpolation, depending on the number of data points involved. In the context of global interpolation, all data points are considered, resulting in a significant increase in computational demands as the number of interpolation points rises. On the other hand, local interpolation utilizes a subset of data points to establish a modeling function, rendering it more adaptable when dealing with a large volume of data points. In practical scenarios, engineering challenges have often been effectively addressed using second-order continuous curves. Radomes constructed with nearly-tapered deep cavities are generally rotating bodies, and their surface equations can be readily obtained by deriving their generatrix equations. These radomes have smooth outer contours, and quadratic polynomials can be used to represent their outer contours in the interpolation method. Since quadratic polynomials can generally express the radome outer contour curve, three interpolation nodes are required for Lagrange interpolation, and 3 × 3 grid of nodes is required for the extension to the bivariate case. Consequently, this paper adopts a local bivariate three-point Lagrange interpolation method for surface reconstruction, that is, a 3 × 3 rectangular grid of nodes is utilized for interpolation. In consideration of the computational accuracy and efficiency, the 3 × 3 grid of nodes is a good choice for surface reconstruction of rotating body radomes.

Coordinate transformation

The contours of tapered deep cavity components exhibit a certain level of continuity and regularity, which facilitates the even and orderly collection of contour data points. In most cases, data collection is aligned with the direction of circumferential cross-section and generatrix, resulting in an organized dataset. Concerning the rotating body depicted in Figure 2, it can be observed that the axis of rotation coincides with the Z-axis. The z-coordinate value of each data point corresponds to the function f concerning the x and y coordinate values. Upon examination of the data points projected onto the xOy plane, it becomes evident that they are distributed in a radial pattern rather than in a rectangular grid pattern. Consequently, the direct application of a bivariate interpolation method does not guarantee the accuracy of surface reconstruction. To address this challenge, a coordinate transformation technique is introduced. This method converts the approximate quadrilateral grid nodes on the xOy plane into approximate square grid nodes on the new ζOη plane. Subsequently, the bivariate interpolation method can be employed for surface reconstruction.

Figure 2.

Data points and interpolation nodes of a rotating body: (a) normal view and (b) top view.

To illustrate, concerning the 3 × 3 nodes that are of fundamental importance for bivariate three-point interpolation, the method can be described as follows: The four vertices of the approximate quadrilateral are identified within the group of nine nodes. These vertices are then subjected to a coordinate transformation, aligning them with the four vertices of a square on the new plane. The transformation in question can be determined by ensuring that the four vertices of both planes before and after the coordinate transformation adhere to the relationship defined by the following equation²⁸:

\begin{matrix} x = a_{1} + b_{1} ζ + c_{1} η + d_{1} ζ η \\ y = a_{2} + b_{2} ζ + c_{2} η + d_{2} ζ η \end{matrix}

(5)

Consider the square on the ζOη plane, which is centered at the origin and possesses a side length of 2. The four vertex coordinates of the square are (−1, −1), (1, −1), (1, 1), and (−1, 1). By substituting the coordinates of each of these four vertices into equation (5), two quaternion equations are derived:

{\begin{matrix} x_{1} = a_{1} - b_{1} - c_{1} + d_{1} \\ x_{2} = a_{1} + b_{1} - c_{1} - d_{1} \\ x_{3} = a_{1} + b_{1} + c_{1} + d_{1} \\ x_{4} = a_{1} - b_{1} + c_{1} - d_{1} \end{matrix} {\begin{matrix} y_{1} = a_{2} - b_{2} - c_{2} + d_{2} \\ y_{2} = a_{2} + b_{2} - c_{2} - d_{2} \\ y_{3} = a_{2} + b_{2} + c_{2} + d_{2} \\ y_{4} = a_{2} - b_{2} + c_{2} - d_{2} \end{matrix}

(6)

From equation (6), the values of the variables a, b, c, and d in equation (5) can be deduced, after which the coordinates of the remaining five points and any point within the scope of the xOy plane can be replaced into equation (5). This process enables the solution of a system of binary quadratic equations, resulting in the determination of coordinates for the corresponding points on the ζOη plane. Figure 3 illustrates the nodes and the target point on the two planes before and after the coordinate transformation.

Figure 3.

Coordinates of the nodes: (a) xOy plane and (b) ζOη plane.

The micro-planar method is employed to determine the normal vector of the target point. The procedure entails the selection of three equidistant points around the target point, which are then combined to form a triangular element with the target point serving as the center of gravity. When the size of the triangular element is sufficiently small, its normal vector can be approximated as the normal vector of the target point. The z-coordinates of the vertices of the triangle are obtained individually through interpolation. The normal vector is calculated by taking the cross-product of the two adjacent vectors of the triangle in three-dimensional space.

When the accuracy of the data points reaches a sufficient level, the rectangular grid after coordinate transformation on the ζOη plane tends to show more regularity. However, in cases of data point errors, projections on the xOy plane may appear with smaller spacing and increased chaos which can disrupt the regularity of the rectangular grid on the ζOη plane, thereby affecting the accuracy of the interpolation. In addition, the bivariate three-point interpolation method following the coordinate transformation on the xOy plane cannot handle scenarios where the generatrix is perpendicular to the horizontal line. This results in all generatrix data points being projected as a single point on the xOy plane, as shown in Figure 4.

Figure 4.

Projection onto different planes: (a) xOy plane and (b) xOz/yOz plane.

Considering that the data points are aligned with the direction of the circumferential cross-section and generatrix, their projection onto the xOz/yOz planes tends to be less chaotic than the projection onto the xOy plane. Therefore, the results after transformation are significantly improved, as shown in Figure 5.

Figure 5.

Outcomes after transformation using projection onto different planes: (a) xOy plane and (b) xOz/yOz plane.

However, the choice between the two planes for projection varies based on their respective positions along the circumference, and at certain angles, neither plane is satisfactory, as shown in Figure 6.

Figure 6.

Projections of nodes onto xOy/yOz plane.

The bivariate three-point interpolation method necessitates only the data points on the three nearest generatrices. Consequently, the nodes are rotated about the Z-axis to 0° of the xOy plane. Specifically, rotate the nodes by the angle θ between the center generatrix and the positive X-axis, as shown in Figure 7.

Figure 7.

Nodes before (blue) and after (red) rotation: (a) rotation process and (b) top view.

Subsequently, the coordinates on the yOz plane are transformed, and bivariate interpolation is employed to perform the interpolation. Following this, the coordinates are rotated back to their original position after the calculations are completed. Figure 8 presents a flowchart that outlines the bivariate three-point interpolation method based on coordinate transformation.

Figure 8.

Flowchart of the bivariate three-point interpolation method based on coordinate transformation.

Other interpolation methods based on rectangular grid nodes may also employ the coordinate transformation process to achieve surface reconstruction at radial sampling points. The relative merits of the different interpolation methods are evaluated to identify their respective advantages and disadvantages. The results of this evaluation are presented in Table 1.

Table 1.

Advantages and disadvantages of different methods.

Method	Advantage	Disadvantage
NURBS	High accuracy	High complexity
Splines (Cubic,²⁹ Trigonometric,³⁰ Polynomial^31,32)	Contains derivative	Medium complexity
Lagrange interpolation	Low complexity	Medium accuracy

Numerical experiments and discussions

To validate the efficacy of the proposed bivariate three-point interpolation method based on coordinate transformation, we conduct surface reconstructions for a representative paraboloid and a sinusoidal surface characterized by substantial curvature. The assessment encompasses the accuracy of surface reconstruction, the precision of normal vector computation at various points, and computational efficiency. A comparative analysis is carried out against the classical bi-cubic spline interpolation method and the NRUBS surface method.¹⁵ The bi-cubic spline interpolation method, which may be considered representative of spline interpolation methods, requires fewer points for interpolation. These examinations are performed using MATLAB software on a desktop computer equipped with a 2.9 GHz Intel i7-10700 CPU and 16 GB RAM.

Paraboloid

Take the common quadratic curve paraboloid as an example, the equation of the paraboloid is z = 0.02 (x² + y²), where z ranges from 0 to 800 mm, data points are selected following the direction of generatrix and circumferential cross-section. These points are arranged in a radial distribution in the top view, as shown in Figure 9.

Figure 9.

Partial data points (red) and non-data points (blue) in a paraboloid: (a) normal view and (b) top view.

A total of 810 data points were utilized for surface reconstruction. Each of the three methods selected 696 points for computation. The outcomes are detailed in Table 2. If the NURBS surface method calculates the non-data points through the parameters u and v, yielding errors like the results of data points. However, this paper entails calculating non-data points through incomplete Cartesian coordinates considering the actual engineering situation, which introduces a certain degree of error.

Table 2.

Results of surface reconstruction methods for paraboloid.

Method	Contour error (mm)			Normal vector error (°)			Time (s)
Method	Mean	RMS	Max	Mean	RMS	Max	Time (s)
NURBS for data points	0.0002	0.0003	0.0012	0.0008	0.0009	0.0015	22
NURBS for non-data points	0.0289	0.0339	0.0672	0.0119	0.0134	0.0194	22
Bi-cubic spline	0.0002	0.0002	0.0006	0.0092	0.0112	0.0405	23
Proposed method	0.0002	0.0003	0.0005	0.0065	0.0075	0.0225	10

Table 2 shows that: (1) Contour accuracy: All three methods (NURBS surface method for data points, bi-cubic spline method, and proposed method) exhibit similar calculation errors, averaging 0.2 µm with the root-mean-square (RMS) of 0.2 or 0.3 µm. The NURBS surface method displays the largest maximum error at 1.2 µm. Notably, the NURBS surface method for non-data points yields larger errors, with an average of 28.9 µm. (2) Normal Vector Accuracy: The NURBS surface method for non-data points, bi-cubic spline method, and proposed method demonstrate close normal vector accuracy, with the proposed method slightly outperforming (average error of 0.0065°), which can satisfy most of the engineering needs. The NURBS surface method for data points notably excels in this aspect (average error of 0.0008°). It is crucial to emphasize that the normal vector accuracy of the NURBS surface method for non-data points is significantly inferior to that of the data point counterpart. (3) Calculation efficiency: The bi-cubic spline and NURBS surface methods exhibit comparable efficiency, with calculation times of 23 and 22 s, respectively. In contrast, the proposed method demonstrates remarkable improvement, taking just 10 s – a more than 50% enhancement over the preceding two methods.

Acknowledging the inevitable occurrence of data point sampling errors in engineering applications, a test of algorithm robustness is imperative. To achieve this, introduce artificial random errors that adhere to a normal distribution N(0, 0.005²) of mean 0 and variance 0.005². It is recommended that a comparative analysis of the three methods be conducted once more, with the outcomes presented in Table 3 and the reconstruction errors using different methods presented in Figures 10 to 12.

Table 3.

Results of surface reconstruction methods for paraboloid after adding errors.

Method	Contour error (mm)			Normal vector error (°)			Time (s)
Method	Mean	RMS	Max	Mean	RMS	Max	Time (s)
NURBS for data points	0.0026	0.0035	0.0164	0.0234	0. 0412	0.2716	22
NURBS for non-data points	0.0706	0.0733	0.1024	0.1669	0.2535	0.6514	22
Bi-cubic spline	0.0038	0.0048	0.0179	0.0479	0.0595	0.2886	23
Proposed method	0.0028	0.0036	0.0163	0.0383	0.0455	0.1576	10

Figure 10.

Error distribution of the reconstructed paraboloid after adding random errors using the proposed method: (a) contour error and (b) normal vector error.

Figure 11.

Error distribution of the reconstructed paraboloid after adding random errors using the bi-cubic spline method: (a) contour error and (b) normal vector error.

Figure 12.

Error distribution of the reconstructed paraboloid after adding random errors using the NURBS surface method: (a) contour error and (b) normal vector error.

As shown in Figures 10 to 12, for the bi-cubic spline method and the proposed method, the introduction of random errors that adhere to a normal distribution N(0, 0.005²) results in significant reconstruction errors at specific points on the surface where the introduced errors are large. Disregarding the specific points with large errors, the two methods exhibit consistent computation accuracy in calculating coordinates or normal vectors for any point on the surface, with the proposed method demonstrating superior overall surface reconstruction accuracy compared to the bi-cubic spline method. With regard to the NURBS surface method, although the introduction of random errors also leads to large reconstruction errors at specific points, the reconstruction accuracy of the NURBS surface method for data point generatrices and non-data point generatrices is evidently inconsistent and differs significantly. It is more challenging to meet the high-precision engineering requirements for surface reconstruction accuracy on non-data point generatrices.

Table 3 reveals a notable decline in calculation accuracy across all three methods following the introduction of significant errors: (1) Contour accuracy: The calculation errors for the three methods (NURBS surface method for data points, bi-cubic spline method, and proposed method) exhibit a similar trend, averaging around 3 µm. However, the NURBS surface method for non-data points displays considerably larger errors, exceeding others by more than 10 times and peaking at 70.6 µm which falls short of meeting high-precision requirements. (2) Normal vector accuracy: Despite the challenges posed by the errors, the NURBS surface method for data points remains closely aligned with the bi-cubic spline method and proposed method, displaying slightly superior performance (average error of 0.0234°) which still accommodates most engineering demands. Conversely, the accuracy of the NURBS surface method for non-data points experiences a significant drop (average error of 0.1669°), rendering it unsuitable for high-precision applications. (3) Computational efficiency: Notably, the proposed method still demonstrates an improvement in efficiency of over 50% compared to the other approaches.

After analyzing the sources of error, we may conclude that the conversion of a portion of the Cartesian coordinates to the NURBS surface parameters u, v introduces errors that deteriorate the reconstruction accuracy for the non-data points when utilizing the NURBS surface method. The error of the bi-cubic spline method is primarily attributable to the approximation of the derivatives of the interpolation nodes and the discrepancy between the theoretical contours and the cubic polynomials. In contrast, the error of the proposed method is caused by the discrepancy between the theoretical contours and the quadratic polynomials formed by interpolation. In practice, increasing the density of sampling data points or choosing sensors with higher measurement accuracy can be used to obtain more precise outer contour sampling data points and thus minimize reconstruction errors.

Figure 13 compares computation times between the proposed method and the NURBS surface method across varying numbers of data points. This encompasses scenarios where data point measurements are encrypted or the workpiece size is expanded. Furthermore, the comparison encompasses computation times when selecting parts of data points for normal vector calculations.

Figure 13.

Run time with different number of data points: (a) calculating all points and (b) calculating 1000 points.

As shown in Figure 13, the computation time of the surface reconstruction algorithm maintains a proportional correlation with the data point count. Impressively, the proposed method consistently demonstrates computation times below 50% of those observed with the NURBS surface method. Furthermore, when employing 1000 points for normal vector calculations under different numbers of total data points, the computation time of the proposed method remains essentially unaltered because of using local interpolation.

Sinusoidal surface

To assess the algorithm’s effectiveness on surfaces with substantial curvature, the sinusoidal surface z =(100 × sinr)/r is introduced, where $r = \sqrt{x^{2} + y^{2}}$ is the distance between the point and Z-axis. The r ranges from 0 to 10 mm with a maximum z of 100 mm. The data points are in a radial distribution, as depicted in Figure 14. For reconstruction purposes, 2040 data points are employed, with each of the three methods opting for 2000 points for computation.

Figure 14.

Partial data points (red) and non-data points (blue) on a sinusoidal surface: (a) normal view and (b) top view.

As can be seen from Table 4, the result is similar to the above situation: (1) Contour accuracy: All three methods (NURBS surface method for data points, bi-cubic spline method, and proposed method) exhibit similar calculation errors, with the average and RMS of about 0.2 µm. Foreseeably, the NURBS surface method for non-data points yields larger errors, with an average of 15.9 µm. (2) Normal vector accuracy: The NURBS surface method for non-data points, bi-cubic spline method, and proposed method demonstrate close normal vector accuracy, with the proposed method slightly outperforming (average error of 0.0443°), which can satisfy most of the engineering needs. The NURBS surface method for data points excels in this aspect (average error of 0.0021°). (3) Calculation efficiency: The bi-cubic spline and NURBS surface methods exhibit comparable efficiency, requiring 68 and 64 s. In contrast, the proposed method takes just 29 s – a more than 50% enhancement over the preceding two methods.

Table 4.

Results of surface reconstruction methods for sinusoidal surface.

Method	Contour error (mm)			Normal vector error (°)			Time (s)
Method	Mean	RMS	Max	Mean	RMS	Max	Time (s)
NURBS for data points	0.0002	0.0003	0.0049	0.0021	0.0065	0.0370	64
NURBS for non-data points	0.0159	0.0196	0.0342	0.0741	0.1014	0.1477	64
Bi-cubic spline	0.0002	0.0002	0.0062	0.0682	0.0845	0.1554	68
Proposed method	0.0001	0.0001	0.0043	0.0443	0.0502	0.1278	29

To assess the robustness of the algorithm, introduce artificial random errors that adhere to a normal distribution N(0, 0.001²) of mean 0 and variance 0.001². A comparative analysis of the three methods is again required, the outcomes are presented in Table 5, and the reconstruction errors using different methods are presented in Figures 15 to 17.

Table 5.

Results of surface reconstruction methods for the sinusoidal surface after adding errors

Method	Contour error (mm)			Normal vector error (°)			Time (s)
Method	Mean	RMS	Max	Mean	RMS	Max	Time (s)
NURBS for data points	0.0009	0.0014	0.0113	0.0609	0.0774	0.1991	64
NURBS for non-data points	0.0183	0.0213	0.0406	0.3980	0.4768	0.9822	65
Bi-cubic spline	0.0025	0.0038	0.0088	0.1177	0.1291	0.3941	68
Proposed method	0.0016	0.0021	0.0081	0.0791	0.0946	0.3731	29

Figure 15.

Error distribution of the reconstructed sinusoidal surface after adding random errors using the proposed method: (a) contour error and (b) normal vector error.

Figure 16.

Error distribution of the reconstructed sinusoidal surface after adding random errors using the bi-cubic spline method: (a) contour error and (b) normal vector error.

Figure 17.

Error distribution of the reconstructed sinusoidal surface after adding random errors using the NURBS surface method: (a) contour error and (b) normal vector error.

As shown in Figures 15 to 17, the error distribution is similar to that of the paraboloid, the introduction of random errors results in significant reconstruction errors at specific points on the surface. The proposed method and the bi-cubic spline method exhibit consistent computation accuracy in calculating coordinates or normal vectors for any point on the surface, with the proposed method demonstrating superior overall surface reconstruction accuracy compared to the bi-cubic spline method. In contrast, the reconstruction accuracy of the NURBS surface method for data point generatrices and non-data point generatrices is inconsistent.

Table 5 reveals a notable decline predictably in calculation accuracy across all three methods following the introduction of errors: (1) Contour accuracy: The calculation errors for the three methods (NURBS surface method for data points, bi-cubic spline method, and proposed method) exhibit a similar trend, averaging no more than 2.5 µm. However, the NURBS surface method for non-data points displays considerably larger errors, exceeding others by about 10 times and peaking at 18.3 µm which falls short of meeting high-precision requirements. (2) Normal vector accuracy: Despite the challenges posed by the errors, the NURBS surface method for data points remains closely aligned with the bi-cubic spline method and proposed method, displaying slightly superior performance (average error of 0.0609°) which still accommodates most engineering demands. Conversely, the accuracy of the NURBS surface method for non-data points experiences a significant drop, rendering it unsuitable for high-precision applications. (3) Computational efficiency: The proposed method improves efficiency by over 50% compared to the other approaches.

Similarly, Figure 18 compares computation times between the proposed method and the NURBS surface method.

Figure 18.

Run time with different number of data points: (a) calculating all points and (b) calculating 1000 points.

As shown in Figure 18, the computation time of the surface reconstruction algorithm still maintains a proportional correlation with the number of data points. The proposed method consistently demonstrates computation times below 50% of those observed with the NURBS surface method.

Conclusion

This paper proposes a bivariate three-point Lagrange interpolation method based on coordinate transformation. By translating the approximate quadrilateral grid nodes into near-square grid nodes through coordinate transformation, computational efficiency is notably enhanced and limitations associated with the bivariate interpolation method for sampling grid nodes are circumvented. Meanwhile, local interpolation ensures parity in the computational accuracy of coordinates or normal vectors between data points and non-data points. The experimental results show that the bivariate three-point Lagrange interpolation method based on coordinate transformation can meet most engineering requirements. While its precision falls short of the NURBS surface method, it remains within a comparable range. Furthermore, the proposed method showcases a noteworthy improvement in computational efficiency, surpassing 50% enhancement. Crucially, the method delivers consistent accuracy in calculating coordinates or normal vectors for any point on the surface. Thus, it offers a simple and practical solution for specific engineering surface reconstruction needs.

Footnotes

Handling Editor: Aarthy Esakkiappan

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Zhijie Zhao

References

Chrisp

Primeau

Echter

MA.

Imaging freeform optical systems designed with NURBS surfaces. Opt Eng 2016; 55: 071208.

Philipp

Breitenberger

D’Auria

, et al. Integrated design and analysis of structural membranes using the Isogeometric B-Rep Analysis. Comput Methods Appl Mech Eng 2016; 303: 312–340.

Zhou

Feng

Liu

, et al. NURBS-based parametric design for ship hull form. J Mar Sci Eng 2022; 10: 686.

Fan

Zhao

, et al. Real-time arc length parameter-based integrated control strategy of contour error compensation for free-form curve CNC machining. Int J Adv Manuf Technol 2024; 131: 1769–1794.

Ding

Kinematics and dynamics analysis of the 3PUS-PRU parallel mechanism module designed for a novel 6-DOF gantry hybrid machine tool. J Mech Sci Technol 2020; 34: 345–357.

Ayiz

Kucuk

. The kinematics of industrial robot manipulators based on the exponential rotational matrices. In: 2009 IEEE international symposium on industrial electronics (ISIE 2009), Seoul, South Korea, 5–8 July 2009, pp.977–982. New York: IEEE.

Toz

Kucuk

Development of derivation of inverse Jacobian matrices for 195 6-DOF GSP mechanisms. Turk J Electr Eng Comput Sci 2016; 24: 4142–4153.

Toz

Kucuk

Parallel manipulator software tool for design, analysis, and simulation of 195 GSP mechanisms. Comput Appl Eng Educ 2015; 23: 931–946.

Pal

A reconstruction method using geometric subdivision and NURBS interpolation. Int J Adv Manuf Technol 2008; 38: 296–308.

10.

Gálvez

Iglesias

Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points. Inf Sci 2012; 192: 174–192.

11.

Yeh

Nashed

YSG

Peterka

, et al. Fast automatic knot placement method for accurate B-spline curve fitting. Comput Aided Des 2020; 128: 102905.

12.

Laube

Franz

Umaluf

Learnt knot placement in B-spline curve approximation using support vector machines. Comput Aided Geom Des 2018; 62: 104–116.

13.

Kruth

JP.

NURBS curve and surface fitting for reverse engineering. Int J Adv Manuf Technol 1998; 14: 918–927.

14.

Deng

Lin

. Progressive and iterative approximation for least squares B-spline curve and surface fitting. Comput Aided Des 2014; 47: 32–44.

15.

Wang

Liu

Yuan

, et al. Iterative least square optimization for the weights of NURBS curve. Math Probl Eng 2022; 2022: 1–12.

16.

Zhang

Deng

Optimizing NURBS curves fitting by least squares progressive and iterative approximation. J Comput Aided Des Comput Graph 2020; 32: 568–574.

17.

Zhou

Liu

Yin

, et al. A fast algorithm of normal vector calculation for NURBS surface based on Taylor expansion. In: 2021 IEEE international conference on mechatronics and automation (ICMA), Takamatsu, Japan, 8–11 August 2021, pp.350–355. New York: IEEE.

18.

Luo

Liu

, et al. Error analysis of higher order bivariate Lagrange and triangular interpolations in electromagnetics. IEEE Open J Antennas Propag 2020; 1: 590–597.

19.

Dell’Accio

Tommaso

Interpolation by bivariate quadratic polynomials and applications to the scattered data interpolation problem. In: Sergeyev

Kvasov

(eds) Numerical computations: theory and algorithms. Cham: Springer, 2019, pp.35–46..

20.

Chen

Wang

. Based on subset interpolation Lagrange polynomials surface reconstruction in non-uniform meshes. In: AOPC 2019: optical sensing and imaging technology, 2019, p.113380M. Washington: SPIE.

21.

Georgieva

Uluchev

Surface reconstruction and Lagrange basis polynomials. In: Lirkov

Margenov

Waśniewski

(eds) 6th international conference on large-scale scientific computing (LSSC 2007). Berlin: Springer, 2007, pp.670–678.

22.

Cao

Ghimire

Wang

Bivariate Lagrange interpolation at the checkerboard nodes. Proc Am Math Soc 2022; 150: 2153–2163.

23.

Harris

LA.

Alternation points and bivariate Lagrange interpolation. J Comput Appl Math 2018; 340: 43–52.

24.

Idais

Yasin

Pasadas

, et al. Optimal knots allocation in the cubic and bicubic spline interpolation problems. Math Comput Simul 2019; 164: 131–145.

25.

Kacala

Torok

. Speedup of bicubic spline interpolation. In: Shi

(ed.) Computational science – ICCS 2018. Cham: Springer, 2018, pp.806–818.

26.

Sadikin

Swardiana

IWA

Wirahman

. Cubic spline interpolation for large regular 3D grid in cylindrical coordinate. In: 2017 International conference on computer, control, informatics and its applications (IC3INA), Jakarta, Indonesia, 23–26 October 2017, pp.1–6. New York: IEEE.

27.

Guan

Zhu

Interpolation for space scattered data by bicubic polynomial natural splines. Acta Sci Nat Univ Sunyatseni 2008; 47: 1–4.

28.

Jin

JM.

The finite element method in electromagnetics. 3rd ed. New York, NY: Wiley, 2014, p.249.

29.

Kucuk

Maximal dexterous trajectory generation and cubic spline optimization for fully planar parallel manipulators. Comput Electr Eng 2016; 56: 634–647.

30.

Simon

Isik

Optimal trigonometric robot joint trajectories. Robotica 1991; 9: 379–386.

31.

Ding

Minimum-jerk trajectory planning pertaining to a translational 3-degree-of-freedom parallel manipulator through piecewise quintic polynomials interpolation. Adv Mech Eng 2020; 12: 1–18.

32.

Ege

Kucuk

Energy minimization of new robotic-type above-knee prosthesis for higher battery lifetime. Appl Sci 2023; 13: 3868.