Godot: Geometry.clip_polygons_2d() is bug

[fian46]

Godot version: 3.2rc4

OS/device including version: any

Issue description: instead of cutting a hole it produce stacked polygon if b completely inside a. the behaviour is right if b only clipped part of a.

Steps to reproduce: -

Minimal reproduction project:
geometry.tar.gz

[Calinou]

cc @Xrayez

@fian46 Can you upload a minimal reproduction project to make this easier to troubleshoot, please?

[fian46]

@Calinou done

[fian46]

enable visible navigation debug to see the result in debug menu

[Xrayez]

I wouldn't call this a bug, but this is certainly a limitation in such cases like this. It's expected that the clip_polygons_2d returns two separate polygons, one being the boundary and another one as a hole, because it's impossible to represent it geometrically otherwise, unless it's a keyholed representation of a polygon, which again is not supported by the Clipper library used currently for polygon boolean operation methods. For more details on this see https://github.com/godotengine/godot-proposals/issues/200#issuecomment-549300676.

Having said that, the method can't be blamed for incorrect results for this use case, but further attempts to use such result with other polygon decomposition methods in Godot are limiting indeed:

1. Godot's Geometry.triangulate_polygon doesn't support holes either, and it only works for strictly simple polygons. Recall Bad Polygon! errors?

2. Polypartition used as another thirdparty library in Godot does support holes to some extent. I've tried it myself in the past but it's quite slow for objects with lots of holes and it breaks on degenerate polygons easily. None of the methods are currently exposed to scripting from this library though. It's used for NavigationPolygon in Godot currently. What can be possibly done is exposing some of the library's methods to Geometry singleton to help this, namely Geometry.decompose_polygon_in_convex, with the ability to pass an array of both outer and inner (holes) polygons.

The new Clipper 10.0.0 alpha/beta does support polygon triangulation with holes but it can't be considered stable for production to be used in Godot yet, but it could solve many functional and performance limitations Godot currently has in this area. If you do want to experiment with this on the C++/GDScript level, you can take a look at my godot-clipper module, but then again it doesn't provide this out-of-the-box yet as there's many ways to use the library, and I'm waiting for the library to become stable enough before continuing working in this direction to make this general-purpose perhaps.

[fian46]

After translating and reading the maintainer explanation i can understand this is just some limitations and not a bug. I am sorry for calling it a bug. We can close this issue.

[Xrayez]

@fian46 I solved your use case, what I've done instead is to call make_polygons_from_outlines because that's how those outer/inner polygons get sorted out internally. I haven't used navigation code yet to figure this out sooner. 😛

func cream():
    for i in $Navigation2D.get_children():
        i.queue_free()

    var target = $Polygon2D
    var moving = $Polygon2D2
    moving.position = get_local_mouse_position()

    var pa = extract_polygon(target)
    var pb = extract_polygon(moving)

    var clip = Geometry.clip_polygons_2d(pa, pb)

    var np = NavigationPolygon.new()
    for poly in clip:
        np.add_outline(poly)
    np.make_polygons_from_outlines()

    var npi = NavigationPolygonInstance.new()
    npi.navpoly = np
    $Navigation2D.add_child(npi)

geom-navpoly-clip-solved.zip

[fian46]

It wont work if you split the polygon with the cuter polygon. I try this method because it work on splitting the polygon. I think it some kind of limitations.

[Xrayez]

By splitting you mean something like this?

If yes, then it seems to work with the code I linked, no part is missing.

[fian46]

Let's close this and wait for 4.0 navigation server implementation. The PR looks good.

[fian46]

Wow you solve the missing puzzle. This is amazing, it do work. You are really cool. Now i can generate random level. Thanks man

[akien-mga]

Closing as discussed above.