Flesh out 2D subsystem

[elalish]

We currently use Polygons as input to several Manifold constructors, and they could easily be output as well (think Slice), but we have no way to operate on them in 2D. I would like to think of Polygon as the 2D equivalent to Mesh, and I'd like to create a CrossSection class that is the 2D equivalent to Manifold.

A CrossSection will always be geometrically-valid (non-overlapping), as any input Polygons will be automatically fixed up according to winding number. Clipper lib seems like a good candidate to support useful 2D operations. I propose we adopt the "strictly positive" fill rule; this will allow Boolean-style operations simply by adding Polygons with the proper winding direction. This class will be totally independent of the Manifold class; they can simply interact through exported Polygons.

[pca006132]

Thinking about this recently, I wonder if we really need a 2D subsystem at all (for now). I think we can just write a simple wrapper to convert to3D(2D op 2D) to to3D(2D) op to3D(2D), e.g. extrude(LargeSquare - SmallSquare, n) to extrude(LargeSquare, n) - extrude(SmallSquare, n). This method will be slower than using a 2D subsystem, but it is really simple and I think our performance is good enough that the users will probably not notice this.

[elalish]

That's a clever idea - I guess 2Dto3D could basically use Extrude and 3Dto2D would basically be Slice? It does seem like a lot of overhead, but if it's quick to code it seems well worthwhile. We should be able to swap it out later without breaking the API in any case. Do you want to give it a try?

[geoffder]

I think Clipper2 is worth considering for wrapping. OpenSCAD actually uses Clipper1 (v6.4.2) for its 2D booleans with a small utility translation layer. Evolving out of Clipper1 it's pretty well used, and has benefitted from recent improvements.

[pca006132]

I think I can just implement it for TypeScript now, other users can implement their own wrapper as this is not complicated. Eventually we should use something like Clipper2, but it will take some time and I prefer having something that works first (kind of sick writing custom polygon generation code...)

[hrgdavor]

@geoffder is there a WASM build of clipper2 maybe ?

[geoffder]

@hrgdavor I'm not really sure, but this issue is the only one that turns up in a search for WASM, and it sounds like building with emcc wasn't cause for much grief at the time after all.

[geoffder]

I've thrown together a minimal example of using Clipper2 in the 2d-via-clipper branch of my fork. I left Polygons as it is in this prototype, since I wasn't sure of the best way to integrate it. I figured a class that could be automatically constructed from the clipper wrapper class would save the need for the overloads on the extrusion functions at least, but I left out an experiment with that for now.

There are more methods from clipper2 (offset, path simplification, minkowski) that I haven't done yet, and transformations/shapes other than translate and square that need filling out, but this skeleton gets from end-to-end in the clippoly_test.cpp example.

[elalish]

@geoffder Awesome! Would you mind opening a draft PR to make it a bit easier to peruse and comment on? I'd like to think through API shape for this, but it'll help to have some code to look at.

[geoffder]

@elalish Done! #341