NavigationServer errors

[gitscher]

Godot version

Godot 3.5 beta 1

System information

Windows 10 Intel i7-7700K 4.20 GHz RAM 64,0 GB

Issue description

Run NavigationServer: print error mesage
imported scene with or generate colision: ConcavePolygonShape or ConvexPolygonShape

Steps to reproduce

1. Start project
2. error messages are output
3. left mouse button to control the agents
4. while holding the left mouse button continuously position update
5. no additional error messages are displayed on the landscape
6. click on the yellow cube field messages appear and performesn drops

Minimal reproduction project

NavigationAgent.zip

[akien-mga]

CC @AndreaCatania @Duroxxigar

[Scony]

I can confirm I've had a lot of errors of type:

ERROR: Attempted to merge a navigation mesh triangle edge with another already-merged edge. This happens when the Navigation's `cell_size` is different from the one used to generate the navigation mesh. This will cause navigation problem

from the very beginning of new navigation implementation. These errors used to happen even if cell_size properties of Navigation and navmesh are the same.

In the past I've been analyzing this issue a bit and the only observation was that it happens on complex geometries only.

[Killfrra]

Also these errors appear if NavigationAgent.radius != NavigationMesh.agent.radius

[Miziziziz]

Getting a lot of these errors as well, attached an example project. Just run and you'll get the errors. if you delete some of the meshes and rebake you won't get them anymore.

E 0:00:02.699 sync: Attempted to merge a navigation mesh triangle edge with another already-merged edge. This happens when the Navigation's cell_size is different from the one used to generate the navigation mesh. This will cause navigation problem.
<C++ Source> modules/navigation/nav_map.cpp:639 @ sync()

Also I've found that having npcs do get_simple_path calls or use NavigationAgent.get_next_location() on these navmeshes will randomly spam this error:
E 0:00:07.225 erase: Condition "!p_I" is true. Returned: false
<C++ Source> ./core/list.h:149 @ erase()

3.5beta_naverror_test.zip

[AndreaCatania]

It's related to the pairing algorithm used to find the near vertices and combine the triangles

godot/modules/navigation/nav_map.cpp

Line 596 in 585231a

if (connections[ek].size() <= 1) {

If it happens with complex geometries, I think that algorithm should be changed with something else.

[Scony]

I've narrowed down the issue and found 2 problems:

1. In @Miziziziz case I've found that due to floating-point arithmetic precision error 2 vertices of the same triangle has been put into the same bucket (cell) by the algorithm mentioned above by @AndreaCatania
2. In @gitscher case I've found that 2 vertices of a triangle were placed in the same bucket (cell) by Recast library - unless we modified them after taking navmesh from Recast.

Due to the above, we've been losing 1 triangle per each error reported by Godot. It was further leading to "holes" in geometry - invisible in debug navmesh, but leading to problems with agents.

Regarding problem (1):

The B and C vertices - separated by 0.3 distance - ended up in the same bucket (cell) meaning AB edge was indistinguishable from AC edge from that moment.
It happened because int(Math::floor(p_pos.z / cell_size)) of both z=9.6 and z=9.9 and cell_size=0.3 was 32 (see https://github.com/godotengine/godot/blob/3.x/modules/navigation/nav_map.cpp#L72)
So, adding AC of blue triangle failed. Also, adding AC of green triangle failed as well (same problem). So in the end we lost both blue and green triangles.

Regarding problem (2):

In this case, 2 vertices of a triangle were placed in the same bucket (cell) - see the cell in the red circle. Since that navmesh is coming from Recast library, I assume it's either Recast error or just a very rare situation that is legal. Anyway, I think @AndreaCatania assumed that such a situation cannot happen. However, since it happened and since 2 triangles were crippled (became a line) we've lost a total of 4 triangles sharing the affected edges.

Since in both cases the triangles which are getting crippled (degraded to line) are very narrow ones, I think it's safe to bypass them in this algorithm just by skipping them. It should have no real impact on anything (maybe with exception of the case (1) where we potentially may lose very narrow triangles at the edges of navmesh).

[akien-mga]

Fixed by #56879.