Geometry.clip_polygons_2d sometimes produces polygon that can't be triangulated

davidscholberg commented 3 years ago

Godot version

v3.3.3.stable.official.b973f997f

System information

Windows 10, OpenGL ES 3.0 Renderer: GeForce GTX 1070/PCIe/SSE2

Issue description

I am attempting to use Geometry.clip_polygons_2d in the following way; I have an initial polygon that must be clipped against a series of other polygons. I use the results of a given call to Geometry.clip_polygons_2d as the polygon_a input in the next clip iteration. The resulting polygon after all clip iterations is then drawn on the screen.

Occasionally, Geometry.clip_polygons_2d used in this manner will produce a polygon that can't be triangulated (and therefore can't be drawn), even though both input polygons are triangulatable. I haven't been able to come up with a simpler contrived example, so I just used actual data taken from the program for the attached reproduction project.

Here's the code from the reproduction project:

extends Node2D

var polygon_a: PoolVector2Array
var polygon_b: PoolVector2Array

func check_triangulation(polygon: PoolVector2Array) -> void:
    print("checking triangulation of " + str(polygon) + "...")
    if Geometry.triangulate_polygon(polygon).empty():
        print("triangulate polygon failed")
    else:
        print("triangulate polygon succeeded")

func _ready() -> void:
    polygon_a = PoolVector2Array([
        Vector2(210.119263, -83.963669),
        Vector2(214.227539, -82.201302),
        Vector2(7.50003, 6.48172),
        Vector2(7.50001, -0.04702),
        Vector2(211.698547, -87.645149),
    ])
    polygon_b = PoolVector2Array([
        Vector2(193.326523, -125.987572),
        Vector2(180.710968, -96.579277),
        Vector2(210.119278, -83.963722),
        Vector2(54745.601563, -23478.873047),
        Vector2(54728.808594, -23520.898438),
    ])

    check_triangulation(polygon_a)
    check_triangulation(polygon_b)

    print("clipping polygon_a against polygon_b")
    var clipped_polygons: Array = Geometry.clip_polygons_2d(polygon_a, polygon_b)
    for polygon in clipped_polygons:
        check_triangulation(polygon)

func _draw() -> void:
    draw_colored_polygon(polygon_a, Color("00FF00"))
    draw_colored_polygon(polygon_b, Color("880000FF"))

Here's the text output when it's run:

checking triangulation of [(210.119263, -83.963669), (214.227539, -82.201302), (7.50003, 6.48172), (7.50001, -0.04702), (211.698547, -87.645149)]...
triangulate polygon succeeded
checking triangulation of [(193.326523, -125.987572), (180.710968, -96.579277), (210.119278, -83.963722), (54745.601563, -23478.873047), (54728.808594, -23520.898438)]...
triangulate polygon succeeded
clipping polygon_a against polygon_b
checking triangulation of [(210.119278, -83.963722), (210.119278, -83.96373), (210.119263, -83.963661), (214.227524, -82.201302), (7.50003, 6.48171), (7.50001, -0.04701), (206.618042, -85.465683)]...
triangulate polygon failed

And here's a screenshot of the two polygons being clipped, scaled up and repositioned to better see the intersection between the them:

ClipPolygonTest

The trouble seems to be with that inner concave point on polygon_a; both polygon_a and polygon_b share a nearly identical point there, and that point seems to be near-duplicated twice in the clipped polygon. Why the point is near-duplicated at all I have no idea.

Steps to reproduce

Open the reproduction project and run it.

Minimal reproduction project

ClipPolygonTest.zip

Calinou commented 3 years ago

Xrayez commented 3 years ago

When doing triangulation with Goost after clipping, I get this expected result:

ClipPolygonTestGoost.zip (requires Goost to run).

So at least we know it's not an issue with clipping, but triangulation. For this, see #52978 and #40911 to get the idea of why errors like this happen.

Why the point is near-duplicated at all I have no idea.

I think it makes sense, shapes are not perfectly aligned, so this leaves a very small dent after clip, something like this when "zoomed in":

davidscholberg commented 3 years ago

@Xrayez thank you for the info!

So I started using GoostGeometry2D.triangulate_polygon in my program to pre-triangulate the clipped polygons before drawing them, as a workaround. The problem appears to be solved visually in that most of the polygon is being drawn as opposed to none of it being drawn, but now there's a different problem; GoostGeometry2D.triangulate_polygon sometimes produces triangles that have two identical points, and when you pass these triangles to a draw call, they still fail on the internal triangulate call. So now my debug console is flooded with triangulate errors. Is there any way around this other than manually checking for duplicate points in these triangles?

davidscholberg commented 3 years ago

Actually, it turns out that checking for duplicate or near-duplicate points is not enough, because there are some triangles being produced that don't have close points but are very thin with little area, and these triangles fail the internal triangulate call (for example, this triangle: PoolVector2Array([Vector2(565.243774, 27.82868), Vector2(559.238037, 28.207991), Vector2(527.298523, 30.22521),])). So what I had to do instead was just manually call Geometry.triangulate_polygon and prevent all triangles that fail this call from being drawn. Because these triangles are so small or have such little area, discarding them doesn't seem to be having a significant impact visually.

Xrayez commented 3 years ago

GoostGeometry2D.triangulate_polygon sometimes produces triangles that have two identical points, and when you pass these triangles to a draw call, they still fail on the internal triangulate call.

In that case you can directly draw the triangles via VisualServer.canvas_item_add_triangle_array(). If you decide to use Goost, you could also use scene-based approach via PolyNode2D class which already does boolean operations and drawing the result, much like CSG nodes in 3D.

In any case, you can refer to this C++ implementation on how to use VisualServer.canvas_item_add_triangle_array(): https://github.com/goostengine/goost/blob/20d8ce4c7d74c26832d69283305b25a72165784a/core/math/geometry/2d/poly/poly_node_2d.cpp#L41-L77.

davidscholberg commented 3 years ago

@Xrayez thank you again for the info!

For now I'll stick with the manual clipping approach and draw with VisualServer.canvas_item_add_triangle_array. Here's what my _draw function now looks like for anyone wanting to use this approach as a workaround:

func _draw() -> void:
    var triangles: Array = []
    for clipped_polygon in clipped_polygons:
        triangles.append_array(GoostGeometry2D.triangulate_polygon(clipped_polygon))
    if triangles.empty():
        return
    var vertices: Array = []
    for triangle in triangles:
        vertices.append_array(Array(triangle))
    VisualServer.canvas_item_add_triangle_array(get_canvas_item(), range(vertices.size()), vertices, [color])

godotengine / godot