godot-proposals icon indicating copy to clipboard operation
godot-proposals copied to clipboard

Add concave hull algorithm and support generating concave polygon from Sprite2D

Open beicause opened this issue 7 months ago • 3 comments

Describe the project you are working on

A 2D game

Describe the problem or limitation you are having in your project

For discontinuous (with gaps) images, currently in editor Sprite2D Convert to Polygon2D or CollisionPolygon2D can only generate multiple polygons.But sometimes we want to treat the image as a single collision shape, Although it can generate one polygon in some cases by adjusty epsilon, the result maybe different from concave hull. Geometry2D has convex_hull method, which is a subset of concave hull, not as useful as it.

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

After adding concave hull algorithm to BitMap and Geometry2D and supporting it in Sprite2d editor plugin, we can generate a single concave polygon from Sprite2D which is easier to use, instead of multiple CollisionPolygon2D.

These are multiple CollisionPolygon2D generated by BitMap::clip_opaque_to_polygons:

The CollisionPolygon2D generated by convex hull:

The CollisionPolygon2D created by concave hull should be like these( generated using concaveman-cpp without simplifying point number ): very low concavity threshold:

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

The concave hull algorithm can refer to https://github.com/mapbox/concaveman and its cpp implementation, or other better algorithms. A example implementation of this proposal: Add method "opaque_to_concave_polygon" in BitMap. Add method "concave_hull" in Geometry2D. Add a option in sprite2d editor to enable concave polygon when converting Sprite2D to polygon.

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

This can be a addon and written in script, but it's better if provided by Godot

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

Sprite2D editor plugin, BitMap and Geometry2D are core

beicause avatar Jul 23 '24 09:07 beicause