基于特征分析的三角网格模型区域划分技术研究
|
摘要
基于测量数据的曲面重建在产品开发、计算机视觉、医学图像重建等领域都有着广泛的应用。任意拓扑三角网格模型的区域划分是复杂曲面重建中的关键和难点问题之一，本文对此进行了研究，主要工作如下：
研究了三角网格模型上顶点曲率的估算方法，并用参数曲面的网格模型验证了曲率估算的精度。
研究了三角网格模型的N边界区域生成方法。研究并实现了三角网格模型的数据分块算法，在分块结果的基础上建立了N边界区域结构，该结构易于编辑和维护，为开发用户交互操作功能和进行四边界区域划分提供了很好的基础。
研究了三角网格模型的四边界区域划分技术。提出了一种计算网格模型上两点间最短距离的方法，该方法简单有效且计算速度较快；建立了一种用于优化网格曲面特征线的Snake模型，生成的特征曲线既光滑又能较好地逼近模型特征，并能满足描述区域边界的要求；提供了一种交互的编辑手段，用户能够在N边界区域的基础上较方便地生成四边界区域，区域划分结果很好地反映了原有样件的构造特点。
Surface reconstruction based on coordinate measuring is widely used in such areas as product development, computer vision and reconstruction of medical image. Region partitioning of arbitrary triangle mesh, one of the critical and difficult problems in the complicated surface reconstruction, is researched in this thesis. The main contents are as follows:
A vertex curvature estimation method for triangle mesh is researched and the accuracy of curvature estimation is verified by parameter surfaces.
A method of N-sided region partitioning based on data segmentation for triangle mesh is researched. The data structure used to express N-sided region is easy to edit and maintain, which provides good basis for developing interactive operation functions and partitioning quadrilateral region.
A method of quadrilateral region partitioning of triangle mesh is put forward. A simple and effective method with rapid calculation is proposed to compute the shortest route between two points of the mesh. A snake model is constructed to optimize feature lines on triangle mesh. The optimized feature lines are not only smooth but also well approximate to the features of model. In addition, they can describe the boundary of quadrilateral region. An interactive editing means is provided to transform N-sided region to quadrilateral region conveniently. The result of quadrilateral region partitioning reflects the construction character of original part very well.
研究了三角网格模型上顶点曲率的估算方法，并用参数曲面的网格模型验证了曲率估算的精度。
研究了三角网格模型的N边界区域生成方法。研究并实现了三角网格模型的数据分块算法，在分块结果的基础上建立了N边界区域结构，该结构易于编辑和维护，为开发用户交互操作功能和进行四边界区域划分提供了很好的基础。
研究了三角网格模型的四边界区域划分技术。提出了一种计算网格模型上两点间最短距离的方法，该方法简单有效且计算速度较快；建立了一种用于优化网格曲面特征线的Snake模型，生成的特征曲线既光滑又能较好地逼近模型特征，并能满足描述区域边界的要求；提供了一种交互的编辑手段，用户能够在N边界区域的基础上较方便地生成四边界区域，区域划分结果很好地反映了原有样件的构造特点。
Surface reconstruction based on coordinate measuring is widely used in such areas as product development, computer vision and reconstruction of medical image. Region partitioning of arbitrary triangle mesh, one of the critical and difficult problems in the complicated surface reconstruction, is researched in this thesis. The main contents are as follows:
A vertex curvature estimation method for triangle mesh is researched and the accuracy of curvature estimation is verified by parameter surfaces.
A method of N-sided region partitioning based on data segmentation for triangle mesh is researched. The data structure used to express N-sided region is easy to edit and maintain, which provides good basis for developing interactive operation functions and partitioning quadrilateral region.
A method of quadrilateral region partitioning of triangle mesh is put forward. A simple and effective method with rapid calculation is proposed to compute the shortest route between two points of the mesh. A snake model is constructed to optimize feature lines on triangle mesh. The optimized feature lines are not only smooth but also well approximate to the features of model. In addition, they can describe the boundary of quadrilateral region. An interactive editing means is provided to transform N-sided region to quadrilateral region conveniently. The result of quadrilateral region partitioning reflects the construction character of original part very well.
引文
[1] 刘之生．逆向工程技术[M]．北京，机械工业出版社，1996
[2] V(?)rady T, Martin R, Cox J. Reverse engineering of geometric models—an introduction [J]. Computer-Aided Design, 1997, 29(4): 255-268.
[3] 张丽艳．逆向工程中模型重建关键技术研究[学位论文]．南京：南京航空航天大学，2001
[4] Milroy M J, Bradley C, Vickers G W. Segmentation of a wrap-around model using an active contour[J], Computer Aided Designed, 1997, 29(4): 299-320.
[5] Huang J, Menq C H. Automatic Data Segmentation for Geometric Feature Extraction from Unorganized 3-D Coordinate Points[J]. IEEE Transactions on Robotics and Automation, 2001, 17(3): 268-279.
[6] Woo H, Kang E, Lee K H. Segmentation of point cloud data using 3D grids[C]. Scanning Congress 2001: Numerization 3D session, Paris, France, April 4-5, 2001.
[7] Besl P J, Jain R C. Segmentation Through Variable-Order Surface Fitting[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1988,10(2): 167-192.
[8] Sapidis N S, Besl P J. Direct construction of polynomal Surfaces from dense range images through region growing[J]. ACM Transactions on Graphics, 1995,14(2): 171-200
[9] Chen Y H, Liu C Y. Quadric surface extraction using genetic algorithms[J]. Computer Aided Designed, 1999, 31(2): 101-110
[10] Yokoya N, Levine M D. Range Image Segmentation Based on differential geometry: a hybrid approach[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1989, 11(6): 644-649
[11] Guo B. Surface reconstruction: from points to splines[J]. Computer-Aided Design. 1997,29(4): 269-277
[12] Eck M, Hoppe H. Automatic reconstruction of B-spline surfaces of arbitrary topological type. SIGGRAPH'96 Proceedings, 325-333.
[13] Ma W, Kruth J P. Parametrization of randomly measured points for least squares fitting of B-spline curves and surfaces[J]. Computer-Aided Design, 1995,27(9): 663-675
[14] Floater M S. Parametrization and smooth approximation of surface triangulations[J]. Computer-Aided Design. 1997,14(3): 231-250
[15] Krishnamurthy V, Levoy M. Fitting smooth surfaces to dense polygon meshes. Computer Graphics (SIGGRAPH'96 Proceedings), 30, 1996, 313-324.
[16] 陈吉象．代数拓扑基础定义[M]．北京，高等教育出版社，1987，第一版
[17] F．P．普雷帕拉塔，M．I．沙莫斯著．庄心谷译．计算几何导论[M]．北京，科学出版社，1990，第一版 ．
[18] 王耕禄．线性代数[M]．北京，北京理工大学出版社，1992，第一版
[19] 唐杰．逆向工程中三角网格模型的数据处理技术研究[学位论文]．南京：南京航空航天大学，2000．1
[20] Taubin G. Estimating the tensor of curvature of a surface from a polyhedral approximation[C] Fifth International Conference on Computer Vision, June.20-23,1995. Massachusetts Institute of Technology, Cambridge, Massachusetts.
[21] Huang J, Menq C H. Combinatorial manifold mesh reconstruction and optimation from unorganized points with arbitrary topology[J] Computer-Aided Design,2002,34(2): 149-165
[22] Meyer M, Desbrun M, schroder P, Barr A. Discrete differential-geometry operators for triangulated 2-manifolds, In: VisMath'02, Berlin, Germany, 2002
[23] Hamann B. Curvature approximation for triangulated surfaces, In: G. Farin et al.,editor, Geometric Modelling, Springer Verlag, 1993: 139-153
[24] Kresk P, Pajdla T, Hlavac V. Estimation of dierential parameters on triangulated surface. In 21st Workshop of the Austrian Association for Pattern Recognition, May 1997
[25] Welch W, Wikin A. Free-from shape design using triangulated surfaces. In:SIGGRAPH 94 Conference Proceedings, Orlando Florida, 1994:247-256
[26] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization[J]. Computer Graphics 1993, 27(3): 19～26
[27] 杨文茂，李全英．空间解析几何[M]．武汉，武汉大学出版社，1997
[28] http://mathworld.wolfram.com/catenoid.html
[29] 柯映林．离散数据的几何造型技术及其应用研究[学位论文]．南京：南京航空航天大学，1991．9
[30] 朱心雄．自由曲线曲面造型技术[M]．北京，科学出版社，2000
[31] 蔡利栋．关于KH和KJ符号图的一些注解[J]．中国图像图形学报，1998,7(3)：562-564
[32] Ma Weiyin, Chu Koon-yan. Extracting geometric features from a virtual environment[J]. Journal of Materials Processing Technology, 2000,107(1):24-30
[33] Rossl C, Kobbelt L and Seidel H. Extraction of feature lines on triangulated surfaces using morphological operators[C]. Smart Graphics, Proceedings of the 2000 AAAI Symposium, AAAI Press, 2000:71-75
[34] Ohtake Y, Belyaev A: Automatic detection of geodesic ridges and ravines on polygonal surfaces[J]. The Journal of Three Dimensional Images, 2001, 15(1):127-132
[35] Sharir M, Schorr A. On shortest path in polyhedron space. SIAM J Computing,1986,15:193-215
[36] Chen J, Han Y. Shortest path on approximate shortest path on the polyhedron. Proc Sixth ACM Symposium on Computer Geometry, Berkley, USA, June 1990,17:360-369
[37] T. Kanai and H. Suzuki, Approximate shortest path on a polyhedral surface and its applications[J]. Computer Aided Design, 2001,33(11): 801-811
[38] 张丽艳，吴熹．三角网格模型上任意两点间的近似最短路径算法研究[J]，计算机辅助设计与图形学学报，2003，15(5)：592-597
[39] Faugeras O, Hebert M, Mussi P, Boissonnat J. Polyhedral approximation of 3-D objects without holes[J].Computer Vision, Graphics, and Image Processing,1984,25:169-183
[40] Kass M, Witkin A, and Terzopouls D, Snakes: Active Contour Models[J] Internation Journal of Computer Vision, 1988,1(4): 321-331
[41] 杨杨，张田文．一种新的主动轮廓线跟踪算法[J]，计算机学报，增刊，1988，21(8)：297-302
[42] 李培华，张田文．主动轮廓线模型(蛇模型)综述[J]，软件学报，2000，11(6)：751-757
[43] Lee Y, Lee S. Geometric snakes for triangular meshes[C]. Computer Graphics Forum (Eurographics 2002), 2002, 21(3): 229-238
[2] V(?)rady T, Martin R, Cox J. Reverse engineering of geometric models—an introduction [J]. Computer-Aided Design, 1997, 29(4): 255-268.
[3] 张丽艳．逆向工程中模型重建关键技术研究[学位论文]．南京：南京航空航天大学，2001
[4] Milroy M J, Bradley C, Vickers G W. Segmentation of a wrap-around model using an active contour[J], Computer Aided Designed, 1997, 29(4): 299-320.
[5] Huang J, Menq C H. Automatic Data Segmentation for Geometric Feature Extraction from Unorganized 3-D Coordinate Points[J]. IEEE Transactions on Robotics and Automation, 2001, 17(3): 268-279.
[6] Woo H, Kang E, Lee K H. Segmentation of point cloud data using 3D grids[C]. Scanning Congress 2001: Numerization 3D session, Paris, France, April 4-5, 2001.
[7] Besl P J, Jain R C. Segmentation Through Variable-Order Surface Fitting[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1988,10(2): 167-192.
[8] Sapidis N S, Besl P J. Direct construction of polynomal Surfaces from dense range images through region growing[J]. ACM Transactions on Graphics, 1995,14(2): 171-200
[9] Chen Y H, Liu C Y. Quadric surface extraction using genetic algorithms[J]. Computer Aided Designed, 1999, 31(2): 101-110
[10] Yokoya N, Levine M D. Range Image Segmentation Based on differential geometry: a hybrid approach[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1989, 11(6): 644-649
[11] Guo B. Surface reconstruction: from points to splines[J]. Computer-Aided Design. 1997,29(4): 269-277
[12] Eck M, Hoppe H. Automatic reconstruction of B-spline surfaces of arbitrary topological type. SIGGRAPH'96 Proceedings, 325-333.
[13] Ma W, Kruth J P. Parametrization of randomly measured points for least squares fitting of B-spline curves and surfaces[J]. Computer-Aided Design, 1995,27(9): 663-675
[14] Floater M S. Parametrization and smooth approximation of surface triangulations[J]. Computer-Aided Design. 1997,14(3): 231-250
[15] Krishnamurthy V, Levoy M. Fitting smooth surfaces to dense polygon meshes. Computer Graphics (SIGGRAPH'96 Proceedings), 30, 1996, 313-324.
[16] 陈吉象．代数拓扑基础定义[M]．北京，高等教育出版社，1987，第一版
[17] F．P．普雷帕拉塔，M．I．沙莫斯著．庄心谷译．计算几何导论[M]．北京，科学出版社，1990，第一版 ．
[18] 王耕禄．线性代数[M]．北京，北京理工大学出版社，1992，第一版
[19] 唐杰．逆向工程中三角网格模型的数据处理技术研究[学位论文]．南京：南京航空航天大学，2000．1
[20] Taubin G. Estimating the tensor of curvature of a surface from a polyhedral approximation[C] Fifth International Conference on Computer Vision, June.20-23,1995. Massachusetts Institute of Technology, Cambridge, Massachusetts.
[21] Huang J, Menq C H. Combinatorial manifold mesh reconstruction and optimation from unorganized points with arbitrary topology[J] Computer-Aided Design,2002,34(2): 149-165
[22] Meyer M, Desbrun M, schroder P, Barr A. Discrete differential-geometry operators for triangulated 2-manifolds, In: VisMath'02, Berlin, Germany, 2002
[23] Hamann B. Curvature approximation for triangulated surfaces, In: G. Farin et al.,editor, Geometric Modelling, Springer Verlag, 1993: 139-153
[24] Kresk P, Pajdla T, Hlavac V. Estimation of dierential parameters on triangulated surface. In 21st Workshop of the Austrian Association for Pattern Recognition, May 1997
[25] Welch W, Wikin A. Free-from shape design using triangulated surfaces. In:SIGGRAPH 94 Conference Proceedings, Orlando Florida, 1994:247-256
[26] Hoppe H, DeRose T, Duchamp T, et al. Mesh optimization[J]. Computer Graphics 1993, 27(3): 19～26
[27] 杨文茂，李全英．空间解析几何[M]．武汉，武汉大学出版社，1997
[28] http://mathworld.wolfram.com/catenoid.html
[29] 柯映林．离散数据的几何造型技术及其应用研究[学位论文]．南京：南京航空航天大学，1991．9
[30] 朱心雄．自由曲线曲面造型技术[M]．北京，科学出版社，2000
[31] 蔡利栋．关于KH和KJ符号图的一些注解[J]．中国图像图形学报，1998,7(3)：562-564
[32] Ma Weiyin, Chu Koon-yan. Extracting geometric features from a virtual environment[J]. Journal of Materials Processing Technology, 2000,107(1):24-30
[33] Rossl C, Kobbelt L and Seidel H. Extraction of feature lines on triangulated surfaces using morphological operators[C]. Smart Graphics, Proceedings of the 2000 AAAI Symposium, AAAI Press, 2000:71-75
[34] Ohtake Y, Belyaev A: Automatic detection of geodesic ridges and ravines on polygonal surfaces[J]. The Journal of Three Dimensional Images, 2001, 15(1):127-132
[35] Sharir M, Schorr A. On shortest path in polyhedron space. SIAM J Computing,1986,15:193-215
[36] Chen J, Han Y. Shortest path on approximate shortest path on the polyhedron. Proc Sixth ACM Symposium on Computer Geometry, Berkley, USA, June 1990,17:360-369
[37] T. Kanai and H. Suzuki, Approximate shortest path on a polyhedral surface and its applications[J]. Computer Aided Design, 2001,33(11): 801-811
[38] 张丽艳，吴熹．三角网格模型上任意两点间的近似最短路径算法研究[J]，计算机辅助设计与图形学学报，2003，15(5)：592-597
[39] Faugeras O, Hebert M, Mussi P, Boissonnat J. Polyhedral approximation of 3-D objects without holes[J].Computer Vision, Graphics, and Image Processing,1984,25:169-183
[40] Kass M, Witkin A, and Terzopouls D, Snakes: Active Contour Models[J] Internation Journal of Computer Vision, 1988,1(4): 321-331
[41] 杨杨，张田文．一种新的主动轮廓线跟踪算法[J]，计算机学报，增刊，1988，21(8)：297-302
[42] 李培华，张田文．主动轮廓线模型(蛇模型)综述[J]，软件学报，2000，11(6)：751-757
[43] Lee Y, Lee S. Geometric snakes for triangular meshes[C]. Computer Graphics Forum (Eurographics 2002), 2002, 21(3): 229-238