Convex decomposition fails for offset_polyline of simple Curve2D

charlieb commented 4 months ago

Tested versions

Reproducible in v4.2.2.stable, v4.2.1.stable, v4.1.4.stable and v4.3.dev6.official [64520fe67] (but different see below)

System information

Godot v4.2.2.stable unknown - Arch Linux #1 SMP PREEMPT_DYNAMIC Thu, 02 May 2024 17:49:46 +0000 - Wayland - Vulkan (Mobile) - dedicated AMD Radeon RX 6600 (amdgpu) - Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz (16 Threads)

Issue description

In the project below I generate a Curve2D of two points and generate a polygon using offset_polyline with width 5. If I then try to decompose that polygon with decompose_polygon_in_convex or assign it to a CollisionPolygon2D I see the error below on the terminal console and and no decomposition is created. This also means that no collisions will be possible from the CollisionPolygon2D.

ERROR: Convex decomposing failed!
   at: decompose_polygon_in_convex (core/math/geometry_2d.cpp:53)

Lines 18 and 19 in the attached project are the lines that trigger the error.

There are four curves that are tested in the attached project: 0: A curve from 0,0 to 210,-1 (relative to the curve origin) The inner line shown is the Curve2D and the red outer line is the collision poly outline, note that its area is not coloured. 1: A curve from 0,0 to 200,0. This generates a single decomposition shape which colours the collision poly area red 2: A curve from 0,0 to 200,0. A mirror in x-axis of the zeroth curve. 4: A curve from 0,0 to 200, 200. Note the great many decomposition polygons.

Interestingly I see different behaviour from the latest release but they fail all the same: v4.2.2.stable, v4.2.1.stable, v4.1.4.stable - as described above: end_pts 0 and 2 generate no decomposition, 1 and 3 do v4.3.dev6.official - end_pts 3 generate no decomposition, 0, 1 and 2 do

Steps to reproduce

Here's a simplified function that will reproduce the error. The project adds shows the same problem visually.


func test()
    var path : Curve2D = Curve2D.new()
    path.clear_points()
    path.add_point(Vector2(0,0), Vector2(0, 0), Vector2(10, 0))
    path.add_point(Vector2(210, -1), Vector2(-10, 0), Vector2(0, 0))
    var polygons = Geometry2D.offset_polyline(path.get_baked_points(), 
                                                5, Geometry2D.JOIN_SQUARE, Geometry2D.END_SQUARE)
    Geometry2D.decompose_polygon_in_convex(polygons[0]) # generates the error directly

Load the project attached
From the Debug menu turn on "Visible Collision Shapes"
Run the project. Clicking the mouse will cycle between 4 curve variants. At least one of them will show and empty collision shape, the others will either be rainbows of the decomposition polygons or just one red one in the case of the perfectly straight curve. The empty variants will also output the error message
```
ERROR: Convex decomposing failed!                 
at: decompose_polygon_in_convex (core/math/geometry_2d.cpp:53)
```
on the console (but not the godot output area)

Minimal reproduction project (MRP)

convex_decomp_bug.zip

charlieb commented 4 months ago

Possibly duplicated by or related to #57789 and #59425 . The workaround of making the CollisionShape2D build_mode BUILD_SEGMENTS works in that it generates a decomposition when BUILD_SOLID cannot but it doesn't solve my use case of tracking mouseover for my objects.

charlieb commented 4 months ago

Confirmed the same issue (as the v4.3.dev6 version) exists in the upstream project

charlieb commented 4 months ago

The issue appears to be that the offset_polyline generates quite a lot of duplicate points that decompose_polygon_in_convex does not handle well. If I remove the duplicate points then the issue goes away. Here's the branch with the fix It's a fairly small fix.

godotengine / godot