search

godotengine / godot-proposals

Godot Improvement Proposals (GIPs)
MIT License
1.12k stars 69 forks source link

Enhancements regarding polygon boolean and polygon deflating geometry methods #913

Open Xrayez opened 4 years ago

Xrayez commented 4 years ago

Describe the project you are working on: Goost - Godot Engine Extension.

I've previously implemented polygon boolean operation methods in Godot: godotengine/godot#28987.

I'm developing Goost module as an extension for Godot, it has geometry component which realizes my vision to a great extent when it comes to polygon-based operations, making most of the internal features as configurable as possible, so you can more easily compare my vision in relation to this proposal.

Describe the problem or limitation you are having in your project: With this proposal I'd like to summarize some of the inconsistencies, limitations and hurdles of using the geometry methods related to polygons at large.

Describe the feature / enhancement and how it helps to overcome the problem or limitation:

Polygon boolean operations

Knowing that it's not really good to bloat the engine, I propose to do the following:

  1. Remove individual per-operation boolean methods (merge_polygons_2d, clip_polygons_2d etc) which accept only two polygons at a time currently.
  2. Instead, add a unified method to perform all polygon boolean operations above: boolean_polygons_2d, which would accept multiple polygons, basically godotengine/godot#35929. The rationale behind this is that I've seen people are oftentimes requesting a method to merge a list of polygons: https://github.com/godotengine/godot/issues/29784#issuecomment-502340297, but it does makes sense to provide the support of this for other boolean operations (I believe that even if some operations are not used as often, it's silly to deny the existence of elementary math operations).

I guess polylines_boolean_2d might not be worth it, considering that there's only two types of operations supported for this: clip and intersect (aka clip_polyline_with_polygon etc).

This actually solves another issue of duplicate documentation which are spread between those individual methods.

Exposing parameters

The Clipper library provides a quite useful option which allows you to turn self-intersecting polygons into strictly-simple polygons. I'm leaving describing the actual use case for this to @HEAVYPOLY, the author of http://www.heavypoly.com/heavypaint. Depending on how those polygons can be simplified, it's also important to expose an enum specifying the fill rule (EvenOdd, NonZero etc).

Alternatively, a dedicated method simplify_polygons could be added, but this would be just a wrapper for merge_polygons(strictly_simple = true), so not much added gain.

Polygon deflating/inflating

I've exposed the methods (offset_polygon_2d and offset_polyline_2d) along with boolean ones because that's what the underlying Clipper library provided. I'm not sure whether this is actually useful for most users. In fact this creates confusion as seen in #777, so it might be worth splitting the method to deflate_polygon and inflate_polygon. It's also possible to deflate a polyline which would turn into a polygon, so again it only makes sense to create deflate_polyline method (yet this wouldn't be used often anyways I guess).

Exposing parameters

It's also a question of whether it makes sense to expose other parameters like miter_limit and arc_tolerance there as seen in godotengine/godot#36369. I've stumbled upon an issue of having to bind more than 6 parameters. Circumventing this limitation is possible by including method_bind_ext header but I suppose this bloats the engine binary size unnecessarily. For that I've simply managed to combine the two existing enums used to configure the join and end types together, but again this kinda creates complexity.

Resolving workarounds

Maybe #1389, #2567.

Describe how your proposal will work, with code, pseudocode, mockups, and/or diagrams: Given my previous conversations with @reduz regarding making this configurable (summary: not so enthusiastic), and nonetheless taking into account the request I've received from people, I propose the updated API similar to the following

Geometry2D.boolean_polygons(polys_a: Array, polys_b: Array = null, fill_rule = FILL_RULE_EVEN_ODD, strictly_simple = false) 
Geometry2D.clip_polyline_with_polygon(poly_a: Vector2Array, poly_b: Vector2Array)
Geometry2D.intersect_polyline_with_polygon(poly_a: Vector2Array, poly_b: Vector2Array)
Geometry2D.offset_polygons(polygons: Array, delta: float, join_type = JOIN_SQUARE, end_type = END_SQUARE, miter_limit = 2.0)

Every method not on the list is proposed to be removed...

If this enhancement will not be used often, can it be worked around with a few lines of script?: Some methods can be removed, but it's quite difficult to reimplement them via script, given the performance is quite critical when it comes to clipping polygons at 60 FPS.

Is there a reason why this should be core and not an add-on in the asset library?: Already part of core, too late. 😛

Note that it's totally fine to leave everything as-is, I personally invite people who need specific features to use the aforementioned module which does provide an extensive solution. I've just created this proposal upon some requests I've received from the community.

HEAVYPOLY commented 4 years ago

Geometry.polygons_boolean_2d with strictly_simple option greatly improves stability of drawing complex polygons.

Current behavior when boolean merging polygons: https://www.dropbox.com/s/nn8h333fpwkza1s/FillLassoBooleanFlicker.mkv?dl=0

With strictly_simple option in geomtools: https://www.dropbox.com/s/d3ftjxuxsi9mxtb/FillLassoBooleanWithStrictlySimple.mkv?dl=0

Xrayez commented 4 years ago

I'd like to link some other misc methods related to polygons I've previously created:

It's not required to expose those since godotengine/godot#29867 already uses the suggested implementation internally.

Av3r3tt commented 4 years ago

@Xrayez : Thank you Andrii -- this looks like some excellent work! It would open up Godot to be not just a full-fledged bitmap display engine for games but also to be a tool to deal with vectors in a much more sophisticated way, both for games and other applications. The use cases for this reach far. Since Godot is already great at rendering, opening it up to more robust and complex 2D polygon vector math operations would make it a truly astonishing tool chest for 2D Vector graphics. I fully support this!

HEAVYPOLY commented 3 years ago

I have tested the strictly simple option with polygon merge and found that it fixes all invalid polygon problems in my project and with great performance! Hope this can be accepted into Godot some day.

RichardEllicott commented 3 years ago

I found the Geometry. clip_polygons_2d method of no use because it is unable to cut a hole into a polygon and return for example, two new polygons that represent my cut shape (it only works with overlapping polygons)

it simply returns the original polygon, and the shape of the hole

so ideally what it would return would either be a list of triangle representing my new shape, or perhaps two new concave polygons

the reason i needed this: i reconstructed the doom UDMF format (which involved a lot of very boring challenge of working out what all the polygon shapes where from linedefs)..... to reconstruct to polygons i end up with coordinates of polygon areas, and also of the linedefs inside them that i call "holes" in the sectors

i think there's many other usage cases two, it's the same as the way CSG is useful for 3D.... i hope people don't think something so fundamental would be engine bloat.... if we then move on to adding higher level functions for it everyone will love booleans for 2D

snailrhymer commented 2 years ago

I think this would make a great core addition.

As it is, the polygon functions in Geometry (e.g. merge_polygons_2d) output the result of the operation as an array of polygons with holes differentiated by their orientation. But am I right that this structure isn't usable anywhere else in the engine?

CollisionPolygon2Ds and Polygon2Ds seem to only accept single polygons (i.e. a PoolVector2Array). (I'm not sure what the polygons property on Polygon2D is for, but it doesn't seem to work to draw polygons with holes (#41447).)

The polygon functions in Gemoetry also only accept a PoolVector2Array for each argument. This means that e.g. merge_polygons_2d can output a polygon with a hole but can't operate on one, which feels very unintuitive. Consequently, if a user wants to merge 3 polygons in script like merge(A, merge(B, C)), they're out of luck if merge(B,C) produces a polygon with a hole.

This was where I got stuck in my project (I need to make a collision shape out of the complement of a number of polygons in order to build a level), and using Goost has got me unstuck. If adding the lovely PolyNode2D functionality from Goost would be too bloaty, letting users have more general access to Clipper's functionality would make polygon operations vastly more useful.

A fear was raised here that deep access would require too much in-depth knowledge about subject and clip polygons from the user. A small change that wouldn't create too much complexity in this regard and that would minimise bloat would be too keep merge, intersect etc as binary operations, but allow them to also accept an array of polygons in the same format as they currently output them:

var polygon_a = [some_outer_polygon, hole_polygon_1, hole_polygon_2]

var polygon_b = [other_outer_polygon, hole_polygon_3]

var merged = merge_polygons_2d( polygon_a, polygon_b )

The current implementation already expects users to understand the 'polygons with holes' structure as an output, so additionally allowing them as input doesn't add much complexity. Having polygons with holes as an input is also well within Clipper's functionality.

Xrayez commented 2 years ago

@snailrhymer I agree, thanks for outlining the limitations!

As it is, the polygon functions in Geometry (e.g. merge_polygons_2d) output the result of the operation as an array of polygons with holes differentiated by their orientation. But am I right that this structure isn't usable anywhere else in the engine?

The output is still usable by navigation nodes as far as I know (via NavigationPolygon.make_from_outlines()), but I don't use it myself.

allow them to also accept an array of polygons in the same format as they currently output them

Rather than operating on a collection of Vector2 arrays, some libraries represent polygons with holes with a special class. In some project I'm working on, I operate on 2D models exclusively (boundary + collection of holes, and some methods which compute area, centroid that also account for holes). That could be an intuitive alternative for these kind of low-level geometry operations. For high-level stuff, using PolyNode2D in Goost is also a solution.

Here's a list of new/existing Godot proposals that can be directly or indirectly resolved by adding PolyNode2D class from Goost in Godot:

Xrayez commented 2 years ago

On the philosophical aspect, the last time I talked with Juan about this 3 years ago, it was difficult to convince him to add even basic clipping functionality in Godot core. You have to be aware of Godot's development philosophy as seen by Goost.

The 2D boolean operations may be a candidate for GDExtension in Godot 4.0 anyways, and I presume CSG nodes (3D) will also be migrated to officially supported GDExtension (I may be wrong). Therefore, it won't make much difference whether this kind of thing will be supported officially or semi-officially (by myself). 🙂

Due to this, I'd say using Goost may be an optimal solution for you. The only concern is that I'm mostly the one who currently actively maintains Goost, but if more people use Goost in production, the more chances that there will be someone who'd be willing to maintain it. Only a few people know about Goost's existence and its purpose (same old Godot story). I'd say a good chunk of currently opened proposals in Godot could already be implemented in Goost right away. But without a doubt, if you think that something should be in Godot, let it be in Godot.

But at the same time, I wouldn't want to be torn between improving Goost features and adding the same stripped features which will never be complete in Godot specifically. In Goost, it only takes me two hours to prepare and merge a feature. In Godot, it could take up to two years (see the date when this proposal was created). This is reality, not speculation.

Calinou commented 2 years ago

and I presume CSG nodes (3D) will also be migrated to officially supported GDExtension (I may be wrong).

There are currently no plans to move CSG nodes to an extension.

Xrayez commented 2 years ago

I've noticed https://github.com/SoloByte/godot-polygon2d-fracture/ by @SoloByte, which uses current Godot's boolean operation methods on polygons. The use case is very concrete, see the project description there (thanks for mentioning Goost as well).

RichardEllicott commented 2 years ago

personally i don't think it's to do with anything other than no-one has the code

when i was interested in this project i checked the goost library, it didn't have what i concider a "boolean", it has a clip

a boolean to me, returns the triangles back as a result of the cut, ir it could return back a big ngon reconstructed back from them triangles ... and this is the same usage of the term "boolean" i have observed in all other programming enviroments

to me, and i recon, most normal people.... calling these functions "boolean" is a miss-sell and as a programmer encourages you to waste time coding something.... THINKING, that a boolean is available... which happened to me with my shelved doom reading addon which i only coded at all because there was a "boolean" available (allegedly)

included is a diagram of how a boolean works normally and manages to return an ngon from a cutting a hole in another ngon

boolean_example

Xrayez commented 2 years ago

I think the more appropriate term would be set-theoretic operations on polygons. But using this kind of terminology could be potentially problematic for someone who's not a mathematician. There are not enough words in a natural language to describe different concepts. Different fields tend to use the same words, but define them differently (like in graph theory).

But if you think about it, the boolean here actually refers to operands called the subject and clip polygons, and operators refer to AND, OR, NOT. Reading the documentation and/or researching the topic is essential to understanding this anyways. 😮

The picture you've shown results in cutline polygon. I think that not a lot of libraries support such operation. But it's always possible to triangulate or decompose into convex the resulting shape that contains holes (with Goost, of course).

Why you need to have a cutline representation of a polygon containing a hole? What if a polygon contains dozens of holes?

RichardEllicott commented 2 years ago

it wouldn't have to be cutline that would be what would normally be expected of a bool, a collection of trinagles would be acceptible

in the doom map format, maps are defined by linedefs, so this means you can have sectors within sectors... the only way to translate them to polygons therefore is to be able to create sectors with holes in them.... different sectors can have different heightlevels.

so i was trying to contruct a mesh from a doom map, just for a hyperthetical thing really and cos i didn't see the solution elsewhere