Baking NavigationPolygon fails when two static body rectangular collision edges overlap for 1 pixel vertically

[heyitsdoodler]

Tested versions

Reproducible in Godot 4.2.stable

System information

Godot v4.2.stable - macOS 14.0.0 - Vulkan (Forward+) - integrated Apple M1 - Apple M1 (8 Threads)

Issue description

When static bodies are placed so that the edge of the outline overlaps exactly with another edge for 1 pixel vertically baking fails.

modules/navigation/nav_mesh_generator_2d.cpp:819 - NavigationPolygon Convex partition failed. Unable to create a valid NavigationMesh from defined polygon outline paths.

(In editor or via NavigationRegion2D.bake_navigation_polygon()).

The Agents -> Radius affects how this error occurs. The larger the radius, the further away the "error sweet spot" is.

Baking with radius of 0px

Bake fail

Bake succeed by moving 1 pixel further along edge

Baking with radius of 5px

Bake fail

Bake succeed by moving 1 pixel further along edge

Bake succeed by lining up vertexes exactly

*This behaviour is a bit odd in my opinion, but it isn't the bake failing.

Steps to reproduce

1. Create a new NavigationRegion2D
2. Create a new NavigationPolygon for the NavigationRegion2D
   • Set Agents -> Radius to 0px, this makes the issue easier to reproduce
3. Add two StaticBody2Ds with rectangular collisions
4. Line up a vertical edge so that a single pixel of the edge overlaps
5. Click 'Bake NavigationPolygon'

Minimal reproduction project (MRP)

TestingNav.zip

[heyitsdoodler]

@smix8 I've seen that you've made significant contributions to NavigationRegion related issues in the past, I'm trying to fix this myself but I figure you may be interested in it

[smix8]

At the core these are all precision issues in the rasterization process amplified by a small scale.

https://www.angusj.com/clipper2/Docs/Robustness.htm

Coordinate upscaling or multi-error polygon checks have a siginificant performance cost and are not even capable of fixing "all" edge case bugs that can result from polygon path clipping operations.

[heyitsdoodler]

At the core these are all precision issues in the rasterization process amplified by a small scale.

Would it be possible to optionally drop/leave out polygons that cause an issue so that the baking process doesn't have to fail outright?

I feel that there may be some situations where a soft fail (with a warning perhaps) would be desirable over the entire navigation disappearing, especially in randomly generated or user generated areas.

[smix8]

The polygon partitioning needs the full polytree as it can not determine what is polygon and what is a "hole" without the full context of all involved paths that interact with each other.

[heyitsdoodler]

Wanted to add that I was able to recreate this issue with spheres as well