9
$\begingroup$

Say you have a triangular mesh on a flat plane. This has been drawn to eventually solve some problem in mechanics, for example.

A mesh of equilateral triangles is the best inasmuch as the distances between the vertices and between the centroids are the same all over. This makes interpolations and the calculation of gradients an easy and accurate task. However, because of constraints and circumstances, it is not always possible to work on a mesh of all equilateral triangles.

So, the questions regard a mesh of triangular elements of arbitrary shape.

Concerning individual mesh elements. Which metrics are commonly used to quantify the dissimilarity of one generic triangle from some underlying ideal equilateral shape?

Concerning the whole mesh. Which metrics are in use to quantity the irregularity of a mesh of arbitrary triangles on the whole? These metrics should indicate how scrambled the mesh is.

Thanks for thinking along.

Note All contributions from the finite-element community have been greatly appreciated. For this question, please note that the interest is to quantify differences purely in the geometry (arbitrary vs equilateral triangles). The subsequent effect on the interpolation and conditioning errors are outside scope. Granted these can be insightful and relevant, they complicate the mathematical handling.

$\endgroup$
  • 4
    $\begingroup$ Have you checked this question? And from that post: "What is a good finite element?". $\endgroup$ – nicoguaro Jun 9 '17 at 12:05
  • 3
    $\begingroup$ I think that the ratio of areas/radii between the incircle and circumcircle might work. The ratio of eigenvalues of the Jacobian, minimum, and maximum angles, as well. $\endgroup$ – nicoguaro Jun 9 '17 at 12:07
  • 4
    $\begingroup$ One of Shewchuck's most famous papers covers this topic in depth: What is a good linear finite element? $\endgroup$ – Paul Jun 10 '17 at 1:25
  • $\begingroup$ @nicoguaro Thanks. I am not specially interested in FEM, but in quantifying difference in the elements' shape. Could you please elaborate on the ratios of radii for example? Is that independent of size? In other words, it will be appreciated if you can list your options in an answer for anyone else to build on. $\endgroup$ – XavierStuvw Jun 10 '17 at 13:54
  • $\begingroup$ You could also look at the minimum angle in any of the mesh elements. The idea is that this wants to be as large as possible $\endgroup$ – KyleW Jun 10 '17 at 16:14
4
$\begingroup$

As @Nicoguaro and @Paul have said in the comments to the question post, there are a great many ways to do this kind of thing, and I'm not sure if there is a single "best" approach.


From a review study of Jonathan Richard Shewchuck at Berkley, an answer is:

enter image description here

Please refer to the original document (version 31/12/2002) for symbology, terminology, special features and possibly more (e.g. tetrahedra). Chapter 6 is about quality measures. The document linked to is the extended version, and in JRS's webpage there is also an abridged one.


Personally, I am a fan of the "volume-length" metric. It's a good robust scalar indicator of (isotropic) simplex quality and is cheap to compute. In two-dimensions:

$a = \frac{4\sqrt{3}}{3}\frac{A}{\|\mathbf{e}_{\mathrm{rms}}\|^{_2}}$

where $A$ is the signed area of the triangle and $\|\mathbf{e}_{\mathrm{rms}}\|$ is the root-mean-square edge length. Ideal elements achieve $a=1$, which decreases toward zero with increased distortion. Inverted elements with reversed orientation have $a < 0$.

To asses the quality of an unstructured triangulation it's typical to look at histograms of such element quality metrics. There are many implementations of such things out there, but one straight-forward MATLAB code-base of mine is here.

In addition to volume-length scores, histograms of element angles and vertex degree are also computed by default.

$\endgroup$
  • $\begingroup$ Why are you a fan of this metric ? Was it good at predicting the accuracy of the simulations you did with the meshes ? $\endgroup$ – BrunoLevy Jun 13 '17 at 15:25
  • $\begingroup$ @BrunoLevy: Well, as a simple "default" choice for simplexes: it robustly generalises to higher-dimensions, is cheap to compute, is numerically well-conditioned, provides a "tangling" indicator re. orientation, and is a simple "geometry-only" indicator, as per the question. Is it a good indicator for simulation quality? Well, that depends on what you're doing! If you are interested in isotropic meshes, I would say yes. Highly direction-dependent anisotropic configurations, then no, not directly, although in such cases it can still be used after suitable coordinate transformation. $\endgroup$ – Darren Engwirda Jun 13 '17 at 18:34
  • 1
    $\begingroup$ Also is smooth, so you can run it with implicit arbitrary Lagrangian-Eulerian formulation. With small effort you can generalise it to anisotropic meshes. $\endgroup$ – likask Jun 14 '17 at 12:01
  • $\begingroup$ @likask: Yes, good point -- it can be a good cost-function for mesh smoothing and optimisation. $\endgroup$ – Darren Engwirda Jun 14 '17 at 12:47
  • $\begingroup$ I have added an excerpt of Shewcuck's work that extends the scope of Darren's answer. This summarises several comments too. Thanks to all contributors to this post. $\endgroup$ – XavierStuvw Jul 8 '17 at 8:43
4
$\begingroup$

I do not think that there exists an answer to this question in general, because it all depends on the intended use for the mesh. For instance, if you are doing computational fluid dynamics, you may want to have a mesh that is extremely anisotropic near the boundary layer. Now if you are doing computational electromagnetics, the best mesh will be probably completely different.

There are in the literature many different definitions for a "mesh quality" criterion. Most of them will favor meshes with triangles that are as equilateral as possible. One can also mention the idea of maximizing the smallest angle (which is realized by Delaunay triangulation for a fixed set of points). It is justified by Jonathan Shewchuk's analysis mentioned in one of the comments, that relates this angle with the condition number of the stiffness matrix for the Laplace equation discretized with P1 elements, but again, depending on the intended use, somebody's good mesh can be somebody else's poor mesh.

I do not think that it makes sense to "quantify differences purely in the geometry (arbitrary vs equilateral triangles)": before measuring whether the triangles are equilateral and deciding which "deviation w.r.t. equilaterality" is the best one, it is necessary to figure out whether "equilateral triangles" is what we want, and it is not always the case ! It all comes from the "interpolation and conditioning" that you mention. Yes, as you said "it complicates the mathematical handling" but without it, it is not possible to make the difference between objective criteria for a given application and criteria that do not make sense at all.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.