2D NavigationPolygon baked in editor produces Navigation map synchronization error in 4.3

[rob1gat]

Tested versions

• Reproducible in v4.3.stable.official [77dcf97d8]
• NOT reproducible in v4.2.1.stable.official [b09f793f5]

System information

Godot v4.3.stable - Linux Mint 21.3 (Virginia) - X11 - Vulkan (Forward+) - dedicated AMD Radeon RX 6700 XT (RADV NAVI22) - 12th Gen Intel(R) Core(TM) i5-12400 (12 Threads)

Issue description

On a simple project (see MRP), I have a NavigationRegion2D (with a simple rectangular outline) and 2 Polygons.

When I launch my scene, I get an error :

E 0:00:00:0231   sync: Navigation map synchronization error. Attempted to merge a navigation mesh polygon edge with another already-merged edge. This is usually caused by crossing edges, overlapping polygons, or a mismatch of the NavigationMesh / NavigationPolygon baked 'cell_size' and navigation map 'cell_size'. If you're certain none of above is the case, change 'navigation/3d/merge_rasterizer_cell_scale' to 0.001.
  <Source C++>   modules/navigation/nav_map.cpp:990 @ sync()

cell_size values are equal and changing navigation/3d/merge_rasterizer_cell_scale to 0.001 has no effect.

Taking a closer look at the produced polygon, I can see this (I guess) problematic triangle :

The thing is, when I open the same project in 4.2.1 and I rebake the navigation map, the produced polygon does not have this problematic triangle, and then I don't have the error. Is it a regression ?

Steps to reproduce

• Open MRP
• Launch scene and look at output for the error

Minimal reproduction project (MRP)

MRP : mrp_navmapsynchroerror.zip

[smix8]

Godot 4.2 forced position integer snapping, that was removed due to popular demand. In Godot 4.3 it allows to use floats and they get up and downscaled. So all the float precision issues with certain layouts can now survive that would have been removed by the old integer snap. You need to snap or otherwise prevent those situations manually now.

[rob1gat]

Thanks for your answer. Could you tell me what settings I should modify to have integer snap ?

[smix8]

There is no direct setting but you can e.g. enable the editor toolbar snapping so that your positions are not running with some weird float numbers, that alone can help a lot.

In general you also want to avoid creating long-distances edges that are only very slightly skewed or rounded shapes that have more edges, because those all gives you more often those kind of tiny polygons that may have difficulties to rasterize properly, it is very layout depending.

If nothing helps loop over the vertices in script and snap them manually, that is also what the official navmesh chunk demo does because float ops are never that precise and you dont know how the navmesh baking will partition things upfront.

[rob1gat]

Thanks but my polygons already have integer snapped verticed, and my outlines too. Do you mean I should edit the baked navmesh ?

I am absolutely not experienced with navigation baking, but could the ClipperLib::SimplifyPaths() function be applied to the produced navmesh (with epsilon = cell_size) in order to get rid of these tiny polygons ?

[smix8]

To really fix this in scripts alone you would need to not only snap the vertices of the baked navmesh but also remove any "duplicates", and fix the polygon indices in turn if removed.

The reason why that tiny polygon that has rasterization issues even gets baked is because the general scale is tiny, that white "collision" shape has a lot of tiny small edges and the agent_radius bake size set to 7 is uneven. All those things together make a very suboptimal bake layout so you end up with more issues to rasterize the resulting edges in the navigation map. E.g. just changing the agent_radius to 6 or 8 removed those tiny edges alone.

[rob1gat]

To really fix this in scripts alone you would need to not only snap the vertices of the baked navmesh but also remove any "duplicates", and fix the polygon indices in turn if removed.

Are there any obstacles to adding this process to the navigation mesh baking ? Maybe performances ?

[smix8]

Performance and because it is not a general fix for bad combinations of layouts and settings. As soon as users rotate and scale or combine with other regions or have different settings its the same issue all over again with rasterization issues. The real fix is to find a combination between geometry and settings that works for a project and the baking can not guess this for users. Same reason why you get light leaks when baking light maps if the mix of geometry and settings just does not work well together.

[rob1gat]

Looking at the code of NavMeshGenerator2D::generator_bake_from_source_geometry_data(), it seems that clipper InflatePaths() function is called (line 957) but path_solution is not simplified then.

To quote clipper documentation (about SimplifyPaths() function):

This function is strongly recommended following offsetting (ie inflating/shrinking), especially when offsetting paths multiple times. Offsetting often creates tiny segments that don't improve path quality.

I (humbly) believe that calling this method could prevent some tiny triangle issues. Moreover, it could improve baking performances since some boolean operations are then performed on path_solution.

What do you think about this ?

[smix8]

I remember I had some commented-out remnant code while developing the 2D navmesh baking using the clipper simplification (RamadaDouglasClass or something back then) and while it worked for some cases it mess-up a lot of others so I removed it again. That was a while ago so if someone else wants to spend time on re-testing this be my guest.

[rob1gat]

I added a call to SimplifyPaths() after InflatePaths() :

if (agent_radius_offset > 0.0) {
    path_solution = InflatePaths(path_solution, -agent_radius_offset, JoinType::Miter, EndType::Polygon);
    path_solution = SimplifyPaths(path_solution, 1.0);
}

With this line of code, the error disappears on the MRP.

I have 2 questions :

• SimplifyPaths() needs a epsilon parameter. On my test, I choose epsilon = 1.0, but I wonder what I could use as a more appropriate value. Do you think cell_size could do the job ?
• Where could I find some projects to test this change ?

[smix8]

SimplifyPaths() needs a epsilon parameter. On my test, I choose epsilon = 1.0, but I wonder what I could use as a more appropriate value. Do you think cell_size could do the job ?

No, that needs to be configurable, likely as a property on the NavigationPolygon.

Where could I find some projects to test this change ?

I am not aware of public projects for this, but there is the recent 2D navmesh baking demo in the godot demo repo for starters.

[rob1gat]

Ok thanks, I tried the nav_mesh_chunks project.

It seems that, when agent radius is equal to 11.0, I get the navigation synchronization error. The project behaves the same in 4.3 and with my modification.

Could you please tell me where I can find information about cell size ? What is it for ? Where is it used ?

[smix8]

The cell sizes is used by the navigation map to rasterize the navigation mesh edges by edge key in order to merge them. In 3D it is also used to define the voxel cell size for the baking.