Improper navigation mesh merging in some cases

[arislapot]

Tested versions

• Reproducible in 4.2.stable, 4.3.stable and 4.4.dev-4

System information

Godot v4.3.stable - Windows 10.0.22631 - Vulkan (Forward+) - dedicated NVIDIA GeForce RTX 4070 Ti SUPER (NVIDIA; 32.0.15.6603) - AMD Ryzen 7 7800X3D 8-Core Processor (16 Threads)

Issue description

The navigation polygon baking doesn't seem to be working properly in some situations as described in the "steps to reproduce" section.

Steps to reproduce

To reproduce, create a new scene with a Node2D and attach the following script:

extends Node2D

var navigation_region = NavigationRegion2D.new()

func _ready() -> void:
	navigation_region.navigation_polygon = NavigationPolygon.new()
	var agent_radius = 0
	navigation_region.navigation_polygon.baking_rect = Rect2(
		0,
		0,
		500,
		500,
	)
	navigation_region.navigation_polygon.agent_radius = 0

	var source_geometry_data = NavigationMeshSourceGeometryData2D.new()
	source_geometry_data.add_traversable_outline([
		Vector2(0, 0),
		Vector2(500, 0),
		Vector2(500, 500),
		Vector2(0, 500),
	])

	for j in range(1, 5):
		for i in range(1, 5):
			var top_left = Vector2(i * 100 - 50, j * 100 - 50)
			var bottom_right = Vector2(i * 100 + 50, j * 100 + 50)
			var outline = [
				top_left,
				Vector2(bottom_right.x, top_left.y),
				bottom_right,
				Vector2(top_left.x, bottom_right.y),
				top_left
			]
			if (
				(i == 1 and j == 1)
				or (i == 2 and j == 2)
			):
				source_geometry_data.add_obstruction_outline(outline)
	add_child(navigation_region)
	NavigationServer2D.bake_from_source_geometry_data(
		navigation_region.navigation_polygon,
		source_geometry_data
	)

Enable "Visible Navigation" from the debug menu and run the scene. You should see the following:

This is suppose to show 2 squares without navigable areas. Instead, the second square has a triangle drawn inside.
This issue doesn't happen if navigation_region.navigation_polygon.agent_radius is above 0.

I also reproduced the same issue using traversable outlines only, instead of adding obstructions.
Also with the 2D scene editor using polygons:

[gd_scene load_steps=3 format=3 uid="uid://b2yb1u0la5ykh"]

[sub_resource type="NavigationPolygon" id="NavigationPolygon_41b13"]
vertices = PackedVector2Array(0, 0, 0, -40, 100, -100, 100, 100, -40, -40, -40, -80, -100, 100, -40, 0, -100, -100, -80, -80, -80, -40)
polygons = Array[PackedInt32Array]([PackedInt32Array(0, 1, 2, 3), PackedInt32Array(2, 1, 4, 5), PackedInt32Array(0, 3, 6, 7), PackedInt32Array(8, 2, 5, 9), PackedInt32Array(6, 8, 9, 10), PackedInt32Array(7, 6, 10, 4), PackedInt32Array(7, 4, 1), PackedInt32Array(7, 1, 4)])
outlines = Array[PackedVector2Array]([PackedVector2Array(-100, -100, 100, -100, 100, 100, -100, 100)])
agent_radius = 0.0
baking_rect = Rect2(-100, -100, 200, 200)

[node name="Node2D" type="Node2D"]

[node name="NavigationRegion2D" type="NavigationRegion2D" parent="."]
navigation_polygon = SubResource("NavigationPolygon_41b13")

[node name="Polygon2D" type="Polygon2D" parent="NavigationRegion2D"]
z_index = -1
polygon = PackedVector2Array(-80, -80, -40, -80, -40, -40, -80, -40)

[node name="Polygon2D2" type="Polygon2D" parent="NavigationRegion2D"]
z_index = -1
position = Vector2(40, 40)
polygon = PackedVector2Array(-80, -80, -40, -80, -40, -40, -80, -40)

This gives the following error:

E 0:00:00:0602   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.
  <C++ Source>   modules/navigation/nav_map.cpp:990 @ sync()

Minimal reproduction project (MRP)

navtest.zip

[smix8]

I am not sure a lot can be done here considering that polygon outline ops are inherently picky when it comes to certain input.

The agent radius can't be really disabled while the input layout includes a mix to form the perfect mortal sin that can be done for polygon outline calculations (integer snapped vertices + axis aligned edges + nested outlines + corner vertex overlap).

This issue doesn't happen if navigation_region.navigation_polygon.agent_radius is above 0.

There is the solution.

The reason why the agent radius is a solution is because due to its (tiny) offset it fixes all the rasterization and interpretation issues caused by the bad input as it reinterprets all the outlines after the offset. Without agent radius the raw input is consumed and the result, while not technically wrong, is interpreted wrong causing flipped polygons which is unwanted.

The baking rect also does a quick cutout that does not reinterpret all the outlines again, which means if there are already some nested outline interpretation errors they get amplified by using the baking rect. The agent radius before basically fixes the errors so the baking rect can work reliable. I am not sure why this combo is even used considering that the baking rect is designed for chunk baking with agent radius. Without an agent radius it is not really needed. Just an outline with this rect shape can be added instead that does the same simpler and more reliable.