浏览全部资源
扫码关注微信
Received：07 June 2017，
Revised：2017-9-19，
Published：16 January 2018
移动端阅览
目的
2
高质量四边形网格生成是计算机辅助设计、等几何分析与图形学领域中一个富有挑战性的重要问题。针对这一问题，提出一种基于边界简化与多目标优化的高质量四边形网格生成新框架。
方法
2
首先针对亏格非零的平面区域，提出一种将多连通区域转化为单连通区域的方法，可生成高质量的插入边界；其次，提出"可简化角度"和"可简化面积比率"两个阈值概念，从顶点夹角和顶点三角形面积入手，将给定的多边形边界简化为粗糙多边形；然后对边界简化得到的粗糙多边形进行子域分解，并确定每个子域内的网格顶点连接信息；最后提出四边形网格的均匀性和正交性度量目标函数，并通过多目标非线性优化技术确定网格内部顶点的几何位置。
结果
2
在同样的离散边界下，本文方法与现有方法所生成的四边网格相比，所生成的四边网格顶点和单元总数目较少，网格单元质量基本类似，计算时间成本大致相同，但奇异点数目可减少70% 80%，衡量网格单元质量的比例雅克比值等相关指标均有所提高。
结论
2
本文所提出的四边形网格生成方法能够有效减少网格中的奇异点数目，并可生成具有良好光滑性、均匀性和正交性的高质量四边形网格，非常适用于工程分析和动画仿真。
Objective
2
The rapid development of advanced and intelligent manufacturing has caused the seamless data integration of geometric design and simulation to be a key problem in computer-aided design (CAD) and computer-aided engineering (CAE). In the product simulation and analysis stage for the classical finite element analysis method and the emerging iso-geometric analysis method
the meshing quality of computational domain is an important factor that affects the accuracy and computing efficiency of simulation results. Mesh generation has become an important research direction in the field of CAE. Research on high-quality quadrilateral meshing has particularly attracted significant attention because it is an important and challenging problem in the fields of CAD
iso-geometric analysis
and computer graphics. The main quad mesh generation methods currently used in commercial software include triangular mesh conversion
paving
template
and medial axis methods. The triangular mesh conversion method is usually limited by the vertex distribution of the triangular mesh and the connectivity among the vertices
and it hardly generates a high-quality quadrilateral mesh with few singular vertices. The quadrilateral mesh generation method based on medial axis decomposition is sensitive to boundary changes
which is insufficiently robust and is difficult to be implemented automatically. For complex planar regions
the paving method can generate high-quality quadrilateral meshes; however
the elements paving in different directions may lead to self-intersections
in which the validity of the generated meshes cannot be guaranteed. For complex boundaries
the paving method generates many singular vertices. To overcome the above limitations of the quadrilateral meshing methods for planar domain
we propose a new framework for high-quality quadrilateral mesh generation by using boundary simplification and multi-objective optimization technique
considering the urgent requirement for data seamless integration in CAD/CAE.
Method
2
First
a new method is proposed to transfer a multiply-connected domain to a simply-connected domain with a high-quality and uniform-boundary insertion. Second
boundary simplification is used in decreasing the number of initial boundary vertex to reduce computing costs. Two threshold concepts
namely simplification angle and simplification area ratio
are proposed to simplify the given boundary into a rough polygon from the vertex angle and the area of vertex triangle. Third
subdomain decomposition method is performed on the rough polygon obtained by boundary simplification
and high-quality domain decomposition can be obtained by uniform vertex insertion. After n-sided domain decomposition is obtained
the optimal quadrilateral mesh is selected from the existing catalog of meshes by high-quality patterns. The vertex connectivity information for each subdomain is determined by meshing rules with few singularities. The main idea of this method is to use integer-programming techniques
such that the resulting topological connectivity template has the smallest number of singularities. Finally
the geometric position of interior mesh vertices is obtained by multi-objective optimization technique
an extended Laplacian operator is proposed for quad mesh
and a uniformity objective function is derived from the concept of variance in statistics and probability theory to obtain a quadrilateral mesh with a uniform element size; that is
if the variance of the quadrilateral element area in the generated grid is zero
then the mesh has a uniform element size. Furthermore
a unified formula for the objective function related to the orthogonality around the vertex with arbitrary valence is proposed. The geometric position of the vertex in the quad mesh is determined by the multi-objective nonlinear optimization technique to minimize the objective functions for the smoothness
uniformity and orthogonality measurements
which are solved by a quasi-Newton nonlinear optimization algorithm.
Result
2
From the same discrete boundary
the quadrilateral mesh generated by our method has smaller numbers of mesh vertices and elements than those of previous methods. The number of extraordinary vertices can also be reduced by 70%~80%. The metrics for the evaluation of mesh quality
such as scaled Jacobian
are also improved. The corresponding computing time for each method in terms of computational efficiency is listed. In terms of algorithm complexity
the proposed method is similar to three classical quadrilateral mesh generation methods
and the time complexity of the proposed method is related to the number of vertices for a given discrete boundary.
Conclusion
2
Compared with previous approaches
the proposed method can generate high-quality quad meshes with fewer extraordinary vertices and higher mesh qualities
such as smoothness
uniformity
and orthogonality
as exhibited by the presented mesh generation examples.
Liang X H, Ebeida M S, Zhang Y J. Guaranteed-quality all-quadrilateral mesh generation with feature preservation[J]. Computer Methods in Applied Mechanics and Engineering, 2010, 199(29-32):2072-2083.[DOI:10.1016/j.cma.2010.03.007]
Hu S M, Lai Y K, Yang Y L. A curvature flow based fairing algorithm of quad-dominant meshes[J]. Chinese Journal of Computers, 2008, 31(9):1622-1628.
胡事民, 来煜坤, 杨永亮.基于曲率流的四边形主导网格的光顺方法[J].计算机学报, 2008, 31(9):1622-1628. [DOI:10.3321/j.issn:0254-4164.2008.09.015]
Xu G, Mourrain B, Duvigneau R, et al. Parameterization of computational domain in isogeometric analysis:methods and comparison[J]. Computer Methods in Applied Mechanics and Engineering, 2011, 200(23-24):2021-2031.[DOI:10.1016/j.cma.2011.03.005]
Alliez P, Cohen-Steiner D, Devillers O, et al. Anisotropic polygonal remeshing[J]. ACM Transactions on Graphics, 2003, 22(3):485-493.[DOI:10.1145/882262.882296]
Huang J, Zhang M Y, Ma J, et al. Spectral quadrangulation with orientation and alignment control[J]. ACM Transactions on Graphics, 2008, 27(5):#147.[DOI:10.1145/1409060.1409100]
Owen S J, Staten M L, Canann S A, et al. Q-Morph:an indirect approach to advancing front quad meshing[J]. International Journal for Numerical Methods in Engineering, 1999, 44(9):1317-1340.[DOI:10.1002/(SICI)1097-0207(19990330)44:9<1317::AID-NME532>3.0.CO;2-N]
Blacker T D, Stephenson M B. Paving:a new approach to automated quadrilateral mesh generation[J]. International Journal for Numerical Methods in Engineering, 1991, 32(4):811-847.[DOI:10.1002/nme.1620320410]
Daniels Ⅱ J, Lizier M, Siqueira M, et al. Template-based quadrilateral meshing[J]. Computers&Graphics, 2011, 35(3):471-482.[DOI:10.1016/j.cag.2011.03.024]
Xu J L, Chen F L, Deng J S. Two-dimensional domain decomposition based on skeleton computation for parameterization and isogeometric analysis[J]. Computer Methods in Applied Mechanics and Engineering, 2015, 284:541-555.[DOI:10.1016/j.cma.2014.09.026]
Chen L G, Zheng Y, Chen J J. Topological improvement for quadrilateral finite element meshes[J]. Journal of Computer-Aided Design&Computer Graphics, 2007, 19(1):78-83.
陈立岗, 郑耀, 陈建军.全四边形有限元网格的拓扑优化策略[J].计算机辅助设计与图形学学报, 2007, 19(1):78-83. [DOI:10.3321/j.issn:1003-9775.2007.01.015]
Quadros W R, Ramaswami K, Prinz F B, et al. LayTracks:a new approach to automated geometry adaptive quadrilateral mesh generation using medial axis transform[J]. International Journal for Numerical Methods in Engineering, 2004, 61(2):209-237.[DOI:10.1002/nme.1063]
Liu Y S, Yan H B, Fan Y G. Polygon simplification algorithms and comparison[J]. Computer Engineering, 2009, 35(23):227-228.
刘亚姝, 严寒冰, 范友贵.多边形简化算法及比较[J].计算机工程, 2009, 35(23) 227-228. [DOI:10.3969/j.issn.1000-3428.2009.23.079]
Gao X. Algorithm for decomposing simple polygon into convex parts[J]. Journal of Yanshan University, 2004, 28(4):355-358.
高翔.一个简单多边形凸单元剖分的算法[J].燕山大学学报, 2004, 28(4):355-358. [DOI:10.3969/j.issn.1007-791X.2004.04.017]
Takayama K, Panozzo D, Sorkine-Hornung O. Pattern-based quadrangulation for N-sided patches[J]. Computer Graphics Forum, 2014, 33(5):177-184.[DOI:10.1111/cgf.12443]
Chen J J, Zheng Y, Chen L G, et al. A new unstructured quadrilateral mesh generation algorithm[J]. Journal of Image and Graphics, 2008, 13(9):1796-1803.
陈建军, 郑耀, 陈立岗, 等.非结构化四边形网格生成新算法[J].中国图象图形学报, 2008, 13(9):1796-1803. [DOI:10.11834/jig.20080927]
Sorkine O. Differential representations for mesh processing[J]. Computer Graphics Forum, 2006, 25(4):789-807.[DOI:10.1111/j.1467-8659.2006.00999.x]
Nocedal J, Wright S J. Numerical Optimization[M]. Berlin Heidelberg:Springer-Verlag, 1999.[DOI:10.1007/978-3-540-35447-5]
Ma X W, Zhao G Q, Sun L. AUTOMESH-2D/3D:robust automatic mesh generator for metal forming simulation[J]. Materials Research Innovations, 2011, 15(S1):S482-S486.[DOI:10.1179/143307511X12858957676038]
Knupp P M. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part Ⅰ-a framework for surface mesh optimization[J]. International Journal for Numerical Methods in Engineering, 2000, 48(3):401-420.[DOI:10.1002/(SICI)1097-0207(20000530)48:3<401::AID-NME880>3.0.CO;2-D]
相关作者
相关机构
京公网安备11010802024621
