godotengine / godotengine/godot

Triangulating fails on a single invalid triangle.

Open
#101,048 3 comments 1 reaction 0 assignees View on GitHub
breaks compat discussion topic:2d topic:core
Dominant language
C++
Stars
117k
Forks
26.8k
PR merge metrics
PR metrics pending

Description

### Tested versions

Reproducible in: versions 4.0+ and probably below but didn't really test

### System information

All platforms

### Issue description

When triangulating a 2d polygon, triangulate_polygon() fails and returns an empty array while the underlaying triangulate() function generates a mostly usable (though maybe incomplete) triangularisation.

Longer description of the situation where this problem arises:
I'm creating a small drawing app where the user can draw filled polygons with the mouse. This easily generates some invalid points which causes the complete fill to disappear. This is because in geometry_2d.h the triangulate_polygon() function discards the generated triangularisation if the triangulate() returns false.

a possible fix is to just ignore the error status returned by the triangulate function and always return the result:

```
diff --git a/core/math/geometry_2d.h b/core/math/geometry_2d.h
index abd395d8df..946a57ab42 100644
--- a/core/math/geometry_2d.h
+++ b/core/math/geometry_2d.h
@@ -345,7 +345,8 @@ public:
static Vector triangulate_polygon(const Vector &p_polygon) {
Vector triangles;
if (!Triangulate::triangulate(p_polygon, triangles)) {
- return Vector(); //fail
+ //return Vector(); //fail
+ // maybe somehow report a warning?
}
return triangles;
}

```

This leads to much more stable triangularisations, but I'm not sure if we'd want to maybe generate a warning that some invalid triangles/points were detected? And how to do that.

### Steps to reproduce

In the supplied project start it and draw with the mouse. As soon as the resulting polygon is invalid it completely disappears.

With the above patch it behaves much more like other drawing apps. I'm not sure if this is the 'correct' way to solve this, but it seems a shame to just throw away the (mostly valid) triangularisation.

### Minimal reproduction project (MRP)

[drawpolygon.zip](https://github.com/user-attachments/files/18294061/drawpolygon.zip)

Contributor guide

Open the contributing guide

Research direction

Start with core/math/geometry_2d.h, focusing on triangulate_polygon() and the underlying Triangulate::triangulate() behavior. Run the supplied drawpolygon.zip project and reproduce the disappearing fill with an invalid polygon. Done means the behavior for partially invalid triangulations is defined and the reproduction no longer loses the usable result unexpectedly.

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
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.