godotengine / godotengine/godot

Convex decomposition fails for offset_polyline of simple Curve2D

Open
#91,607 3 comments 0 reactions 0 assignees View on GitHub
bug topic:2d topic:core
Dominant language
C++
Stars
117k
Forks
26.8k
PR merge metrics
PR metrics pending

Description

### 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)
![image](https://github.com/godotengine/godot/assets/37277/3bb2dfb1-14e3-4e4a-a77d-4645263fc47a)
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
![image](https://github.com/godotengine/godot/assets/37277/a8197e12-0299-4c0f-8067-3a88258ce6ac)
2: A curve from 0,0 to 200,0. A mirror in x-axis of the zeroth curve.
![image](https://github.com/godotengine/godot/assets/37277/b92197eb-4baf-4c77-9731-edf7200f8968)
4: A curve from 0,0 to 200, 200.
![image](https://github.com/godotengine/godot/assets/37277/e839e984-568b-431b-938d-9cecdf654938)
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
![image](https://github.com/godotengine/godot/assets/37277/d176d823-647d-4a1c-8fa0-73fd9e473c4f)

### Steps to reproduce

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

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](https://github.com/godotengine/godot/files/15217144/convex_decomp_bug.zip)

Contributor guide

Open the contributing guide

Research direction

Start with core/math/geometry_2d.cpp at decompose_polygon_in_convex and run the provided test() reproduction using the attached convex_decomp_bug.zip project. Compare the polygons returned by Geometry2D.offset_polyline for the listed Curve2D variants. Done means the reproduced offset polygon decomposes without the "Convex decomposing failed!" error and produces the expected collision shapes.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
computer-graphics, game-dev
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.