Objective

2

In computer-aided geometric design and computer graphics

fitting point clouds with the smooth curve is a widely studied problem. Measurement data can be taken from real objects using techniques such as laser scanning

structure light source converter

and X-ray tomography. We use these scanned discrete data points for data fitting to perform a general model reconstruction and functional recovery for the original model or product

which is widely used in the field of geometric analysis and image analysis. The data points used in this paper are unstructured scattered data points. Compared with the parametric curves

implicit curves do not need to parameterize scattered data points. Therefore

they are widely studied because of their ability to describe objects with complicated geometry and topology. Because the control points of the conventional implicit B-spline curve need to be arranged regularly in the entire area

a large number of redundant control points are required to satisfy the topological constraints and has some limitations in the local subdivision

which will lead to the phenomenon of control point redundancy. The T-spline effectively solves this problem. Based on the advantages of B-spline curves and surfaces

it admits the structure of T-nodes

and thus

it has many advantages

such as fewer control points and convenient local subdivision. This is the reason why we chose T-spline to perform the implicit curve reconstruction. In some cases

the data points we obtain may not only be scattered coordinate information but also contain some shape constraint conditions

such as the processing of data points with the normal constraints in the field of optical engineering. Therefore

we not only need to constrain the errors of the data points but also have certain requirements for the normal errors. Hence

an implicit T-spline curve reconstruction algorithm with normal constraints is proposed in this paper.

Method

2

We first preprocess the data

which adjusts the density of sampling points adaptively by combining with the curvature to remove the redundant data points and add auxiliary points. The step of adding auxiliary points not only avoids the singular solutions but also helps to eliminate the zero level set. Two-dimensional T-meshes are constructed from the scattered point set by using binary tree and subdivision process. Here

we define a maximum number of subdivisions and then count the number of data points in each sub-rectangular block. If the number of data points is greater than the given number of subdivisions

it is subdivided until the number of data points is less than the maximum number of subdivisions and we obtain the initial T-mesh. Then

an effective curve fitting model is proposed based on the implicit T-spline function. Because the number of equations is far more than the number of unknowns

we transform the problem of the implicit T-spline curve reconstruction into a quadratic optimization problem to obtain the objective function. The objective function of our model is divided into three parts: the fitting error term

normal term

and smoothing term. The fitting error term includes the error of data points and auxiliary points. We eliminate the extra zero-level sets by adding offset points and smoothing the term. We also add the normal term to reduce the normal error of the constructed curve. According to the optimization principle

we take the partial derivative of the objective function concerning each of the control coefficients and set it equal to zero. In this case

the original problem is transformed into linear equations. The unknown control coefficients can be obtained by solving the system of linear equations to solve the problem of implicit curve reconstruction. Finally

we insert the control coefficient into the area of the large error to carry out the local subdivision of T-mesh until the precision requirement is reached to improve the accuracy of the reconstruction of the implicit curve.

Result

2

The experiment is compared with two existing methods on three datasets

including two concave and convex curves and a complicated hand curve. From the figures in paper

we can see that although the proposed method and the existing method 1 which contructs implicit equations with normal vector constraints

reconstruct the shape of the implicit T-spline curve

some extra zero level sets appear around the curve of method 1

which destroy the quality of the reconstructed curves. The reconstructed results of the proposed method do not have the extra zero level set. The experimental data show that in terms of the error of the data points

the algorithm presented in this paper differs little from the two methods in terms of the average error and the maximum error of data points

which are in the same order of magnitude. However

in the normal error

the proposed algorithm has a significant reduction. In the curves of examples 1 and 2

the proposed algorithm reduces the average error of the normal direction from the order of 10

-3

to the order of 10

-4

and the maximum error of the normal direction from the order of 10

-2

to the order of 10

-3

. Meanwhile

in the curve of example 3

the proposed algorithm can still significantly reduce the normal error while method 2 which uses least square fitting method by adding auxiliarg points

has the worst normal constraint. In terms of the quality of the reconstructed curve

the extra zero level set is eliminated by the proposed method while the obvious zero level set exists in method 1 and the reconstruction effect is poor. Meanwhile

compared with the implicit B-spline control grid

the number of control points in the T-mesh of the three data sets was only 55.88 %

39.80 %

and 47.06 % of that in the B-spline grid.

Conclusion

2

Experimental results indicate that the proposed algorithm effectively reduces the normal errors under the premise of ensuring the accuracy of data points. The proposed algorithm also successfully eliminates extra zero-level sets and improves the quality of the reconstructed curve. Compared with the implicit B-spline curves

the proposed method reduces the number of control coefficients and improves the operation speed. Hence

the proposed method successfully solves the problem of implicit T-spline curve reconstruction with normal constraints.