[RFC] Replace the ear-clipping triangulation in core with a monotone triangulator.

[nical]

Godot version: 3.x OS/device including version: All. Description:

Godot currently includes two triangulation (also called tessellation) algorithms:

• There is the one in core/math/triangulate.cpp which is a simple ear clipping implementation used to render polygons in the 2D engine,
• and another one in thirdpaty/misc/triangulator.cpp which use the more popular triangulation through monotone polygon partition algorithm, used for collisions and navmeshs.

Ear clipping's biggest advantage is that it is very simple. On the other hand it is usually much slower than monotone triangulation (it is pretty much a brute-force approach to finding the tessellation of a polygon), and more importantly it isn't capable of handling self-intersecting polygons (in some cases the self intersection doesn't bother the algorithm resulting in a tessellation that doesn't necessarily make sense, and in other times it just fails to tessellate altogether:

The image on the left shows a case where some tessellation is produced with some overlapping triangles while on the right, Tessellation just fails, both in the editor.

Monotone partition tessellators handle self-intersections explicitly and produce a triangulation that "makes more sense" as in, it will do what you see in SVG/inkscape/illustrator with no overlapping triangles, and doesn't fail in cases that look somewhat arbitrary and hard to explain to the user. The result would look like:

I don't know how good the tessellator in the thirdparty directory is, but I think that it would be worth using it (or another monotone partition implementation) everywhere, because the approach is superior to ear clipping.

Note hat the ear-clipping implementation appears to be exposed to scripts, but there shouldn't be any problem with keeping the interface while using the other implementation under the hood, if it is OK to change the behavior of the tessellation when there are self-intersection (it would go from incorrect/fail to something that makes sense, but that's a user visible change nonetheless).

Addendum: The monotone triangulation isn't used anywhere, it is the convex partition in from the same file that is used for nav meshes and collisions.

[Calinou]

Feature and improvement proposals for the Godot Engine are now being discussed and reviewed in a dedicated Godot Improvement Proposals (GIP) (godotengine/godot-proposals) issue tracker. The GIP tracker has a detailed issue template designed so that proposals include all the relevant information to start a productive discussion and help the community assess the validity of the proposal for the engine.

The main (godotengine/godot) tracker is now solely dedicated to bug reports and Pull Requests, enabling contributors to have a better focus on bug fixing work. Therefore, we are now closing all older feature proposals on the main issue tracker.

If you are interested in this feature proposal, please open a new proposal on the GIP tracker following the given issue template (after checking that it doesn't exist already). Be sure to reference this closed issue if it includes any relevant discussion (which you are also encouraged to summarize in the new proposal). Thanks in advance!

[Xrayez]

I'm developing a module which expose those triangulation types in the Goost Geometry component.

I don't know how good the tessellator in the thirdparty directory is

The monotone triangulation isn't used anywhere

I've actually stumbled upon a crash with using Triangulate_MONO, so perhaps that's one of the reasons why it didn't end up used, there are no bug reports either because nothing uses it as you say. The crash doesn't seem to be originating from the thirdparty code, because the code was adapted to work with Godot native types it seems, and this was probably not tested well.

This is why I'm using Clipper 10.0.0 which seems to use the monotone partitioning of polygons (still in development, so in either case both libraries could contain bugs).

This might help the use case described in https://github.com/godotengine/godot-proposals/issues/913#issuecomment-634355321 by @HEAVYPOLY (when it comes to drawing self-intersecting polygons), yet you'd also would want to provide different fill rule as well (EvenOdd, NonZero etc).

[HEAVYPOLY]

Would love anything that can handle self intersections, that's a big limitation in my project at the moment.