godot: NavigationPolygon make_polygons_from_outlines fails on specific inner outlines sizes combinations

So @jarmush pretty much already pinpointed the issue. The problem is in here: https://github.com/godotengine/godot/blob/b29bb11a4cb5ffcca6ddcc4d495656f146bfd22a/scene/resources/navigation_polygon.cpp#L270-L272 When the segment (r[0], outside_point) being checked for intersection goes directly through an outline point (e.g. a corner in examples in here) then it’s being deduced to intersect with both outline segments defined by the intersected outline point. But it should be counted only once as it’s a single intersection with that outline.

The current Godot “homebrew” outline calculation proved time and time again to be not very robust with user created outlines.

The convex partion function is responsible for this issue error msg but the source is that the Godot “homebrew” calculation does no fixes for crossing / overlapping polygon outlines and often calculates wrong what is considered a “hole” in a complex polygon.

The plan is to replace it with a solution using Clipper2 polytree to pre-process the outline paths doing all the required “fixes” before forwarding the outlines to the convex partition function.

This approach is already tested in a development branch and yields very promising results even with very complex polygons.

As this change is also part of the 2D navigation mesh baking feature the plan is to add it to pr https://github.com/godotengine/godot/pull/70724.

Problem happens when B corner do not cross AC line

i’m really not good in C++, but i assume that problem may be in NavigationPolygon::make_polygons_from_outlines() function, that tries to find intersections by this code

	for (int i = 0; i < outlines.size(); i++) {
		Vector<Vector2> ol = outlines[i];
		int olsize = ol.size();
		if (olsize < 3) {
			continue;
		}
		const Vector2 *r = ol.ptr();

		int interscount = 0;
		//test if this is an outer outline
		for (int k = 0; k < outlines.size(); k++) {
			if (i == k) {
				continue; //no self intersect
			}

			Vector<Vector2> ol2 = outlines[k];
			int olsize2 = ol2.size();
			if (olsize2 < 3) {
				continue;
			}
			const Vector2 *r2 = ol2.ptr();

			for (int l = 0; l < olsize2; l++) {
				if (Geometry2D::segment_intersects_segment(r[0], outside_point, r2[l], r2[(l + 1) % olsize2], nullptr)) {
					interscount++;
				}
			}
		}

		bool outer = (interscount % 2) == 0;

		TPPLPoly tp;
		tp.Init(olsize);
		for (int j = 0; j < olsize; j++) {
			tp[j] = r[j];
		}

		if (outer) {
			tp.SetOrientation(TPPL_ORIENTATION_CCW);
		} else {
			tp.SetOrientation(TPPL_ORIENTATION_CW);
			tp.SetHole(true);
		}

		in_poly.push_back(tp);
	}

It finds the outside_point first, that is outside the biggest outline, counts how many times something intersects with something, and divide it by modulo 2 to decide is it a hole, or an outer I don’t completely understand what’s the math is going on there, but i think that in some outline sizes combination this function calls tpart.ConvexPartition_HM method with wrong attributes and then fails

Need more-good-in-code guy

@Ninjars yes it is probably the same issue. Have a look at this PR: https://github.com/godotengine/godot/pull/74699 you can try building it and see if it fixes it for you.

Discussion there came to a stop and I didn’t push it further because we still did the fix in our internal godot build. Maybe if there is enough demand the mantainers can have another look at that PR and merge it.

seems like changing the implementation on the function above to something simpler like:

if ((C.y * D.y) > 0) {
	return false;
}

also fixes the issue for both my problem, and the test scene provided by OP. I am now working on some thorough test suite to check what is the outcome on different data inputs.

I have no idea why make_polygons_from_outlines() should work in Godot 3.5 but not in Godot 4 as the navigation related code is identical in that part.

Actually, this bug seems to be present at 3.5, and I am very sorry for wrong information. Godot 3.5 just don’t throw error here, that’s why i was sure that everything works in my old project. I checked it carefully and found out that it has same strange behavior, but instead of failing with error it just draws another outer outline instead of hole, choosing wrong winding here, i suppose (i took the code from master, but it’s the same for 3.5) (https://github.com/godotengine/godot/blob/b29bb11a4cb5ffcca6ddcc4d495656f146bfd22a/scene/resources/navigation_polygon.cpp#L284-L289)

It’s much harder to reproduce than in godot4, cause i cannot see any regularity in its appearance

I have no idea why make_polygons_from_outlines() should work in Godot 3.5 but not in Godot 4 as the navigation related code is identical in that part.

The only thing that I can spot that has received meaningful changes is the underlying ConvexPartition library.

@aaronfranke Can you maybe help here? Your pr updated / modified the ConvexPartition lib in Godot 4. Any idea what could cause this bug or how we can solve it? @kleonc You were pretty quick spotting navigation polygon related issues in the past, maybe you can work a miracle here as well? 😃