Adaptive Mesh Smoothing

[foxyseta]

Because it uses Lloyd's algorithm, SimpleSmoother tends to damage adaptive meshes (i.e. meshes with non-uniform element sizes) by "stretching out" smaller triangles towards the bigger ones. On the other hand, bigger triangles shrink a little in order to accommodate more space for the smaller ones.


I feel like having at least one smoothing method preserving adaptiveness in meshes as they are smoothed would be nice. Unfortunately, I'm not very prepared on the topic.

[foxyseta]

Here's another, more intense instance of the problem.

[wo80]

It's called SimpleSmoother for a reason :-)

I looked into this topic a couple of years ago. Here's a publication I remember which looked promising:

• Efficient Mesh Optimization Schemes based on Optimal Delaunay Triangulations, Long Chen and Michael J. Holst, 2010

For boundary elements (triangles containing at least one node on the boundary), they propose to use the barycenter instead of circumcenters. A MATLAB implementation can be found in iFem meshsmoothing.m

The crucial point to get a high quality graded mesh, is to weight the new point location by a density function (given a priori, or by a FEM error estimate, or some approximation of the boundary feature size).

The current implementation of SimpleSmoother corresponds to a constant density function. A density function corresponding to the boundary feature size could be automatically defined by looking at the triangle sizes of the initial input mesh, see section (5.1.2.):

There are some cases for which the user may not know the density function a priori. In other words, the user provides a mesh as an input, and wants an output mesh with better mesh quality while keeping similar mesh density. In this case, we simply choose rho = C/|t| in ODT or CPT smoothers and thus use the formulae (4.22).

[foxyseta]

Thanks a bunch! Both the article and the MATLAB implementation are illuminating.
Were I to rewrite Chen and Michael's algorithm for Triangle.NET's IMeshes, could you perhaps recommend me some known .NET implementations? Even one written in C++ might be of use. Or perhaps directly porting iFEM's smoothing procedure to Triangle.NET is itself trivial?

[timoria21]

Hello Christian,

You already linked this paper to my issue. The problem is that is difficult to translate. I've finally made a $40 donation for your help in this project.

Hope you can find something easier to translate to C# or a sort of MatLab to C++ translator.

Thanks.

[wo80]

@timoria21 Thanks a bunch for your donation!

[wo80]

[...] could you perhaps recommend me some known .NET implementations? Even one written in C++ might be of use. Or perhaps directly porting iFEM's smoothing procedure to Triangle.NET is itself trivial?

I haven't seen any C# implementation. You can find some C code based on the paper

• Conforming Centroidal Voronoi Delaunay Triangulation for Quality Mesh Generation, Lili Ju, 2007

on Ju's homepage, called MESHGEN. I remember thinking about integrating it into https://github.com/wo80/Triangle. I have to see what I did back then and if it's worth having a second look.

In general, writing a high quality mesh generator like presented in the papers isn't trivial. The MATLAB code might still be a good starting point to get some inspiration, though direct porting will be difficult.

[timoria21]

Does anybody have access to this MatLab feature? https://www.mathworks.com/videos/automatically-converting-matlab-code-to-c-code-96483.html

Having a C version of the code would be a good starting point.

Did you try contacting the article author? Just to check if a C++ version of the smoother code is available.

[wo80]

@timoria21 I don't have access to MATLAB at all, using Octave here. But in general, those automatic converters produce code that is really hard to look at.
In the first paper mentioned above, the authors talk about an implementation using CGAL, but that's only for the 3D case. I don't think that a 2D version is available in C++.

I've added density function support to the smoother using a simple triangle midpoint quadrature rule. Feel free to fetch the smoother branch and hack around. See example 12 for usage (in the picture below left with constant density, right with higher density around the inner squares):

You can still see lower quality around the borders of the geometry, so I guess to achieve high quality, you'd have to come up with some clever extra handling of vertices near the boundary.

[timoria21]

Thanks @wo80, these results are far from optimal. It's difficult to imagine that in the year 2022 there are no open-source options for smoothing graded meshes. There are tons of papers online on the meshing subject. I'm really surprised. I hope that somebody else can provide some help here.

[wo80]

It's difficult to imagine that in the year 2022 there are no open-source options for smoothing graded meshes

@timoria21 I guess most FEM packages will have some kind of quality mesh generator. And you could always take a look at https://gmsh.info - there's a mesh optimizer in the contrib folder which seems to use a rather different approach. Gmsh is more or less meant to run as a monolithic application, either using the GUI or from command line, but most applications (FEM, 3D modelling or whatever you're doing) will allow you to import the produced meshes.

[foxyseta]

Are we talking about the MeshOptimizer or the MeshQualityOptimizer here?

[wo80]

MeshQualityOptimizer uses MeshOptimizer. I grepped for both and couldn't see them being used anywhere in the gmsh source code.

[timoria21]

So, anybody out there, wrote a graded mesh smoother for Triangle, not even for the C++ version? Hard to believe...