Assert in sweep.cpp (Line 351) - Expression "VertLeq( e->Org, e->Dst )"

[MelvynMay]

Hi from Unity! We're seeing the occasional crash and infinite loop in libtess2 from the PolygonCollider2D. The following code produces a crash:

    struct vec2
    {
        vec2(float _x, float _y)
            : x(_x)
            , y(_y)
        {}

        float x;
        float y;
    };
    vec2 points[34] =
    {
        vec2(3.65450994e-08f, -0.545000076f),
        vec2(2.17929479e-08f, -0.325000018f),
        vec2(1.64285296e-08f, -0.245000020f),
        vec2(5.02914155e-09f, -0.0750000030f),
        vec2(-2.34693287e-09f, 0.0350000039f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-1.00582831e-09f, 0.0150000015f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-1.24052164e-08f, 0.185000017f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-2.24634995e-08f, 0.335000008f),
        vec2(-2.58162611e-08f, 0.385000050f),
        vec2(-3.65450994e-08f, 0.545000076f),
        vec2(-3.65450994e-08f, 0.545000076f),
        vec2(-3.18512328e-08f, 0.475000054f),
        vec2(-2.71573661e-08f, 0.405000061f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-8.38190317e-09f, 0.125000015f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-3.68803743e-09f, 0.0550000072f),
        vec2(-3.35276112e-10f, 0.00500000035f),
        vec2(5.69969405e-09f, -0.0850000083f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.98978557e-08f, -0.595000029f)
    };

    TESStesselator* tess = tessNewTess(NULL);
    tessAddContour(tess, 2, points, sizeof(vec2), 34);
    tessTesselate(tess, TESS_WINDING_ODD, TESS_POLYGONS, 8, 2, NULL);
    tessDeleteTess(tess);
}

[MelvynMay]

I understand this is hardly a great dataset(!) but would you expect a crash?

[memononen]

It should not crash in any case.

Thanks for very concise repro case. I'm very tight on time, so I'm going to ask you to try few things before I'll dive into debugging myself.

Can you try to remove duplicate points in the data set and see it still crashes?

Also, are you using the latest version? The line number in the assert does not match code in github.

[MelvynMay]

Sorry yes, I tried added the last few changes which altered the lines. I am using the latest version. If I check each X & Y point for near zero and clamp it to zero then it does not crash.

The crash occurs doing this:

    if ( !tessComputeInterior( tess ) ) {
        longjmp(tess->env,1);  /* could've used a label */
    }

[MelvynMay]

... and yes, I do remove the coincident points. :)

[memononen]

There's 3 duplicate consequent points in the dataset from the repro.

vec2 points[34] =
    {
        vec2(3.65450994e-08f, -0.545000076f),
        vec2(2.17929479e-08f, -0.325000018f),
        vec2(1.64285296e-08f, -0.245000020f),
        vec2(5.02914155e-09f, -0.0750000030f),
        vec2(-2.34693287e-09f, 0.0350000039f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-5.02914155e-09f, 0.0750000030f),
        vec2(-1.00582831e-09f, 0.0150000015f),
        vec2(-7.04079861e-09f, 0.105000012f),
        vec2(-1.24052164e-08f, 0.185000017f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-2.24634995e-08f, 0.335000008f),
        vec2(-2.58162611e-08f, 0.385000050f),
        vec2(-3.65450994e-08f, 0.545000076f),
        vec2(-3.65450994e-08f, 0.545000076f), // dupe
        vec2(-3.18512328e-08f, 0.475000054f),
        vec2(-2.71573661e-08f, 0.405000061f),
        vec2(-1.70990830e-08f, 0.255000025f),
        vec2(-8.38190317e-09f, 0.125000015f),
        vec2(-6.37024655e-09f, 0.0950000137f),
        vec2(-3.68803743e-09f, 0.0550000072f),
        vec2(-3.35276112e-10f, 0.00500000035f),
        vec2(5.69969405e-09f, -0.0850000083f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(3.98978557e-08f, -0.595000029f),
        vec2(3.98978557e-08f, -0.595000029f),  // dupe
        vec2(3.92273058e-08f, -0.585000038f),
        vec2(2.51457095e-08f, -0.375000060f),
        vec2(3.98978557e-08f, -0.595000029f), 
        vec2(3.98978557e-08f, -0.595000029f)  // dupe
    };

Since a lot of the X-coordinates are close to 0, can you check what happens in tessProjectPolygon()? That is, does s and t for the vertices end up with something sane.

[MelvynMay]

So yes, I just checked and I end up with 31 points as those three are too close to each other so get dropped before I pass them in to libtess2. I'm finding if I check for near zero in the dataset as well and simply set them to zero if that's the case then I do not get a crash. So maybe it being near collinear but not quite is causing it, not sure.

[MelvynMay]

can you check what happens in tessProjectPolygon()? That is, does s and t for the vertices end up with something sane.

Sorry, I misread that. I'll do that now.

[MelvynMay]

Yes, they all look good to me. Nothing crazy anyway.

[memononen]

That's good. Can you try few more things:

1) what if you offset the points a bit (i.e. 42.0f) instead of clamping, does it till crash?

2) what if you change the TESSreal to double? https://github.com/memononen/libtess2/blob/master/Include/tesselator.h#L117

The original GLU tessellator ran in double precision mode, and it is possible that some behavior expects that (I did not write the algorithm, just tuned it, though, I once understood it).

[MelvynMay]

I tried adding 42.0f (meaning of life?) rather than clamping and that also solves the issue.

I'll be honest; the other issue I reported is the one to which I have no solution (infinite loop) as that is being reported a lot lately: https://github.com/memononen/libtess2/issues/23

[memononen]

Finally found the the time to look into this and made fix. Thanks for the report and repro.