When I scramble the face order, project() runs much more slowly and

That sentence is a non-sense. I meant that "I shuffled the face order".
Sorry about that.

Revar has written a union() that operates on point lists and produces point
lists as output.  I don't know how fast it is, though.  It's in BOSL2.

Parkinbot wrote

--
Sent from: http://forum.openscad.org/

Not very fast, and not free of bugs yet. Really wish I could call a union function built in that would let clipperlib do the actual work far faster.

-Revar

Interesting. Can you give a rough outline of the algorithm your function
uses?

RevarBat wrote

--
Sent from: http://forum.openscad.org/

Roughly, boolean 2D geometry works as follows:

First, we have the concept of a region, which is a list of closed paths.  You are inside a region if you can draw a line from that point out to an arbitrarily distant outside point and you cross an odd number of the region paths.

A boolean operation like a union, difference, or intersection can be performed upon more than two regions at a time, but you can simplify them all to being successive operations on only two regions at a time. All boolean operations use a similar method to calculate:

1. Split each region's paths up into path segments where they cross the paths of the other region.

2. Tag each path segment of one region as being inside, outside, or coincident with the edge of the other region. Coincident segments come in two varieties, shared and unshared.  If a point infinitesimally to one side of the middle of the segment is inside both regions, then it is shared.  If it is only inside one, then it is unshared. This tagging is done for both regions separately.

3. Filter the tagged path segments for the specific operation: (See image below.)
   a) union() needs the outside and shared segments from the first region, and the outside segments from the other.
   b) difference() needs the outside and unshared segments from the first region, and the inside segments from the other.
   c) intersection() needs the inside and unshared segments from the first region, and the inside segments from the other.

4. Assemble all of the filtered segments from both regions into closed paths. There's some fiddly bits here where you assure the shortest closed paths by checking for path self-intersection as you assemble it, and put the trailing bits back into the segments pool.

5. Calculate how many other paths that each resultant path is inside of.

6. Sort the paths from most-outside to most inside. You now have the result region.

• Revar

Perhaps add a set of functions to OpenSCAD with the same names as the
boolean ops that take geometry as lists and return new lists. That would
allow everything to be done in user land harnessing clipper.

On Sun, 23 Feb 2020 at 22:57, Parkinbot rudolf@digitaldocument.de wrote:

Wow... adding a set of functions like that would be fantastic

Sent from my iPhone

nophead wrote

Hasn't someone done that, OpenSCAD modules etc rewritten in user-land?
Found it! https://github.com/thehans/FunctionalOpenSCAD

Admin - email* me if you need anything,  or if I've done something stupid...

• click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain; to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work. Obviously inclusion of works of previous authors is not included in the above.

--
Sent from: http://forum.openscad.org/

I would love to see built-in functions for union(), difference(), intersection(), and offset() too.  That last one is far harder to implement correctly than the boolean ops. Clipperlib would be far faster and it’s already been debugged. While we’re at it, functional hull() would be nice, too.

-RevarBat