摘要
有限元法是适应计算机使用而发展起来的一种有效的数值分析方法,它在工程实践中的作用已从分析校核扩展到优化设计,并且通过与计算机辅助设计(CAD)相结合成为计算机辅助工程(CAE)的重要组成部分。随着工程实践问题的复杂程度不断增加,集有限元法和误差分析方法于一体的自适应有限元法的应用不断普及。以曲面三角形网格描述的三维实体域为输入,生成四面体划分的三维实体网格是当今有限元网格生成和重要算法之一。可靠、高效的四面体生成算法是实现CAE的基础和前提。
本文研究、改进和实现了非结构化自适应有限元网格自动生成的三维Delaunay四面体化方法。
首先,本文在绪论中介绍了国内外有限元网格研究的现状和发展的方向。分析了几种当今流行的实体网格生成算法的特点。然后对工程应用最为普遍的Delaunay四面体化方法加以详细论述。在Delaunay四面体化方法的边界恢复、内部点生成和薄元消除这几个方面,本文介绍了其研究现状,并讨论已有算法的特点。
第2章,介绍了本文Delaunay四面体化方法的算法框架。以下章节对框架中的三维Delaunay插点算法、约束边界恢复算法、边界一致性恢复算法以及内部点生成算法进行详细介绍。本文在已有工作基础上,对这些算法进行改进,提高Delaunay四面体化算法的稳定性。
第3章,提出了一种面向大规模科学计算的三维Delaunay快速插点算法。这一算法提高了单机有限元建模的规模,可在PC计算机生成千万级有限元四面体网格。本文从提高点定位算法速度和提高建立新单元邻接关系算法效率两个方面实现三维Delaunay快速插点。针对三种在工程中最常使用的点集(空间任意点集、正交栅格点集和表面三角面片点集),提出相应的Delaunay快速插点算法,进而扩大算法在实际工程中的适用范围。
第4章,介绍了一种有效的三维约束Delaunay三角化的边界恢复算法。本文算法以“任意精度”算法为基础,提出一种可靠的求解空间线段和三角形面片相交判断的算法。然后在这一算法之上,提出解决三维任意域的约束Delaunay三角化问题方法。该方法尽可能减少插入边界上的Steiner点,完成约束边界恢复,保持了实体边界的完整性,解决了经典Delaunay算法不能剖分凹域的问题,从而实现了复杂三维实体的网格剖分。
第5章,提出一种能够满足多面体边界几何与拓扑约束的边界一致恢复算法,解决了任意多面体的边界一致四面体网格生成问题。在恢复多面体的几何约束时,边界上可能会引入Steiner点,这样就不满足拓扑约束。对此,本文采用动态规划方法将Steiner点从边界上消除；修复与其相关四面体单元的拓扑关系,以保持原多面体边界的拓扑完整性；并采用扩展的Laplacian光顺算法优化劣质单元。理论上本文算法能够保证完整地恢复任意多面体的边界。
第6章,介绍了一种Delaunay四面体化方法与推进波前法(AFT)相结合的三维实体内部点生成算法。这种算法以约束Delaunay四面体化方法生成的模型初始划分为背景网格,并以模型的边界三角形为初始前沿,然后通过AFT生成内部结点,再将这些结点以约束Delaunay的方式插入模型体内。从而,有效的结合了AFT的布点优势和Delaunay整体网格质量较好的特点。
最后总结全文,并展望了可以进一步开展的研究工作。
The Finite Element Method (FEM) is increasingly important in the field of the structure analyzing and design. Combining with the computer Aided Design (CAD), FEM has become one of the essential parts of the Computer Aided Engineering (CAE). As the increasing complexity of the engineering problems, the fully automatic mesh generation is more crucial than before. The efficiency and robustness of the tetrahedral mesh generation is the guarantee of the application of FEM in engineering and science.
In this paper, the Delaunay tetrahedral mesh generation method is well studied and improved.
In the first section of this paper, the recent work of the unstructured mesh generation is discussed. Firstly, kinds of popular unstructured mesh generation algorithms are illustrated here. Then we introduce the Delaunay triangulation from the following aspects:(1) the boundary recovery; (2) the inner nodes generation; (3) the elimination of sliver elements. We demonstrate the current researches as well as the existing algorithms.
In section 2, the frame of the algorithm proposed in this paper is illustrated. To be more exactly, the components of the frame are the rapid node inserting, the confirming boundary recovery, the constrained boundary recovery and the inner node generation. Based on existing algorithm, we improve the current mesh generating methods by enhance their robustness.
In section 3, a rapid Delaunay inserting process is proposed. It enlarges the solution scale of the generation method, which can generate more than 10 million elements in one personal computer. We achieve this from two aspects, speeding up the node locating and the new tetrahedral constructing. Through proposing different methods for three mostly used point sets (which are the random point set, the cubic point set and the triangular surface point set) respectively, we make tetrahedral generator works well in vast engineering applications.
In section 4, a robust confirming boundary recovery method is developed. Robust geometric predicates are employed to detect the intersection of an edge and a facet. Then arbitrary triangular boundaries are recovered with the help of these predicates. Through a heuristic insertion process, the algorithm reduces the number of Steiner points on the boundary. We resolve the problem of the tetrahedralization for the concave domain (which is impossible for classical Delaunay triangulation) successfully.
In section 5, a constrained boundary recovery algorithm is proposed. Despite the confirming boundary recovery method recovered the geometry boundary of the given model, the topological property of the original triangular mesh is destroyed during the process of Steiner nodes inserting. To solve this problem, we employ a kind of dynamic programming method to remove the Steiner nodes on the boundary. Although this algorithm generates elements with zero volume, we utilize a modified Laplacian smoothing method to eliminate the zero-volume elements. In theory, the constrained boundary recovery method can recover arbitrary boundary.
In section 6, a Delaunay triangulation with advancing front technology (AFT) is introduced. This approach takes the initialized Delaunay triangulation as background mesh, and then generates the new nodes by AFT. Finally the new generated nodes are inserted by constrained Delaunay inserting process. This method combines the merits of Delaunay triangulation and AFT.
Finally, a summery is given and the future work is discussed.
引文
[1]Zienkiewicz,O. C., Achievements and some unsolved problems of the finite element method [J]. International Journal for Numerical Methods in Engineering,2000; 47: 9-28.
[2]张洪武,et al.,有限元分析与CAE技术基础[M].北京：清华大学出版社,2004.
[3]关振群,et al.,有限元网格生成方法研究的新进展[J].计算机辅助设计与图形学学报,2003：1：1-14.
[4]Frey, P. J. and L. Marechal, Fast Adaptive Quadtree Mesh Generation [J]. Proceedings, 7th International Meshing Roundtable, Sandia National Lab, USA,1998:211-224.
[5]Tchon, K. F., C. Hirsch, and R. Schneiders, Octree-Based Hexahedral Mesh Generation For Viscous Flow Simulations [J].13th AIAA Computational Fluid Dynamics Conference, AIAA-97-1980. AIAA, June,1997.
[6]McMorris, H. and Y. Kallinderis, Octree-advancing front method for generation of unstructured surface and volume meshes [J]. AIAA Journal,1997; 35:976-984.
[7]Schneiders, R., R. Schindler, and F. Weiler. Octree-based generation of hexahedral element meshes[C].5th International Meshing Roundtable.1996. pp.
[8]Schneiders, R. and Bunten. R, Automatic generation of hexahedral finite element meshes [J]. Computer Aided Geometric Design,1995; 12:693-707.
[9]Shewchuk, J. R. Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery[C].11th International Meshing Roundtable (Ithaca, New York).2004. pp. 193-204
[10]Du, Q. and D. Wang, Boundary recovery for three dimensional conforming Delaunay triangulation [J]. Computer methods in applied mechanics and engineering,2004; 193:2547-2563.
[11]Secchi, S. and L. Simoni, An improved procedure for 2D unstructured Delaunay mesh generation [J]. Advances in Engineering Software,2003; 34:217-234.
[12]Li, X.-Y., Generating well-shaped d-dimensional Delaunay Meshes [J]. Theoretical Computer Science,2003; 296:145-165.
[13]Shewchuk, J. R., Delaunay refinement algorithms for triangular mesh generation [J]. Computational Geometry:Theory and Applications,2002; 22:21-74.
[14]Xiangyang, L. Sliver-Free Three Dimensional Delaunay Mesh Generation [D]. University of Illinois:2000
[15]Borouchaki, H., P. Laug, and P. L. George, Parametric surface meshing using a combined advancing-front generalized Delaunay approach [J]. International Journal for Numerical Methods in Engineering,2000; 49:233-259.
[16]Shewchuk, J. R. Delaunay Refinement Mesh Generation [D]. School of Computer Science, Carnegie Mellon University:1997
[17]Chen, H. and J. Bishop. Delaunay Triangulation for Curved Surfaces[C].6th International Meshing Roundtable.1997. pp.
[18]Borouchaki, H., et al., Delaunay Mesh Generation Governed by Metric Specifcations. Part I. Algorithms [J]. Finite Element Analysis and Design,1997; 25:61-83.
[19]Borouchaki, H. and P. L. George, Aspects of 2-d Delaunay mesh generation [J]. International Journal for Numerical Methods in Engineering,1997; 40: 1957-1975.
[20]Wright, J. P. and A. G. Jack, Aspects of three-dimensional constrained Delaunay meshing [J]. International Journal for Numerical Methods in Engineering,1994; 37: 1841-1861.
[21]Weatherill, N. P. and 0. Hassan, Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints [J]. International Journal for Numerical Methods in Engineering,1994; 37: 2005-2039.
[22]Joe, B., Construction of three-dimensional Delaunay triangulations using local transformations [J]. Computer Aided Geometric Design,1991; 8:123-142.
[23]George, P. L., F. Hecht, and E. Saltel, Automatic mesh generator with specified boundary [J]. Computer methods in applied mechanics and engineering,1991; 92: 169-188.
[24]Weatherhill, N. P., The integrity of geometrical boundaries in the two-dimensional Delaunay triangulation [J]. Commun. Appl. Numer Meth,1990; 6:101-109.
[25]Baker, T. J., Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation [J]. Engineering with Computers,1989; 5: 161-175.
[26]Watson, D. F., Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes [J]. The Computer Journal,1981; 24:167.
[27]D. T, L. and B. J. Schacter, Two Algorithms for Constructing a Delaunay Triangulation [J]. International Journal of Computer and Information Sciences,1980; 3: 219-242.
[28]Si, H., Constrained Delaunay tetrahedral mesh generation and refinement [J]. Finite Elements in Analysis and Design,2010; 46:33-46.
[29]Ghadyani, H., J. Sullivan, and Z. Wu, Boundary recovery for Delaunay tetrahedral meshes using local topological transformations [J]. Finite Elements in Analysis and Design,2010; 46:74-83.
[30]Dey, T. K. and J. A. Levine, Delaunay meshing of isosurfaces [J]. The Visual Computer, 2008; 24:411-422.
[31]Liu, J., B. Chen, and Y. Chen, Boundary recovery after 3D Delaunay tetrahedralization without adding extra nodes [J]. International Journal for Numerical Methods in Engineering,2007; 72:744-756.
[32]Guan, Z., C. Song, and Y. Gu, The boundary recovery and sliver elimination algorithms of three-dimensional constrained Delaunay triangulation [J].2006; 68: 192-209.
[33]宋超,关振群,and顾元宪,三维约束Delaunay三角化的边界恢复和薄元消除方法[J].计算力学学报,2004：21：169-176.
[34]George, P. L., H. Borouchaki, and E. Saltel,'Ultimate'robustness in meshing an arbitrary polyhedron [J]. International Journal for Numerical Methods in Engineering,2003; 58:1061-1089.
[35]关振群,et al.,薄元分解与Laplacian光顺相结合的四面体有限元网格优化方法[J].计算力学学报,2007：24：257-263.
[36]Ito, Y., A.M. Shih, and B. K. Soni. Reliable isotropic tetrahedral mesh generation based on an advancing frontmethod[C]. Proceedings of the 13th International Meshing Roundtable.2004. pp.95-105
[37]Yamakawa, S. and K. Shimada, Anisotropic tetrahedral meshing via bubble packing and advancing front [J]. International Journal for Numerical Methods in Engineering, 2003; 57:1923-1942.
[38]C. K. Lee, Automatic Metric Advancing Front Triangulation over Curved Surfaces [J]. Engineering Computations,2000; 17:48-74.
[39]C. K. Lee and R. E. Hobbs, Automatic Adaptive Finite Element Mesh Generation over Arbitrary Two-dimensional Domain using Advancing Front Technique [J]. Computers & Structures,1999; 71:9-34.
[40]C. K. Lee, Automatic adaptive mesh generation using metric advancing front approach [J]. Engineering Computations,1999; 16:230-263.
[41]R. Tristano, J., S. J. Owen, and S. A. Canann. Advancing Front Surface Mesh Generation in Parametric Space Using a Riemannian Surface Definition[C]. Proceedings of the 7th International Meshing Roundtable.1998. pp.429-445
[42]C. K. Lee and R. E. Hobbs, Automatic Adaptive Finite Element Mesh Generation over Rational B-spline Surfaces [J]. Computers & Structures,1998; 69:577-608.
[43]Seveno, E. Towards an adaptive advancing front method[C]. Proceeding,6th International Meshing Roundtable.1997. pp.
[44]Lau, T. S. and S. H. Lo, Finite Element Mesh Generation Over Analytical Surfaces [J]. Computers and Structures,1996; 59:301-309.
[45]Nakahashi, K. and D. Sharov. Direct Surface Triangulation using the Advancing Front Method[C]. AIAA Computational Fluid Dynamics Conference,12th.1995. pp.442-451
[46]Dey, T. Delaunay mesh generation of three dimensional domains [R]. USA:Ohio State University,2007
[47]Du, Q. and D. Wang, Constrained boundary recovery for three dimensional Delaunay triangulations [J]. International Journal for Numerical Methods in Engineering, 2004; 61:1471-1500.
[48]Liu, A. and M. Baida. How far flipping can go towards 3D conforming/constrained triangulation[C]. Proceedings of 9th International Meshing Roundtable.2000. pp. 295-306
[49]Shewchuk, J. R. Tetrahedral mesh generation by Delaunay refinement[C]. Proceedings of the fourteenth annual symposium on Computational geometry.1998. pp.86-95
[50]Rivara, M. C., New longest-edge algorithms for the refinement and/or improvement of unstructured triangulations [J]. International journal for numerical methods in engineering 1997; 40:3313-3324.
[51]Du, Q. and D. Wang, Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations [J]. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations,2003; 56:1355-1373.
[52]Frey, P. J., H. Borouchaki, and P. L. George. Delaunay tetrahedralization using an advancing-front approach [C].5th International Meshing Roundtable.1996.
[53]Bowyer, A., Computing Dirichlet tessellations [J]. The Computer Journal,1981; 24:162-166.
[54]D. L. Marcum, N. P. W., Unstructured grid generation using iterative point insertion and local reconnection [J]. AIAA journal,1995; 33:1619-1625.
[55]Du, Q. and D. Wang, Recent progress in robust and quality Delaunay mesh generation [J]. Journal of Computational and Applied Mathematics,2006; 195:8-23.
[56]George, P. L., Improvements on Delaunay-based three-dimensional automatic mesh generator [J]. Finite Elements in Analysis and Design,1997; 25:297-317.
[57]Borouchaki, H. and S.H. Lo, Fast Delaunay triangulation in three dimensions [J]. Computer Methods in Applied Mechanics and Engineering,1995; 128:153-167.
[58]Thompson, K. E., Fast and robust Delaunay tessellation in periodic domains [J]. International Journal for Numerical Methods in Engineering,2002; 55: 1345-1366.
[59]李水乡,et al.,快速Delaunay逐点插入网格生成算法[J].北京大学学报,2007；43：302-306.
[60]徐永安and杨钦,三维约束Delaunay三角化的实现[J].软件学报,2001；12：103-110.
[61]Karamete, B. K., M. W. Beall, and M. S. Shephard, Triangulation of arbitrary polyhedra to support automatic mesh generators [J]. International Journal for Numerical Methods in Engineering,2000; 49:167-191.
[62]Bank, R. E., The efficient implementation of local mesh refinement algorithms [J]. Adaptive computational methods for partial differential equations,1983; 14: 74-81.
[63]Si, H. and K. Gaertner. Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations[C]. Proceedings of the 14th International Meshing Roundtable. 2005. pp.147-164
[64]Paul Chew, L. Constrained delaunay triangulations[C]. Proceedings of the third annual symposium on Computational geometry.1987. pp.215-222
[65]杨钦and谭建荣,三维约束Delaunay三角化的研究[J].计算机辅助设计与图形学学报,2000；12：590-594.
[66]Richard Shewchuk, J., Adaptive precision floating-point arithmetic and fast robust geometric predicates [J]. Discrete and Computational Geometry,1997; 18: 305-363.
[67]Du, Q. and D. Wang, Boundary recovery for three dimensional conforming Delaunay triangulation [J]. Computer methods in applied mechanics and engineering,2004; 193:2547-2563.
[68]Segura, R. J. and F. R. Feito. Algorithms to test ray-triangle intersection. Comparative study[C]. WSCG 2001 Conference Proceedings.2001. pp.
[69]Yerry, M., Modified quadtree approach to fnite element mesh generation [J]. IEEE Computer Graphics and Applications,1983; 3:39-46.
[70]George, J. A. Computer implementation of the finite element method [D]. Standford University:Computer Science Dept.1971
[71]Ruppert, J. and R. Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra [J]. Discrete and Computational Geometry,1992; 7:227-253.
[72]Chazelle, B. and L. Palios, Triangulating a nonconvex polytope [J]. Discrete and computational geometry,1990; 5:505-526.