About projection()

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

Re: About projection()

RevarBat
Just because something can be and has been implemented in user space (more than once, apparently) doesn’t mean it should be. :-) Some algorithms are just rather slow and buggy to reimplement in user space.

-Revar


> On Feb 23, 2020, at 6:33 PM, MichaelAtOz <[hidden email]> wrote:
>
> nophead wrote
>> 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.
>
> 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/
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

adrianv
The referenced github project has *as*its*goal* the implementation of
everything in user space.  The actual state of the project, however, is that
nothing nontrivial has been implemented.  The boolean operations and offset
are both listed under the future work section, along with hull and
minkowski.  

One major challenge of implementing these sorts of functions in user space
is that the efficient algorithms typically require data structures that are
not available in OpenSCAD, or whose implementation will be so inefficient
that it wouldn't deliver the intended speed-up.  


RevarBat wrote
> Just because something can be and has been implemented in user space (more
> than once, apparently) doesn’t mean it should be. :-) Some algorithms are
> just rather slow and buggy to reimplement in user space.    
>
> -Revar
>
>
>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;

> oz.at.michael@

> &gt; wrote:
>>
>> nophead wrote
>>> 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.
>>
>> 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/
>>
>> _______________________________________________
>> OpenSCAD mailing list
>>

> Discuss@.openscad

>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

boxcarmib
my enthusiasm for exteneded 2d boolean functions isn’t about efficiency but the flexibility of being able to manipulate point defined objects after they’ve been modified with 2d boolean functions. as it stands, as soon as you surrender a polygon of your own creation to the existing functions you no longer have access to the underlying point definition.
Maybe there are ways around that, but I confess I’m not a power user by any means, but the possibility of built-in 2d operations that return point lists seems very attractive. i wouldn’t care if they were efficient… just that they could actually do the operations.

> On Feb 23, 2020, at 7:14 PM, adrianv <[hidden email]> wrote:
>
> The referenced github project has *as*its*goal* the implementation of
> everything in user space.  The actual state of the project, however, is that
> nothing nontrivial has been implemented.  The boolean operations and offset
> are both listed under the future work section, along with hull and
> minkowski.  
>
> One major challenge of implementing these sorts of functions in user space
> is that the efficient algorithms typically require data structures that are
> not available in OpenSCAD, or whose implementation will be so inefficient
> that it wouldn't deliver the intended speed-up.  
>
>
> RevarBat wrote
>> Just because something can be and has been implemented in user space (more
>> than once, apparently) doesn’t mean it should be. :-) Some algorithms are
>> just rather slow and buggy to reimplement in user space.    
>>
>> -Revar
>>
>>
>>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;
>
>> oz.at.michael@
>
>> &gt; wrote:
>>>
>>> nophead wrote
>>>> 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.
>>>
>>> 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/
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>>
>
>> Discuss@.openscad
>
>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>> _______________________________________________
>> OpenSCAD mailing list
>
>> Discuss@.openscad
>
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

adrianv
So you're willing to wait 24 hours for them to run?  


boxcarmib wrote

> my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
> but the flexibility of being able to manipulate point defined objects
> after they’ve been modified with 2d boolean functions. as it stands, as
> soon as you surrender a polygon of your own creation to the existing
> functions you no longer have access to the underlying point definition.
> Maybe there are ways around that, but I confess I’m not a power user by
> any means, but the possibility of built-in 2d operations that return point
> lists seems very attractive. i wouldn’t care if they were efficient… just
> that they could actually do the operations.
>
>> On Feb 23, 2020, at 7:14 PM, adrianv &lt;

> avm4@

> &gt; wrote:
>>
>> The referenced github project has *as*its*goal* the implementation of
>> everything in user space.  The actual state of the project, however, is
>> that
>> nothing nontrivial has been implemented.  The boolean operations and
>> offset
>> are both listed under the future work section, along with hull and
>> minkowski.  
>>
>> One major challenge of implementing these sorts of functions in user
>> space
>> is that the efficient algorithms typically require data structures that
>> are
>> not available in OpenSCAD, or whose implementation will be so inefficient
>> that it wouldn't deliver the intended speed-up.  
>>
>>
>> RevarBat wrote
>>> Just because something can be and has been implemented in user space
>>> (more
>>> than once, apparently) doesn’t mean it should be. :-) Some algorithms
>>> are
>>> just rather slow and buggy to reimplement in user space.    
>>>
>>> -Revar
>>>
>>>
>>>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;
>>
>>> oz.at.michael@
>>
>>> &gt; wrote:
>>>>
>>>> nophead wrote
>>>>> 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.
>>>>
>>>> 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/
>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>>
>>
>>> Discuss@.openscad
>>
>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>
>>> Discuss@.openscad
>>
>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>>
>>
>>
>>
>> --
>> Sent from: http://forum.openscad.org/
>>
>> _______________________________________________
>> OpenSCAD mailing list
>>

> Discuss@.openscad

>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


boxcarmib wrote

> my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
> but the flexibility of being able to manipulate point defined objects
> after they’ve been modified with 2d boolean functions. as it stands, as
> soon as you surrender a polygon of your own creation to the existing
> functions you no longer have access to the underlying point definition.
> Maybe there are ways around that, but I confess I’m not a power user by
> any means, but the possibility of built-in 2d operations that return point
> lists seems very attractive. i wouldn’t care if they were efficient… just
> that they could actually do the operations.
>
>> On Feb 23, 2020, at 7:14 PM, adrianv &lt;

> avm4@

> &gt; wrote:
>>
>> The referenced github project has *as*its*goal* the implementation of
>> everything in user space.  The actual state of the project, however, is
>> that
>> nothing nontrivial has been implemented.  The boolean operations and
>> offset
>> are both listed under the future work section, along with hull and
>> minkowski.  
>>
>> One major challenge of implementing these sorts of functions in user
>> space
>> is that the efficient algorithms typically require data structures that
>> are
>> not available in OpenSCAD, or whose implementation will be so inefficient
>> that it wouldn't deliver the intended speed-up.  
>>
>>
>> RevarBat wrote
>>> Just because something can be and has been implemented in user space
>>> (more
>>> than once, apparently) doesn’t mean it should be. :-) Some algorithms
>>> are
>>> just rather slow and buggy to reimplement in user space.    
>>>
>>> -Revar
>>>
>>>
>>>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;
>>
>>> oz.at.michael@
>>
>>> &gt; wrote:
>>>>
>>>> nophead wrote
>>>>> 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.
>>>>
>>>> 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/
>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>>
>>
>>> Discuss@.openscad
>>
>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>
>>> Discuss@.openscad
>>
>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>>
>>
>>
>>
>> --
>> Sent from: http://forum.openscad.org/
>>
>> _______________________________________________
>> OpenSCAD mailing list
>>

> Discuss@.openscad

>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

boxcarmib
well there’s always a tradeoff of course… and if you’re stating that any built in 2d boolean operation will take 24 hours to execute, then yes, I spoke too soon. On the other hand if the computational time is relative to the complexity of the object and that is what is time dependent then it would depend on the application. I’m led to believe than in our current palette the most computationally expensive function is minkowski… and depending on what you want to combine it can take hours and hours to run. Notwithstanding, I presume there are lots of people who use minkowski regardless of it’s execution speed because it provides them with functionality they require.
The purpose of my post was simply to identify that my enthusiasm for a point based 2d boolean function suite was not with a goal of greater efficiency, and that there may be other users like me for whom speed of computation would be at best a secondary concern.

On Feb 23, 2020, at 8:03 PM, adrianv <[hidden email]> wrote:

So you're willing to wait 24 hours for them to run?  


boxcarmib wrote
my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
but the flexibility of being able to manipulate point defined objects
after they’ve been modified with 2d boolean functions. as it stands, as
soon as you surrender a polygon of your own creation to the existing
functions you no longer have access to the underlying point definition.
Maybe there are ways around that, but I confess I’m not a power user by
any means, but the possibility of built-in 2d operations that return point
lists seems very attractive. i wouldn’t care if they were efficient… just
that they could actually do the operations.

On Feb 23, 2020, at 7:14 PM, adrianv &lt;

avm4@

&gt; wrote:

The referenced github project has *as*its*goal* the implementation of
everything in user space.  The actual state of the project, however, is
that
nothing nontrivial has been implemented.  The boolean operations and
offset
are both listed under the future work section, along with hull and
minkowski.  

One major challenge of implementing these sorts of functions in user
space
is that the efficient algorithms typically require data structures that
are
not available in OpenSCAD, or whose implementation will be so inefficient
that it wouldn't deliver the intended speed-up.  


RevarBat wrote
Just because something can be and has been implemented in user space
(more
than once, apparently) doesn’t mean it should be. :-) Some algorithms
are
just rather slow and buggy to reimplement in user space.    

-Revar


On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;

oz.at.michael@

&gt; wrote:

nophead wrote
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.

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/

_______________________________________________
OpenSCAD mailing list


Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________
OpenSCAD mailing list

Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list


Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list

Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


boxcarmib wrote
my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
but the flexibility of being able to manipulate point defined objects
after they’ve been modified with 2d boolean functions. as it stands, as
soon as you surrender a polygon of your own creation to the existing
functions you no longer have access to the underlying point definition.
Maybe there are ways around that, but I confess I’m not a power user by
any means, but the possibility of built-in 2d operations that return point
lists seems very attractive. i wouldn’t care if they were efficient… just
that they could actually do the operations.

On Feb 23, 2020, at 7:14 PM, adrianv &lt;

avm4@

&gt; wrote:

The referenced github project has *as*its*goal* the implementation of
everything in user space.  The actual state of the project, however, is
that
nothing nontrivial has been implemented.  The boolean operations and
offset
are both listed under the future work section, along with hull and
minkowski.  

One major challenge of implementing these sorts of functions in user
space
is that the efficient algorithms typically require data structures that
are
not available in OpenSCAD, or whose implementation will be so inefficient
that it wouldn't deliver the intended speed-up.  


RevarBat wrote
Just because something can be and has been implemented in user space
(more
than once, apparently) doesn’t mean it should be. :-) Some algorithms
are
just rather slow and buggy to reimplement in user space.    

-Revar


On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;

oz.at.michael@

&gt; wrote:

nophead wrote
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.

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/

_______________________________________________
OpenSCAD mailing list


Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

_______________________________________________
OpenSCAD mailing list

Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list


Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list

Discuss@.openscad

http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

adrianv
Obviously run times will be dependent on input size.  My user space offset()
code is O(n^2).  A good offset is more like O(n log n).  That means if you
have a lot of points, it's going to be a lot slower than the built-in
options at some point.  I just tested running offset on circles and with
$fn=1000 my code takes 8s and native OpenSCAD takes 0s.  For 4000 points
native OpenSCAD still takes 0s and my code takes 2 minutes.   Too slow?  Who
can say.   With 10k points OpenSCAD native still runs in 0s.  My code failed
after 13 minutes---probably something having to do with the very small
segment size.  But hard to debug something that takes 13 minutes to
manifest.  One thing I do with my offset() is call it from offset_sweep()
which needs to run offset for every layer in the swept polyhedron.  So if
offset() takes 2 minutes and you want 100 layers you're now approaching 3
hours.  

I'd use minkowski more if it was faster.  One reason I wrote offset() was to
avoid minkowski.   At least for my applications, I don't need a lot of
points.  But my point is that the run time of these user space
implementations is potentially really slow, like a thousand times slower
than native OpenSCAD.   And my algorithm is not as robust as I would like.  


boxcarmib wrote

> well there’s always a tradeoff of course… and if you’re stating that any
> built in 2d boolean operation will take 24 hours to execute, then yes, I
> spoke too soon. On the other hand if the computational time is relative to
> the complexity of the object and that is what is time dependent then it
> would depend on the application. I’m led to believe than in our current
> palette the most computationally expensive function is minkowski… and
> depending on what you want to combine it can take hours and hours to run.
> Notwithstanding, I presume there are lots of people who use minkowski
> regardless of it’s execution speed because it provides them with
> functionality they require.
> The purpose of my post was simply to identify that my enthusiasm for a
> point based 2d boolean function suite was not with a goal of greater
> efficiency, and that there may be other users like me for whom speed of
> computation would be at best a secondary concern.
>
>> On Feb 23, 2020, at 8:03 PM, adrianv &lt;

> avm4@

> &gt; wrote:
>>
>> So you're willing to wait 24 hours for them to run?  
>>
>>
>> boxcarmib wrote
>>> my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
>>> but the flexibility of being able to manipulate point defined objects
>>> after they’ve been modified with 2d boolean functions. as it stands, as
>>> soon as you surrender a polygon of your own creation to the existing
>>> functions you no longer have access to the underlying point definition.
>>> Maybe there are ways around that, but I confess I’m not a power user by
>>> any means, but the possibility of built-in 2d operations that return
>>> point
>>> lists seems very attractive. i wouldn’t care if they were efficient…
>>> just
>>> that they could actually do the operations.
>>>
>>>> On Feb 23, 2020, at 7:14 PM, adrianv &lt;
>>
>>> avm4@
>>
>>> &gt; wrote:
>>>>
>>>> The referenced github project has *as*its*goal* the implementation of
>>>> everything in user space.  The actual state of the project, however, is
>>>> that
>>>> nothing nontrivial has been implemented.  The boolean operations and
>>>> offset
>>>> are both listed under the future work section, along with hull and
>>>> minkowski.  
>>>>
>>>> One major challenge of implementing these sorts of functions in user
>>>> space
>>>> is that the efficient algorithms typically require data structures that
>>>> are
>>>> not available in OpenSCAD, or whose implementation will be so
>>>> inefficient
>>>> that it wouldn't deliver the intended speed-up.  
>>>>
>>>>
>>>> RevarBat wrote
>>>>> Just because something can be and has been implemented in user space
>>>>> (more
>>>>> than once, apparently) doesn’t mean it should be. :-) Some algorithms
>>>>> are
>>>>> just rather slow and buggy to reimplement in user space.    
>>>>>
>>>>> -Revar
>>>>>
>>>>>
>>>>>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;
>>>>
>>>>> oz.at.michael@
>>>>
>>>>> &gt; wrote:
>>>>>>
>>>>>> nophead wrote
>>>>>>> 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.
>>>>>>
>>>>>> Hasn't someone done that, OpenSCAD modules etc rewritten in
>>>>>> user-land?
>>>>>> Found it! https://github.com/thehans/FunctionalOpenSCAD
>>>>>> &lt;https://github.com/thehans/FunctionalOpenSCAD&gt;
>>>>>>
>>>>>>
>>>>>>
>>>>>> -----
>>>>>> 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/
>>>>>> &lt;http://forum.openscad.org/&gt;
>>>>>>
>>>>>> _______________________________________________
>>>>>> OpenSCAD mailing list
>>>>>>
>>>>
>>>>> Discuss@.openscad
>>>>
>>>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>
>>>>> Discuss@.openscad
>>>>
>>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sent from: http://forum.openscad.org/
>>>> &lt;http://forum.openscad.org/&gt;
>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>>
>>
>>> Discuss@.openscad
>>
>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>>
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>
>>> Discuss@.openscad
>>
>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>
>>
>> boxcarmib wrote
>>> my enthusiasm for exteneded 2d boolean functions isn’t about efficiency
>>> but the flexibility of being able to manipulate point defined objects
>>> after they’ve been modified with 2d boolean functions. as it stands, as
>>> soon as you surrender a polygon of your own creation to the existing
>>> functions you no longer have access to the underlying point definition.
>>> Maybe there are ways around that, but I confess I’m not a power user by
>>> any means, but the possibility of built-in 2d operations that return
>>> point
>>> lists seems very attractive. i wouldn’t care if they were efficient…
>>> just
>>> that they could actually do the operations.
>>>
>>>> On Feb 23, 2020, at 7:14 PM, adrianv &lt;
>>
>>> avm4@
>>
>>> &gt; wrote:
>>>>
>>>> The referenced github project has *as*its*goal* the implementation of
>>>> everything in user space.  The actual state of the project, however, is
>>>> that
>>>> nothing nontrivial has been implemented.  The boolean operations and
>>>> offset
>>>> are both listed under the future work section, along with hull and
>>>> minkowski.  
>>>>
>>>> One major challenge of implementing these sorts of functions in user
>>>> space
>>>> is that the efficient algorithms typically require data structures that
>>>> are
>>>> not available in OpenSCAD, or whose implementation will be so
>>>> inefficient
>>>> that it wouldn't deliver the intended speed-up.  
>>>>
>>>>
>>>> RevarBat wrote
>>>>> Just because something can be and has been implemented in user space
>>>>> (more
>>>>> than once, apparently) doesn’t mean it should be. :-) Some algorithms
>>>>> are
>>>>> just rather slow and buggy to reimplement in user space.    
>>>>>
>>>>> -Revar
>>>>>
>>>>>
>>>>>> On Feb 23, 2020, at 6:33 PM, MichaelAtOz &lt;
>>>>
>>>>> oz.at.michael@
>>>>
>>>>> &gt; wrote:
>>>>>>
>>>>>> nophead wrote
>>>>>>> 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.
>>>>>>
>>>>>> 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/
>>>>>> &lt;http://forum.openscad.org/&gt;
>>>>>>
>>>>>> _______________________________________________
>>>>>> OpenSCAD mailing list
>>>>>>
>>>>
>>>>> Discuss@.openscad
>>>>
>>>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>
>>>>> Discuss@.openscad
>>>>
>>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>>> &lt;http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org&gt;
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sent from: http://forum.openscad.org/
>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>>
>>
>>> Discuss@.openscad
>>
>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>>
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>
>>> Discuss@.openscad
>>
>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>>
>>
>>
>>
>> --
>> Sent from: http://forum.openscad.org/
>>
>> _______________________________________________
>> OpenSCAD mailing list
>>

> Discuss@.openscad

>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

David Eccles (gringer)
In reply to this post by nophead
nophead wrote
> 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.

Or add a function that returns the points that would be encoded in
a rendered version of its children
<http://forum.openscad.org/User-Poll-What-do-you-want-to-see-from-OpenSCAD-development-tp27802p27851.html>
, so that the point list can be generated after the /existing/ OpenSCAD
operations are carried out.



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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Parkinbot
In reply to this post by adrianv
adrianv wrote
> One thing I do with my offset() is call it from offset_sweep()
> which needs to run offset for every layer in the swept polyhedron.  
> ...
> I'd use minkowski more if it was faster.  One reason I wrote offset() was
> to
> avoid minkowski.   At least for my applications, I don't need a lot of
> points.  But my point is that the run time of these user space
> implementations is potentially really slow, like a thousand times slower
> than native OpenSCAD.   And my algorithm is not as robust as I would like.  

You name it. Personally I implement stuff in user land only, when I can't
avoid sweep() / skin() to finish a design in a decent way; and then I don't
care about robustness and run time in the first hand, mainly because I am
not able to affort to do it for time. To say it with Pareto, you spend 80%
of the time for the remaining 20% of a task or even more.

Our current dilemma is: Once you cross the border to profit from a native
operation like a Boolean op or something like offset(), there is no way back
... and since no sweep/skin is available there, the only way to proceed is
to implement those ops in user land. Therefore, having sweep() / skin() in
native OpenSCAD, things would get much easier for us.

But I also understand that the dev team doesn't want to include *unsafe*
operations into OpenSCAD that can (und will, if not used with care)
potentially produce invalid results - besides polyhedron() which is unsafe
by its very nature (and lets us do all our nasty things).

On the other hand, I think that once the door has be opened towards this
kind of functionality in native OpenSCAD, it should also be manageable to
implement it in a way so that it offers a *protected* mode testing each
polygon in the input feed for self-intersection and against all others for
mutual intersection. For most of us it would be fine to live with an
*unsafe* implementation of sweep()/skin() and big red *use at you own risk*
sign in the wiki paired with a best practice documentation, as it can be
found for polyhedron().





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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Ronaldo
I agree that Boolean operations, offset e minkovski of objects defined by points has its own interested. However, my point when I started this thread was the inefficiency of the projection() operator. I consider brute force to approach the projection by simply joining polygons by Boolean union. Something better would be expected but it seems that is the way OpenSCAD does projection as you can see by this small example:

$fn=400;
tw=180;
sc=0.01;
projection()
union(){
  linear_extrude(20,twist=tw,scale=sc)
    circle(30);
  mirror([0,0,1])
    linear_extrude(20,twist=tw,scale=sc)
      circle(30);
}

It took more than 7 min. in my computer to find a circle with 400 vertices at the end. Even with tw=0 and sc=0.8, it required 8 sec.

I think the union of polygons is one of the worst strategy to projection despite its conceptual simplicity. The border of the projection of a polyhedron is contained in the projection of its vertical silhouette edges namely and loosely those edges whose adjacent faces are one facing upward and the other, downward. Usually the set of silhouette edges is a small fraction of the total number. After finding the silhouette edges and projecting them a sweep algorithm may be used to connect the segments and define a polygon. To those that may be interested, here is a reference:


 It is not an easy task to implement in OpenSCAD language but it would be far easier and faster than polygon union. Anyway, I am not interested here in native language implementations of projection but to have a faster built-in one.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

cacb
On 24.02.2020 15:32, Ronaldo Persiano wrote:

> I agree that Boolean operations, offset e minkovski of objects defined
> by points has its own interested. However, my point when I started this
> thread was the inefficiency of the projection() operator. I consider
> brute force to approach the projection by simply joining polygons by
> Boolean union. Something better would be expected but it seems that is
> the way OpenSCAD does projection as you can see by this small example:
>
>     $fn=400;
>     tw=180;
>     sc=0.01;
>     projection()
>     union(){
>        linear_extrude(20,twist=tw,scale=sc)
>          circle(30);
>        mirror([0,0,1])
>          linear_extrude(20,twist=tw,scale=sc)
>            circle(30);
>     }
>
>
> It took more than 7 min. in my computer to find a circle with 400
> vertices at the end. Even with tw=0 and sc=0.8, it required 8 sec.

The problem here is mostly the 3d boolean, less so projection(). I
installed openscad-nightly 2020.01.25 under Kubuntu 18.04 (32 GB RAM)
and ran a couple of tests

body1.scad
==========
$fn=400;
tw=180;
sc=0.01;
linear_extrude(20,twist=tw,scale=sc)
    circle(30);

This took virtually no time, exported to body1.stl and body1.off


body2.scad
=========
$fn=400;
tw=180;
sc=0.01;
mirror([0,0,1])
linear_extrude(20,twist=tw,scale=sc)
   circle(30);

Again, this took virtually no time, exported to body2.stl and body2.off


Union_b1b2.scad
===============
union() {
   import("body1.stl");
   import("body2.stl");
}

The imports took 4 seconds, but the union took 3min, using 5 GB of
RAM... If you don't have a lot of RAM I guess it will take *much* longer.

This was exported to Union_b1b2.stl and Union_b1b2.off

Union_b1b2_projection.scad
==========================
projection()
   import("Union_b1b2.stl");

This took 54s so about ~50s for projection

Although the projection() took some time (~30% of boolean union), the 3d
boolean is the main problem.

Running your original code as written took 4min 25s consuming 5 GB RAM
on my machine.

For comparison, I read the same data into AngelCAD:

Union_b1b2_ac.as
================
shape@ main_shape()
{
    return polyhedron("body1.off") + polyhedron("body2.off");
}

This took 16.6 sec (including export to STL and OFF) consuming at most
2.1GB RAM


Union_b1b2_projection_ac.as
==========================

shape@ main_shape()
{
    return projection2d(polyhedron("Union_b1b2.off"));
}

This took 52 sec (including export to DXF) consuming ~1.8GB RAM


So clearly, the projection() code in OpenSCAD and AngelCAD takes about
the same time for this model (~50s on my machine). By running 2d
booleans in threads I guess it can be made to run faster, but I am not
sure it is worth the effort.

The big difference is in 3d booleans.

Carsten Arnholm





_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: About projection()

Ronaldo
Thank you Carsten for spending your time to check my example, showing the Boolean operation is the main culprit for the long running time. Your analysis almost makes me complacent with the projection() low performance. But at the end, I have decided to investigate what makes it stuck.

As a test case, I took a torus knot generated by sweeping a circle. To simplify I have chosen a knot (3,2) which has only 4 areas of projection overlapping (see attached image). 

My test main code was simply:

// geometric data
n = 20;  // section discretization
m = 40 ;  // path discretization
d = 20;   // section radius
R = 400;  // knot major radius
r = 150;  // knot minor radius

p  = 3;
q  = 2;
to = true;
echo(p=p, q=q);
echo(n=n, m=m);

if(to) {
  echo("only knot");
  sweep(sections(p,q,n,m,d));
}
else{
  echo("knot projection");
  projection()
  sweep(sections(p,q,n,m,d));
}

where sections() generates m circular sections with n points each along a (3,2) knot path. The full code I have used in my tests is attached. Note that the circular sections have a radius d very small compared to the torus major radius. I have ran three cases with 20000 vertices and I got these time results:

                        just the knot           knot projection   
n =  50, m = 400           6 sec                    12 sec
n = 100, m = 200           6 sec                    16 sec
n = 500, m =  40           6 sec                  2 min 45 sec

What makes the last projection so slow? The last one is the case whose projected polygon has the least number of vertices, estimated as something near 2*m = 80 point. The reason might be the number of triangles that have intersection after the projection. My second image shows the detail of one of those intersections in wireframe view for n=6 and m=40. With n=500, more than 2000 triangles overlap at each of the 4 intersections. The third image shows the detail of the same knot intersections in wireframe view for n=6 and m=200 and it seems that much more triangles overlap when m is increased. So, the number of overlapping triangles doesn't seem to be the reason for a long run time of the projection. Two additional tests have shown the puzzle complexity: with 25000 points (n=500, m=50) the projection required 2 min and 2 sec and with n=500 and m=80 (40000 vertices) the projection time was nearly the same: 2 min and 43 sec..

The torus knot seems to be easy to project by silhouette computation followed by the sweep line algorithm: it may have a lot of silhouette segments but a few intersections between them. A much harder case for that algorithm would be a linear_extrusion of a circle with a cleverly chosen twist and a scale a slightly less than 1.

OpenSCAD projection() performance is still a mystery.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

torus_knot_3_2_top.PNG (70K) Download Attachment
torus_knot_3_2_top_wireframe_6x40.PNG (30K) Download Attachment
torus_knot_3_2_top_wireframe_6x200.PNG (43K) Download Attachment
Sweep_Knot.scad (1K) Download Attachment
12