godotengine / godotengine/godot

`Geometry2D.triangulate_polygon` returns nothing for small but non-degenerate triangles

Open
#112,705 7 comments 1 reaction 0 assignees View on GitHub
needs testing topic:core
Dominant language
C++
Stars
117k
Forks
26.8k
PR merge metrics
PR metrics pending

Description

### Tested versions

4.5.1 stable

### System information

Godot v4.5.1.stable - Windows 10 (build 19045) - Multi-window, 2 monitors - Vulkan (Forward+) - dedicated AMD Radeon RX 6800 XT (Advanced Micro Devices, Inc.; 32.0.21025.15011) - 11th Gen Intel(R) Core(TM) i7-11700KF @ 3.60GHz (16 threads) - 31.88 GiB memory

### Issue description

When using `Geometry2D.triangulate_polygon` with a very small but non-degenerate triangle, it will sometimes return an empty array. Changing the scale of the triangle very slightly can make it succeed but not always. It also happens sometimes with reasonably large triangles that are far away from the origin.

It seems likely to me that the small triangle is being incorrectly detected as degenerate due to an incorrect area check and/or floating point errors. Poking through the code of `core/math/triangulate.cpp`, I see this triangle area check in `Triangulate::snip`:
```
// It can happen that the triangulation ends up with three aligned vertices to deal with.
// In this scenario, making the check below strict may reject the possibility of
// forming a last triangle with these aligned vertices, preventing the triangulation
// from completing.
// To avoid that we allow zero-area triangles if all else failed.
float threshold = relaxed ? -CMP_EPSILON : CMP_EPSILON;

if (threshold > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) {
return false;
}
```
Elsewhere in the code (`Triangulate::get_area`) the area is calculated by multiplying the cross product by `0.5`. Additionally since this is an area check, I think the constant used should be `CMP_EPSILON2` instead of `CMP_EPSILON` as this is used elsewhere in the codebase for zero-area checks.

This could also potentially be related to #91285.

### Steps to reproduce

Attach the following script to a new `Node2D` in an empty scene and run the scene. You can adjust the scale `s` and see it only fails sometimes depending on the scale.
```gdscript
extends Node2D

var triangle := PackedVector2Array([
Vector2(135.0, 101.2301483154),
Vector2(135.0, 101.3175659180),
Vector2(134.9851989746, 101.25)
])

func _ready():
var s := 1.0
var t := Transform2D(0.0, Vector2.ONE * s, 0.0, Vector2.ZERO)
var triangles := Geometry2D.triangulate_polygon(t * triangle)
assert(not triangles.is_empty())
```

### Minimal reproduction project (MRP)

[triangle-test.zip](https://github.com/user-attachments/files/23514770/triangle-test.zip)

Contributor guide

Open the contributing guide

Research direction

Start in core/math/triangulate.cpp, focusing on Triangulate::snip and Triangulate::get_area and their epsilon checks. Run the supplied GDScript reproduction or triangle-test.zip across the reported scales, then verify that valid small or far-from-origin triangles produce indices without changing handling of genuinely degenerate input.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, godot
Domain
computer-graphics, game-dev
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.