逆向工程中数据分块和规则曲面拟合算法的研究
|
摘要
我国航空工业对逆向工程技术有着迫切的需求。本文在理解产品设计意图的思路下，研究了结构件CAD模型重建中的数据分块技术和曲面拟合算法。完成的主要工作如下：
对结构件建模中所遇到的各类特征、特征间的约束进行了详细的分类，并给出由规则曲面组成的结构件CAD模型的约束方程。
逆向工程中，数据分块是一个非常关键的环节。本文借鉴特征分块的思想和八叉树的理论，利用八叉树元格的逐步细分实现点云的分块；然后基于元格点域的法矢和曲率，通过八叉树的回溯，完成各局部区域块的识别；最后按照规则曲面、扫掠曲面、自由曲面的顺序进行特征的自动识别。
研究了规则曲面的拟合算法，给出最小二乘法拟合平面、球面、圆柱面、圆锥面、圆环面等规则曲面的方法，这些方法的显著优点是提高了计算效率，避免了拟合过程中奇异点的影响。
With the development of aviation industry in our country, the application of reverse engineering in CAD/CAM becomes more widely and important than ever. Based on capturing designers' intentions, this thesis studies segmentation of point clouct-and fitting of regular surfaces (including planes, spheres, cylinders, cones, tori, etc.) in structural parts modeling. The main work is as follows:
Features and constraints in the reconstruction of CAD models are classfied in detail, and the constraint equations about structural parts constituted by regular surfaces are given.
Data segmentation that extracts the edges and partitions point cloud plays an important role in reverse engineering. This thesis proposes an octree-based 3D-cell subdivision method for data segmentation. Firstly, the final 3D-cells are constructed through a refinement process and iterative subdivision of cells. Then, based on normals or curvatures of cells, this method identifies local surface parts through backdating octree. Lastly, feature recognition is implemented automatically according to the sequence of regular surfaces, swept surfaces and free-form surfaces.
The least-squares fitting for regular surfaces, such as planes, spheres, cones, tori to 3D data points is researched. The efficiency of computing is improved greatly and the effect of singularities on fitting is avoided.
对结构件建模中所遇到的各类特征、特征间的约束进行了详细的分类，并给出由规则曲面组成的结构件CAD模型的约束方程。
逆向工程中，数据分块是一个非常关键的环节。本文借鉴特征分块的思想和八叉树的理论，利用八叉树元格的逐步细分实现点云的分块；然后基于元格点域的法矢和曲率，通过八叉树的回溯，完成各局部区域块的识别；最后按照规则曲面、扫掠曲面、自由曲面的顺序进行特征的自动识别。
研究了规则曲面的拟合算法，给出最小二乘法拟合平面、球面、圆柱面、圆锥面、圆环面等规则曲面的方法，这些方法的显著优点是提高了计算效率，避免了拟合过程中奇异点的影响。
With the development of aviation industry in our country, the application of reverse engineering in CAD/CAM becomes more widely and important than ever. Based on capturing designers' intentions, this thesis studies segmentation of point clouct-and fitting of regular surfaces (including planes, spheres, cylinders, cones, tori, etc.) in structural parts modeling. The main work is as follows:
Features and constraints in the reconstruction of CAD models are classfied in detail, and the constraint equations about structural parts constituted by regular surfaces are given.
Data segmentation that extracts the edges and partitions point cloud plays an important role in reverse engineering. This thesis proposes an octree-based 3D-cell subdivision method for data segmentation. Firstly, the final 3D-cells are constructed through a refinement process and iterative subdivision of cells. Then, based on normals or curvatures of cells, this method identifies local surface parts through backdating octree. Lastly, feature recognition is implemented automatically according to the sequence of regular surfaces, swept surfaces and free-form surfaces.
The least-squares fitting for regular surfaces, such as planes, spheres, cones, tori to 3D data points is researched. The efficiency of computing is improved greatly and the effect of singularities on fitting is avoided.
引文
[1]金涛，童永光等．逆向工程技术．北京，机械工业出版社，2003
[2]H. James de St. Germain. Reverse engineering utilizing domain specific knowledge [PhD. Thesis]. University of Utah, 2002
[3]李建军，温建勇，肖祥芷．逆向工程及其相关技术．机械与电子，1999(3)：16-18
[4]张舜德，朱东波，卢秉恒．反求工程中三维几何形状测量及数据预处理．机电工程技术，2001年第一期：7-10
[5]张丽艳．逆向工程中模型重建关键技术研究[学位论文]．南京：南京航空航天大学，2001
[6]V?rady T., Martin R. R. and Cox J. Reverse engineering of geometric models-an introduction. Computer-Aided Design, 1997, 29(4), 255-268
[7]Benk(?) P., Martin R. R. and V?rady T. Algorithms for reverse engineering boundary representation Models. Computer-Aided Design, 2001, 33(11), 839-851
[8]Schroeder W., Marin K. and Lorensen B. The Visualization Toolkit: An Object Oriented Approach to 3D Graphics. Prentice Hall, 1997.
[9]Sonka M., Hlavac V. and Boyle R. Image Processing, Analysis and Machine Vision,PWS, 1999.
[10]Woo H., Kang E., Semyung Wang and Kwan H. Lee. A new segmentation method for point cloud data. Machine Tools & Manufacture, 2002, 42:167-178
[11]TienTung Chung and ChaoYaug Liao. An automatic data segmentation method for 3D measured data points. Dept. of Mechanical Engineering National Taiwan University, Taipei, Taiwan
[12]范玉清．现代飞机制造技术．北京，北京航空航天大学出版社，2001
[13]Benk(?) P., Andor L., K?s G. and Martin R. R. Constrained fitting in reverse engineering.Computer Aided Geometric Design, 2002, 19, 173-205
[14]金涛，单岩，童永光．产品反求工程中基于几何特征及约束的模型重建．计算机辅助设计及图形学学报，2001，13(3)，202-207
[15]Vida J., Martin R. R. and Varady T. A survey of blending methods that use parametric surfaces. Computer-Aided Design, Vol 26, No 5, (1994), pp 341-365
[16]Werghi N., Fisher R. B. and Robertson C. Object reconstruction by incorporating geometric constraints in reverse engineering. Computer-Aided Design, 1999,33:363-399
[17]施法中．计算机辅助几何设计与非均匀有理B样条(CAGD&NURBS)．北京，北京航空航天大学出版社，1994
[18]谭昌柏．结构件反求建模中的数据处理技术[学位论文]．南京：南京航空航天大学，2003
[19]朱心雄等．自由曲线曲面造型技术．北京，科学出版社，2000
[20]Yang M. and Lee E. Segmentation of measured data using a parametric quadric surface approximation[J]. Computer Aided Design, 1999, 31 (7): 449-457
[21]Ma W. Y. and Kruth J. P. Parameterization of randomly measured points,for least squares fitting of B-spline curves and surfaces. Computer-Aided Design, 1995,vol 27, no. 9, pp. 663-675.
[22]贺美芳，周来水，朱延娟．基于局部基面参数化的点云数据边界自动提取．机械科学与技术，2003(12)
[23]梅向明，黄敬之．微分几何．北京，高等教育出版社，1988
[24]Besl P. J. and Jain R. C. Segmentation Through Variable-Order Surface Fitting[J].IEEE Transaction on Pattern Analysis and Machine Intelligence, 1988,10(2): 167-192.
[25]刘胜兰，周儒荣，安鲁陵．三角网格模型的数据分块算法．南京航空航天大学学报，2003，35(6)
[26]Thitiwan Srinark and Chandra Kambhamettu. A novel method for 3D surface mesh Segmentation. 6th IASTED International Conference on Computers, Graphics, and Imaging, Honolulu, Hawaii, USA, August 13-15, 2003.
[27]Milroy M. J., Bradley C. and Vickers G. W. Segmentation of a wrap-around model using an active contour[J]. Computer-Aided Designed, 1997, 29(4),299-320
[28]彭群生，鲍虎军，金小刚．计算机真实感图形的算法基础．北京，科学出版社，1999
[29]潘愗，王勇，李魁星，孙世鹏．多解析度八叉树数据结构理论探索与应用．地理与地理信息科学，2003，19(4)：37-40
[30]肖乐斌，龚建华，谢传节．线性四叉树和线性八叉树邻域寻找的一种新算法．测绘学报，1998，27(3)：195-203
[31]黄雪梅，王平江，陈吉红，张新访，周济．三维算乱数据三角形网格逼近的一种算法．计算机工程与设计，1998，19(2)：9-15
[32]Samet H. Neighbor finding in images represented by octrees. Computer Vision,Graphics and Image Processing, 1989, 46:367-386
[33]刘炉山．基于数字化样件的虚拟测量及数据处理技术[学位论文]．南京，南京航空航天大学，2003
[34]王联芳译．直观几何．北京，高等教育出版社，1984
[35]Vanco M. A direct approach for the segmentation of unorganized points and recognition of simple algebraic surfaces[Phd Thesis]. University of Technology Chemnitz, 2002.
[36]Benk(?) P. and V?rady T. Segmenting large point clouds in reverse engineering conventional engineering objects, Proc. First Hungarian Conference on Computer Graphics and Geometry, Eds.: L. Szirmay-Kalos and G. Renner, Budapest, 2002, pp63-69
[37]Pottmann H. and Randrup T. Rotational and helical surface approximation for reverse engineering. Computering, 60(1998), 307-322.
[38]彭雨哟．基于草图轮廓的特征模型重建技术[学位论文]．南京，南京航空航天大学，2004
[39]张池平，施云慧．计算方法．北京：科学出版社，2002．7
[40]王中良．线性代数与解析几何．北京：科学出版社，2000．8
[41]Luk?cs G., Marshall A. D. and Martin R. R. Faithful least-squares-fitting of spheres,cylinders, cones and tori for reliable segmentation. In: Burkhardt H, Neumann B (Eds.), Proc ECCV 98,Lecture Notes in Computer Science, Vol.1. Springer, Berlin,1998,pp. 671-686
[42]袁亚湘，孙文瑜．最优化理论与方法[M]．北京，科学出版社，1997
[43]孟道骥，梁科．微分几何．北京，科学出版社，2002
[2]H. James de St. Germain. Reverse engineering utilizing domain specific knowledge [PhD. Thesis]. University of Utah, 2002
[3]李建军，温建勇，肖祥芷．逆向工程及其相关技术．机械与电子，1999(3)：16-18
[4]张舜德，朱东波，卢秉恒．反求工程中三维几何形状测量及数据预处理．机电工程技术，2001年第一期：7-10
[5]张丽艳．逆向工程中模型重建关键技术研究[学位论文]．南京：南京航空航天大学，2001
[6]V?rady T., Martin R. R. and Cox J. Reverse engineering of geometric models-an introduction. Computer-Aided Design, 1997, 29(4), 255-268
[7]Benk(?) P., Martin R. R. and V?rady T. Algorithms for reverse engineering boundary representation Models. Computer-Aided Design, 2001, 33(11), 839-851
[8]Schroeder W., Marin K. and Lorensen B. The Visualization Toolkit: An Object Oriented Approach to 3D Graphics. Prentice Hall, 1997.
[9]Sonka M., Hlavac V. and Boyle R. Image Processing, Analysis and Machine Vision,PWS, 1999.
[10]Woo H., Kang E., Semyung Wang and Kwan H. Lee. A new segmentation method for point cloud data. Machine Tools & Manufacture, 2002, 42:167-178
[11]TienTung Chung and ChaoYaug Liao. An automatic data segmentation method for 3D measured data points. Dept. of Mechanical Engineering National Taiwan University, Taipei, Taiwan
[12]范玉清．现代飞机制造技术．北京，北京航空航天大学出版社，2001
[13]Benk(?) P., Andor L., K?s G. and Martin R. R. Constrained fitting in reverse engineering.Computer Aided Geometric Design, 2002, 19, 173-205
[14]金涛，单岩，童永光．产品反求工程中基于几何特征及约束的模型重建．计算机辅助设计及图形学学报，2001，13(3)，202-207
[15]Vida J., Martin R. R. and Varady T. A survey of blending methods that use parametric surfaces. Computer-Aided Design, Vol 26, No 5, (1994), pp 341-365
[16]Werghi N., Fisher R. B. and Robertson C. Object reconstruction by incorporating geometric constraints in reverse engineering. Computer-Aided Design, 1999,33:363-399
[17]施法中．计算机辅助几何设计与非均匀有理B样条(CAGD&NURBS)．北京，北京航空航天大学出版社，1994
[18]谭昌柏．结构件反求建模中的数据处理技术[学位论文]．南京：南京航空航天大学，2003
[19]朱心雄等．自由曲线曲面造型技术．北京，科学出版社，2000
[20]Yang M. and Lee E. Segmentation of measured data using a parametric quadric surface approximation[J]. Computer Aided Design, 1999, 31 (7): 449-457
[21]Ma W. Y. and Kruth J. P. Parameterization of randomly measured points,for least squares fitting of B-spline curves and surfaces. Computer-Aided Design, 1995,vol 27, no. 9, pp. 663-675.
[22]贺美芳，周来水，朱延娟．基于局部基面参数化的点云数据边界自动提取．机械科学与技术，2003(12)
[23]梅向明，黄敬之．微分几何．北京，高等教育出版社，1988
[24]Besl P. J. and Jain R. C. Segmentation Through Variable-Order Surface Fitting[J].IEEE Transaction on Pattern Analysis and Machine Intelligence, 1988,10(2): 167-192.
[25]刘胜兰，周儒荣，安鲁陵．三角网格模型的数据分块算法．南京航空航天大学学报，2003，35(6)
[26]Thitiwan Srinark and Chandra Kambhamettu. A novel method for 3D surface mesh Segmentation. 6th IASTED International Conference on Computers, Graphics, and Imaging, Honolulu, Hawaii, USA, August 13-15, 2003.
[27]Milroy M. J., Bradley C. and Vickers G. W. Segmentation of a wrap-around model using an active contour[J]. Computer-Aided Designed, 1997, 29(4),299-320
[28]彭群生，鲍虎军，金小刚．计算机真实感图形的算法基础．北京，科学出版社，1999
[29]潘愗，王勇，李魁星，孙世鹏．多解析度八叉树数据结构理论探索与应用．地理与地理信息科学，2003，19(4)：37-40
[30]肖乐斌，龚建华，谢传节．线性四叉树和线性八叉树邻域寻找的一种新算法．测绘学报，1998，27(3)：195-203
[31]黄雪梅，王平江，陈吉红，张新访，周济．三维算乱数据三角形网格逼近的一种算法．计算机工程与设计，1998，19(2)：9-15
[32]Samet H. Neighbor finding in images represented by octrees. Computer Vision,Graphics and Image Processing, 1989, 46:367-386
[33]刘炉山．基于数字化样件的虚拟测量及数据处理技术[学位论文]．南京，南京航空航天大学，2003
[34]王联芳译．直观几何．北京，高等教育出版社，1984
[35]Vanco M. A direct approach for the segmentation of unorganized points and recognition of simple algebraic surfaces[Phd Thesis]. University of Technology Chemnitz, 2002.
[36]Benk(?) P. and V?rady T. Segmenting large point clouds in reverse engineering conventional engineering objects, Proc. First Hungarian Conference on Computer Graphics and Geometry, Eds.: L. Szirmay-Kalos and G. Renner, Budapest, 2002, pp63-69
[37]Pottmann H. and Randrup T. Rotational and helical surface approximation for reverse engineering. Computering, 60(1998), 307-322.
[38]彭雨哟．基于草图轮廓的特征模型重建技术[学位论文]．南京，南京航空航天大学，2004
[39]张池平，施云慧．计算方法．北京：科学出版社，2002．7
[40]王中良．线性代数与解析几何．北京：科学出版社，2000．8
[41]Luk?cs G., Marshall A. D. and Martin R. R. Faithful least-squares-fitting of spheres,cylinders, cones and tori for reliable segmentation. In: Burkhardt H, Neumann B (Eds.), Proc ECCV 98,Lecture Notes in Computer Science, Vol.1. Springer, Berlin,1998,pp. 671-686
[42]袁亚湘，孙文瑜．最优化理论与方法[M]．北京，科学出版社，1997
[43]孟道骥，梁科．微分几何．北京，科学出版社，2002