godotengine / godot

Godot Engine – Multi-platform 2D and 3D game engine
https://godotengine.org
MIT License
91.12k stars 21.19k forks source link

2D Polygon data valid but visual debug throws invalid polygon data, triangulation failed error #52978

Open udit opened 3 years ago

udit commented 3 years ago

Godot version

3.3.3.stable

System information

Windows 10

Issue description

My game procedurally generates polygons and I noticed that it was intermittently throwing Invalid polygon data, triangulation failed error when I enable visible collision shapes. I have isolated few points when this error occurs:

var test_poly = [
        Vector2(-1003.706177, 977.725403),
        Vector2(-1002.706177, 978.509827),
        Vector2(-1001.706177, 979.294678),
        Vector2(-1000.706177, 980.079651),
        Vector2(-999.706177, 980.864563),
        Vector2(-999.706177, 1080)
    ]

As you can see the points form a valid polygon and are in correct order, but it still throws following error:

E 0:00:01.209   canvas_item_add_polygon: Invalid polygon data, triangulation failed.
  <C++ Error>   Condition "indices.empty()" is true.
  <C++ Source>  servers/visual/visual_server_canvas.cpp:775 @ canvas_item_add_polygon()

Steps to reproduce

Provided minimal reproduction project below

Minimal reproduction project

PolygonTest.zip

Calinou commented 3 years ago

cc @Xrayez

Xrayez commented 3 years ago

Godot's triangulator may fail when there are:

  1. Duplicate vertices.
  2. Coincident edges.
  3. Vertices touch edges.
  4. Polygon is self-intersecting in general.

This could be considered a duplicate of #40911, or rather part of the triangulation error problem (see potential solutions and workarounds there).

udit commented 3 years ago

I am quite sure that the example polygon with 6 vertices doesn't fall into 1,2,4 category. Can you explain what you mean by vertices touch edges scenario?

Xrayez commented 3 years ago

Can you explain what you mean by vertices touch edges scenario?

This one:

image

But it appears that this case works in fact. I'm not actually sure what could cause the error, the cases I listed are more like common causes for triangulation libraries...

16423 could likely fix this (for rendering).

udit commented 3 years ago

Could floating point error be the cause since the points are quite close in my example? I transposed the polygon towards origin on x axis and the error disappeared and it comes back on some positions as I keep moving it.

Xrayez commented 3 years ago

Godot compares floats in some cases using CMP_EPSILON. When used in the context of triangulation, perhaps this is where those errors come from...

Therefore, I suggest snapping coordinates to integer values for procedurally generated stuff as a workaround, but I don't know whether it would resolve all errors.