Unable to perform polygon boolean operation on a list of polygons simultaneously

[Xrayez]

Godot version:
3.2, 4.0

Pertains to #28987.

Issue description:
Currently it's not as easy to perform polygon boolean operations with Geometry methods like merge_polygons_2d on a list of polygons. One has to use these methods in multiple iterations, for instance, to merge a list of polygons that may or may not be adjacent to each other, see this use case.

Steps to reproduce:

var polygons = [] # assume they all can be merged into one polygon
var poly_a = polygons[0]

for idx in range(1, polygons.size()):
    var poly_b = polygons[idx]
    var solution = Geometry.merge_polygons_2d(poly_a, poly_b)
    assert(solution.size() == 1) # might fail as polygons may be far apart
    poly_a = solution[0]

@Dr4kzor, @avencherus

[Xrayez]

@Dr4kzor, in order to solve your issue, you first you need to make sure the tiles do overlap, having them adjacent might not be sufficient. If they do not overlap, you could grow them with offset_polygon_2d by a tiny positive delta first.

Then, you could perform some sort of flood fill algorithm against your tiles to ensure connectivity. So there would be two cases: one type of merge that increases your overall merged polygons area and ones that do not contribute to the overall area. You would have to keep track of each visited tile. In the end, you'll get a set of merged areas (polygons) that way.

But yes, having ability to add all polygons before doing a single merge operation would simplify your use case, and is actually possible under the hood, though I'm not sure whether it's worth it to have ability to add an array of polygons as it could potentially make the implementation/interface more complex.

[Xrayez]

@avencherus responding to your comment, I feel like the implementation might need to be changed to cater more use cases. There's a notion of Subject and Clip polygons which are represented as single polygon_a and polygon_b here. Merging polygons doesn't require to have this distinction, so they could be all Subjects.

In this case, having merge_polygons_2d(polygons : Array) would be quite acceptable. But then you have other methods like clip_polygons_2d that do distinct between Subject and Clip polygons. So going with the same approach, these methods would have to be changed as:

clip_polygons_2d(polygons_subject : Array, polygons_clip : Array)
intersect_polygons_2d(polygons_subject : Array, polygons_clip : Array)
exclude_polygons_2d(polygons_subject : Array, polygons_clip : Array)

Instead of:

clip_polygons_2d(polygon_a : PoolVector2Array, polygon_b : PoolVector2Array)
intersect_polygons_2d(polygon_a : PoolVector2Array, polygon_b : PoolVector2Array)
exclude_polygons_2d(polygon_a : PoolVector2Array, polygon_b : PoolVector2Array)

This is was I meant by additional complexity added to core, but if it worth it, these could be rewritten to operate on array of polygons rather than single polygons, one would have to use it like that:

# Notice constructing additional arrays to merge single polygons
Geometry.clip_polygons_2d([polygon_a], [polygon_b])

As these methods return an array of polygons as a result of operation already, yeah this starts to make more sense to me to have this that way, so you could pass the result of operation to other methods as input quite easily.

[ghost]

I see. If I understand, you'd have to load all your polygons into a subject array and feed them in that way. Leaving the clip array empty.

You may have to break with the language of the api, because the complexity is in the implementation details and their concepts. Does an end user that wants to merge distant polygons need to first get familiar with the concepts of subject polygons and clip polygons?

I think your concerns about the complexity of those two arrays of polygons is correct. Stuffing parameters into arrays does add a little bit of mental overhead, which would go away once you got familiar with how it was working. But needing to understand additional concepts about the back-end is going to add quite a bit of friction.

If it was left with no documentation, it would be very time consuming to figure out how it was working, at least if you're like me and approaching it ignorant of the library.

I imagine you could keep with the 1 to 1 polygon if you created multiple functions or additional parameters that changed the behavior.

So here would be some ideas that are hopefully more specific, but I can't be too specific since I'm not familiar with the API and what you're having to wrangle together.

1. Additional parameters to change the behavior.

merge_polygons(a : PoolVector2Array, b : PoolVector2Array, only_when_intersecting : bool = true)

Or phrasing the same parameter differently.

merge_polygons(a : PoolVector2Array, b : PoolVector2Array, fill_gaps : bool = true)

2. If the branching or implementation get ugly, it might be worth splittting things up into more methods and change the terminology as best as possible to represent what the user intentions would typically be.

Below are two more thoughts about signatures. The first just combines everything into the fewest points. the second one has clipping types as a parameter. Then most of the documentation about the clipping is contained in the TYPE/MODE constants.

combine_polygons(a, b)
clip_polygons(a, b, clip_type : int = UNION)

[Xrayez]

I see. If I understand, you'd have to load all your polygons into a subject array and feed them in that way. Leaving the clip array empty.

This is not really a problem as the signature could be changed to accept subject polygons only for merge_polygons_2d(polygons). For other methods, it is acceptable that clip polygons array might be empty, the underlying library handles that smoothly returning subject polygons (possibly it also eliminates some self-intersections as well even if no operation has occurred).

So here would be some ideas that are hopefully more specific, but I can't be too specific since I'm not familiar with the API and what you're having to wrangle together.

These would lead to changing how the underlying library works or coming up with custom solutions which feels quite specific indeed. The logic behind those would certainly blow up (similarly to what I've done in the past via scripting). Passing an array would solve most of the use cases I believe.

The approach with replacing single polygon parameters with arrays seems fine to me. I think it might be possible to accept Variants as arguments which would be treated automatically as either single polygon (PoolVector2Array) or an array of polygons (Array) for convenience.

clip_polygons(a, b, clip_type : int = UNION)

I thought about that but the user would find it more difficult to search for specific methods, and it's hard to come up with a generic name for polygon boolean operation, mixing up names like clip_polygons and default operation as UNION would confuse people.

[Daw11]

I think that the Variant parameter is the best solution to the problem.

@Xrayez The Clipper library has a property called PreserveCollinear, if you are merging together the outlines of a NavigationPolygon then this option must be active because otherwise the resulting polygon won't be able to connect with his neighbours.

Could it be possible to have it as an additional optional parameter? ( default to false )

[Xrayez]

@Daw11 I haven't used PreserveCollinear option to tell if this would really solve this, if you could provide an example input polygons to test this I could try it out, but here's my concern.

The new version of Clipper (10.0.0, beta) doesn't have these init options at all, so it could imply that those could be mere "hacks" in the 6.4.2. StrictlySimple option was also removed in 10.0.0 which severely impacted performance in 6.4.2, the new version just ensures that the output polygons are indeed strictly simple without performance bottlenecks.

So if we're ever going to upgrade to the newest version at some point, those options would make no sense anymore.

Perhaps PreserveCollinear could be enabled by default but there's a reason why it's not enabled (again performance reasons?)

But I think it wouldn't hurt to add this as optional parameter only for merge operation where this would make more sense. For that matter, an optional StrictlySimple option could be added to merge method as a way to ensure polygons are strictly simple, so we don't have to expose another method just for simpifying polygons like simplify_polygons_2d. In the new version these options would have to be ignored, or reused if other clipping implementation replaces Clipper (unlikely, I think it's the best library out there).

[ghost]

clip_polygons(a, b, clip_type : int = UNION)

I thought about that but the user would find it more difficult to search for specific methods, and it's hard to come up with a generic name for polygon boolean operation, mixing up names like clip_polygons and default operation as UNION would confuse people.

Good points. That was also a syntax mistake on my part, I was a bit fixated on showing all at once it would take constants, but yeah, ended up being an unintentional default parameter. XD

[Daw11]

@Xrayez I did a test and with PreserveCollinear at true it generates the correct result for a NavigationPolygon.

true

false

However I noticed that with version 6.4.2 PreserveCollinear is not always reliable and sometimes it fails to merge the polygons and it keeps them separated. So I don't think that it should be the default option for the function.

I looked at the source code of version 10 and at first glance it seems that they don't remove the extra edges anymore. I think that it's disabled in version 6.4.2 because in that version it didn't always work.

On a different topic,
would processing the polygons from the smallest to the largest improve the performance?
It would require to sort an array of references by the size of each polygon, so I'm not sure if ultimately it would be faster than not doing it.

[Xrayez]

would processing the polygons from the smallest to the largest improve the performance?

I think it doesn't matter for Clipper, or in fact similar is done already internally by sorting vertices according to Y coordinate as a requirement for Vatti algorithm:

The Vatti algorithm involves processing both subject and clipping polygon edges in an orderly fashion, starting with the lowermost edges and working towards the top; this is conceptually similar to the Bentley–Ottmann algorithm. This sweep line approach divides the problem space by scanlines, imaginary horizontal lines that pass through every vertex of the participating polygons. These scanlines outline scanbeams – the spaces between adjacent scanlines. These scanbeams are processed in turn, starting with the lowest scanbeam, with the algorithm adding points of intersection within these scanbeams into the solution polygons.

[Xrayez]

@Xrayez The Clipper library has a property called PreserveCollinear, if you are merging together the outlines of a NavigationPolygon then this option must be active because otherwise the resulting polygon won't be able to connect with his neighbours.

Could it be possible to have it as an additional optional parameter? ( default to false )

I've created GeometryTools module with both Clipper 6.4.2 and 10.0.0 backends.

PreserveCollinear using the clipper6 backend requires you to create an optional instance of poly clipping parameters:

var polygons = [] # a list of polygons...
var params = PolyBooleanParameters.new()
params.preserve_collinear = true
params.strictly_simple = true # Also available.
var solution = GeometryTools2D.merge_multiple_polygons(polygons, [], params)

Both options are ignored in clipper10 backend.

[Xrayez]

Tbh I wish I could implement this within the engine, but the current Godot's philosophy is that the API must be kept simple, and these methods with so much parameters belong to a module, so I just consider closing all of the geometry-related PR's of mine unless they prove to be essential to Godot.

[Xrayez]

I've opened a master proposal to handle all related stuff regarding this: godotengine/godot-proposals#913, please describe your use cases there if you really need this to be implemented in core, otherwise feel free to use GeometryTools module for now. 🙂