Openscad: Lazy union (aka. no implicit union)

Created on 7 May 2013 · 87Comments · Source: openscad/openscad

Don't perform a union in the following cases:

Separate root objects
for loops: A for loop will create a list of separate object passed on to the parent node (or the root)
children(). A children() statement will pass on the list of children to the parent node

See also https://github.com/openscad/openscad/wiki/OEP2:-Implicit-Unions.

The code lives in https://github.com/openscad/openscad/tree/issue350

This feature is currently experimental. To enabled it, _lazy unions_ must be enabled in Preferences or the cmd-line (--enable=lazy-union).

Exporting top-level object to STL/OFF/AMF/DXF/SVG will attempt to keep the objects separate as far as the used file format supports it.

TODO:

[x] Basic implementation
[x] Tag as experimental feature (to be able to merge)
[x] Test csg output (top level, for() and children())
[x] Test intersection() for()
[x] Test hull() for()
[x] Test nested for test
[x] Test simple top-level objects
[x] Test minkowski() for()
[x] Test difference() for()
[x] Test children()
[x] STL export
[x] OFF export
[x] AMF export
[x] DXF export
[x] SVG export
[x] Deprecate intersection_for: To combine this with the experimental feature, we need to defer builtin initialization until after preferences has been read => no need to combine it with experimental for now, deprecate intersection_for after we move out of the experimental stage
[ ] Document the behavior of each file format for some slicer engines
[ ] Consider the unwrap operator: https://github.com/openscad/openscad/wiki/OEP4%3A-Unwrap-Operator
[ ] Evaluate compatibility with OpenSCAD2: https://github.com/doug-moen/openscad2/blob/master/rfc/Functions.md#fixing-the-module-composability-problem
[ ] Test AMF import of separate objects.

This has been discussed a bit, and is interesting for a number of reasons:

Speed: In many cases, most (half?) of the time and memory used for compiling an OpenSCAD design is consumed by the final union of the top-level objects (see e.g. #261 and #342)
Necessity: Slicer software (Slic3r in particular, others unknown) supports slicing overlapping objects as it performs an implicit union of all submeshes.
Multi-material 3D printing: We could, at the top-level, specify different colors for different top-level objects. When exporting as separate meshes, these colors could be mapped to materials by the slicer software. Combined with amf or obj export, this could make multi-material prints a lot more convenient.
Manifoldness: This will partially let users export more complex models where the final manifold test done today fails (see #337).

Further work past this issue:

Don't need to perform _any_ unions which are not influenced by subsequent operations, independent on top-level or not. This will allow modules to create on non-unioned objects.
Do lazy evaluation of CGAL Nef polyhedrons. This will make it possible to defer calculation of transformations until the last minute, which perhaps makes it possible to avoid caching more than one instance of geometries which only differ in transformation.

Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.

Enhancement

Source

kintel

👍6

Most helpful comment

I'd really like to experiment with this, but I'm having issues building it - I get issues very similar to https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=844881 Any ideas?

I hate to see us leave this much performance in a branch just because we're not sure how it mixes with the (probably far) future directions of OpenSCAD. I feel like having this performance boost in play might change the whole narrative, for the better, about how to use OpenSCAD and what sort of applications it's capable of.

What if, instead of waiting until we can commit to a global change of behavior, we put this behind a system variable like $union. When $union is true (the default) OpenSCAD would behave as it always has. A user could then pass $union=false to modules where it's safe to do so and skip the implicit unions.

This would get us some real-world experience to better refine our vision for the OpenSCAD-2. Older versions of OpenSCAD would just ignore $union, and only users who know to set $union=true would be affected by any potential problems. If it all turns out to be mostly a non-issue (or we make it a non-issue by handling any unforeseen issues at export time), we can change the default to $union=false down the road so you get the performance by default.

lostapathy on 3 Feb 2018

👍2

All 87 comments

Some quick experiments using the design below, show very promising results:

Current OpenSCAD: 10m38s @ 385 MB
Without the top-level union: 1m4s @ 256 MB
Resulting STL slices correctly in Slic3r

num=20;
for (i=[0:num-1])
  rotate([0,0,i*360/num])
    translate([40,0,0])
      rotate([0,i*90,0])
        scale([0.7,1,1])
          rotate_extrude() translate([10,0,0]) circle(r=2);

..and with new implementation (May 7th 2014): 2 seconds @ 50 MB

kintel on 7 May 2013

🎉1

Some printer software (MakerWare I think) supports multiple materials only through loading separate STL files for each material. To facilitate this workflow, we could add an option to STL export to export each top-level object as a separate STL, indexed or named according to the color() of each object.

kintel on 7 May 2013

Eliminating the top level union would be a great feature by itself as far as i am concerned. It would be nice to see just this feature in the development releases soon and add features on top of this later.

Aside from the separate stl's per top level object, one feature we may want is collision detection between top level objects, for instance if the chains are mis-aligned and touch, i'd like to know. If this is a costly calculation (i can't imagine it is) it could be made optional.

ivoknutsel on 8 May 2013

I agree that we should get the minimal feature set into master - it's still a bit of work to make this robust though..

We don't have any code for doing collision detection yet, but that's an interesting feature request.
Collision detection is still an extra feature, since intersecting objects are sometimes OK since slicing software might handle it well (e.g. Slic3r does).

kintel on 8 May 2013

Some thoughts about syntax:

ununion(){ ... omit explicit union of these elements (childs)...);

ununion in F5 is treated as a normal union
ununion in F6 starts the compile for every child and just appends the
result to the list of nerf-polygons

ununion() can only be used on 'root' level
ununion can be used more than ones in a file
ununion can be used inside if/else statements
ununion can not be used inside of for-loops, but a for-loop can be used as
'argument' of ununion

no testing for non-two manifold?

Sincerely,

TakeItAndRun

On 8 May 2013 10:22, Marius Kintel [email protected] wrote:

I agree that we should get the minimal feature set into master - it's
still a bit of work to make this robust though..

We don't have any code for doing collision detection yet, but that's an
interesting feature request.
Collision detection is still an extra feature, since intersecting objects
are sometimes OK since slicing software might handle it well (e.g. Slic3r
does).

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17592506
.

[email protected] [email protected]

P.S. Falls meine E-Mail kürzer ausfällt als Dir angenehm ist:
Ich probiere gerade aus kurze Antworten statt gar keine Antworten zu
schreiben.
Wenn Du gerne mehr lesen möchtest, dann lass es mich bitte wissen.

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

TakeItAndRun on 8 May 2013

I imagine that this ununion() module is so as not to break backwards compatibility and have to explicitly declare not unioning the objects. Can the group() module be cleverly used for this purpose in place of ununion() its a horrible name for a module an "unun" was a bit clumsy to type correctly.

GilesBathgate on 8 May 2013

I think group should do that anywhere in the tree. For example I group
logically separate things so they can be translated together, but they are
separate objects so an explicit union is just a waste of processing.

On 8 May 2013 13:25, Giles Bathgate [email protected] wrote:

I imagine that this ununion() module is so as not to break backwards
compatibility and have to explicitly declare not unioning the objects. Can
the group() module be cleverly used for this purpose in place of ununion()
its a horrible name for a module an "unun" was a bit clumsy to type
correctly.

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17602135
.

nophead on 8 May 2013

Sorry typo:

I think group should do that anywhere in the tree. For example I group
logically separate things so they can be translated together, but they are
separate objects so an *implicit *union is just a waste of processing
.

On 8 May 2013 13:33, nop head nop.[email protected] wrote:

I think group should do that anywhere in the tree. For example I group
logically separate things so they can be translated together, but they are
separate objects so an explicit union is just a waste of processing.

On 8 May 2013 13:25, Giles Bathgate [email protected] wrote:

I imagine that this ununion() module is so as not to break backwards
compatibility and have to explicitly declare not unioning the objects. Can
the group() module be cleverly used for this purpose in place of ununion()
its a horrible name for a module an "unun" was a bit clumsy to type
correctly.

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17602135
.

nophead on 8 May 2013

@nophead group() is currently just an alias for union(), so you might think you are saving processing, but actually its not doing anything for you until group is implemented properly. The proposed hack is to not union things implicitly at the top level, but @TakeItAndRun seems to think we should have an ununion() module?! I was just pointing out that group() might be a more appropriate choice, since group() seems to be, by everyone's understanding, not unioned. break_appart() , ungroup() or deunion() would also be ok, but ununununion() wouldn't.

GilesBathgate on 8 May 2013

Another point, there is an implicit union() inside for loops, leading to the need for intersection_for() {} in place of: intersection() for() { } which is more generic. I showed Marius how I had implemented this in RapCAD, and he said he would consider it. This might be a good time to consider it.

Regards,
Giles

GilesBathgate on 8 May 2013

Giles ideas match mine exactly. intersection_for() is a hack made to avoid having to refactor internal workings and will be deprecatable once group() is implemented properly.

kintel on 8 May 2013

On 7 May 2013 17:49, Marius Kintel [email protected] wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a system
upgrade.

Using SSD here... not sure how much that helps

Torsten

torwag on 8 May 2013

On 2013-05-08, at 16:32 , torwag wrote:

On 7 May 2013 17:49, Marius Kintel [email protected] wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a system
upgrade.

Hm, my computer does feel slow, but it shouldn't be that bad (2.6 GHz i7) - perhaps I need a reinstall…
Hopefully, the speed improvement ratio will stay similar though :)

-Marius

kintel on 8 May 2013

just as a reference:

Intel(R) Xeon(R) CPU E3-1225 V2 @ 3.20GHz
32GB of RAM
256GB SSD
NVIDIA Quadro 600

Arch Linux

Torsten

On 8 May 2013 16:38, Marius Kintel [email protected] wrote:

On 2013-05-08, at 16:32 , torwag wrote:

On 7 May 2013 17:49, Marius Kintel [email protected] wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a system
upgrade.

Hm, my computer does feel slow, but it shouldn't be that bad (2.6 GHz i7)

perhaps I need a reinstall…
Hopefully, the speed improvement ratio will stay similar though :)

-Marius

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17610022
.

torwag on 8 May 2013

Off topic:

Hi torwag,

would you be so nice and run the attached program and let me know how long
this will take on your machine.(F5 and/or F6)

Thanks,

TakeItAndRun

On 8 May 2013 16:53, torwag [email protected] wrote:

just as a reference:

Intel(R) Xeon(R) CPU E3-1225 V2 @ 3.20GHz
32GB of RAM
256GB SSD
NVIDIA Quadro 600

Arch Linux

Torsten

On 8 May 2013 16:38, Marius Kintel [email protected] wrote:

On 2013-05-08, at 16:32 , torwag wrote:

On 7 May 2013 17:49, Marius Kintel [email protected] wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a system
upgrade.

Hm, my computer does feel slow, but it shouldn't be that bad (2.6 GHz
i7)

perhaps I need a reinstall…
Hopefully, the speed improvement ratio will stay similar though :)

-Marius

—
Reply to this email directly or view it on GitHub<
https://github.com/openscad/openscad/issues/350#issuecomment-17610022>
.

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17610978
.

[email protected] [email protected]

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

TakeItAndRun on 8 May 2013

Silly me, I intended to append the code!

Sorry,

TakeItAndRun

On 8 May 2013 17:53, Peter Falke [email protected]:

Off topic:

Hi torwag,

would you be so nice and run the attached program and let me know how long
this will take on your machine.(F5 and/or F6)

Thanks,

TakeItAndRun

On 8 May 2013 16:53, torwag [email protected] wrote:

just as a reference:

Intel(R) Xeon(R) CPU E3-1225 V2 @ 3.20GHz
32GB of RAM
256GB SSD
NVIDIA Quadro 600

Arch Linux

Torsten

On 8 May 2013 16:38, Marius Kintel [email protected] wrote:

On 2013-05-08, at 16:32 , torwag wrote:

On 7 May 2013 17:49, Marius Kintel [email protected] wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a system
upgrade.

Hm, my computer does feel slow, but it shouldn't be that bad (2.6 GHz
i7)

perhaps I need a reinstall…
Hopefully, the speed improvement ratio will stay similar though :)

-Marius

—
Reply to this email directly or view it on GitHub<
https://github.com/openscad/openscad/issues/350#issuecomment-17610022>
.

—
Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17610978
.

[email protected] [email protected]

P.S. Falls meine E-Mail kürzer ausfällt als Dir angenehm ist:
Ich probiere gerade aus kurze Antworten statt gar keine Antworten zu
schreiben.
Wenn Du gerne mehr lesen möchtest, dann lass es mich bitte wissen.

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

[email protected] [email protected]

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

TakeItAndRun on 8 May 2013

Collision detection would be useful (currently I use #of volumes after F6 to check this). I assume detecting a collision is the same computational burdon as a union (though if a shortcut is available, that would be great). Perhaps put in an F7 render where it also detects collisions, and takes longer. Would be especially good if it could color the colliding objects.

elalish on 14 May 2013

I agree - collision detection would be cool. Since we only need detection, not evaluation, perhaps the clipper library could be utilized for this.

kintel on 14 May 2013

You could perform an intersection between the projections of the objects onto the ground, but that would detect many false positives. Not sure how you would use Clipper for that :)

alranel on 14 May 2013

ah, if course - clipper is 2D only..

This should work (I used it a decade ago and it was pretty solid IIRC): http://sourceforge.net/projects/coldet/

kintel on 15 May 2013

Hi,

sorry just read your email. I tried my best but couldn't still find any
kind of code to test in your mails.
Send me the code and I am happy to give it a try

Greetings

Torsten

On 8 May 2013 18:08, TakeItAndRun [email protected] wrote:

Silly me, I intended to append the code!

Sorry,

TakeItAndRun

On 8 May 2013 17:53, Peter Falke [email protected]:

Off topic:

Hi torwag,

would you be so nice and run the attached program and let me know how
long
this will take on your machine.(F5 and/or F6)

Thanks,

TakeItAndRun

On 8 May 2013 16:53, torwag [email protected] wrote:

just as a reference:

Intel(R) Xeon(R) CPU E3-1225 V2 @ 3.20GHz
32GB of RAM
256GB SSD
NVIDIA Quadro 600

Arch Linux

Torsten

On 8 May 2013 16:38, Marius Kintel [email protected] wrote:

On 2013-05-08, at 16:32 , torwag wrote:

On 7 May 2013 17:49, Marius Kintel [email protected]
wrote:

Current OpenSCAD: 10m38s @ 385 MB

Total rendering time: 0 hours, 2 minutes, 30 seconds

Hmmm either I do something wrong, or you would benefit from a
system
upgrade.

Hm, my computer does feel slow, but it shouldn't be that bad (2.6 GHz
i7)

perhaps I need a reinstall…
Hopefully, the speed improvement ratio will stay similar though :)

-Marius

—
Reply to this email directly or view it on GitHub<
https://github.com/openscad/openscad/issues/350#issuecomment-17610022>
.

—
Reply to this email directly or view it on GitHub<
https://github.com/openscad/openscad/issues/350#issuecomment-17610978>
.

[email protected] [email protected]

P.S. Falls meine E-Mail kürzer ausfällt als Dir angenehm ist:
Ich probiere gerade aus kurze Antworten statt gar keine Antworten zu
schreiben.
Wenn Du gerne mehr lesen möchtest, dann lass es mich bitte wissen.

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

[email protected] [email protected]

P.S. Falls meine E-Mail kürzer ausfällt als Dir angenehm ist:
Ich probiere gerade aus kurze Antworten statt gar keine Antworten zu
schreiben.
Wenn Du gerne mehr lesen möchtest, dann lass es mich bitte wissen.

P.S. In case my e-mail is shorter than you enjoy:
I am currently trying short replies instead of no replies at all.
Please let me know, if you like to read more.

Enjoy!

—

Reply to this email directly or view it on GitHubhttps://github.com/openscad/openscad/issues/350#issuecomment-17615991
.

torwag on 22 May 2013

+1. This would be very useful for verification if part still fit together well after changes made to a project, kind of unit-tests. In some situations one might to occupy some space with a solid and render an animation to make sure nothing comes in the way. As for detection itself I think it should be "optionally optional". One may want to turn it on or off globally and for each solid separately.

steelman on 24 Aug 2013

As of their last release, MakerWare now also does a proper top-level union before slicing, just like Slic3r. I think this is becoming a popular approach.

elalish on 31 Dec 2013

This would be an excellent feature to have, especially since I very frequently have nemurous top-level objects that are non-intersecting but would be failing bounding-box checks (eg. packed triangles).

AustinSpafford on 4 Mar 2014

In a thread I on the mailing list I presented a case for not implicitly unioning not olny _top level_ objects, but also any node. In the particular case it was solids created by a for loop à la hull() for() {...}. When the objects generated by for did not overlap, the code was roaring fast. When they did overlap, it became inacceptable, because the implicit union on the for-objects took so long.

So deferring unioning in the tree as long as finally necessary for the next higher node seems to be very relevant with respect to performance, not only at the top level.

szabi on 10 Apr 2014

It seems like implicit union only on anonymous blocks (such as the top block) might be a reasonable behavior.

I tend to think a lot of the issue is that the way that the engine does unions is just slow. How hard would it be to have some kind of looseunion() that uses a faster - possibly less exact - algorithm to produce a simple cgal object? Ideally using the alternative explicitly on the top level would then make the implicit top level union into a case that can be recognized and handled quickly.

NateTG on 10 Apr 2014

Another example using hull() for():
This takes forever (too lazy to wait) in 2014.03, both in F5 and F6 mode, but renders in 2-3 seconds in this branch. F6 is as fast as F5.

points=600;
random_angles=rands(0,360,points,42);

hull()
  for(i=[0:3:points])
    rotate([random_angles[i],random_angles[i+1],random_angles[i+2]]) translate([10,0,0]) cube();

kintel on 20 May 2014

What's the status on this? How can we help to move it forward?

zittix on 28 Oct 2014

The missing piece is deciding how to deal with backwards incompatibilities.
One alternative is to implement the OEP 4 counter proposal.
See https://github.com/openscad/openscad/wiki/OEP2:-Implicit-Unions

I'm likely to postpone the final integration until we have a clear vision of other related language changes.
Another alternative is to enable this as an experimental feature and be vocal about it being likely to break in the future.

kintel on 28 Oct 2014

I've read through the OEP4 proposal a few times and just finally understand what it's trying to do.

It seems the OEP4 unblocks users while preserving backward compatibility. It also adds new abilities for user defined library functions, which is awesome. So it seems like a win all around and should be implemented regardless of what happens with OEP2.

OEP2 is a harder issue that i'm not sure of the right way to go. On the one hand, it provides faster renders and less confusing code (especially for beginners). On the other hand, it will confuse existing users and break previous scripts. Offering a settings option doesn't do much to help since it will fracture new scripts into scripts that assume implicit union and those that do not. That doesn't seem like a great way to go. One way to solve this would be to provide a way to convert an implicit union script into one that doesn't require implicit unions... it would basically just add a union operation around every module. That's a bit janky, but at least would provide some ability for legacy scripts to be usable.

atartanian on 1 Dec 2014

One could have the view that outputting overlapping STLs is a "hack", and AMF is the "proper" way to do multi-volumes.

In the case of AMF, the standard requires volumes to be non-overlapping.[1] So for AMF export, it would have to call back into the geometry functions before exporting to resolve the geometry. Exporting to AMF could then create an unexpected long delay, which currently is not cancellable. The AMF output might not match the output in other file formats.

That all seems rather messy. I think it would be much cleaner to have all the geometry resolved before export functions are called.

If we had a faster CSG, do we still need lazy unions?

[1] https://en.wikipedia.org/wiki/Additive_Manufacturing_File_Format#Structure

bobc on 31 Jul 2015

Lazy union is indeed a workaround for faster CSG. I foresee that CSG will still be a bottleneck, even if it's significantly faster, so we might eventually have to revisit this.

kintel on 18 Aug 2015

Not sure it's the place or time for that, but what about a more simple "render by color()" and "export STL by color()", provided the scad file was using separate colors (e.g. color("red")…) for each part?

francoisbecker on 12 Nov 2015

@francoisbecker I think the color() module only works for rendering using OpenCSG, and you cannot export a model to STL until it has been rendered in CGAL mode.

(For multi material support see: https://github.com/openscad/openscad/wiki/Ideas-for-Development-Tasks#multi-material-support)