Undesired variable element sizes

[foxyseta]

When attempting a simple meshing operation on consistent file ig.poly, I obtain elements whose sizes vary.

using TriangleNet;
using TriangleNet.Geometry;
using TriangleNet.Meshing;
using TriangleNet.IO;
using TriangleNet.Smoothing;

public static class MyClass
{

    private static IPolygon ReadPolygon()
        => FileProcessor.Read("ig.poly");

    private static Configuration GetConfiguration()
        => new Configuration() {
            Predicates = () => new RobustPredicates(),
            TrianglePool = () => new TrianglePool().Restart()
        };

    private static GenericMesher GetMesher()
        => new GenericMesher(GetConfiguration());

    private static ConstraintOptions GetCostraintOptions()
        => new ConstraintOptions() {
            SegmentSplitting = 1,
            ConformingDelaunay = true
        };

    private static QualityOptions GetQualityOptions()
        => new QualityOptions()
        {
            MaximumArea = .043301270189221933,
            MinimumAngle = 33.8
        };

    private static IMesh GetMesh()
        => GetMesher().Triangulate(ReadPolygon(), GetCostraintOptions(), GetQualityOptions());

    private static void Smooth(IMesh m)
        => new SimpleSmoother().Smooth(m);

    private static void WriteMesh(IMesh m)
        => FileProcessor.Write(m, "tm.poly");

    public static void Run()
    {
        var m = GetMesh();
        Smooth(m);
        WriteMesh(m);
    }

}

Attached files:

• ig.poly
• tm.ele
• tm.poly

geometries.tar.gz

[wo80]

Take a look at https://github.com/wo80/Triangle.NET/blob/f70be6a937c4c447b4cee05505d7ee2b75d68e62/src/Triangle/Meshing/QualityMesher.cs#L733-L744

If area constraints are imposed, Triangle.NET falls back to the classical Ruppert refinement algorithm, which is known to perform bad for large minimum angles, see https://www.cise.ufl.edu/~ungor/aCute/quality.html

If you comment out the if-else and always use the aCute algorithm, the geometry you provided will be refined as expected. I cannot remember, why I chose to leave the original algorithm in place, but I think there were crashes for some input geometries. Not sure when I find the time to look into this...

[timoria21]

So what are the correct parameters if you aim for the equilateral triangles of a specified edge size? I thought that using the max angle + area constraint was the only way to go.

[wo80]

@timoria21 At the moment, your best bet would be to relax the angle constraints and use smoothing to improve the triangle shapes.

I think it's quite possible that the fallback to Ruppert's algorithm isn't necessary anymore since there were some fixes I did to the aCute code along the way. I'll have to do some testing to verify...

[wo80]

I ran some tests on a set of 274 poly files. It seems that the fallback to Ruppert's algorithm can be removed.

L_min/max = min/max segment length of input polygon
        h = (L_min + L_max) / 2
 max area =  sqrt(3)/4*h*h

// Results with fall back to Ruppert's algorithm
min_angle  valid        time
     25.0  266 (97.1%)  2.116 sec
     33.0  266 (97.1%)  9.051 sec
     34.0   --          infinite loop

// Results when always using aCute algorithm
min_angle  valid        time
     25.0  266 (97.1%)  3.203 sec
     33.0  266 (97.1%)  5.435 sec
     34.0  265 (96.7%)  6.649 sec

[foxyseta]

Thanks! Once I removed the fallback to Ruppert's algorithm, the element sizes in the test case I posted above became pretty much uniform. However, the same did not happen with the following test case (which is different from the previous one, although similar), even after removing the fallback to Ruppert's algorithm.

At the moment, your best bet would be to relax the angle constraints and use smoothing to improve the triangle shapes.

As I am already using SimpleSmoother, I've tried relaxing the triangle constraints. 33.8 as minimum angle: 25 as minimum angle: No minimum angle constraint:

geometries2.tar.gz

[wo80]

Thanks for testing! It would be interesting to see some actual quality measures for those triangulations.

At first glance, the 25 min angle version seems to be best. There are obviously some defects. Those could probably be corrected manually by looking at the topology in a post-processing step (nodes with low/high valance, diamonds):

If you look at the last section "Premium Quality Uniform Triangulations" on https://www.cise.ufl.edu/~ungor/aCute/quality.html you'll find the exact same patterns there. I never bothered to find out where those irregularities come from since the meshes are good enough for what I'm doing.

[foxyseta]

That is a good idea. Once again, thanks for the thorough explanation.

I ran some tests on a set of 274 poly files. It seems that the fallback to Ruppert's algorithm can be removed.

I am leaving this issue open in case you wish to do so in production. I suppose you do not need a PR for such a small patch?

[wo80]

I am leaving this issue open in case you wish to do so in production. I suppose you do not need a PR for such a small patch?

Yes. I'll close this issue with the next commit. QualityOptions has a new option to switch between the original algorithm and aCute. So, if wanted, the legacy refinement method can still be used.

[foxyseta]

Hello again! Please discard the last set of images I sent you (the ones with the grey triangles). I eventually noticed that a different kind of smoother was kicking in in place of SimpleSmoother. I deeply apologize. Nonetheless, not all instances of slot meshing improve when using the aCute algorithm only. I'm sending you a relevant poly file with meshing parameters as soon as possible, in case you are interested (since this fix is now in the master branch).

[wo80]

Yes, upload the relevant poly file here (also, show the meshing parameters used). And feel free to re-open.

not all instances of slot meshing improve

Regarding the latest commit, the question would be, whether the original algorithm produces better results. Or does the aCute algorithm fail completely?