四边形网格优化中的螺旋条带生成
|
摘要
已有的四边形网格的简化及优化方法大多数都是三角形网格简化在局部几何上的推广.四边形网格的结构受螺旋条带的影响,移除四边形网格中的螺旋条带则可以在拓扑结构上明显提高四边形网格的质量.文中具体讨论了四边形网格上螺旋条带与网格上奇异点的关系及其性质,并根据这个性质给出了四边形网格中螺旋条带的一般生成算法.实验结果表明,该算法可以有效地搜索四边形网格上的螺旋条带,进而通过删除螺旋条带优化四边形网格的拓扑结构.
Currently most quad mesh simplification and optimization methods are based on the extension of triangle mesh simplification and optimization locally.The quality of the structure of a quad mesh is affected by its helical strips,and adjusting these helical strips can significantly improve the quality of the quad mesh in topological structure.In paper the relationship and properties of helical strips and irregular vertices in quad mesh are discussed.Based on this analysis,ageneral algorithm which searches helical strips in quad mesh is proposed.Experimental results show that it can effectively find helical strips and optimizing complex quad mesh.
Currently most quad mesh simplification and optimization methods are based on the extension of triangle mesh simplification and optimization locally.The quality of the structure of a quad mesh is affected by its helical strips,and adjusting these helical strips can significantly improve the quality of the quad mesh in topological structure.In paper the relationship and properties of helical strips and irregular vertices in quad mesh are discussed.Based on this analysis,ageneral algorithm which searches helical strips in quad mesh is proposed.Experimental results show that it can effectively find helical strips and optimizing complex quad mesh.
引文
[1]Liu Y,Pottmann H,Wallner J.Geometric modeling with conical meshes and developable surfaces[J].ACM Transactions on Graphics,2006,25(3):681-689
[2]Robinson J.CRE method of element testing and the Jacobian shape parameters[J].Engineering Computations,1987,4(2):113-118
[3]Robinson J.Some new distortion measures for quadrilaterals[J].Finite Elements in Analysis and Design,1987,3(3):183-197
[4]Alliez P,Ucelli G,Gotsman C,et al.Recent advances in remeshing of surfaces[M]Shape Analysis and Structuring,Mathematics and Visualization.Heidelberg:Springer,2008:53-82
[5]Bommes D,Lévy B,Pietroni N,et al.Quad-mesh generation and processing:a survey[J].Computer Graphics Forum,2013,32(6):51-76
[6]Gurung T,Laney D,Lindstrom P.SQuad:compact representation for triangle meshes[J].Computer Graphics Forum,2011,30(2):355-364
[7]Remacle J F,Lambrechts J,Seny B,et al.Blossom-quad:a non-uniform quadrilateral mesh generator using a minimumcost perfect-matching algorithm[J].International Journal for Numerical Methods in Engineering,2012,89(9):1102-1119
[8]Tarini M,Pietroni N,Cignoni P,et al.Practical quad mesh simplification[J].Computer Graphics Forum,2010,29(2):407-418
[9]Tong Y,Alliez P,Cohen-Steiner D,et al.Designing quadrangulations with discrete harmonic forms[C]//Proceedings of the 4th Eurographics Symposium on Geometry Processing.Aire-la-Ville:Eurographics Association Press,2006:201-210
[10]Bommes D,Zimmer H,Kobbelt L.Mixed-integer quadrangulation[J].ACM Transactions on Graphics,2009,28(3):Article No.77
[11]Huang J,Zhang M Y,Ma J,et al.Spectral quadrangulation with orientation and alignment control[J].ACM Transactions on Graphics,2008,27(5):Article No.147
[12]Shen D,Bremer P T,Garland M,et al.Spectral surface quadrangulation[J].ACM Transactions on Graphics,2006,25(3):1057-1066
[13]Klberer F,Nieser M,Polthier K.Quadcover-surface parameterization using branched coverings[J].Computer Graphics Forum,2007,26(3):375-384
[14]Zhang M Y,Huang J,Liu X G.A wave-based anisotropic quadrangulation method[J].ACM Transactions on Graphics,2010,29(4):Article No.118
[15]Kovacs D,Myles A,Zorin D.Anisotropic quadrangulation[J].Computer Aided Geometric Design,2011,28(8):449-462
[16]Bommes D,Lempfer T,Kobbelt L.Global structure optimization of quadrilateral meshes[J].Computer Graphics Forum,2011,30(2):375-384
[17]Shen Jianguo,Chen Zhiyang,Zhang Yin,et al.Iterative optimization of triangle meshing for FEM analysis[J].Journal of Computer-Aided Design&Computer Graphics,2009,21(12):1715-1721(in Chinese)(沈建国,陈志杨,张引,等.面向有限元分析的三角网格迭代优化[J].计算机辅助设计与图形学学报,2009,21(12):1715-1721)
[18]Han Yinghua,Li Guiqing,Peng Li,et al.Dual Voronoi clustering and remeshing[J].Journal of Computer-Aided Design&Computer Graphics,2009,21(11):1535-1544(in Chinese)(韩英华,李桂清,彭莉,等.对偶Voronoi聚类与重网格化[J].计算机辅助设计与图形学学报,2009,21(11):1535-1544)
[19]Peng Li,Li Guiqing,Xiong Yunhui,et al.A new multiresolution representation approach based on curvature[J].Journal of Computer-Aided Design&Computer Graphics,2008,20(6):700-706(in Chinese)(彭莉,李桂清,熊赟晖,等.按曲率选取基点的多分辨率表示重构算法[J].计算机辅助设计与图形学学报,2008,20(6):700-706)
[20]Li Jituo,Chen Guodong.Mesh simplification and optimization with edge collapse and mass-spring model[J].Journal of Computer-Aided Design&Computer Graphics,2006,18(3):426-432(in Chinese)(李基拓,陈国栋.基于边折叠和质点-弹簧模型的网格简化优化算法[J].计算机辅助设计与图形学学报,2006,18(3):426-432)
[21]Canann S A,Tristano J R,Staten M L.An approach to combined Laplacian and optimization-based smoothing for triangular,quadrilateral,and quad-dominant meshes[OL].[2013-10-22].http://www.math.zju.edu.cn/cagd/Seminar/2006_AutumnWinter/2006_Winter_Master_zhg_ref.pdf
[22]Zhang Y J,Bajaj C,Xu G L.Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow[J].Communications in Numerical Methods in Engineering,2009,25(1):1-18
[23]Daniels J,Silva C T,Shepherd J,et al.Quadrilateral mesh simplification[J].ACM Transactions on Graphics,2008,27(5):Article No.148
[24]Li Y F,Wang W P,Ling R T,et al.Shape optimization of quad mesh elements[J].Computers&Graphics,2011,35(3):444-451
[25]Kinney P.Cleanup:improving quadrilateral finite element meshes[C].[2013-10-22].http://www.cs.berkeley.edu/~jrs/meshpapers/Kinney.pdf
[26]Staten M L,Benzley S,Scott M.A methodology for quadrilateral finite element mesh coarsening[J].Engineering with Computers,2008,24(3):241-251
[27]Staten M,Canann S A.Post refinement element shape improvement for quadrilateral meshes[C]//Proceedings of Trends in Unstructured Mesh Generation.New York:ASME Press,1997:9-16
[28]Canann S A,Muthukrishnan S N,Phillips R K.Topological improvement procedures for quadrilateral finite element meshes[J].Engineering with Computers,1998,14(2):168-177
[29]Chen Ligang,Zheng Yao,Chen Jianjun.Topological improvement for quadrilateral finite element meshes[J].Journal of Computer-Aided Design&Computer Graphics,2007,19(1):78-83(in Chinese)(陈立岗,郑耀,陈建军.全四边形有限元网格的拓扑优化策略[J].计算机辅助设计与图形学学报,2007,19(1):78-83)
[30]Peng C H,Zhang E,Kobayashi Y,et al.Connectivity editing for quadrilateral meshes[J].ACM Transactions on Graphics,2011,30(6):Article No.141
[31]Staten M L.Sheet-based generation and modification of unstructured conforming all-hexahedral finite element meshes[D].Pittsburgh:Carnegie Mellon University,2010
[2]Robinson J.CRE method of element testing and the Jacobian shape parameters[J].Engineering Computations,1987,4(2):113-118
[3]Robinson J.Some new distortion measures for quadrilaterals[J].Finite Elements in Analysis and Design,1987,3(3):183-197
[4]Alliez P,Ucelli G,Gotsman C,et al.Recent advances in remeshing of surfaces[M]Shape Analysis and Structuring,Mathematics and Visualization.Heidelberg:Springer,2008:53-82
[5]Bommes D,Lévy B,Pietroni N,et al.Quad-mesh generation and processing:a survey[J].Computer Graphics Forum,2013,32(6):51-76
[6]Gurung T,Laney D,Lindstrom P.SQuad:compact representation for triangle meshes[J].Computer Graphics Forum,2011,30(2):355-364
[7]Remacle J F,Lambrechts J,Seny B,et al.Blossom-quad:a non-uniform quadrilateral mesh generator using a minimumcost perfect-matching algorithm[J].International Journal for Numerical Methods in Engineering,2012,89(9):1102-1119
[8]Tarini M,Pietroni N,Cignoni P,et al.Practical quad mesh simplification[J].Computer Graphics Forum,2010,29(2):407-418
[9]Tong Y,Alliez P,Cohen-Steiner D,et al.Designing quadrangulations with discrete harmonic forms[C]//Proceedings of the 4th Eurographics Symposium on Geometry Processing.Aire-la-Ville:Eurographics Association Press,2006:201-210
[10]Bommes D,Zimmer H,Kobbelt L.Mixed-integer quadrangulation[J].ACM Transactions on Graphics,2009,28(3):Article No.77
[11]Huang J,Zhang M Y,Ma J,et al.Spectral quadrangulation with orientation and alignment control[J].ACM Transactions on Graphics,2008,27(5):Article No.147
[12]Shen D,Bremer P T,Garland M,et al.Spectral surface quadrangulation[J].ACM Transactions on Graphics,2006,25(3):1057-1066
[13]Klberer F,Nieser M,Polthier K.Quadcover-surface parameterization using branched coverings[J].Computer Graphics Forum,2007,26(3):375-384
[14]Zhang M Y,Huang J,Liu X G.A wave-based anisotropic quadrangulation method[J].ACM Transactions on Graphics,2010,29(4):Article No.118
[15]Kovacs D,Myles A,Zorin D.Anisotropic quadrangulation[J].Computer Aided Geometric Design,2011,28(8):449-462
[16]Bommes D,Lempfer T,Kobbelt L.Global structure optimization of quadrilateral meshes[J].Computer Graphics Forum,2011,30(2):375-384
[17]Shen Jianguo,Chen Zhiyang,Zhang Yin,et al.Iterative optimization of triangle meshing for FEM analysis[J].Journal of Computer-Aided Design&Computer Graphics,2009,21(12):1715-1721(in Chinese)(沈建国,陈志杨,张引,等.面向有限元分析的三角网格迭代优化[J].计算机辅助设计与图形学学报,2009,21(12):1715-1721)
[18]Han Yinghua,Li Guiqing,Peng Li,et al.Dual Voronoi clustering and remeshing[J].Journal of Computer-Aided Design&Computer Graphics,2009,21(11):1535-1544(in Chinese)(韩英华,李桂清,彭莉,等.对偶Voronoi聚类与重网格化[J].计算机辅助设计与图形学学报,2009,21(11):1535-1544)
[19]Peng Li,Li Guiqing,Xiong Yunhui,et al.A new multiresolution representation approach based on curvature[J].Journal of Computer-Aided Design&Computer Graphics,2008,20(6):700-706(in Chinese)(彭莉,李桂清,熊赟晖,等.按曲率选取基点的多分辨率表示重构算法[J].计算机辅助设计与图形学学报,2008,20(6):700-706)
[20]Li Jituo,Chen Guodong.Mesh simplification and optimization with edge collapse and mass-spring model[J].Journal of Computer-Aided Design&Computer Graphics,2006,18(3):426-432(in Chinese)(李基拓,陈国栋.基于边折叠和质点-弹簧模型的网格简化优化算法[J].计算机辅助设计与图形学学报,2006,18(3):426-432)
[21]Canann S A,Tristano J R,Staten M L.An approach to combined Laplacian and optimization-based smoothing for triangular,quadrilateral,and quad-dominant meshes[OL].[2013-10-22].http://www.math.zju.edu.cn/cagd/Seminar/2006_AutumnWinter/2006_Winter_Master_zhg_ref.pdf
[22]Zhang Y J,Bajaj C,Xu G L.Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow[J].Communications in Numerical Methods in Engineering,2009,25(1):1-18
[23]Daniels J,Silva C T,Shepherd J,et al.Quadrilateral mesh simplification[J].ACM Transactions on Graphics,2008,27(5):Article No.148
[24]Li Y F,Wang W P,Ling R T,et al.Shape optimization of quad mesh elements[J].Computers&Graphics,2011,35(3):444-451
[25]Kinney P.Cleanup:improving quadrilateral finite element meshes[C].[2013-10-22].http://www.cs.berkeley.edu/~jrs/meshpapers/Kinney.pdf
[26]Staten M L,Benzley S,Scott M.A methodology for quadrilateral finite element mesh coarsening[J].Engineering with Computers,2008,24(3):241-251
[27]Staten M,Canann S A.Post refinement element shape improvement for quadrilateral meshes[C]//Proceedings of Trends in Unstructured Mesh Generation.New York:ASME Press,1997:9-16
[28]Canann S A,Muthukrishnan S N,Phillips R K.Topological improvement procedures for quadrilateral finite element meshes[J].Engineering with Computers,1998,14(2):168-177
[29]Chen Ligang,Zheng Yao,Chen Jianjun.Topological improvement for quadrilateral finite element meshes[J].Journal of Computer-Aided Design&Computer Graphics,2007,19(1):78-83(in Chinese)(陈立岗,郑耀,陈建军.全四边形有限元网格的拓扑优化策略[J].计算机辅助设计与图形学学报,2007,19(1):78-83)
[30]Peng C H,Zhang E,Kobayashi Y,et al.Connectivity editing for quadrilateral meshes[J].ACM Transactions on Graphics,2011,30(6):Article No.141
[31]Staten M L.Sheet-based generation and modification of unstructured conforming all-hexahedral finite element meshes[D].Pittsburgh:Carnegie Mellon University,2010