Mesh Quality

  • Published on
    26-May-2015

  • View
    1.583

  • Download
    7

Embed Size (px)

DESCRIPTION

Shape measures, which provide an effective quantitative mean of comparison of element shapes in a mesh, are of great relevance in many fields related to finite element analysis, but particularly in mesh adaptation. Still, while most serious works in the field of mesh adaptation directly make use of shape measures, very little work has been devoted to the actual comparison of shape measures, with the notable exceptions of Liu and Joe (1994) who have thoroughly analyzed a set of a few selected measures. While the published works present some of the standard shape measures in current use, new shape measures steadily appear in recent literature for which no analysis is available. Furthermore, no classification scheme has been proposed, and fitness of new measures is often not assessed. This lecture aims to survey a wider range of shape measures in general use, to define validity criteria for those measures and to classify then in broad categories, beginning with valid vs. invalid shape measures. The lecture also addresses issues regarding the use of shape measures in non-Euclidean spaces, such as the use of shape measures in Riemannian spaces for anisotropic mesh adaptation. The lecture summarizes important properties of simplices and introduces a classification of simplex degeneracies in two and three dimensions. I will present a wide range of shape measures, introduce shape measures validity criteria, and present a visualization scheme that helps analyze and compare shape measures to one another. Shape measures are then classified, and conclusions are drawn on the pertinence of developing new shape measures or choosing one among the currently existing ones. Mesh adaptivity is a process that generates a sequence of meshes and numerical solutions on these meshes such that the sequence converges to some goal which usually is error equirepartition whilst minimizing the computational effort by minimizing the number of vertices of the mesh. For unstructured meshes, the process of computing a mesh in the sequence can be decomposed in two steps: first, a size specification map is computed by analyzing the numerical solution; second, a mesh is computed that satisfies this size specification map. The subject of the present lecture is to offer a measure of the degree to which a mesh satisfies it\'s size specification map. More than ten years ago, Marie-Gabrielle Vallet (1990, 1991, 1992) showed that giving the size specification map using a metric tensor representation eased the generation of adapted and anisotropic meshes by combining the desired size and stretching into a single mathematical concept. Metric tensors modify the way distances are measured. The adapted and anisotropic mesh in the real Euclidean space is constructed by building a regular, isotropic and unitary mesh in the metric tensor space. The use of a metric tensor representation for the size specification map is now a widely used tool for the generation and adaptation of anisotropic meshes. It has been used in two and three dimensions, for various PDE simulations with finite element and finite volume methods, for surface discretization, graphic representation, etc. The most complete references are George and Borouchaki (1997) and Frey and George (1999) the references therein. However, the issue of metric conformity is still not clear. There is no well defined way to measure the degree to which a mesh satisfies a size specification map given in the form of a field of metric tensors. Most authors rely on two competing measures to assess the quality of their meshes with respect to a size specification map. One measure compares the simplex shape with the specified stretching. This is usually done by computing a shape criterion

Transcript

  • 1. Mesh Quality Julien Dompierrejulien@cerca.umontreal.ca Centre de Recherche en Calcul Applique (CERCA) Ecole Polytechnique de Montreal Mesh Quality p. 1/331

2. Authors Research professionals Julien Dompierre Paul Labb Marie-Gabrielle Vallet Professors Franois Guibault Jean-Yves Trpanier Ricardo Camarero Mesh Quality p. 2/331 3. References 1J. D OMPIERRE , P. L ABB ,M.-G. VALLET, F. G UIBAULTAND R. C AMARERO , Critresde qualit pour les maillagessimpliciaux. in Maillage etadaptation, Herms, October2001, Paris, pages 311348.Mesh Quality p. 3/331 4. References 2A. L IU and B. J OE, Relationship betweenTetrahedron Shape Measures, Bit, Vol. 34,pages 268287, (1994). Mesh Quality p. 4/331 5. References 3P. L ABB, J. D OMPIERRE, M.-G. VALLET, F.G UIBAULT and J.-Y. T RPANIER, A UniversalMeasure of the Conformity of a Mesh withRespect to an Anisotropic Metric Field,Submitted to Int. J. for Numer. Meth. in Engng,(2003).Mesh Quality p. 5/331 6. References 4P. L ABB, J. D OMPIERRE, M.-G. VALLET, F.G UIBAULT and J.-Y. T RPANIER, A Measure ofthe Conformity of a Mesh to an AnisotropicMetric, Tenth International Meshing Roundtable,Newport Beach, CA, pages 319326, (2001). Mesh Quality p. 6/331 7. References 5P.-L. G EORGE AND H. B O -ROUCHAKI , Triangulation deDelaunay et maillage, appli-cations aux lments nis.Herms, 1997, Paris.This book is available in En-glish.Mesh Quality p. 7/331 8. References 6P. J. F REY AND P.-L.G EORGE, Maillages. Ap-plications aux lments nis.Herms, 1999, Paris.This book is available inEnglish.Mesh Quality p. 8/331 9. Table of Contents1. Introduction8. Non-Simplicial2. Simplex Denition Elements3. Degeneracies of 9. Shape QualitySimplicesVisualization4. Shape Quality of10. Shape QualitySimplicesEquivalence5. Formulae for Sim- 11. Mesh Quality andplices Optimization6. Voronoi, Delaunay 12. Size Quality ofand RiemannSimplices7. Shape Quality and 13. Universal QualityDelaunay 14. Conclusions Mesh Quality p. 9/331 10. Introduction and JusticationsWe work on mesh generation, mesh adaptationand mesh optimization.How can we choose the conguration thatproduces the best triangles ? A triangle shapequality measure is needed. Mesh Quality p. 10/331 11. Face FlippingHow can we choose the conguration thatproduces the best tetrahedra ? A tetrahedronshape quality measure is needed. Mesh Quality p. 11/331 12. Edge Swapping S4 S3 S4 S3S5S5 AABB S2S2 S1S1How can we choose the conguration thatproduces the best tetrahedra ? A tetrahedronshape quality measure is needed.Mesh Quality p. 12/331 13. Mesh Optimization Let O1 and O2 , two three-dimensional unstructured tetrahedral mesh Optimizers.Mesh Quality p. 13/331 14. Mesh Optimization Let O1 and O2 , two three-dimensional unstructured tetrahedral mesh Optimizers. What is the norm O of a mesh optimizer ?Mesh Quality p. 13/331 15. Mesh Optimization Let O1 and O2 , two three-dimensional unstructured tetrahedral mesh Optimizers. What is the norm O of a mesh optimizer ? How can it be asserted that O1 > O2 ?Mesh Quality p. 13/331 16. Its Obvious ! Let B be a benchmark. Mesh Quality p. 14/331 17. Its Obvious ! Let B be a benchmark. Let M1 = O1 (B) be the optimized mesh obtained with the mesh optimizer O1 . Mesh Quality p. 14/331 18. Its Obvious ! Let B be a benchmark. Let M1 = O1 (B) be the optimized mesh obtained with the mesh optimizer O1 . Let M2 = O2 (B) be the optimized mesh obtained with the mesh optimizer O2 . Mesh Quality p. 14/331 19. Its Obvious ! Let B be a benchmark. Let M1 = O1 (B) be the optimized mesh obtained with the mesh optimizer O1 . Let M2 = O2 (B) be the optimized mesh obtained with the mesh optimizer O2 . Common sense says : The proof is in the pudding. Mesh Quality p. 14/331 20. Its Obvious ! Let B be a benchmark. Let M1 = O1 (B) be the optimized mesh obtained with the mesh optimizer O1 . Let M2 = O2 (B) be the optimized mesh obtained with the mesh optimizer O2 . Common sense says : The proof is in the pudding. If M1 > M2 then O1 > O2 . Mesh Quality p. 14/331 21. Benchmarks for Mesh OptimizationJ. D OMPIERRE, P. L ABB, F. G UIBAULT andR. C AMARERO.Proposal of Benchmarks for 3D UnstructuredTetrahedral Mesh Optimization.7th International Meshing Roundtable, Dearborn,MI, October 1998, pages 459478.Mesh Quality p. 15/331 22. The Trick... Because the norm O of a mesh optimizer is unknown, the comparison of two optimizers is replaced by the comparison of two meshes. Mesh Quality p. 16/331 23. The Trick... Because the norm O of a mesh optimizer is unknown, the comparison of two optimizers is replaced by the comparison of two meshes. What is the norm M of a mesh ? Mesh Quality p. 16/331 24. The Trick... Because the norm O of a mesh optimizer is unknown, the comparison of two optimizers is replaced by the comparison of two meshes. What is the norm M of a mesh ? How can we assert that M1 > M2 ? Mesh Quality p. 16/331 25. The Trick... Because the norm O of a mesh optimizer is unknown, the comparison of two optimizers is replaced by the comparison of two meshes. What is the norm M of a mesh ? How can we assert that M1 > M2 ? This is what you will know soon, or you money back ! Mesh Quality p. 16/331 26. What to Retain This lecture is about the quality of the elements of a mesh and the quality of a whole mesh.Mesh Quality p. 17/331 27. What to Retain This lecture is about the quality of the elements of a mesh and the quality of a whole mesh. The concept of element quality is necessary for the algorithms of egde and face swapping.Mesh Quality p. 17/331 28. What to Retain This lecture is about the quality of the elements of a mesh and the quality of a whole mesh. The concept of element quality is necessary for the algorithms of egde and face swapping. The concept of mesh quality is necessary to do research on mesh optimization.Mesh Quality p. 17/331 29. Table of Contents1. Introduction 8. Non-Simplicial2. Simplex DenitionElements3. Degeneracies of9. Shape QualitySimplices Visualization4. Shape Quality of 10. Shape QualitySimplices Equivalence5. Formulae for Simplices 11. Mesh Quality and6. Voronoi, Delaunay andOptimizationRiemann 12. Size Quality of7. Shape Quality andSimplicesDelaunay13. Universal Quality14. ConclusionsMesh Quality p. 18/331 30. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.Mesh Quality p. 19/331 31. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices. Mesh Quality p. 19/331 32. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices.The segment in one dimension. Mesh Quality p. 19/331 33. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices.The segment in one dimension.The triangle in two dimensions. Mesh Quality p. 19/331 34. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices.The segment in one dimension.The triangle in two dimensions.The tetrahedron in three dimensions. Mesh Quality p. 19/331 35. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices.The segment in one dimension.The triangle in two dimensions.The tetrahedron in three dimensions.The hypertetrahedron in four dimensions. Mesh Quality p. 19/331 36. Denition of a SimplexMeshes in two and three dimensions are made ofpolygons or polyhedra named elements.The most simple amongst them, the simplices, arethose which have the minimal number of vertices.The segment in one dimension.The triangle in two dimensions.The tetrahedron in three dimensions.The hypertetrahedron in four dimensions.Quadrilaterals, pyramids, prisms, hexahedra and othersuch aliens are named non-simplicial elements. Mesh Quality p. 19/331 37. Denition of a d-Simplex in RdLet d + 1 points Pj = (p1j , p2j , . . . , pdj ) Rd , 1 j d + 1,not in the same hyperplane, id est, such that the matrix oforder d + 1, p11 p12 p1,d+1 p21 p22 p2,d+1 . . A= .. . .. . . .. . pd1 pd2 pd,d+1 11 1be invertible. The convex hull of the points Pj is named thed-simplex of points Pj .Mesh Quality p. 20/331 38. A Simplex Generates RdAny point X Rd , with Cartesian coordinates (xi )d , is i=1characterized by the d + 1 scalars j = j (X) dened assolution of the linear system d+1 pij j = xi for 1 i d,j=1d+1 j = 1,j=1whose matrix is A. Mesh Quality p. 21/331 39. What to RetainIn two dimensions, the simplex is a triangle.Mesh Quality p. 22/331 40. What to RetainIn two dimensions, the simplex is a triangle.In three dimensions, the simplex is a tetrahedron.Mesh Quality p. 22/331 41. What to RetainIn two dimensions, the simplex is a triangle.In three dimensions, the simplex is a tetrahedron.The d + 1 vertices of a simplex in Rd give d vectors thatform a base of Rd .Mesh Quality p. 22/331 42. What to RetainIn two dimensions, the simplex is a triangle.In three dimensions, the simplex is a tetrahedron.The d + 1 vertices of a simplex in Rd give d vectors thatform a base of Rd .The coordinates j (X) of a point X Rd in the basegenerated by the simplex are the barycentriccoordinates.Mesh Quality p. 22/331 43. Table of Contents1. Introduction 8. Non-Simplicial2. Simplex DenitionElements3. Degeneracies of9. Shape QualitySimplices