浏览全部资源
扫码关注微信
Received：13 October 2020，
Revised：2020-11-17，
Accepted：24 November 2020，
Published：16 April 2022
移动端阅览
目的
2
隐式曲线能够描述复杂的几何形状和拓扑结构，而传统的隐式B样条曲线的控制网格需要大量多余的控制点满足拓扑约束。有些情况下，获取的数据点不仅包含坐标信息，还包含相应的法向约束条件。针对这个问题，提出了一种带法向约束的隐式T样条曲线重建算法。
方法
2
结合曲率自适应地调整采样点的疏密，利用二叉树及其细分过程从散乱数据点集构造2维T网格; 基于隐式T样条函数提出了一种有效的曲线拟合模型。通过加入偏移数据点和光滑项消除额外零水平集，同时加入法向项减小曲线的法向误差，并依据最优化原理将问题转化为线性方程组求解得到控制系数，从而实现隐式曲线的重构。在误差较大的区域进行T网格局部细分，提高重建隐式曲线的精度。
结果
2
实验在3个数据集上与两种方法进行比较，实验结果表明，本文算法的法向误差显著减小，法向平均误差由10
-3
数量级缩小为10
-4
数量级，法向最大误差由10
-2
数量级缩小为10
-3
数量级。在重构曲线质量上，消除了额外零水平集。与隐式B样条控制网格相比，3个数据集的T网格的控制点数量只有B样条网格的55.88 %、39.80 %和47.06 %。
结论
2
本文算法能在保证数据点精度的前提下，有效降低法向误差，消除了额外的零水平集。与隐式B样条曲线相比，本文方法减少了控制系数的数量，提高了运算速度。
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.
Hamza Y F, Lin H W and Li Z H. 2020. Implicit progressive-iterative approximation for curve and surface reconstruction. Computer Aided Geometric Design, 77: #101817 [DOI: 10.1016/j.cagd.2020.101817]
Hu L C and Shou H H. 2016. Particle swarm optimization algorithm for B-spline curve approximation with normal constraint. Journal of Computer-Aided Design and Computer Graphics, 28(9): 1443-1450
胡良臣, 寿华好. 2016. PSO求解带法向约束的B样条曲线逼近问题. 计算机辅助设计与图形学学报, 28(9): 1443-1450 [DOI: 10.3969/j.issn.1003-9775.2016.09.006]
Hu Q L and Shou H H. 2014. Cubic uniform B-spline curves interpolation with normal constrains. Journal of Zhejiang University (Science Edition), 41(6): 619-623
胡巧莉, 寿华好. 2014. 带法向约束的3次均匀B样条曲线插值. 浙江大学学报(理学版), 41(6): 619-623) [DOI: 10.3785/j.issn.1008-9497.2014.06.002]
Lin H W. 2012. Adaptive data fitting by the progressive-iterative approximation. Computer Aided Geometric Design, 29(7): 463-473 [DOI: 10.1016/j.cagd.2012.03.005]
Lin H W and Zhang Z Y. 2013. An efficient method for fitting large data sets using T-splines. SIAM Journal on Scientific Computing, 35(6): A3052-A3068 [DOI: 10.1137/120888569]
Liu Y, Song Y Z, Yang Z W and Deng J S. 2017. Implicit surface reconstruction with total variation regularization. Computer Aided Geometric Design, 52-53: 135-153 [DOI: 10.1016/j.cagd.2017.02.005]
Lu Z H, Jiang X, Huo G Y, Ye D L, Wang B L and Zheng Z M. 2020. A fast T-spline fitting method based on efficient region segmentation. Computational and Applied Mathematics, 39(2): #55 [DOI: 10.1007/s40314-020-1071-6]
Sederberg T W, Cardon D L, Finnigan G T, North N S, Zheng J M and Lyche T. 2004. T-spline simplification and local refinement. ACM Transactions on Graphics, 23(3): 276-283 [DOI: 10.1145/1015706.1015715]
Sederberg T W, Zheng J M, Bakenov A and Nasri A. 2003. T-splines and T-NURCCs. ACM Transactions on Graphics, 22(3): 477-484 [DOI: 10.1145/882262.882295]
Tang Y H, Li X J, Cheng Z M and Qian M F. 2011. Closed surface reconstruction based on implicit T-splines. Journal of Computer-Aided Design and Computer Graphics, 23(2): 270-275
唐月红, 李秀娟, 程泽铭, 钱明凤. 2011. 隐式T样条实现封闭曲面重建. 计算机辅助设计与图形学学报, 23(2): 270-275
Tong W H, Feng Y Y and Chen F L. 2006. A surface reconstruction algorithm based on implicit T-spline surfaces. Journal of Computer-Aided Design and Computer Graphics, 18(3): 358-365
童伟华, 冯玉瑜, 陈发来. 2006. 基于隐式T样条的曲面重构算法. 计算机辅助设计与图形学学报, 18(3): 358-365) [DOI: 10.3321/j.issn:1003-9775.2006.03.006]
Várady T, Martin R R and Cox J. 1997. Reverse engineering of geometric models——an introduction. Computer-Aided Design, 29(4): 255-268 [DOI: 10.1016/S0010-4485(96)00054-1]
Wang Y M and Zheng J M. 2007. Adaptive T-spline surface approximation of triangular meshes//Proceedings of the 6th International Conference on Information, Communications and Signal Processing. Singapore, Singapore: IEEE: 1-5 [ DOI: 10.1109/ICICS.2007.4449775 http://dx.doi.org/10.1109/ICICS.2007.4449775 ]
Wang Y M and Zheng J M. 2013. Curvature-guided adaptive T-spline surface fitting. Computer-Aided Design, 45(8/9): 1095-1107 [DOI: 10.1016/j.cad.2013.04.006]
Yang Z W, Deng J S and Chen F L. 2005. Fitting unorganized point clouds with active implicit B-spline curves. The Visual Computer, 21(8/10): 831-839 [DOI: 10.1007/s00371-005-0340-0]
Zheng J M, Wang Y M and Seah H S. 2005. Adaptive T-spline surface fitting to z-map models//Proceedings of the 3rd International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia. Dunedin, New Zealand: ACM: 405-411 [ DOI: 10.1145/1101389.1101468 http://dx.doi.org/10.1145/1101389.1101468 ]
相关文章
相关作者
相关机构
京公网安备11010802024621
