Implicit unions

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Implicit unions

kintel
Administrator
Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

 -Marius




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

signature.asc (210 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Whosawhatsis
I would love to see fewer implicit unions, though I know that it will break some designs. I almost never use union anymore except (sometimes) for the first child of a difference, and I've gotten in the habit of omitting that in cases where I know an implicit union will be used. Fortunately, when things do break, the fix is as simple as adding union() in the places where the necessary implicit union used to occur (no additional braces necessary). The language would be a lot more logical without all the implicit unions, even if that would make it a bit more verbose.

On Monday, April 22, 2013 at 7:50 PM, Marius Kintel wrote:

Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

-Marius


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Jesse Donaldson-2
If you really want to avoid breaking existing designs, you could always make the new rules "opt in".  E.g., let scripts specify a language version explicitly, or something like that.  Not really very pretty, but it lets you continue to evolve the language without being crippled by backwards compatibility (even if you then need to support multiple "language versions" on an ongoing basis).

A possible middle ground is that if/when you make this change, you could also release an update tool that would parse an existing script and insert the unions that used to be implicit.


Jesse


On Mon, Apr 22, 2013 at 8:20 PM, whosawhatsis <[hidden email]> wrote:
I would love to see fewer implicit unions, though I know that it will break some designs. I almost never use union anymore except (sometimes) for the first child of a difference, and I've gotten in the habit of omitting that in cases where I know an implicit union will be used. Fortunately, when things do break, the fix is as simple as adding union() in the places where the necessary implicit union used to occur (no additional braces necessary). The language would be a lot more logical without all the implicit unions, even if that would make it a bit more verbose.

On Monday, April 22, 2013 at 7:50 PM, Marius Kintel wrote:

Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

-Marius


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Peter Falke
Hi,

I dont grasp the significance of the issue.
Could I get a code example that explains it, please?

Sincerely,

TakeItAndRun


On 23 April 2013 06:08, Jesse Donaldson <[hidden email]> wrote:
If you really want to avoid breaking existing designs, you could always make the new rules "opt in".  E.g., let scripts specify a language version explicitly, or something like that.  Not really very pretty, but it lets you continue to evolve the language without being crippled by backwards compatibility (even if you then need to support multiple "language versions" on an ongoing basis).

A possible middle ground is that if/when you make this change, you could also release an update tool that would parse an existing script and insert the unions that used to be implicit.


Jesse


On Mon, Apr 22, 2013 at 8:20 PM, whosawhatsis <[hidden email]> wrote:
I would love to see fewer implicit unions, though I know that it will break some designs. I almost never use union anymore except (sometimes) for the first child of a difference, and I've gotten in the habit of omitting that in cases where I know an implicit union will be used. Fortunately, when things do break, the fix is as simple as adding union() in the places where the necessary implicit union used to occur (no additional braces necessary). The language would be a lot more logical without all the implicit unions, even if that would make it a bit more verbose.

On Monday, April 22, 2013 at 7:50 PM, Marius Kintel wrote:

Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

-Marius


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566



--
[hidden email]

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!

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

kintel
Administrator
On 2013-04-23, at 24:18 , Peter Falke wrote:

> I dont grasp the significance of the issue.
> Could I get a code example that explains it, please?
>
For the first case (build platform layout), this should illustrate it:
 for (y=[0:9], x=[0:9]) translate([x*22,y*22,0]) cylinder(r=10, r2=0, h=20);

The objects don't touch, the unions won't affect the output in any way which breaks 3D printing workflows.
Ideally, this should evaluate really fast, but instead takes a long time (with F6, F5 is fast).

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

nophead
It was confusing to me that union isn't needed in a lot of places and a complete surprise when you said assign() does an implicit union(). That seems completely illogical.

Presumably if you miss out a union where two objects overlap you would get a non manifold result? Is it possible to quickly decide if objects overlap and only do an implicit union if they do? That should be largely backwards compatible I think.


On 23 April 2013 06:43, Marius Kintel <[hidden email]> wrote:
On 2013-04-23, at 24:18 , Peter Falke wrote:

> I dont grasp the significance of the issue.
> Could I get a code example that explains it, please?
>
For the first case (build platform layout), this should illustrate it:
 for (y=[0:9], x=[0:9]) translate([x*22,y*22,0]) cylinder(r=10, r2=0, h=20);

The objects don't touch, the unions won't affect the output in any way which breaks 3D printing workflows.
Ideally, this should evaluate really fast, but instead takes a long time (with F6, F5 is fast).

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Alan Cox
In reply to this post by kintel
On Mon, 22 Apr 2013 22:50:16 -0400
Marius Kintel <[hidden email]> wrote:

> Hi all,
>
> An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
> o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
> o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
> o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.
>
> I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.
>
> My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Breaking existing objects doesn't worry me too much providing they break
loudly and it tells you where the error is. One problem right now is that
there are not good warnings for misplaced ';' leading to children that
are not used or applying things to children that are null when you know
it is almost certainly an error. I'd like to get things like

        "315: transform of an empty child is probably an error"
        "433: child of cube() is not used"

For language version maybe its time to have a "$version" that like $fn
and other magic values controls this but would mean you could do

$version=1.0;

at the top of the file and have any later interpreters do

        if ($version > self) error("upgrade me");
        set_compatibility($version);


I'm wary of the unions thing. It would at the very least need the ability
to check for overlapping objects to fix stuff up, and I thought the point
of a computer was to save me doing the work. I think I'd rather the
openscad engine simply got smarter and did some basic bounding box
checks - optimising union handling ought to be more effective and better
for the object creator as well as drastically reducing error rates. It's
also more future proof - because the check can be improved over time
without changing any language properties.

And if there are difficult cases would

        no_overlap() {
                A();
                B();
        }

work as an optimisation the designer could use ? Again its future proof,
in the perfect world one day it becomes a nop.

The other question - given a pair of non unioned objects overlapping but
of different colours what will the drawing engine do with it ?


It feels to me a bit like the way C tried to add pointer aliasing rules
and dumped a pile of quite foul problems on the programmers who either
then screwed up horribly with weird bugs, or turned the feature off in
everything they wrote.

Alan
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Whosawhatsis
On Tuesday, April 23, 2013 at 3:13 AM, Alan Cox wrote:
The other question - given a pair of non unioned objects overlapping but
of different colours what will the drawing engine do with it ?
Color is only applied in OpenCSG mode, and OpenCSG doesn't really do unions, it just allows things to intersect and treats both meshes as one object, so the parts with each object would have their original colors.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

donbright
In reply to this post by kintel
From the Nef_polyhedron side of things, what if instead of having a single nef_polyhedron at each node, instead, there is a 'list' of nef_polyhedra?

This is the only way I can think of to do 'color' with Nef polyhedra. 

It appears, in fact, that the operation of 'union' on two different colored objects is mathematically different from the 'union' of two same-color objects.

consider two overlapping cubes.

ordinary 'union'  produces a single result volume of space.

colorized 'union' produces two individual volumes of space. (well, three, if you want to 'muddy' the intersection piece, but lets just say for argument, that it adopts the color of the cube on the left side of the union operator)

Nef polyhedron can't really represent that, even if you add some fancy way to color the facets... there is no object there between the volumes to indicate the boundary.


Whereas now we have things like

   Nef_poly operator Nef_poly

we would instead of

   list_of_nef_poly operator list_of_nef_poly

but I think it is possible to redefine the operators (intersection, difference, union) to operate on lists of nef_poly instead of a single nef_poly.

-----

but i dont know how that would fit in with the basic 'node' tree or the OpenCSG tree.

-DB


On Mon, Apr 22, 2013 at 9:50 PM, Marius Kintel <[hidden email]> wrote:
Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

 -Marius




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Peter Falke
Hm, I thought the beauty of the underlying CSG method was that there are rules for pruning the tree that check via bounding boxes (and other, more sophisticated rules) if a union, intersection, difference (union with one member negated) actually needs to evaluated or not.

Does OpenSCAD internally just brute force everything without pruning?

(Please note, that my understanding of this subject is somewhat limited. Maybe I`m taking (total) nonsense.)


Sincerely,

TakeItAndRun


On 23 April 2013 14:05, Don Bright <[hidden email]> wrote:
From the Nef_polyhedron side of things, what if instead of having a single nef_polyhedron at each node, instead, there is a 'list' of nef_polyhedra?

This is the only way I can think of to do 'color' with Nef polyhedra. 

It appears, in fact, that the operation of 'union' on two different colored objects is mathematically different from the 'union' of two same-color objects.

consider two overlapping cubes.

ordinary 'union'  produces a single result volume of space.

colorized 'union' produces two individual volumes of space. (well, three, if you want to 'muddy' the intersection piece, but lets just say for argument, that it adopts the color of the cube on the left side of the union operator)

Nef polyhedron can't really represent that, even if you add some fancy way to color the facets... there is no object there between the volumes to indicate the boundary.


Whereas now we have things like

   Nef_poly operator Nef_poly

we would instead of

   list_of_nef_poly operator list_of_nef_poly

but I think it is possible to redefine the operators (intersection, difference, union) to operate on lists of nef_poly instead of a single nef_poly.

-----

but i dont know how that would fit in with the basic 'node' tree or the OpenCSG tree.

-DB


On Mon, Apr 22, 2013 at 9:50 PM, Marius Kintel <[hidden email]> wrote:
Hi all,

An increasingly wanted feature seems to be removing the implicit unions which we do in certain places:
o All top-level objects are unioned in the end: This makes it very slow to e.g. design build plate layouts of non-intersecting objects
o All objects under for loops are unioned. This caused us to introduce intersection_for(), and it limits peoples design opportunities in various ways
o Similarly, all objects under assign, transforms, and probably other nodes as well, undergo an implicit union. The damage seems low, but it's mostly about processing time.

I'd love to hear some feedback/wishes/suggestions for ways forward which would make it possible to eliminate some or all of these implicit unions.

My greatest fear is breaking a lot of existing objects, but I've probably also overlooked other dangers, as well as opportunities.

Cheers,

 -Marius




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566



--
[hidden email]

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!

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Michael Möller
In reply to this post by kintel
Ask, and ye shall receive :)

With the (wasted) processing overhead of needless union - remove them !

The suggestion of having a compiler/version switch with/without implicit
unions is the most userfriendly (default OFF for faster work - note in
help: "if it looks more correct with union ON you are missing a union").
The suggestion to have a seperate "insert explictly union structures to
emulate old code" button probably means less work for you developers to
maintain two compile versions - this only needs a simple(?) text
manipulation of the code. And is still reasonably clear to users.

>
> I'd love to hear some feedback/wishes/suggestions for ways forward
> which would make it possible to eliminate some or all of these
> implicit unions. My greatest fear is breaking a lot of existing
> objects, but I've probably also overlooked other dangers, as well as
> opportunities. Cheers, -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Peter Falke
Guy,

I'm sorry, but I think your riding a dead horse:
The fast display is (F5) is done by representing an object in a CSG-tree.
Branches (better knots) of this tree are one of the 3 operations union, intersection, or difference.
Leafs of this tree are primitives like cube, cylinder, or sphere.
This tree need to get normalised by certain rules (see a paper OpenCSG: A Library for Image-Based CSG Rendering, section 2.1 http://static.usenix.org/event/usenix05/tech/freenix/full_papers/kirsch/kirsch.pdf)
Then you can work with it. (What the program actually does then I haven't quite understood, so)
Not doing an 'implicid union' is like having more then one tree.

Sincerely,

TakeItAndRun


On 23 April 2013 23:20, Michael Möller <[hidden email]> wrote:
Ask, and ye shall receive :)

With the (wasted) processing overhead of needless union - remove them !

The suggestion of having a compiler/version switch with/without implicit
unions is the most userfriendly (default OFF for faster work - note in
help: "if it looks more correct with union ON you are missing a union").
The suggestion to have a seperate "insert explictly union structures to
emulate old code" button probably means less work for you developers to
maintain two compile versions - this only needs a simple(?) text
manipulation of the code. And is still reasonably clear to users.

>
> I'd love to hear some feedback/wishes/suggestions for ways forward
> which would make it possible to eliminate some or all of these
> implicit unions. My greatest fear is breaking a lot of existing
> objects, but I've probably also overlooked other dangers, as well as
> opportunities. Cheers, -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566



--
[hidden email]

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!

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

kintel
Administrator
On 2013-04-24, at 14:45 , Peter Falke wrote:

> The fast display is (F5) is done by representing an object in a CSG-tree.

The whole talk about implicit unions is really only relevant to F6 (CGAL) mode.
In F5 (OpenCSG) mode, everything is implicitly unioned at zero cost by OpenGL anyway.

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

Peter Falke
And CGAL does not use the CSG-tree?
Do you know of some further reading on this subject?

Thanks,

TakeItAndRun


On 24 April 2013 20:50, Marius Kintel <[hidden email]> wrote:
On 2013-04-24, at 14:45 , Peter Falke wrote:

> The fast display is (F5) is done by representing an object in a CSG-tree.

The whole talk about implicit unions is really only relevant to F6 (CGAL) mode.
In F5 (OpenCSG) mode, everything is implicitly unioned at zero cost by OpenGL anyway.

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566



--
[hidden email]

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!

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Implicit unions

kintel
Administrator
On 2013-04-24, at 14:57 , Peter Falke wrote:

> And CGAL does not use the CSG-tree?
> Do you know of some further reading on this subject?
>
CGAL doesn't need normalization. We just traverse the internal node tree and perform the suitable operation per node. The implicit union is done in C++ inside each node where this should happen.

I'm afraid reading source code is the only documentation available on this subject, perhaps glance at some of the development helper diagrams here: https://github.com/openscad/openscad/tree/master/doc

I'd like to have more development documentation available. I'm thinking about putting that in the github wiki, but it's mostly a question of writing it..

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566