NavigationPolygon make_polygons_from_outlines fails on specific inner outlines sizes combinations

[jarmush]

Godot version

v4.0.beta10.official [d0398f62f]

System information

Windows 10

Issue description

I'm making navigation region and I want to place a polygon inside a hole inside a polygon, like here ^ I expect to use big counterclockwise outline first, then add smaller clockwise outline, and finally add smallest counterclockwise outline. I create three outlines and everyting works fine.

    var poly1 = PackedVector2Array([Vector2(500, -50), Vector2(500, 500), Vector2(-50, 500), Vector2(-50, -50)])
    var poly2 = PackedVector2Array([Vector2(101, 101), Vector2(101, -5), Vector2(-5, -5), Vector2(-5, 101)])
    var poly3 = PackedVector2Array([Vector2(59, 59), Vector2(37, 59), Vector2(37, 37), Vector2(59, 37)])

And these outlines works fine if order is Counterclockwise(poly1)->Clockwise(poly2)->Clockwise(poly3) or if Counterclockwise(poly1)->Clockwise(poly2)->Counterclockwise(poly3)

But then I try to make another navigation region with bigger outer outline (poly1 array), wierd things happen. I use

    var poly1 = PackedVector2Array([Vector2(600, -50), Vector2(600, 600), Vector2(-50, 600), Vector2(-50, -50)])
    var poly2 = PackedVector2Array([Vector2(101, 101), Vector2(101, -5), Vector2(-5, -5), Vector2(-5, 101)])
    var poly3 = PackedVector2Array([Vector2(59, 59), Vector2(37, 59), Vector2(37, 37), Vector2(59, 37)])

If order is Counterclockwise(poly1)->Clockwise(poly2)->Clockwise(poly3) everything is fine. If order is Counterclockwise(poly1)->Clockwise(poly2)->Counterclockwise(poly3) i get an error NavigationPolygon outlines can not overlap vertices or edges inside same outline or with other outlines or have any intersections.

Steps to reproduce

Open minimal reproduction project included, turn on "Visible navigation" in "Debug" menu Press "500x500" button Run agaun Press "600x600" button

Minimal reproduction project

testtileminim.zip

[smix8]

In this layout case it is better to use the NavigationRegion2D polygon draw tool to copy from example of a valid NavigationPolygon resource with a similar layout. The 2D outline PackedVector2Arrays need to be in same winding for all outlines as the conversion takes place internally, e.g. like ...

[resource]
outlines = [PackedVector2Array(0, 0, 256, 0, 256, 256, 0, 256), PackedVector2Array(64, 64, 192, 64, 192, 192, 64, 192), PackedVector2Array(96, 96, 168, 96, 168, 168, 96, 168)]

... but also a part of the error msg is wrong / obscure as the winding is for (internal) polygons using the Clipper lib but the error msg still talks about outlines. I also noticed that on smaller displays Godot Editor is unable to display the full error msg due to length and cuts it of at an inconvenient part adding to the confusing.

That said even if this solves the immediate error msg it will not fix the NavigationPolygon. NavigationPolygons can not self-connect on the NavigationServer so those inner regions will be largly useless for pathfinding. If islands are needed better create them with a separate NavigationRegion2D so connections can work between them.

The reason why it is even possible to draw such a navigation-dysfunctional 2D polygons in the Editor is cause the Editor polygon draw function is generic and shared with other Editor parts and those have a far less strict requirement.

[jarmush]

Thank you for clarifying. A little backstory: my 2d top-down project was based on tilemaps and i used tilemap navigation first. But tilemaps create a separate region for every tile. I make infinite world with procedurally generated map (new chunks spawned when needed) and typically I have 100k - 200k tiles in game world. Every time when new map chunk spawns it freezes the game, cause new 10k navigation regions (100x100 tiles tilemap) added That's why i considered to not use tilemaps for navigation and manage single navigation region around a player by code.

I cannot draw NavigationRegion2D polygon in editor, because player can change it ingame. When player build something, the game changes the cell in tilemap to draw sprite and to create collider, and for navigation it creates innternal polygon (hole) in navigation region

So if i got it right, if player, (for example), build a wall, surrounding himself from all sides, navigation won't work inside this inner polygon (that island inside a hole)? So i have to somehow find if an "island" forming when "holes" are merging inside navigation region's polygon, while player is building a wall tile-by-tile, and then if so - I have to make a new region that have a polygon inside these new big "hole"?

[smix8]

Basic pathfinding on an island when the player is also trapped on that very same island should still work.

What wouldn't work is the edge merge between islands. E.g. if you bring an island edge close enough to another island edge where it normally would connect by edge proximity it wouldn't if both islands are from the same NavigationPolygon. In this case you need to use two NavigationRegion2D for the proximity connection to occur between the two islands.

TileMap at the moment is not very efficient when it comes to navigation so using a NavigationRegion2D to bundle a larger area of tiles together is a good choice for both performance and path quality. I did not expect you to handdraw this polygons in the Editor, only create one with the Editor so you have the correct resource format at hand to copy from.

[jarmush]

now its perfectly clear, thanks. Each outline must be in same winding. I changed my minimal reproduction project and all PackedVector2Array are CCW now. Problem still exists, try to turn on "Visible navigation" and press 500 vs 600 buttons here testtileminim.zip

[jarmush]

Works fine in 3.5.1 btw, just for information. In any winding direction combinations. It was so useful for me to keep different winding for polygons outlines and for holes outlines, because i don't want to compare each outline to each outline every navigation update, when i can simply do

        if Geometry2D.is_polygon_clockwise(outline):
            holes.append(outline)
        else:
            islands.append(outline)

[jarmush]

i found the exact coordinate, where error begins try this buttons, 475 works fine, 476 causes error testtileminim475.zip

[smix8]

Since Godot 3.5 seems to work fine this narrows down the bug sources as the NavigationPolygon code that should be relevant for this error msg is basically identical between Godot 4 and 3.5.

Navigation unrelated this NavigationPolygon function uses multiple Godot core libs behind the scene that got changed in Godot 4 compared to Godot 3.5. The polypartition thirdparty library comes to mind (which is called a step before this error) that was not only changed for Godot 4 but also received a custom Godot patch that does not exist in Godot 3.5.

It is only an assumption but possible that this pr https://github.com/godotengine/godot/pull/45125 added some unforeseen problems.

[jarmush]

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

[jarmush]

Renamed issue because it seems not related to winding direction itself, but more to finding inner/outer outline algorithm

[smix8]

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? :)

[kleonc]

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.

[aaronfranke]

@smix8 I don't know much about the library, the update I did awhile ago had superficial involvement by me.

[jarmush]

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

[jarmush]

@kleonc how about this ^ solution? I've added offsets to prevent the "line" to go straight through other outline's point when outlines are snapped to grid (for example, like in my case)

[kleonc]

@jarmush It's feels hackish to me. Even if it fixes your use case I doubt it really fixes the issue. Very likely it just makes a different specific use case failing instead.

BTW my previous comment:

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.

is not fully correct. Whether an intersection going directly through an outline point should be counted just once depends on how the outline segments incident to the intersection point are oriented in relation to each other and to that intersection point. It should be counted just once only when this instersection in an actual "crossing":

[smix8]

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.

[0xafbf]

I faced this issue today, don't know if is the exact same issue but feels similar. My use case is that I use navmesh generation with some extremely small numbers ( in the -PI~PI range) I feel that the issue is not exactly in navmesh generation, but in the segment collision detection.

I found that changing the order in which the segments are provided yields different (and more accurate) results. I modified the call like this:

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

because I found that the operation to find if the vertex is inside a polygon was tracing a segment through a vertex directly, and this ended up counting two segments instead of one. doing it this way detects if the vertex is in or out correctly.

I am now looking suspiciously at the segment_intersects_segment function, specially this part:

if ((C.y < (real_t)-CMP_EPSILON && D.y < (real_t)-CMP_EPSILON) || (C.y > (real_t)CMP_EPSILON && D.y > (real_t)CMP_EPSILON)) {
    return false;
}

I'll come back with any result I get from further experiments

[0xafbf]

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.

[Ninjars]

Possibly related to challenge I'm facing with Godot 4.1.1 stable: I'm trying to add holes to a navigation polygon at runtime but I'm finding that at certain values I'll get the "convex partition failed" error, and other values I'll end up with multiple polygons overlaid atop one another rather than them becoming holes.

As an example, this simple sequence of nested squares centered at the origin fails with "convex partition failed" :

extends NavigationRegion2D
func _ready():
    var navPoly = NavigationPolygon.new()

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-500, -500),
            Vector2(500, -500),
            Vector2(500, 500),
            Vector2(-500, 500),
        ]))

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-300, -300),
            Vector2(300, -300),
            Vector2(300, 300),
            Vector2(-300, 300),
        ]))

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-10, -10),
            Vector2(10, -10),
            Vector2(10, 10),
            Vector2(-10, 10),
        ]))

    navPoly.make_polygons_from_outlines()

    set_navigation_polygon(navPoly)

However, just changing one of the params to make the middle polygon irregular it succeeds and generates the expected inner navigation island surrounded by a hole in the outer navigation region:

extends NavigationRegion2D
func _ready():
    var navPoly = NavigationPolygon.new()

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-500, -500),
            Vector2(500, -500),
            Vector2(500, 500),
            Vector2(-500, 500),
        ]))

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-350, -300), # changed -300 to -350
            Vector2(300, -300),
            Vector2(300, 300),
            Vector2(-300, 300),
        ]))

    navPoly.add_outline(
        PackedVector2Array([
            Vector2(-10, -10),
            Vector2(10, -10),
            Vector2(10, 10),
            Vector2(-10, 10),
        ]))

    navPoly.make_polygons_from_outlines()

    set_navigation_polygon(navPoly)

I even found what seemed to be an instability or race condition, where I saw it work once then changed a value on an unrelated and when I ran a second time it failed.

This is most frustrating, as as far as I can see I'm not doing anything unusual and appears to be in-line with both docs and general examples, but this is a major blocker for even simple procedurally generated maps. It certainly feels like something is very off with the "polygon from outline" algo.

[0xafbf]

@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.

[Ninjars]

Looks like I was just a couple of days early trying to do this, given that merge! I'll have to see if 4.2 serves me better on this front.