search

dweremeichik / godot_autopoly_plugin

A Godot Engine plugin that automatically triangulates Polygon2D nodes - making mesh deformation much easier!
20 stars 3 forks source link

skip non internal vertices and return early #5

Open genevictor opened 1 year ago

genevictor commented 1 year ago

This fixed the bugs, and should be doing less unnecessary checks but it does not consider edge case where a vertices lies on an edge of the outer polygon. But should be fine in most cases.

It prints verbosely which point failed the check

dweremeichik commented 1 year ago

Thanks for reporting issue #4, and for creating this PR. The extra checks that seem to be making this issue worse (it still exists to some extent even with this PR) are necessary. See the images from PR #2 as to what happens when these checks are removed.

Unfortunately Geometry2D.triangulate_delaunay isn't designed to keep all of the generated polygons inside of our external polygon. I'm currently unsure if a different algorithm would improve this issue, or if Geometry2D.triangulate_polygon would be a better candidate.

genevictor commented 1 year ago

Thanks for the reply. I think you're right about Geometry2D.triangulate_delaunay isn't meant for non-convex polygons. I couldn't find a simple way to drop the triangles that lay outside of the polygon perfectly.

A little research points me to some other algorithms which might or might not be feasible to be implemented on the gd script side.

References: constrained Delaunay triangulation Triangulation By Ear clipping