基于骨架图的曲面四边形剖分算法
摘要
近年来,三维网格模型的曲面四边形分割日益受到人们的重视,但由于三维网格模型的复杂性和多样性,各种直接针对表面网格进行处理的四边形分割算法多数着力于几何(形状)性质的优化,而忽略了组合(拓扑)性质；另外的少数算法则主要满足组合(拓扑)方面的某些约束,而不考虑几何形状的好坏。本文提出了一种由骨架图分割得到相匹配的模型四边形分割的新方法,是一种获得同时具有较好的拓扑和几何性质的四边形分割的有效可行的方法。
本文首先简单介绍了几种常见的曲面四边形分割方法,同时对三维网格曲面分割的发展现状进行了综述；然后本文改进了三角网格模型骨架的提取算法,即细化算法,提出了一种通过解二维线性方程组的体素化方法,简化了简单点的判定准则；然后通过对骨架图的编辑和H型分割,进而将三维模型曲面分割为T-shirt型或者Pants型曲面,为进一步获取高质量的曲面四边形剖分提供了基础；最后本文提出一种基于T-shirt型和Pants型曲面的四边形分割方法,同时满足组合(拓扑)方面的某些约束,为进一步几何优化的灵活性提供了条件。本文中各个算法均在MFC+OpenGL平台上编程实现,并给出了详细的数值实验分析。
Mesh quadrangulation has received increasing attention in the past decade. Because of the complexity and diversity of the three-dimensional mesh, the majority of quadrangular segmentation algorithms focused on the geometry optimization, while ignoring the topological properties; others focused on the topological properties, while ignoring the geometry properties. This paper presents a new quadrangular segmentation algorithm based on skeleton, which get combinatorial optimization in both topology and geometry.
Firstly, we review the development of three-dimensional mesh segmentation, and introduce several common quadrangular segmentation algorithms. Secondly, this paper improves the three dimensional model skeletonization algorithm, presents a new voxelization method, which based on solving system of linear equations. Thirdly, By editing and H-type segmentation of skeleton graph, three-dimensional model is splited into the T-shirt type and the Pants type of surface. Finally, we propose a quadrangular segmentation method based on the surface of the T-shirt and Pants type, while meeting the constraint condition of topology, which provides the conditions for the flexibility of geometry optimization. In this paper, numerical experiments of algorithms are done on MFC+OpenGL platform.
本文首先简单介绍了几种常见的曲面四边形分割方法,同时对三维网格曲面分割的发展现状进行了综述；然后本文改进了三角网格模型骨架的提取算法,即细化算法,提出了一种通过解二维线性方程组的体素化方法,简化了简单点的判定准则；然后通过对骨架图的编辑和H型分割,进而将三维模型曲面分割为T-shirt型或者Pants型曲面,为进一步获取高质量的曲面四边形剖分提供了基础；最后本文提出一种基于T-shirt型和Pants型曲面的四边形分割方法,同时满足组合(拓扑)方面的某些约束,为进一步几何优化的灵活性提供了条件。本文中各个算法均在MFC+OpenGL平台上编程实现,并给出了详细的数值实验分析。
Mesh quadrangulation has received increasing attention in the past decade. Because of the complexity and diversity of the three-dimensional mesh, the majority of quadrangular segmentation algorithms focused on the geometry optimization, while ignoring the topological properties; others focused on the topological properties, while ignoring the geometry properties. This paper presents a new quadrangular segmentation algorithm based on skeleton, which get combinatorial optimization in both topology and geometry.
Firstly, we review the development of three-dimensional mesh segmentation, and introduce several common quadrangular segmentation algorithms. Secondly, this paper improves the three dimensional model skeletonization algorithm, presents a new voxelization method, which based on solving system of linear equations. Thirdly, By editing and H-type segmentation of skeleton graph, three-dimensional model is splited into the T-shirt type and the Pants type of surface. Finally, we propose a quadrangular segmentation method based on the surface of the T-shirt and Pants type, while meeting the constraint condition of topology, which provides the conditions for the flexibility of geometry optimization. In this paper, numerical experiments of algorithms are done on MFC+OpenGL platform.
引文
[1]H. Blum. A Transformation for Extracting New Descriptors-of Shape. Models for the Perception of Speech and Visual Form. W. Walthen-Dune, ed.,1967.
[2]胡恩球,张新访,向文等.有限元网格生成方法发展综述.计算机辅助设计与图形学学报.1997,9(4)：378-383.
[3]Petersen S. B, Rodrigues J. M. C, Martins P. A. F. Automatic generation of quadrilateral meshes for the finite element analysis of metal forming processes. Finite Elements in Analysis and Design 2000,35:157-168.
[4]Peggy L. Baehmann, Scott L. Wittchen, Mark S. Shephard, Kurt R. Grice, Mark A. Yerry. Robust, geometrically based, automatic two-dimensional mesh generation[J]. International Jounral for Numercial Methods in Engineering,1987, 24:1043-1078.
[5]J. A. Talbert and A. R. Parkinson. Development of an automatic, two dimensional finite element mesh generator using quadrilateral elements and Bezier curve boundary definition[J]. Int. J. Numer Meth. Engng.1991,29:1551-1567.
[6]刘阳.二维四边形网格生成技术的研究[D].杭州：浙江大学,2005.
[7]郭晓霞.四边形有限元网格划分方法—二分法的改进[J].塑性工程学报,2005,12(5)：96-100.
[8]Zhu, J. Z.,O. C. Zienkiewicz, E. Hinton et al. A new approach to the development of automatic quadrilateral mesh generation[J]. Int. J. Numer Meth. Engng.1991, 32:849-866.
[9]T. D. Blacker, M. B. Stephenson. Paving:A new approach to automated quadrilateral mesh generation[J]. International Jounral for Numercial Methods in Engineering, 1991.32:811-847.
[10]R. J. Cass, S.E. Benzley, R.J. Meyers, T. D. Blacker. Generalized 3-D paving:An Automated Quadrilateral Surface Mesh Geneartion Algorithm[J]. International Jounral for Numercial Methods in Engineering,1996,39:1475-1489.
[11]David R. White, Paul Kinney. Redesign of the Paving Algorithm:Robustness Enhancements Through Element by Element Meshing[J]. Peceeding international Meshing Roundtabel, Snadia National Laboratories,1997,323-335.
[12]S. H. Lo. Generating Quadrilateral Elements on Plane and Over Curved Surfaces[J]. Computers and Structures.1981,31(3):421-426.
[13]B. P. Johnston, John M. Sullivan Jr, A. Kwasnik. Automatic Conversion of Triangular Finite Element Meshes to Quadrilateral Elements [J]. Int. J. Numer beth. Engng.1991, 31:67-84.
[14]C. K Lee. S. n. Lo. A New Scheme for the Generation of a Graded Quadrilateral Mesh[J]. Computers and Structures.1994,52:847-857.
[15]Owen SJ, Staten ML, Canann SA, Saigal S. Advancing Front Quadrilateral Meshing Using Local Triangle Transformations[C], Proceedings of the 7th International Meshing Roundtable,1998, P.409-28
[16]林胜良,方兴,张武,王正光.一种改进的高品质全四边形网格生成方法[J].江南大学学报.2006.5(1).70-73.
[17]顾元宪,马正阳,关振群.平面任意区域四边形网格自动生成的一种方法[J].计算机辅助设计与图形学学报.1998,10(5)：432-439.
[18]Cendes Z J, Shenton D, Shahnasser H. Magnetic field computation using Delaunay triangulation and complementary finite element methods [J]. IEEE Trans Mag,1983,19 (6):2551-2557.
[19]胡向红,陈康宁.由区域生长算法实现四边形网格划分[J].计算机辅助设计与图形学学报.2004.16(1)：29-34.
[20]B. Levy, S. Petitjean, N. Ray, and J. Maillot. Least squares conformal maps for automatic texture atlas generation. In Proceedings of SIGGRAPH 2002, pages 362-371. ACM SIGGRAPH,2002.
[21]Sander P V, Snyder J, Gorter S J, Hoppe H. Texture Mapping Progressive Meshes[C]. IN Proceedings of SIGGRAPH 2001. New York. USA:ACM,2001:409-416.
[22]Floater, M.S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design.14,231-250,1997.
[23]Floater, M.S. Parametric tilings and scattered data approximation. Intern. J. Shape Modeling[J] 4,165-182,1998.
[24]James D L, Twigg C D. Skinning mesh animations [J]. ACM Transactions on Graphics, 2005,24(3):399-407.
[25]Der K. G., Sumner R. W., Popovi6 J. Inverse kinematics for reduced deformable models[J]. ACM Transactions on Graphics,2006,25(3):1174-1179.
[26]Yamauchi H, Lee S, Lee Y J, et al. Feature sensitive mesh segmentation with mean shift[C] Proceedings of International Conference on Shape Modeling and Applications. Washington DC, USA:IEEE Computer Society,2005:238-245.
[27]Julius D, Kraevoy V, Sheffer A. D-charts:Quasi-developable mesh segmentation[J]. Computer Graphics Forum 2005,24(3):981-990.
[28]Katz S, Leifman G, Tal A. Mesh segmentation using feature point and core extraction [J]. The Visual Computer.2005,21(8-10):865-875.
[29]Katz S, Tal A. Hierarchical mesh decomposition using fuzzy clustering and cuts[J]. ACM Transactions on Graphics,2003,22(3):954-961.
[30]董洪伟,李重,周儒荣,等.基于凸凹信号的网络分割[J].计算机辅助设计与图形学学报.2009,21(3)：295.304.
[31]Lavoue G, Dupont F, Baskurt A. A new CAD mesh segmentation method based on curvature tensor analysis[J]. Computer—Aided Design,2005,37(10):975-987.
[32]钱江,陈志杨,叶修梓等.噪声鲁棒的分水岭网格分割算法.计算机辅助设计与图形学学报[J],2008,20(3)：310-315.
[33]Chen L., Georganas N. D. An efficient and robust algorithm for 3D mesh segmentation[J]. Multimedia Tools and Applications,2006,29(2):109-125.
[34]Razdan A., Bae M. A hybrid approach to feature segmentation of 3-dimensional meshes[J]. Computer—Aided Design,2003,35(99):783-789.
[35]Liu R, Zhang H. Segmentation of 3D meshes through spectral clustering [C]. Proceeding of Pacific Graphics 2004. Washington DC, USA:IEEE Computer Society, 2004:298-305.
[36]Liu R., Zhang H. Mesh segmentation via spectral embedding and contour analysis[J]. Computer Graphics Forum,2007,26(3):385-394.
[37]Lien J. M., Keyser J., Amato N. M. Simultaneous shape decomposition and skeletonization[C]. Proceedings of the 2006 ACM symposium on Solid and physical modeling. New York, USA:ACM,2006:219-228.
[38]Goes F D, Goldenstein S, Velho L. A hierarchical segmentation of articulated bodies[J]. Computers Graphis Forum,2008,27(5):1349-1356.
[39]D. Brunner, G. Brunnett, Mesh Segmentation using the Object Skeleton Graph, Computer Graphics and Imaging,2004:48-55.
[40]董洪伟.三角网格分割综述[J].中国图象图形学报,2010,15(2)：182-193.
[41]Au 0 K C, Tai C L, Chu H K, Cohen-Or D, Lee T Y. Skeleton extraction by mesh contraction. ACM Transactions on Graphics,2008,27(3):44:1-44:10.
[42]H. Sundar, D. Silver,N. Gagvani, S. Dickinson. Skeleton Based Shape Matching and Retrieval[C], International Conference on Shape Modeling and Applications 2003, May 12-15,2003, Seoul, Korea.
[43]Tamal K Dey,etc. Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee [J], Algorithmica. (S0178-4617),2001,38(1):179-200.
[44]Masaki Hilaga, Yoshihisa Shinagawa. Topology Matching for Fully Automatic Similarity Estimatioin of 3D Shapes. International Conference on Computer Graphics and Interactive Techniques[C], Proceedings of the 28th annual conference on Computer graphics and interactive techniques table ofcontents,2001.203-212.
[45]J. M. Lien. Simultaneous Shape Decomposition and Skeletonization Using Approximate Convex Decomposition[R]. Technical Report, TR05-015, Parasol Laboratory, Department of Computer Science, Texas A&M University,Dec 2005.
[46]Kaufman A, Cohen D, Yagel R. Volume graphics [J]. IEEE Computer,1993,26:51-64.
[47]T. Y. Kong, A. W. Roscoe,A Rosenfeld, concepts of digital topology:Introduction and survey, Computer Vision Graphics and Image Processing,1989,48:357-393.
[48]Au 0 K C, Tai C L, Chu H K, Cohen-Or D, Lee T Y. Skeleton extraction by mesh contraction. ACM Transactions on Graphics,2008,27(3):44:1-44:10.
[49]Saha P. K., Chauhuri B.B. Detection of 3-D simple points for topology preserving transformations with application to thinning[J],IEEE Trans.Pattern Anal Machine Intell,1994,16:1028-1032.
[50]Y. F. Tsao, K. S. Fu, A parallel thinning algorithm for 3D pictures, Computer Graphics and Image Processing,1981,17:315-331.
[51]G. Bertrand, Z. Aktouf, A three-dimensional thinning algorithm using subfields,Proceedings of the SPIE Conference on Vision Geometry.1994,113-124.
[52]Lee TC, Kashyap R. L. Building skeleton models via 3-D medial surface axis thinning algorithms [J]. CVGIP:Graphical Models and Image Processing,1994,56(6):462-478.
[53]栗芳.带边三角网格曲面的四边形分割[D].大连：大连理工大学,2009.
[54]Peter sen S. B, Rodrigues J. M. C bartins P. A. F. Automatic generation of quadrilateral meshes for the finite element analysis of metal forming processes[J]. Finite Elements in Analysis and Design.2000,35:157-168.
[2]胡恩球,张新访,向文等.有限元网格生成方法发展综述.计算机辅助设计与图形学学报.1997,9(4)：378-383.
[3]Petersen S. B, Rodrigues J. M. C, Martins P. A. F. Automatic generation of quadrilateral meshes for the finite element analysis of metal forming processes. Finite Elements in Analysis and Design 2000,35:157-168.
[4]Peggy L. Baehmann, Scott L. Wittchen, Mark S. Shephard, Kurt R. Grice, Mark A. Yerry. Robust, geometrically based, automatic two-dimensional mesh generation[J]. International Jounral for Numercial Methods in Engineering,1987, 24:1043-1078.
[5]J. A. Talbert and A. R. Parkinson. Development of an automatic, two dimensional finite element mesh generator using quadrilateral elements and Bezier curve boundary definition[J]. Int. J. Numer Meth. Engng.1991,29:1551-1567.
[6]刘阳.二维四边形网格生成技术的研究[D].杭州：浙江大学,2005.
[7]郭晓霞.四边形有限元网格划分方法—二分法的改进[J].塑性工程学报,2005,12(5)：96-100.
[8]Zhu, J. Z.,O. C. Zienkiewicz, E. Hinton et al. A new approach to the development of automatic quadrilateral mesh generation[J]. Int. J. Numer Meth. Engng.1991, 32:849-866.
[9]T. D. Blacker, M. B. Stephenson. Paving:A new approach to automated quadrilateral mesh generation[J]. International Jounral for Numercial Methods in Engineering, 1991.32:811-847.
[10]R. J. Cass, S.E. Benzley, R.J. Meyers, T. D. Blacker. Generalized 3-D paving:An Automated Quadrilateral Surface Mesh Geneartion Algorithm[J]. International Jounral for Numercial Methods in Engineering,1996,39:1475-1489.
[11]David R. White, Paul Kinney. Redesign of the Paving Algorithm:Robustness Enhancements Through Element by Element Meshing[J]. Peceeding international Meshing Roundtabel, Snadia National Laboratories,1997,323-335.
[12]S. H. Lo. Generating Quadrilateral Elements on Plane and Over Curved Surfaces[J]. Computers and Structures.1981,31(3):421-426.
[13]B. P. Johnston, John M. Sullivan Jr, A. Kwasnik. Automatic Conversion of Triangular Finite Element Meshes to Quadrilateral Elements [J]. Int. J. Numer beth. Engng.1991, 31:67-84.
[14]C. K Lee. S. n. Lo. A New Scheme for the Generation of a Graded Quadrilateral Mesh[J]. Computers and Structures.1994,52:847-857.
[15]Owen SJ, Staten ML, Canann SA, Saigal S. Advancing Front Quadrilateral Meshing Using Local Triangle Transformations[C], Proceedings of the 7th International Meshing Roundtable,1998, P.409-28
[16]林胜良,方兴,张武,王正光.一种改进的高品质全四边形网格生成方法[J].江南大学学报.2006.5(1).70-73.
[17]顾元宪,马正阳,关振群.平面任意区域四边形网格自动生成的一种方法[J].计算机辅助设计与图形学学报.1998,10(5)：432-439.
[18]Cendes Z J, Shenton D, Shahnasser H. Magnetic field computation using Delaunay triangulation and complementary finite element methods [J]. IEEE Trans Mag,1983,19 (6):2551-2557.
[19]胡向红,陈康宁.由区域生长算法实现四边形网格划分[J].计算机辅助设计与图形学学报.2004.16(1)：29-34.
[20]B. Levy, S. Petitjean, N. Ray, and J. Maillot. Least squares conformal maps for automatic texture atlas generation. In Proceedings of SIGGRAPH 2002, pages 362-371. ACM SIGGRAPH,2002.
[21]Sander P V, Snyder J, Gorter S J, Hoppe H. Texture Mapping Progressive Meshes[C]. IN Proceedings of SIGGRAPH 2001. New York. USA:ACM,2001:409-416.
[22]Floater, M.S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design.14,231-250,1997.
[23]Floater, M.S. Parametric tilings and scattered data approximation. Intern. J. Shape Modeling[J] 4,165-182,1998.
[24]James D L, Twigg C D. Skinning mesh animations [J]. ACM Transactions on Graphics, 2005,24(3):399-407.
[25]Der K. G., Sumner R. W., Popovi6 J. Inverse kinematics for reduced deformable models[J]. ACM Transactions on Graphics,2006,25(3):1174-1179.
[26]Yamauchi H, Lee S, Lee Y J, et al. Feature sensitive mesh segmentation with mean shift[C] Proceedings of International Conference on Shape Modeling and Applications. Washington DC, USA:IEEE Computer Society,2005:238-245.
[27]Julius D, Kraevoy V, Sheffer A. D-charts:Quasi-developable mesh segmentation[J]. Computer Graphics Forum 2005,24(3):981-990.
[28]Katz S, Leifman G, Tal A. Mesh segmentation using feature point and core extraction [J]. The Visual Computer.2005,21(8-10):865-875.
[29]Katz S, Tal A. Hierarchical mesh decomposition using fuzzy clustering and cuts[J]. ACM Transactions on Graphics,2003,22(3):954-961.
[30]董洪伟,李重,周儒荣,等.基于凸凹信号的网络分割[J].计算机辅助设计与图形学学报.2009,21(3)：295.304.
[31]Lavoue G, Dupont F, Baskurt A. A new CAD mesh segmentation method based on curvature tensor analysis[J]. Computer—Aided Design,2005,37(10):975-987.
[32]钱江,陈志杨,叶修梓等.噪声鲁棒的分水岭网格分割算法.计算机辅助设计与图形学学报[J],2008,20(3)：310-315.
[33]Chen L., Georganas N. D. An efficient and robust algorithm for 3D mesh segmentation[J]. Multimedia Tools and Applications,2006,29(2):109-125.
[34]Razdan A., Bae M. A hybrid approach to feature segmentation of 3-dimensional meshes[J]. Computer—Aided Design,2003,35(99):783-789.
[35]Liu R, Zhang H. Segmentation of 3D meshes through spectral clustering [C]. Proceeding of Pacific Graphics 2004. Washington DC, USA:IEEE Computer Society, 2004:298-305.
[36]Liu R., Zhang H. Mesh segmentation via spectral embedding and contour analysis[J]. Computer Graphics Forum,2007,26(3):385-394.
[37]Lien J. M., Keyser J., Amato N. M. Simultaneous shape decomposition and skeletonization[C]. Proceedings of the 2006 ACM symposium on Solid and physical modeling. New York, USA:ACM,2006:219-228.
[38]Goes F D, Goldenstein S, Velho L. A hierarchical segmentation of articulated bodies[J]. Computers Graphis Forum,2008,27(5):1349-1356.
[39]D. Brunner, G. Brunnett, Mesh Segmentation using the Object Skeleton Graph, Computer Graphics and Imaging,2004:48-55.
[40]董洪伟.三角网格分割综述[J].中国图象图形学报,2010,15(2)：182-193.
[41]Au 0 K C, Tai C L, Chu H K, Cohen-Or D, Lee T Y. Skeleton extraction by mesh contraction. ACM Transactions on Graphics,2008,27(3):44:1-44:10.
[42]H. Sundar, D. Silver,N. Gagvani, S. Dickinson. Skeleton Based Shape Matching and Retrieval[C], International Conference on Shape Modeling and Applications 2003, May 12-15,2003, Seoul, Korea.
[43]Tamal K Dey,etc. Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee [J], Algorithmica. (S0178-4617),2001,38(1):179-200.
[44]Masaki Hilaga, Yoshihisa Shinagawa. Topology Matching for Fully Automatic Similarity Estimatioin of 3D Shapes. International Conference on Computer Graphics and Interactive Techniques[C], Proceedings of the 28th annual conference on Computer graphics and interactive techniques table ofcontents,2001.203-212.
[45]J. M. Lien. Simultaneous Shape Decomposition and Skeletonization Using Approximate Convex Decomposition[R]. Technical Report, TR05-015, Parasol Laboratory, Department of Computer Science, Texas A&M University,Dec 2005.
[46]Kaufman A, Cohen D, Yagel R. Volume graphics [J]. IEEE Computer,1993,26:51-64.
[47]T. Y. Kong, A. W. Roscoe,A Rosenfeld, concepts of digital topology:Introduction and survey, Computer Vision Graphics and Image Processing,1989,48:357-393.
[48]Au 0 K C, Tai C L, Chu H K, Cohen-Or D, Lee T Y. Skeleton extraction by mesh contraction. ACM Transactions on Graphics,2008,27(3):44:1-44:10.
[49]Saha P. K., Chauhuri B.B. Detection of 3-D simple points for topology preserving transformations with application to thinning[J],IEEE Trans.Pattern Anal Machine Intell,1994,16:1028-1032.
[50]Y. F. Tsao, K. S. Fu, A parallel thinning algorithm for 3D pictures, Computer Graphics and Image Processing,1981,17:315-331.
[51]G. Bertrand, Z. Aktouf, A three-dimensional thinning algorithm using subfields,Proceedings of the SPIE Conference on Vision Geometry.1994,113-124.
[52]Lee TC, Kashyap R. L. Building skeleton models via 3-D medial surface axis thinning algorithms [J]. CVGIP:Graphical Models and Image Processing,1994,56(6):462-478.
[53]栗芳.带边三角网格曲面的四边形分割[D].大连：大连理工大学,2009.
[54]Peter sen S. B, Rodrigues J. M. C bartins P. A. F. Automatic generation of quadrilateral meshes for the finite element analysis of metal forming processes[J]. Finite Elements in Analysis and Design.2000,35:157-168.