Godot: Polygon2D invert doesnt work

[Zylann]

Godot 2.1.4, Godot 3.0

Polygon2D has an invert property, which I guess is supposed to draw the outside of the polygon rather than the inside (up to some distance), but in some cases it does't work.

Example in 3.0:
Polygon2DInvert.zip

The fact the polygon is convex or concave doesn't seem to matter. Sometimes invert works, but in the repro project it doesn't work and the console says bad polygon. If you move points a little bit you will see it works again, but some configurations don't work. I don't see a pattern predicting when this happens.

[nical]

The error appears to come from the triangulation algorithm in core/math/triangulate.cpp. The latter looks like a simple ear clipping implementation although there isn't much in the comments and git history (it's from before godot's open-sourcing) to confirm that.
As an aside, godot imports with a third party triangulation library which only appears to be used with nav-meshes and physics. I wouldn't be surprised that the third party implementation perform better actually (it supports monotone partition which is a different and usually faster approach).

I'll have a look at the issue in the triangulation algorithm but I am compiling on a slow computer so it'll take a bit of time.

[nical]

I looked into how the algorithm works and here are my findings:

The this works is that in order to invert the polygon, godot creates a single-contour path that goes through vertices of the shape and the bounding box. If you log the contour that is fed into the triangulator and turn it into an SVG, it'll look like this:

With this the triangulator goes though each edge and try to connect them to neighboring vertices to form a triangle. In order to form a triangle we need to look at all other vertices and make sure none of them would be in the triangle. If we manage to build a triangle then we can collapse two edges of the triangle into a single edge and remove it from the contour, otherwise we try another edge and keep going until we have removed all edges.
So this is definitely the ear clipping algorithm.

The problem reported here is that we end up in some cases looping through all combinations without managing to build a triangle. In this scenario, the algorithm has to bail out otherwise it would loop indefinitely. This is a fundamental issue with ear clipping, not all shapes can be triangulated that way so it has to detect whether we have tried all combinations to avoid looping infinitely.
But in reality ear clipping should work for the provided example, and the issue, I think, is that the is_inside_triangle test in snip is too strict. It considers that points exactly on the edge are inside the triangle which cause us to cases that would create a completely flat triangle. The problem with this is that in some cases as vertices get removed from the shape, some edges start to align and having a flat triangle is the only way to continue simplifying the geometry.

If I change the the comparisons like this, the bug goes away.

    return ((aCROSSbp > 0.0) && (bCROSScp > 0.0) && (cCROSSap > 0.0));

Thankfully is_inside_triangle is not used anywhere else in the code, so it's safe to change it's behavior to fix this bug.

Edit: a more thorough explanation of ear clipping can be found here: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

[akien-mga]

Thanks a lot for the detailed insights and additional reference, it should definitely help contributors better understand this algorithm.