13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lecture 23 Dr. W. Cho Prof. N.m. Patrikalakis Copyright@2003 Massachusetts Institute of Technology Contents 23 F.E. and B.E. Meshing Algorithms 23.1 General 23.1.1 Finite Element Method(FEM) 23.1.2Mesh 23. 1.3 Some Criteria for a Good Meshin 23. 1.4 Finite Element Analysis in a CAD Environment 23. 1.5 Background Information 222334468 23.1.6 Mesh Conformity 23. 1. 7 Mesh refin 23.2 Mesh Generation Methods 23.2.1 Mapped Mesh Generation (23, 10, 11, 5 10 23.2.2 Topology Decomposition Approach 20, 3 23.2.3 Geometry Decomposition Approach 6, 17, 13 23.2.4 Volume Triangulation - Delaunay Based 7, 15 234 23.2.5 Spatial Enumeration Methods [ 21, 22 15 Bibliography
13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lecture 23 Dr. W. Cho Prof. N. M. Patrikalakis Copyright c 2003 Massachusetts Institute of Technology Contents 23 F.E. and B.E. Meshing Algorithms 2 23.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 23.1.1 Finite Element Method (FEM) . . . . . . . . . . . . . . . . . . . . . . 2 23.1.2 Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 23.1.3 Some Criteria for a Good Meshing . . . . . . . . . . . . . . . . . . . . 3 23.1.4 Finite Element Analysis in a CAD Environment . . . . . . . . . . . . . 4 23.1.5 Background Information . . . . . . . . . . . . . . . . . . . . . . . . . . 4 23.1.6 Mesh Conformity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 23.1.7 Mesh Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 23.2 Mesh Generation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 23.2.1 Mapped Mesh Generation [23, 10, 11, 5] . . . . . . . . . . . . . . . . . 10 23.2.2 Topology Decomposition Approach [20, 3] . . . . . . . . . . . . . . . . 12 23.2.3 Geometry Decomposition Approach [6, 17, 13] . . . . . . . . . . . . . . 13 23.2.4 Volume Triangulation – Delaunay Based [7, 15] . . . . . . . . . . . . . 14 23.2.5 Spatial Enumeration Methods [21, 22] . . . . . . . . . . . . . . . . . . 15 Bibliography 16 1
Lecture 23 F.E. and B.E. Meshing Algorithms 23.1 General 23.1.1 Finite Element Method (FEM) FEM solves numerically complex continuous systems for which it is not possible to construct any analytic solution, see Figure 23.1 Physical Problem aw of physics Formulation of Equations PDE Weighted Residual Methods Integral Formulation Transformation of equations Unknown Function Approximation (using finite element mesh and matrix organization Algebraic System of Eq uations Numerical Solution Approximate Solution Figure 23.1: FEM Procedure
Lecture 23 F.E. and B.E. Meshing Algorithms 23.1 General 23.1.1 Finite Element Method (FEM) FEM solves numerically complex continuous systems for which it is not possible to construct any analytic solution, see Figure 23.1. Physical Problem Law of Physics PDE Weighted Residual Methods Integral Formulation Algebraic System of Equations Unknown Function Approximation (using finite element mesh and matrix organization) Approximate Solution Numerical Solution Formulation of Equations Transformation of Equations Solution Figure 23.1: FEM Procedure 2
23.1.2Mesh Mesh is the complex of elements discretizing the simulation domain, eg. triangular or quadri- lateral mesh in 2D. tetrahedral or hexahedral mesh in 3D Why Use mesh o construct a discrete version of the original PDe problems Types of Mesh See Figure 23.2 Figure 23.2: Structured(n=6) and unstructured(nf constant)mesh Structured mesh The number of elements n surrounding an internal node is constant The connectivity of the grid can be calculated rather than explicitly stored. simpler and less computer memory intensive Lack of geometric flexibility Unstructured mesh The number of elements surrounding an internal node can be arbitrary Greater geometric flexibility crucial when dealing with domains of compler geometry or when the mesh has to be adapted to complicated features of computational domain or to complicated features of the solution(eg. boundary layers, internal layers, shocks, etc) Expensive in time and memory requirements 23.1. 3 Some Criteria for a Good Meshing Shape of elements [2, 18 meshing should avoid both very sharp and flat angles, see Figure 23.3 may cause serious numerical problems in both finite element mesh generation and nal
23.1.2 Mesh Mesh is the complex of elements discretizing the simulation domain, eg. triangular or quadrilateral mesh in 2D, tetrahedral or hexahedral mesh in 3D. Why Use Mesh ? To construct a discrete version of the original PDE problems. Types of Mesh See Figure 23.2. Figure 23.2: Structured (n = 6) and unstructured (n 6= constant) mesh • Structured mesh – The number of elements n surrounding an internal node is constant. – The connectivity of the grid can be calculated rather than explicitly stored. → simpler and less computer memory intensive – Lack of geometric flexibility • Unstructured mesh – The number of elements surrounding an internal node can be arbitrary. – Greater geometric flexibility → crucial when dealing with domains of complex geometry or when the mesh has to be adapted to complicated features of computational domain or to complicated features of the solution (eg. boundary layers, internal layers, shocks, etc). – Expensive in time and memory requirements 23.1.3 Some Criteria for a Good Meshing • Shape of elements [2, 18] – meshing should avoid both very sharp and flat angles, see Figure 23.3. – may cause serious numerical problems in both finite element mesh generation and analysis. 3
Figure 23.3: Elements with sharp and flat angles ● Number of elements should be moderate related to efficiency of finite element analysis Topological consistency(homeomorphism)between the eract input domain and its mesh - related to robustness of finite element analysis 8, 9 Automation, adaptability, etc 23.1. 4 Finite Element Analysis in a CAD Environment See figure 23. 4 In Figure 23. 4, " input data preparation" includes the preparations of boundary conditions loads, and integration constants At etc. "post-processing of results" includes scientific visual- ization. etc 23.1.5 Background Information Delaunay Triangulation [4, 19 Given a set of points Pi, the Voronoi region, Vi is a set of points closer to a site Pi than any other site P,(See Figure 23.5). Delaunay triangulation is constructed by connecting those points whose Voronoi regions have a common edge(2D) or face(3D). Some properties of Delaunay triangulation are it maximizes the minimum angle(globally) circumcircle criterion: every circle passing through the 3 vertices of a triangle does not contain any other vertices . it covers the convex hull of all sites Mesh Conversion Performed if a mesh generator produces only one type of element and another type is required Quadrilaterals(Hexahedra)- Triangles(Tetrahedra)[12: easy and well-shaped mesh, ee Figure 23.6 Triangles(Tetrahedra)-Quadrilaterals(Hexahedra)
Figure 23.3: Elements with sharp and flat angles • Number of elements – should be moderate. – related to efficiency of finite element analysis. • Topological consistency (homeomorphism) between the exact input domain and its mesh. – related to robustness of finite element analysis [8, 9]. • Automation, adaptability, etc. 23.1.4 Finite Element Analysis in a CAD Environment See Figure 23.4. In Figure 23.4, “input data preparation” includes the preparations of boundary conditions, loads, and integration constants ∆t etc.; “post-processing of results” includes scientific visualization, etc. 23.1.5 Background Information Delaunay Triangulation [4, 19] Given a set of points Pi , the Voronoi region, Vi is a set of points closer to a site Pi than any other site Pj (See Figure 23.5). Delaunay triangulation is constructed by connecting those points whose Voronoi regions have a common edge (2D) or face (3D). Some properties of Delaunay triangulation are: • it maximizes the minimum angle (globally). • circumcircle criterion: every circle passing through the 3 vertices of a triangle does not contain any other vertices. • it covers the convex hull of all sites. Mesh Conversion Performed if a mesh generator produces only one type of element and another type is required. • Quadrilaterals (Hexahedra) → Triangles (Tetrahedra) [12]: easy and well-shaped mesh, see Figure 23.6. • Triangles (Tetrahedra) → Quadrilaterals (Hexahedra) 4
Geometric Model Generation Mesh Generator FE Mesh Input Data Preparation FE Model Input Data of the Problem FE System Post-Processing of results Design Improvement Mesh Improvement Figure 23.4: FE analysis in a CAD environment Voronoi region Figure 23.5: 2D Delaunay triangulation 5
User Geometric Model Generation Mesh Generator FE Mesh Input Data of the Problem FE Analysis Post−Processing of Results Design Improvement Mesh Improvement FE Model Input Data Preparation FE System Figure 23.4: FE analysis in a CAD environment Delaunay triangle Voronoi region Pi Pj Figure 23.5: 2D Delaunay triangulation 5
Figure 23.6: Mesh conversion: quadrilateral triangles 23.7: New node insertion New node insertion [12]: not well-shaped mesh -+ flat angle, see Figure 23.7 Pairing of adjacent triangles(tetrahedra)[14: pairing test should be performed to generate conver quadrilaterals. -pairing AABC and ACDA is unsuitable, see of triangles Mesh Smoothing Make elements better-shaped by iteratively repositioning an internal node Pi, [12 p+ where N is the number of elements connected by P Pi converges to the centroid of the polygon formed by its connected neighbors Example: After 5 iterations, Pi converges from(7, 4)to(4.5, 3), see Figure 23.9 23.1.6 Mesh Conformity If adjacent elements share a common vertex or whole edge or a whole face, see Figure 23.10, we have conforming mesh. Otherwise, mesh is non-conformin
Figure 23.6: Mesh conversion : quadrilateral → triangles Figure 23.7: New node insertion – New node insertion [12]: not well-shaped mesh → flat angle, see Figure 23.7. – Pairing of adjacent triangles (tetrahedra) [14]: pairing test should be performed to generate convex quadrilaterals. → pairing ∆ABC and ∆CDA is unsuitable, see A B D C Figure 23.8: Pairing of triangles Figure 23.8. Mesh Smoothing Make elements better-shaped by iteratively repositioning an internal node Pi , [12]. • Pi = Pi+ PN j=1 Pj N+1 , where N is the number of elements connected by Pi . → Pi converges to the centroid of the polygon formed by its connected neighbors. • Example: After 5 iterations, Pi converges from (7,4) to (4.5,3), see Figure 23.9. 23.1.6 Mesh Conformity • If adjacent elements share a common vertex or whole edge or a whole face, see Figure 23.10, we have conforming mesh. Otherwise, mesh is non-conforming. 6
Figure 23.9: Mesh smoothing (a)Conforming meshes (b) Non-conforming meshes Figure 23.10: Conforming and non-conforming mesh
Pi x y x y Figure 23.9: Mesh smoothing (a) Conforming meshes (b) Non−conforming meshes Figure 23.10: Conforming and non-conforming mesh 7
In case of non-conforming mesh, multiple constraints need to be applied to the midside nodes to make the mesh analyzable [1], see Figures 23 11 and 23.12 N igure 23. 11: Constrained node, n Figure 23. 12: Displacement 23.1.7 Mesh refinement Increase mesh density from region to region Conforming mesh refinement algorithm 16 Let To be any conforming initial triangulation having No triangles. Then a new triangulation Ti is defined as follows 1. Bisect triangle T by the longest side, VT E To, see Figure 23.13 Figure 23. 13: Step 1
• In case of non-conforming mesh, multiple constraints need to be applied to the midside nodes to make the mesh analyzable [1], see Figures 23.11 and 23.12. N1 N2 a b n Figure 23.11: Constrained node, n → (eg) Un = b a+b UN2 + a a+b UN1 N2 N1 n N1 N2 U U Un Figure 23.12: Displacement 23.1.7 Mesh Refinement Increase mesh density from region to region. Conforming mesh refinement algorithm [16] Let τ0 be any conforming initial triangulation having N0 triangles. Then a new triangulation τ1 is defined as follows: 1. Bisect triangle T by the longest side, ∀T ∈ τ0, see Figure 23.13. A B D C Figure 23.13: Step 1 8
2. Find the set S1 of triangles generated in step l and such that the midpoint of one of its sides is a non-conforming node, i.e. node D and the corresponding S1=4ABC1, see Figure 23.13 3. For each triangle T E S1, join its non-conforming node with the opposite vertex, i.e. join D and C. see Figure 23.14 Figure 23. 14: Step 3, New conforming triangulation
2. Find the set S1 of triangles generated in step 1 and such that the midpoint of one of its sides is a non-conforming node, i.e. node D and the corresponding S1 = {∆ABC}, see Figure 23.13. 3. For each triangle T ∈ S1, join its non-conforming node with the opposite vertex, i.e. join D and C, see Figure 23.14. D C Figure 23.14: Step 3, New conforming triangulation 9
23.2 Mesh Generation methods 23. 2.1 Mapped Mesh Generation 23, 10, 11, 5 This is the earliest method for mesh generation which appeared in 1970 Mapped Element Approach Figure 23. 15: Mapped element approach 1. Subdivide the physical domain into simple regions, e. g, quadrilaterals, triangles 2. Generate mesh in computational space(u, a), see Figure 23.15 3. Determine nodes in the physical domain using shape functions Example 1: Isoparametric curvilinear mapping of quadrilaterals a mapped mesh generation method for surfaces Figure 23. 16: Isoparametric curvilinear mapping X X where Xi=(ai, yi, zi): coordinates of each node in the physical domain X=( and Ni (u, v)is the shape function associated with each node, see Figure 23. 16 (3, g, 2)
23.2 Mesh Generation Methods 23.2.1 Mapped Mesh Generation [23, 10, 11, 5] This is the earliest method for mesh generation which appeared in 1970’s. Mapped Element Approach x y u v Figure 23.15: Mapped element approach 1. Subdivide the physical domain into simple regions, e.g., quadrilaterals, triangles. 2. Generate mesh in computational space (u, v), see Figure 23.15. 3. Determine nodes in the physical domain using shape functions. • Example 1: Isoparametric curvilinear mapping of quadrilaterals → a mapped mesh generation method for surfaces. x y z u v u v Figure 23.16: Isoparametric curvilinear mapping → X~ = P8 i=1 Ni(u, v)X~ i , where X~ i = (xi , yi , zi) : coordinates of each node in the physical domain X~ = (x, y, z) and Ni(u, v) is the shape function associated with each node, see Figure 23.16. 10
