godotengine / godotengine/godot
Triangulating fails on a single invalid triangle.
- 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
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