Expose Geometry2D::decompose_polygon_in_convex() to GDScript

[djrain]

Describe the project you are working on

A game using polygons as terrain, where I custom draw borders on the polygons (similar to Unity SpriteShape).

Describe the problem or limitation you are having in your project

In order to render these borders on the polygons I need some triangulation of the border shape. Unfortunately regular triangulation does not give a satisfactory result, I need some kind of "nice" triangulation. Delaunay looks much better, but my shapes are concave and delaunay triangulates the convex hull. So my idea is to first convex decompose my concave shape, and then delaunay triangulate each convex shape and combine the results. Actually, just getting the convex shapes themselves might be enough to work with. But convex decomposition isn't available from GDScript. I could try to implement the algorithm myself, but I think this would be a very slow thing to run fully in GDScript.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Expose Geometry2D::decompose_polygon_in_convex() to GDScript, so I can simply call the function and have it run fast.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Self explanatory.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Not a few lines of script, the convex decomposition is rather complex, and besides it would run slow in GDScript.

Is there a reason why this should be core and not an add-on in the asset library?

It's already a core function, so might as well just expose it, especially considering there are already a lot of similar geometry functions available.

[Xrayez]

I previously worked on this in godotengine/godot#35706 but it hasn't received much approval/user support.

In my experience, just exposing this method won't solve further problems. The decomposition doesn't work in all cases and may fail if you do this at run-time rather than in editor, and does not currently support holes. But that's certainly a method which is worth exposing in either case, and depending on your exact requirements, may be enough to solve your problem.

A game using polygons as terrain, where I custom draw borders on the polygons (similar to Unity SpriteShape).

I confirm this is a real-life use case, that's what I'm doing as well. That said, you can use Goost which should help you in solving all related problems. See GoostGeometry2D class specifically, or nodes such as PolyNode2D and PolyCollisionShape2D which do both rendering (with textures) and decomposition, and be used for physics bodies.

PolyDecomp2D also exposes a bunch of decomposition algorithms which are not even used in Godot at all, even internally.

[djrain]

In my experience, just exposing this method won't solve further problems. The decomposition doesn't work in all cases and may fail if you do this at run-time rather than in editor

That doesn't sound good :/ Does it need to be fixed or what? I for one would definitely like to see these kinds of methods more fleshed out.

As long as it works for simple concave polygons, it should work for me. I could limit it to the editor as well if needed. But in the meantime I guess I will try Goost. I do like the sound of trying various decomposition algorithms.

[Xrayez]

Godot uses PolyPartition library under the hood. It does the job for most cases, but when you deal with input which you cannot control in your game, then the convex decomposition may fail:

For input parameters and return values see method declarations in polypartition.h. All methods require that the input polygons are not self-intersecting, are defined in the correct vertex order (counter-clockwise for non-holes, clockwise for holes), and any holes must be explicitly marked as holes (you can use SetHole(true)). Polygon vertices can easily be ordered correctly by calling TPPLPoly::SetOrientation method.

So, well, you may also stumble upon those issues in Goost since it uses the same library. But Goost provides other implementations beside PolyPartition (like newest Clipper's triangulation code), which works better with degenerate input such as self-intersection polygons. The only limitation is that if you do need convex decomposition specifically (not just triangulation), then yeah those operations may fail occasionally, but not to the point of being useless, of course.

Triangulation is better in terms of rendering (not necessarily quality, but ease of use), since you just have to pass an array of triangles, but maybe slightly worse for physics collisions etc. Decomposed shapes still go through triangulation by Godot if you draw with draw_polygon() and whatnot.

[ghost]

I want to implement a pathfinder for my project and I'd probably make good use of this, especially if something like godotengine/godot#35706 were to be merged.

[akien-mga]

Implemented by godotengine/godot#66096.