On Element Shape Measures for Mesh Optimization

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Centre de Recherche en Calculs Applique, 5160. boul Decarie, suite 400, Montreal, (Quebec), H3X 2H9
[paul | [julien | [francois | [ricardo]@cerca.umontreal.ca

Abstract

Shape measures are needed during mesh optimization to quantify the element regularity. The purpose of this paper is first to examine several shape measures for triangles and tetrahedra. It is then proved that they are all equivalent, which means that they are all as good, in the context of mesh optimization. In a third part, shape measures are derived for quadrangles, prisms and hexahedra.

A simplex is a triangle in 2-D and a tetrahedron in 3-D. A simplex is regular if all its edges have the same length. A simplex is degenerate if its vertices are collinear in 2-D and collinear or coplanar in 3-D. There are so many tetrahedron shape measures in the literature [1] that we "suggest" the following global definition, introduced in [2]:

DEFINITION 1: A simplex shape measure is a continuous function that evaluates the quality of a simplex. It must be invariant under translation, rotation, reflection and uniform scaling of the simplex. It must be maximum for the regular simplex and it must be minimum for a degenerate simplex. For the ease of comparison, it should be scaled to the interval [0, 1], and be 1 for the regular simplex and 0 for a degenerate simplex.

In this paper, we analyze and give a precise definition of a few shape criteria including radius ratio, mean ratio, minimum of the solid angles and inverse of the interpolation error. It is shown that the edge length ratio and the dihedral angle are not valid shape measures in the sense of Def. 1. Shape criteria are written using only the length of the edges of the simplex. In fact, a simplex is completely characterized by the length of its edges and all characteristics (area, volume, inradius, circumradius) can be rewritten in terms of edge lengths. Furthermore, shape measures of triangles are visualized by using 2-D graphs, as suggested in [3].

In the context of mesh optimization, there are only minor consequences of using one shape criterion or another. This is proved through the notion of measure equivalence, following Liu and Joe [2].

DEFINITION 2: Let u and v be two different simplex shape measures with values in interval [0,1]. u and v are equivalent if there exist positive constants C0, C1, E0 and E1 such that C0*pow(u,E0) <= v <= C1*pow(u,E1).

A sketch of the proof of the conjecture presented in [4] is provided:

THEOREM: All simplex shape measures that satisfy Definition 1 are equivalent in the sense of Definition 2.

This equivalence between simplex shape measures implies that if one of these simplex shape measures approaches zero, which indicates a poorly-shaped simplex, then so do the others. Conversely, if one of these simplex shape measures approaches unity, then so do the others. This theorem implies that any shape measure can be used for steering a mesh optimization process. This is verified on a 2-D test-case: the same mesh optimizer gives the same optimal mesh by using different triangle shape measures.

Finally, these shape measures are extended to non simplicial elements: the quadrilateral element in 2-D, the prism and the hexahedron in 3-D. A non simplicial element is regular if its surface is minimum for a given volume. The shape measure of a non simplicial element is defined by the minimum of the shape measure of the simplexes originating from each of the vertices of the non simplicial element. This value is scaled in order to satisfy Def. 1 for a regular element.

References

[1] V. N. Parthasarathy, C. M. Graichen and A. F. Hathaway, `A Comparison of Tetrahedron Quality Measures', Finite Elements in Analysis and Design, Vol. 15, pp. 255-261, 1993.

[2] A. Liu and B. Joe, `Relationship between Tetrahedron Shape Measures', Bit, Vol. 34, pp. 268-287, 1994.

[3] M.-G. Vallet, `Generation de maillages elements finis anisotropes et adaptatifs', Ph.D. Thesis. Universite Pierre et Marie Curie, France, 1992.

[4] J. Dompierre, P. Labbe, F. Guibault and R. Camarero, `Proposal of Benchmarks for 3D Unstructured Tetrahedral Mesh Optimization', 7th International Meshing Roundtable, Dearborn, MI, pp. 459-478, October 1998.