BitMap.opaque_to_polygons can still create invalid polygons

[Lemonymous]

Godot version

4.0.dev (30800d20f452015c054dc7d1d7cfd38362fe28ff)

System information

Windows 10, Forward+, NVIDIA GeForce GTX 1050 Ti (31.0.15.1694)

Issue description

BitMap.opaque_to_polygons can create invalid polygons when epsilon is higher than 0; which if added as a child to a collision node will produce the following error

Convex decomposing failed!
<C++ Source>   core\math\geometry_2d.cpp:53 @ Geometry2D::decompose_polygon_in_convex()

Some examples of images that produced invalid polygons with Epsilon = 2. The polygons can be seen by the red lines. Some of these examples include shapes that didn't even produce a single polygon. These will not throw an error, but I believe they are part of the same bug.

Steps to reproduce

• Create an Image node with opaque pixels in certain configurations
• Create a BitMap node
• Use BitMap.create_from_image_alpha to create an bitmap based on the image
• Use BitMap.opaque_to_polygons with Epsilon higher than 0 (I have used 2 in my tests) to create polygons based on the opaque pixels in the image
• Add the polygons as children to a collision object like Area2D, RigidBody2d, etc
• If the image contained configurations that lead to invalid polygons, Godot will throw the error listed above.

Minimal reproduction project

This project is a drawing tool that lets you draw on a 16x16 canvas and have the polygons be generated on the fly. This makes it easy to produce broken polygons, and see the errors thrown by the game. Create any of the shapes in the images above, or try to draw your own.

Shortcuts:

• F - fill the square with Color.WHITE
• C - fill the square with Color.TRANSPARANT
• Left Mouse - draw a pixel
• Right Mouse - remove a pixel

Opaque To Polygons Bug.zip

[AThousandShips]

At a glance this looks like the polygons have spikes, didn't try to mess with the reduction code when I worked on this but will take a look and see if I can find a solution

[AThousandShips]

I believe there's an error in the implementation of the RDP algorithm, will check more properly tomorrow ran some basic tests and it looks like there's a solution relatively straight forward.

[kleonc]

I believe there's an error in the implementation of the RDP algorithm

@AThousandShips Original RDP doesn't prevent self intersections, and that what seems to be the problem here. Here's a version preventing self intersections (if you'd like to implement it).

[AThousandShips]

@kleonc Thank you! Will take a look and see what I can make work!

[kleonc]

@KleoNN Thank you!

@AThousandShips Close enough. :smile:

Will take a look and see what I can make work!

Found also this algorithm which (according to that paper) should be faster and give better results (more similar to the original polygon) than the one I've linked in my previous comment.

[AThousandShips]

Making strides in implementing the first algorithm, with a number of modifications, will hopefully be able to post a PR before too long, currently not working against the engine for prototyping and once I've completed the basic implementation I'll take implement it for the engine proper, and I'll elaborate all my details and decisions in the PR

[AThousandShips]

I'm not currently pursuing this fix, made some headway but it is a pretty complex process and got bogged down in details, might pick up again later but if anyone else is interested in this feel free to do so

[Sinowa-Programming]

Hey, I have been working on implementing the first algorithm for over a month and have realized that the issues present are bugs with the original RDP and perpendicular_intersection implementations.