L-systems demo. Fractal designs, interpreter performance stress testing

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

L-systems demo. Fractal designs, interpreter performance stress testing

thehans
Howdy folks,

I wanted to share this experiment I've created which implements some
L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.

The script is here:
https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66

There is documentation at the top of the script which explains a
little more about what its doing, so I won't repeat all that here.
It can be used to generate various 2D fractal designs, of which I've
implemented about a dozen.
Just uncomment the one you want to view, tweak the n value for number
of iterations if you like, etc.

I created this just to play with some ideas and don't have a specific
3D printable object that I plan to create with it, but it could be
interesting to incorporate into some designs(e.g. emboss a fractal
deisgn on a flat box lid or something).

It also could be potentially extended to support 3D systems with a few
more commands(basically positive and negative turn command for
pitch/roll/yaw) but I haven't attempted that yet.

The most important takeaway I got from this for me is that recursively
building lists is incredibly inefficient in OpenSCAD, because concat
takes O(n) time, and doing that for every element makes it take
O(n^2).

Any ideas on tweaks to the script or improvements to the language that
could be done to help with this issue?  Would something like a O(1)
"cons" function for constructing lists be feasible to add to the
OpenSCAD language?

Cheers,
Hans

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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

runsun
very nicely done. Thx for sharing. It'd be interesting if a randomness is
applied, like, somethings turn 30 degrees, sometimes turn 45, or left or
right, etc.



-----

$  Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ), runscad.py ( 2 , git ), synwrite ( 2 );   $ tips: Collection of tips on github

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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
In reply to this post by thehans
You could implement Lisp style lists directly.

function cons(a,b)=[a,b];
function car(a)=a[0];
function cdr(a)=a[1];
nil=[];

Then a list like [1,2,3] would be encoded as
cons(1,cons(2,cons(3,nil))) or
[1,[2,[3,[]]]].

Now concatenation-to-the-front is O(1) but indexing is O(N), just like in Lisp.

On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
Howdy folks,

I wanted to share this experiment I've created which implements some
L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.

The script is here:
https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66

There is documentation at the top of the script which explains a
little more about what its doing, so I won't repeat all that here.
It can be used to generate various 2D fractal designs, of which I've
implemented about a dozen.
Just uncomment the one you want to view, tweak the n value for number
of iterations if you like, etc.

I created this just to play with some ideas and don't have a specific
3D printable object that I plan to create with it, but it could be
interesting to incorporate into some designs(e.g. emboss a fractal
deisgn on a flat box lid or something).

It also could be potentially extended to support 3D systems with a few
more commands(basically positive and negative turn command for
pitch/roll/yaw) but I haven't attempted that yet.

The most important takeaway I got from this for me is that recursively
building lists is incredibly inefficient in OpenSCAD, because concat
takes O(n) time, and doing that for every element makes it take
O(n^2).

Any ideas on tweaks to the script or improvements to the language that
could be done to help with this issue?  Would something like a O(1)
"cons" function for constructing lists be feasible to add to the
OpenSCAD language?

Cheers,
Hans

_______________________________________________
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: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
Doug,

Is there any possible way to then flatten that list in O(n) time?

I think the issue with that is then you need to eventually process
that LIsp style list in a module to get any geometry output, and
modules handle recursion incredibly poorly.  There is an absolute
module recursion limit of i think 10,000, but getting anywhere close
to that would take  prohibitively long to process.  Here is a very
simplified example of module recursion:
module recur(i) {
  if (i % 100 == 0) echo(i);
  if (i > 0) {
    recur(i-1);
  }
}
recur(1000);
// Total rendering time: 0 hours, 0 minutes, 21 seconds

// recur(2000);
// Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!

Is this slow because its doing 2000 implicit unions on null geometries or what?

On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:

> You could implement Lisp style lists directly.
>
> function cons(a,b)=[a,b];
> function car(a)=a[0];
> function cdr(a)=a[1];
> nil=[];
>
> Then a list like [1,2,3] would be encoded as
> cons(1,cons(2,cons(3,nil))) or
> [1,[2,[3,[]]]].
>
> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
> Lisp.
>
> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>
>> Howdy folks,
>>
>> I wanted to share this experiment I've created which implements some
>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>
>> The script is here:
>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>
>> There is documentation at the top of the script which explains a
>> little more about what its doing, so I won't repeat all that here.
>> It can be used to generate various 2D fractal designs, of which I've
>> implemented about a dozen.
>> Just uncomment the one you want to view, tweak the n value for number
>> of iterations if you like, etc.
>>
>> I created this just to play with some ideas and don't have a specific
>> 3D printable object that I plan to create with it, but it could be
>> interesting to incorporate into some designs(e.g. emboss a fractal
>> deisgn on a flat box lid or something).
>>
>> It also could be potentially extended to support 3D systems with a few
>> more commands(basically positive and negative turn command for
>> pitch/roll/yaw) but I haven't attempted that yet.
>>
>> The most important takeaway I got from this for me is that recursively
>> building lists is incredibly inefficient in OpenSCAD, because concat
>> takes O(n) time, and doing that for every element makes it take
>> O(n^2).
>>
>> Any ideas on tweaks to the script or improvements to the language that
>> could be done to help with this issue?  Would something like a O(1)
>> "cons" function for constructing lists be feasible to add to the
>> OpenSCAD language?
>>
>> Cheers,
>> Hans
>>
>> _______________________________________________
>> 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
>

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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:

> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

Ronaldo
Take a look at the CSG tree of your recursion code. 

Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

_______________________________________________
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: L-systems demo. Fractal designs, interpreter performance stress testing

davidconeff
Trying to do fractals or nested objects like this seems to be like using a hammer (OpenSCAD) to try and turn a screw. There are simply better tools out there for it now that will be more computationally efficient by using f-rep as the basis of the geometric representation.

Matt Keeter's libfive / Studio project would probably do this much better, but I don't have an Ubuntu/OS-X install running at the moment and there is no pre-compiled build of it for Win10.

The Studio GUI app was developed to work very similarly to OpenSCAD with a much more efficient underlying engine as well as GUI interaction with shape parameters that back-propagate to the code. I believe this is an eventual goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is just inherently a lot slower.

On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano <[hidden email]> wrote:
Take a look at the CSG tree of your recursion code. 

Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

_______________________________________________
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



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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
In reply to this post by Ronaldo
Here's the csg result from recur(1000)
https://gist.github.com/thehans/0ea178e47084bc41ff563f2098ad486a
The csg file itself is 5.1MB, but thats mostly tab characters due to
high nesting.

In the file there's 3014 calls to group, with an expected high degree
of nesting.
1002 of them are completely empty groups with the semicolon
immediately following:  `group();`
It seems like at the very least those empty groups should be
eliminated (not created in the first place).

But overall I feel like the csg output should be nil whenever since
there is no geometry in any leaf node.

In general it seems like any group node with 0 or 1 children could be
safely pruned from the tree, right?

After running recur(1000) I see in my task manager that OpenSCAD is
using 6.8GB of memory.  Meaning that in this case, group nodes require
an average ~2.25MB each, which still seems quite odd even if you
accept the total number of extraneous group calls.




On Thu, Feb 15, 2018 at 4:01 PM, Ronaldo Persiano <[hidden email]> wrote:

> Take a look at the CSG tree of your recursion code.
>
> Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
>>
>> After looking at it again, the slowness of the above recursion seems
>> to come from insane memory usage of dozens of gigabytes and hitting my
>> swap incredibly hard.
>> How is it even possible to require that much memory for the simplest
>> task?  Something seems terribly wrong here.
>> I had to set up a 256GB NVMe swap partition to allow me to test some
>> of this madness.
>>
>> On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
>> > Doug,
>> >
>> > Is there any possible way to then flatten that list in O(n) time?
>> >
>> > I think the issue with that is then you need to eventually process
>> > that LIsp style list in a module to get any geometry output, and
>> > modules handle recursion incredibly poorly.  There is an absolute
>> > module recursion limit of i think 10,000, but getting anywhere close
>> > to that would take  prohibitively long to process.  Here is a very
>> > simplified example of module recursion:
>> > module recur(i) {
>> >   if (i % 100 == 0) echo(i);
>> >   if (i > 0) {
>> >     recur(i-1);
>> >   }
>> > }
>> > recur(1000);
>> > // Total rendering time: 0 hours, 0 minutes, 21 seconds
>> >
>> > // recur(2000);
>> > // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>> >
>> > Is this slow because its doing 2000 implicit unions on null geometries
>> > or what?
>> >
>> > On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> >> You could implement Lisp style lists directly.
>> >>
>> >> function cons(a,b)=[a,b];
>> >> function car(a)=a[0];
>> >> function cdr(a)=a[1];
>> >> nil=[];
>> >>
>> >> Then a list like [1,2,3] would be encoded as
>> >> cons(1,cons(2,cons(3,nil))) or
>> >> [1,[2,[3,[]]]].
>> >>
>> >> Now concatenation-to-the-front is O(1) but indexing is O(N), just like
>> >> in
>> >> Lisp.
>> >>
>> >> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>> >>>
>> >>> Howdy folks,
>> >>>
>> >>> I wanted to share this experiment I've created which implements some
>> >>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>> >>>
>> >>> The script is here:
>> >>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>> >>>
>> >>> There is documentation at the top of the script which explains a
>> >>> little more about what its doing, so I won't repeat all that here.
>> >>> It can be used to generate various 2D fractal designs, of which I've
>> >>> implemented about a dozen.
>> >>> Just uncomment the one you want to view, tweak the n value for number
>> >>> of iterations if you like, etc.
>> >>>
>> >>> I created this just to play with some ideas and don't have a specific
>> >>> 3D printable object that I plan to create with it, but it could be
>> >>> interesting to incorporate into some designs(e.g. emboss a fractal
>> >>> deisgn on a flat box lid or something).
>> >>>
>> >>> It also could be potentially extended to support 3D systems with a few
>> >>> more commands(basically positive and negative turn command for
>> >>> pitch/roll/yaw) but I haven't attempted that yet.
>> >>>
>> >>> The most important takeaway I got from this for me is that recursively
>> >>> building lists is incredibly inefficient in OpenSCAD, because concat
>> >>> takes O(n) time, and doing that for every element makes it take
>> >>> O(n^2).
>> >>>
>> >>> Any ideas on tweaks to the script or improvements to the language that
>> >>> could be done to help with this issue?  Would something like a O(1)
>> >>> "cons" function for constructing lists be feasible to add to the
>> >>> OpenSCAD language?
>> >>>
>> >>> Cheers,
>> >>> Hans
>> >>>
>> >>> _______________________________________________
>> >>> 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
>> >>
>>
>> _______________________________________________
>> 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
>

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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
> In general it seems like any group node with 0 or 1 children could be
> safely pruned from the tree, right?

quick correction to my above comment:
I should say: a group node with 0 children can be pruned/deleted, and
a group node with 1 child could be *replaced by its child* (don't
prune the child away indiscriminately).

On Thu, Feb 15, 2018 at 5:09 PM, Hans L <[hidden email]> wrote:

> Here's the csg result from recur(1000)
> https://gist.github.com/thehans/0ea178e47084bc41ff563f2098ad486a
> The csg file itself is 5.1MB, but thats mostly tab characters due to
> high nesting.
>
> In the file there's 3014 calls to group, with an expected high degree
> of nesting.
> 1002 of them are completely empty groups with the semicolon
> immediately following:  `group();`
> It seems like at the very least those empty groups should be
> eliminated (not created in the first place).
>
> But overall I feel like the csg output should be nil whenever since
> there is no geometry in any leaf node.
>
> In general it seems like any group node with 0 or 1 children could be
> safely pruned from the tree, right?
>
> After running recur(1000) I see in my task manager that OpenSCAD is
> using 6.8GB of memory.  Meaning that in this case, group nodes require
> an average ~2.25MB each, which still seems quite odd even if you
> accept the total number of extraneous group calls.
>
>
>
>
> On Thu, Feb 15, 2018 at 4:01 PM, Ronaldo Persiano <[hidden email]> wrote:
>> Take a look at the CSG tree of your recursion code.
>>
>> Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
>>>
>>> After looking at it again, the slowness of the above recursion seems
>>> to come from insane memory usage of dozens of gigabytes and hitting my
>>> swap incredibly hard.
>>> How is it even possible to require that much memory for the simplest
>>> task?  Something seems terribly wrong here.
>>> I had to set up a 256GB NVMe swap partition to allow me to test some
>>> of this madness.
>>>
>>> On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
>>> > Doug,
>>> >
>>> > Is there any possible way to then flatten that list in O(n) time?
>>> >
>>> > I think the issue with that is then you need to eventually process
>>> > that LIsp style list in a module to get any geometry output, and
>>> > modules handle recursion incredibly poorly.  There is an absolute
>>> > module recursion limit of i think 10,000, but getting anywhere close
>>> > to that would take  prohibitively long to process.  Here is a very
>>> > simplified example of module recursion:
>>> > module recur(i) {
>>> >   if (i % 100 == 0) echo(i);
>>> >   if (i > 0) {
>>> >     recur(i-1);
>>> >   }
>>> > }
>>> > recur(1000);
>>> > // Total rendering time: 0 hours, 0 minutes, 21 seconds
>>> >
>>> > // recur(2000);
>>> > // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>>> >
>>> > Is this slow because its doing 2000 implicit unions on null geometries
>>> > or what?
>>> >
>>> > On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>>> >> You could implement Lisp style lists directly.
>>> >>
>>> >> function cons(a,b)=[a,b];
>>> >> function car(a)=a[0];
>>> >> function cdr(a)=a[1];
>>> >> nil=[];
>>> >>
>>> >> Then a list like [1,2,3] would be encoded as
>>> >> cons(1,cons(2,cons(3,nil))) or
>>> >> [1,[2,[3,[]]]].
>>> >>
>>> >> Now concatenation-to-the-front is O(1) but indexing is O(N), just like
>>> >> in
>>> >> Lisp.
>>> >>
>>> >> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>> >>>
>>> >>> Howdy folks,
>>> >>>
>>> >>> I wanted to share this experiment I've created which implements some
>>> >>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>> >>>
>>> >>> The script is here:
>>> >>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>> >>>
>>> >>> There is documentation at the top of the script which explains a
>>> >>> little more about what its doing, so I won't repeat all that here.
>>> >>> It can be used to generate various 2D fractal designs, of which I've
>>> >>> implemented about a dozen.
>>> >>> Just uncomment the one you want to view, tweak the n value for number
>>> >>> of iterations if you like, etc.
>>> >>>
>>> >>> I created this just to play with some ideas and don't have a specific
>>> >>> 3D printable object that I plan to create with it, but it could be
>>> >>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> >>> deisgn on a flat box lid or something).
>>> >>>
>>> >>> It also could be potentially extended to support 3D systems with a few
>>> >>> more commands(basically positive and negative turn command for
>>> >>> pitch/roll/yaw) but I haven't attempted that yet.
>>> >>>
>>> >>> The most important takeaway I got from this for me is that recursively
>>> >>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> >>> takes O(n) time, and doing that for every element makes it take
>>> >>> O(n^2).
>>> >>>
>>> >>> Any ideas on tweaks to the script or improvements to the language that
>>> >>> could be done to help with this issue?  Would something like a O(1)
>>> >>> "cons" function for constructing lists be feasible to add to the
>>> >>> OpenSCAD language?
>>> >>>
>>> >>> Cheers,
>>> >>> Hans
>>> >>>
>>> >>> _______________________________________________
>>> >>> 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
>>> >>
>>>
>>> _______________________________________________
>>> 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
>>

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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
In reply to this post by davidconeff
libfive studio does look pretty interesting, but there's no
pre-compiled build for Ubuntu either.

The required dependency version of guile-2.2 is too bleeding edge to
install from any current Ubuntu release.  I'm attempting to build that
now, it takes a bit.

And if you're not on 17.04 or newer (I'm on 16.04 LTS), then the Qt
version is not high enough either, so I'll have to compile that next.



On Thu, Feb 15, 2018 at 4:59 PM, David Coneff <[hidden email]> wrote:

> Trying to do fractals or nested objects like this seems to be like using a
> hammer (OpenSCAD) to try and turn a screw. There are simply better tools out
> there for it now that will be more computationally efficient by using f-rep
> as the basis of the geometric representation.
>
> Matt Keeter's libfive / Studio project would probably do this much better,
> but I don't have an Ubuntu/OS-X install running at the moment and there is
> no pre-compiled build of it for Win10.
> https://libfive.com/studio/
>
> The Studio GUI app was developed to work very similarly to OpenSCAD with a
> much more efficient underlying engine as well as GUI interaction with shape
> parameters that back-propagate to the code. I believe this is an eventual
> goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is just
> inherently a lot slower.
>
> On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano <[hidden email]>
> wrote:
>>
>> Take a look at the CSG tree of your recursion code.
>>
>> Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
>>>
>>> After looking at it again, the slowness of the above recursion seems
>>> to come from insane memory usage of dozens of gigabytes and hitting my
>>> swap incredibly hard.
>>> How is it even possible to require that much memory for the simplest
>>> task?  Something seems terribly wrong here.
>>> I had to set up a 256GB NVMe swap partition to allow me to test some
>>> of this madness.
>>>
>>> On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
>>> > Doug,
>>> >
>>> > Is there any possible way to then flatten that list in O(n) time?
>>> >
>>> > I think the issue with that is then you need to eventually process
>>> > that LIsp style list in a module to get any geometry output, and
>>> > modules handle recursion incredibly poorly.  There is an absolute
>>> > module recursion limit of i think 10,000, but getting anywhere close
>>> > to that would take  prohibitively long to process.  Here is a very
>>> > simplified example of module recursion:
>>> > module recur(i) {
>>> >   if (i % 100 == 0) echo(i);
>>> >   if (i > 0) {
>>> >     recur(i-1);
>>> >   }
>>> > }
>>> > recur(1000);
>>> > // Total rendering time: 0 hours, 0 minutes, 21 seconds
>>> >
>>> > // recur(2000);
>>> > // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>>> >
>>> > Is this slow because its doing 2000 implicit unions on null geometries
>>> > or what?
>>> >
>>> > On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>>> >> You could implement Lisp style lists directly.
>>> >>
>>> >> function cons(a,b)=[a,b];
>>> >> function car(a)=a[0];
>>> >> function cdr(a)=a[1];
>>> >> nil=[];
>>> >>
>>> >> Then a list like [1,2,3] would be encoded as
>>> >> cons(1,cons(2,cons(3,nil))) or
>>> >> [1,[2,[3,[]]]].
>>> >>
>>> >> Now concatenation-to-the-front is O(1) but indexing is O(N), just like
>>> >> in
>>> >> Lisp.
>>> >>
>>> >> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>> >>>
>>> >>> Howdy folks,
>>> >>>
>>> >>> I wanted to share this experiment I've created which implements some
>>> >>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>> >>>
>>> >>> The script is here:
>>> >>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>> >>>
>>> >>> There is documentation at the top of the script which explains a
>>> >>> little more about what its doing, so I won't repeat all that here.
>>> >>> It can be used to generate various 2D fractal designs, of which I've
>>> >>> implemented about a dozen.
>>> >>> Just uncomment the one you want to view, tweak the n value for number
>>> >>> of iterations if you like, etc.
>>> >>>
>>> >>> I created this just to play with some ideas and don't have a specific
>>> >>> 3D printable object that I plan to create with it, but it could be
>>> >>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> >>> deisgn on a flat box lid or something).
>>> >>>
>>> >>> It also could be potentially extended to support 3D systems with a
>>> >>> few
>>> >>> more commands(basically positive and negative turn command for
>>> >>> pitch/roll/yaw) but I haven't attempted that yet.
>>> >>>
>>> >>> The most important takeaway I got from this for me is that
>>> >>> recursively
>>> >>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> >>> takes O(n) time, and doing that for every element makes it take
>>> >>> O(n^2).
>>> >>>
>>> >>> Any ideas on tweaks to the script or improvements to the language
>>> >>> that
>>> >>> could be done to help with this issue?  Would something like a O(1)
>>> >>> "cons" function for constructing lists be feasible to add to the
>>> >>> OpenSCAD language?
>>> >>>
>>> >>> Cheers,
>>> >>> Hans
>>> >>>
>>> >>> _______________________________________________
>>> >>> 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
>>> >>
>>>
>>> _______________________________________________
>>> 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
>>
>
>
> _______________________________________________
> 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
|

L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
In reply to this post by davidconeff
Libfive studio is great, but I don't think it's good for rendering L-systems.

L-systems and IFS (Iterated Function Systems) are two ways to represent fractals. Some fractals, like Hans' dragon curve, can be represented using either system. F-Rep works well for IFS fractals. But I don't see how F-Rep can work efficiently for large L-system fractals.

You could do a dragon curve in Libfive using the IFS representation. But then you encounter another issue, which is that the libfive rendering algorithm (for rendering the shape onto the display) doesn't render fine details. In fact, it renders the shape to a mesh before displaying it. This means you can't do deep zooms into a deeply iterated IFS fractal.

Curv can perform these deep zooms, at interactive frame rates, at least for IFS fractals, because it uses a combination of sphere tracing and GPU rendering. Sphere tracing is best for fractals, but libfive uses a different rendering algorithm.

But if you want a good tool for exploring L-systems, try https://www.contextfreeart.org/

On Thursday, 15 February 2018, David Coneff <[hidden email]> wrote:
Trying to do fractals or nested objects like this seems to be like using a hammer (OpenSCAD) to try and turn a screw. There are simply better tools out there for it now that will be more computationally efficient by using f-rep as the basis of the geometric representation.

Matt Keeter's libfive / Studio project would probably do this much better, but I don't have an Ubuntu/OS-X install running at the moment and there is no pre-compiled build of it for Win10.

The Studio GUI app was developed to work very similarly to OpenSCAD with a much more efficient underlying engine as well as GUI interaction with shape parameters that back-propagate to the code. I believe this is an eventual goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is just inherently a lot slower.

On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano <[hidden email]> wrote:
Take a look at the CSG tree of your recursion code. 

Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

_______________________________________________
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



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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

davidconeff
I may have been confusing it with Keeter's Ao project

He used a similar sample image with the libfive project of a menger sponge.
The affine-transformations page about Ao was mentioning decreased tree depth when doing recursive transformations on nested trees, e.g., successively smaller, rotated boxes stacked on one another.
To be honest it's a bit above my head, the guy looks like a genius. His previous work with Antimony looked great, I wish OpenSCAD had that sort of functionality - most of the modelling I desire to do with it is basically successive parameterization of smaller and smaller parts of a larger whole, and Antimony has a GUI that makes that easy to track. Really need to get an Ubuntu setup going so I can use his software someday! 

On Thu, Feb 15, 2018 at 7:52 PM, doug moen <[hidden email]> wrote:
Libfive studio is great, but I don't think it's good for rendering L-systems.

L-systems and IFS (Iterated Function Systems) are two ways to represent fractals. Some fractals, like Hans' dragon curve, can be represented using either system. F-Rep works well for IFS fractals. But I don't see how F-Rep can work efficiently for large L-system fractals.

You could do a dragon curve in Libfive using the IFS representation. But then you encounter another issue, which is that the libfive rendering algorithm (for rendering the shape onto the display) doesn't render fine details. In fact, it renders the shape to a mesh before displaying it. This means you can't do deep zooms into a deeply iterated IFS fractal.

Curv can perform these deep zooms, at interactive frame rates, at least for IFS fractals, because it uses a combination of sphere tracing and GPU rendering. Sphere tracing is best for fractals, but libfive uses a different rendering algorithm.

But if you want a good tool for exploring L-systems, try https://www.contextfreeart.org/


On Thursday, 15 February 2018, David Coneff <[hidden email]> wrote:
Trying to do fractals or nested objects like this seems to be like using a hammer (OpenSCAD) to try and turn a screw. There are simply better tools out there for it now that will be more computationally efficient by using f-rep as the basis of the geometric representation.

Matt Keeter's libfive / Studio project would probably do this much better, but I don't have an Ubuntu/OS-X install running at the moment and there is no pre-compiled build of it for Win10.

The Studio GUI app was developed to work very similarly to OpenSCAD with a much more efficient underlying engine as well as GUI interaction with shape parameters that back-propagate to the code. I believe this is an eventual goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is just inherently a lot slower.

On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano <[hidden email]> wrote:
Take a look at the CSG tree of your recursion code. 

Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

_______________________________________________
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



_______________________________________________
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: L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
Libfive is just a continuation of the Ao project. Menger sponge is a common IFS fractal demo.
https://en.wikipedia.org/wiki/Menger_sponge

An order 0 Menger sponge is just a cube. An order N sponge contains 20^n subcubes. So an interesting test of a 3D modelling program is, how large a value of N can you use before the sponge fails to render?

It should be possible to 3D print an order 4 sponge. If the subcubes are 1mm wide, then the entire cube is 3^4 == 81mm wide.

In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which is a lot of triangles.

In Libfive, studio/examples/menger.io is an order 3 sponge. For some reason, it goes haywire if you try to make an order 4 sponge. Libfive renders shapes on the screen as triangle meshes, so I don't expect it to work with large order Menger sponges.

In Curv, "examples/menger.curv" is an order 4 sponge, and it renders at 60 FPS on my GPU. If I crank N up to 20, it still renders at 15 FPS. It fails to compile at N=50.


On 15 February 2018 at 23:40, David Coneff <[hidden email]> wrote:
I may have been confusing it with Keeter's Ao project

He used a similar sample image with the libfive project of a menger sponge.
The affine-transformations page about Ao was mentioning decreased tree depth when doing recursive transformations on nested trees, e.g., successively smaller, rotated boxes stacked on one another.
To be honest it's a bit above my head, the guy looks like a genius. His previous work with Antimony looked great, I wish OpenSCAD had that sort of functionality - most of the modelling I desire to do with it is basically successive parameterization of smaller and smaller parts of a larger whole, and Antimony has a GUI that makes that easy to track. Really need to get an Ubuntu setup going so I can use his software someday! 

On Thu, Feb 15, 2018 at 7:52 PM, doug moen <[hidden email]> wrote:
Libfive studio is great, but I don't think it's good for rendering L-systems.

L-systems and IFS (Iterated Function Systems) are two ways to represent fractals. Some fractals, like Hans' dragon curve, can be represented using either system. F-Rep works well for IFS fractals. But I don't see how F-Rep can work efficiently for large L-system fractals.

You could do a dragon curve in Libfive using the IFS representation. But then you encounter another issue, which is that the libfive rendering algorithm (for rendering the shape onto the display) doesn't render fine details. In fact, it renders the shape to a mesh before displaying it. This means you can't do deep zooms into a deeply iterated IFS fractal.

Curv can perform these deep zooms, at interactive frame rates, at least for IFS fractals, because it uses a combination of sphere tracing and GPU rendering. Sphere tracing is best for fractals, but libfive uses a different rendering algorithm.

But if you want a good tool for exploring L-systems, try https://www.contextfreeart.org/


On Thursday, 15 February 2018, David Coneff <[hidden email]> wrote:
Trying to do fractals or nested objects like this seems to be like using a hammer (OpenSCAD) to try and turn a screw. There are simply better tools out there for it now that will be more computationally efficient by using f-rep as the basis of the geometric representation.

Matt Keeter's libfive / Studio project would probably do this much better, but I don't have an Ubuntu/OS-X install running at the moment and there is no pre-compiled build of it for Win10.

The Studio GUI app was developed to work very similarly to OpenSCAD with a much more efficient underlying engine as well as GUI interaction with shape parameters that back-propagate to the code. I believe this is an eventual goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is just inherently a lot slower.

On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano <[hidden email]> wrote:
Take a look at the CSG tree of your recursion code. 

Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
After looking at it again, the slowness of the above recursion seems
to come from insane memory usage of dozens of gigabytes and hitting my
swap incredibly hard.
How is it even possible to require that much memory for the simplest
task?  Something seems terribly wrong here.
I had to set up a 256GB NVMe swap partition to allow me to test some
of this madness.

On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
> Doug,
>
> Is there any possible way to then flatten that list in O(n) time?
>
> I think the issue with that is then you need to eventually process
> that LIsp style list in a module to get any geometry output, and
> modules handle recursion incredibly poorly.  There is an absolute
> module recursion limit of i think 10,000, but getting anywhere close
> to that would take  prohibitively long to process.  Here is a very
> simplified example of module recursion:
> module recur(i) {
>   if (i % 100 == 0) echo(i);
>   if (i > 0) {
>     recur(i-1);
>   }
> }
> recur(1000);
> // Total rendering time: 0 hours, 0 minutes, 21 seconds
>
> // recur(2000);
> // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>
> Is this slow because its doing 2000 implicit unions on null geometries or what?
>
> On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>> You could implement Lisp style lists directly.
>>
>> function cons(a,b)=[a,b];
>> function car(a)=a[0];
>> function cdr(a)=a[1];
>> nil=[];
>>
>> Then a list like [1,2,3] would be encoded as
>> cons(1,cons(2,cons(3,nil))) or
>> [1,[2,[3,[]]]].
>>
>> Now concatenation-to-the-front is O(1) but indexing is O(N), just like in
>> Lisp.
>>
>> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>
>>> Howdy folks,
>>>
>>> I wanted to share this experiment I've created which implements some
>>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>
>>> The script is here:
>>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>
>>> There is documentation at the top of the script which explains a
>>> little more about what its doing, so I won't repeat all that here.
>>> It can be used to generate various 2D fractal designs, of which I've
>>> implemented about a dozen.
>>> Just uncomment the one you want to view, tweak the n value for number
>>> of iterations if you like, etc.
>>>
>>> I created this just to play with some ideas and don't have a specific
>>> 3D printable object that I plan to create with it, but it could be
>>> interesting to incorporate into some designs(e.g. emboss a fractal
>>> deisgn on a flat box lid or something).
>>>
>>> It also could be potentially extended to support 3D systems with a few
>>> more commands(basically positive and negative turn command for
>>> pitch/roll/yaw) but I haven't attempted that yet.
>>>
>>> The most important takeaway I got from this for me is that recursively
>>> building lists is incredibly inefficient in OpenSCAD, because concat
>>> takes O(n) time, and doing that for every element makes it take
>>> O(n^2).
>>>
>>> Any ideas on tweaks to the script or improvements to the language that
>>> could be done to help with this issue?  Would something like a O(1)
>>> "cons" function for constructing lists be feasible to add to the
>>> OpenSCAD language?
>>>
>>> Cheers,
>>> Hans
>>>
>>> _______________________________________________
>>> 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
>>

_______________________________________________
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



_______________________________________________
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



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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
I think I posted this on the mailing list a while ago, but I do have a
specific menger sponge implementation that can do n=4 in a somewhat
reasonable time, and technically will do up to n=5 if you have the RAM
and a couple days patience.
https://www.thingiverse.com/thing:2424565

Note: the diagonally rotated models on that thingiverse page have
weird artifacts that I never figured out:
https://github.com/openscad/openscad/issues/2067
But the models in standard orientation are fine.

On Fri, Feb 16, 2018 at 12:57 PM, doug moen <[hidden email]> wrote:

> Libfive is just a continuation of the Ao project. Menger sponge is a common
> IFS fractal demo.
> https://en.wikipedia.org/wiki/Menger_sponge
>
> An order 0 Menger sponge is just a cube. An order N sponge contains 20^n
> subcubes. So an interesting test of a 3D modelling program is, how large a
> value of N can you use before the sponge fails to render?
>
> It should be possible to 3D print an order 4 sponge. If the subcubes are 1mm
> wide, then the entire cube is 3^4 == 81mm wide.
>
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due to
> slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which is
> a lot of triangles.
>
> In Libfive, studio/examples/menger.io is an order 3 sponge. For some reason,
> it goes haywire if you try to make an order 4 sponge. Libfive renders shapes
> on the screen as triangle meshes, so I don't expect it to work with large
> order Menger sponges.
>
> In Curv, "examples/menger.curv" is an order 4 sponge, and it renders at 60
> FPS on my GPU. If I crank N up to 20, it still renders at 15 FPS. It fails
> to compile at N=50.
>
>
> On 15 February 2018 at 23:40, David Coneff <[hidden email]> wrote:
>>
>> I may have been confusing it with Keeter's Ao project
>> http://www.mattkeeter.com/blog/2016-03-20-affine/
>>
>> He used a similar sample image with the libfive project of a menger
>> sponge.
>> The affine-transformations page about Ao was mentioning decreased tree
>> depth when doing recursive transformations on nested trees, e.g.,
>> successively smaller, rotated boxes stacked on one another.
>> To be honest it's a bit above my head, the guy looks like a genius. His
>> previous work with Antimony looked great, I wish OpenSCAD had that sort of
>> functionality - most of the modelling I desire to do with it is basically
>> successive parameterization of smaller and smaller parts of a larger whole,
>> and Antimony has a GUI that makes that easy to track. Really need to get an
>> Ubuntu setup going so I can use his software someday!
>>
>> On Thu, Feb 15, 2018 at 7:52 PM, doug moen <[hidden email]> wrote:
>>>
>>> Libfive studio is great, but I don't think it's good for rendering
>>> L-systems.
>>>
>>> L-systems and IFS (Iterated Function Systems) are two ways to represent
>>> fractals. Some fractals, like Hans' dragon curve, can be represented using
>>> either system. F-Rep works well for IFS fractals. But I don't see how F-Rep
>>> can work efficiently for large L-system fractals.
>>>
>>> You could do a dragon curve in Libfive using the IFS representation. But
>>> then you encounter another issue, which is that the libfive rendering
>>> algorithm (for rendering the shape onto the display) doesn't render fine
>>> details. In fact, it renders the shape to a mesh before displaying it. This
>>> means you can't do deep zooms into a deeply iterated IFS fractal.
>>>
>>> Curv can perform these deep zooms, at interactive frame rates, at least
>>> for IFS fractals, because it uses a combination of sphere tracing and GPU
>>> rendering. Sphere tracing is best for fractals, but libfive uses a different
>>> rendering algorithm.
>>>
>>> But if you want a good tool for exploring L-systems, try
>>> https://www.contextfreeart.org/
>>>
>>>
>>> On Thursday, 15 February 2018, David Coneff <[hidden email]>
>>> wrote:
>>>>
>>>> Trying to do fractals or nested objects like this seems to be like using
>>>> a hammer (OpenSCAD) to try and turn a screw. There are simply better tools
>>>> out there for it now that will be more computationally efficient by using
>>>> f-rep as the basis of the geometric representation.
>>>>
>>>> Matt Keeter's libfive / Studio project would probably do this much
>>>> better, but I don't have an Ubuntu/OS-X install running at the moment and
>>>> there is no pre-compiled build of it for Win10.
>>>> https://libfive.com/studio/
>>>>
>>>> The Studio GUI app was developed to work very similarly to OpenSCAD with
>>>> a much more efficient underlying engine as well as GUI interaction with
>>>> shape parameters that back-propagate to the code. I believe this is an
>>>> eventual goal of OpenSCAD as well but the CGAL engine that OpenSCAD uses is
>>>> just inherently a lot slower.
>>>>
>>>> On Thu, Feb 15, 2018 at 3:01 PM, Ronaldo Persiano
>>>> <[hidden email]> wrote:
>>>>>
>>>>> Take a look at the CSG tree of your recursion code.
>>>>>
>>>>> Em 15 de fev de 2018 18:27, "Hans L" <[hidden email]> escreveu:
>>>>>>
>>>>>> After looking at it again, the slowness of the above recursion seems
>>>>>> to come from insane memory usage of dozens of gigabytes and hitting my
>>>>>> swap incredibly hard.
>>>>>> How is it even possible to require that much memory for the simplest
>>>>>> task?  Something seems terribly wrong here.
>>>>>> I had to set up a 256GB NVMe swap partition to allow me to test some
>>>>>> of this madness.
>>>>>>
>>>>>> On Thu, Feb 15, 2018 at 1:58 PM, Hans L <[hidden email]> wrote:
>>>>>> > Doug,
>>>>>> >
>>>>>> > Is there any possible way to then flatten that list in O(n) time?
>>>>>> >
>>>>>> > I think the issue with that is then you need to eventually process
>>>>>> > that LIsp style list in a module to get any geometry output, and
>>>>>> > modules handle recursion incredibly poorly.  There is an absolute
>>>>>> > module recursion limit of i think 10,000, but getting anywhere close
>>>>>> > to that would take  prohibitively long to process.  Here is a very
>>>>>> > simplified example of module recursion:
>>>>>> > module recur(i) {
>>>>>> >   if (i % 100 == 0) echo(i);
>>>>>> >   if (i > 0) {
>>>>>> >     recur(i-1);
>>>>>> >   }
>>>>>> > }
>>>>>> > recur(1000);
>>>>>> > // Total rendering time: 0 hours, 0 minutes, 21 seconds
>>>>>> >
>>>>>> > // recur(2000);
>>>>>> > // Total rendering time: 0 hours, 6 minutes, 10 seconds !!!!!
>>>>>> >
>>>>>> > Is this slow because its doing 2000 implicit unions on null
>>>>>> > geometries or what?
>>>>>> >
>>>>>> > On Thu, Feb 15, 2018 at 12:58 PM, doug moen <[hidden email]> wrote:
>>>>>> >> You could implement Lisp style lists directly.
>>>>>> >>
>>>>>> >> function cons(a,b)=[a,b];
>>>>>> >> function car(a)=a[0];
>>>>>> >> function cdr(a)=a[1];
>>>>>> >> nil=[];
>>>>>> >>
>>>>>> >> Then a list like [1,2,3] would be encoded as
>>>>>> >> cons(1,cons(2,cons(3,nil))) or
>>>>>> >> [1,[2,[3,[]]]].
>>>>>> >>
>>>>>> >> Now concatenation-to-the-front is O(1) but indexing is O(N), just
>>>>>> >> like in
>>>>>> >> Lisp.
>>>>>> >>
>>>>>> >> On Thursday, 15 February 2018, Hans L <[hidden email]> wrote:
>>>>>> >>>
>>>>>> >>> Howdy folks,
>>>>>> >>>
>>>>>> >>> I wanted to share this experiment I've created which implements
>>>>>> >>> some
>>>>>> >>> L-systems( https://en.wikipedia.org/wiki/L-system ) in OpenSCAD.
>>>>>> >>>
>>>>>> >>> The script is here:
>>>>>> >>> https://gist.github.com/thehans/a1494db8046a58832e2ebb10a5908a66
>>>>>> >>>
>>>>>> >>> There is documentation at the top of the script which explains a
>>>>>> >>> little more about what its doing, so I won't repeat all that here.
>>>>>> >>> It can be used to generate various 2D fractal designs, of which
>>>>>> >>> I've
>>>>>> >>> implemented about a dozen.
>>>>>> >>> Just uncomment the one you want to view, tweak the n value for
>>>>>> >>> number
>>>>>> >>> of iterations if you like, etc.
>>>>>> >>>
>>>>>> >>> I created this just to play with some ideas and don't have a
>>>>>> >>> specific
>>>>>> >>> 3D printable object that I plan to create with it, but it could be
>>>>>> >>> interesting to incorporate into some designs(e.g. emboss a fractal
>>>>>> >>> deisgn on a flat box lid or something).
>>>>>> >>>
>>>>>> >>> It also could be potentially extended to support 3D systems with a
>>>>>> >>> few
>>>>>> >>> more commands(basically positive and negative turn command for
>>>>>> >>> pitch/roll/yaw) but I haven't attempted that yet.
>>>>>> >>>
>>>>>> >>> The most important takeaway I got from this for me is that
>>>>>> >>> recursively
>>>>>> >>> building lists is incredibly inefficient in OpenSCAD, because
>>>>>> >>> concat
>>>>>> >>> takes O(n) time, and doing that for every element makes it take
>>>>>> >>> O(n^2).
>>>>>> >>>
>>>>>> >>> Any ideas on tweaks to the script or improvements to the language
>>>>>> >>> that
>>>>>> >>> could be done to help with this issue?  Would something like a
>>>>>> >>> O(1)
>>>>>> >>> "cons" function for constructing lists be feasible to add to the
>>>>>> >>> OpenSCAD language?
>>>>>> >>>
>>>>>> >>> Cheers,
>>>>>> >>> Hans
>>>>>> >>>
>>>>>> >>> _______________________________________________
>>>>>> >>> 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
>>>>>> >>
>>>>>>
>>>>>> _______________________________________________
>>>>>> 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
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> 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
>>
>
>
> _______________________________________________
> 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: L-systems demo. Fractal designs, interpreter performance stress testing

NateTG
In reply to this post by doug.moen
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due
to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which
is a lot of triangles.

Did you try the old example?

https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad



--
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: L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
Hans: Thanks, that's nice code.

NateTG: Yes, it was the example that I tried, a few years back.

On 16 February 2018 at 14:48, NateTG <[hidden email]> wrote:
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due
to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which
is a lot of triangles.

Did you try the old example?

https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad



--
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: L-systems demo. Fractal designs, interpreter performance stress testing

davidconeff
Curv looks quite interesting
https://github.com/doug-moen/curv

From the history/rationale section, looks like you have tried to fill a gap I was feeling very sorely last year when I got started on the 3D modelling/printing. The first model I wanted to re-create was a klein bottle that I found on thingiverse, however it's non-trivial to make a wire-frame of one, and the shape is easily defined as an f-rep but not easily translated into even a continuous-surface model from OpenSCAD primitives. I ended up giving up and trying some other stuff. I imagine curv would be able to do it nearly instantly if I plugged in the right equation - really glad you focused on GPU rendering vs. multi-threaded CPU. It's been my feeling that this type of code is what we really need to be using for scientific visualization as well since the inherent resolution of any data is preserved rather than obscured by rasterization processes - being able to deep-zoom is a big deal. Guess I'll be getting Ubuntu going soon so I can try this out rather than prioritizing Keeter's stuff. From the sound of it, would be much more of a pain in the ass to get his installed if it's requiring the latest ubuntu releases and unusual library packages. I'm not enough of a linux/low-level programmer guy to navigate all the errors that happen trying to get that stuff working. Hopefully your build instructions work for me! Looks short and sweet.



On Fri, Feb 16, 2018 at 1:21 PM, doug moen <[hidden email]> wrote:
Hans: Thanks, that's nice code.

NateTG: Yes, it was the example that I tried, a few years back.

On 16 February 2018 at 14:48, NateTG <[hidden email]> wrote:
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due
to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which
is a lot of triangles.

Did you try the old example?

https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad



--
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



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

Re: L-systems demo. Fractal designs, interpreter performance stress testing

thehans
This thread is kinda all over the place, haha, but back on the topic
of libfive: I just succeeded in building it, and created a PR to add
some more helpful instructions for Ubuntu users.

I hadn't used the "Qt Online Installer" before but its pretty
straightforward wizard style and I didn't have to actually build all
of Qt from source thankfully.

Also the first build I tried for guile took quite a while but I was
naively doing it from a clone of the git repo.  I got some help in
freenode #guile irc where they informed me that building from the
tar.gz files is much faster(a few minutes instead of hour+) due it
having some of the "bootstrap" steps prebuilt in the archive.

The entire process from start to finish isn't that bad now that I've
figured out the proper steps.


On Fri, Feb 16, 2018 at 3:07 PM, David Coneff <[hidden email]> wrote:

> Curv looks quite interesting
> https://github.com/doug-moen/curv
>
> From the history/rationale section, looks like you have tried to fill a gap
> I was feeling very sorely last year when I got started on the 3D
> modelling/printing. The first model I wanted to re-create was a klein bottle
> that I found on thingiverse, however it's non-trivial to make a wire-frame
> of one, and the shape is easily defined as an f-rep but not easily
> translated into even a continuous-surface model from OpenSCAD primitives. I
> ended up giving up and trying some other stuff. I imagine curv would be able
> to do it nearly instantly if I plugged in the right equation - really glad
> you focused on GPU rendering vs. multi-threaded CPU. It's been my feeling
> that this type of code is what we really need to be using for scientific
> visualization as well since the inherent resolution of any data is preserved
> rather than obscured by rasterization processes - being able to deep-zoom is
> a big deal. Guess I'll be getting Ubuntu going soon so I can try this out
> rather than prioritizing Keeter's stuff. From the sound of it, would be much
> more of a pain in the ass to get his installed if it's requiring the latest
> ubuntu releases and unusual library packages. I'm not enough of a
> linux/low-level programmer guy to navigate all the errors that happen trying
> to get that stuff working. Hopefully your build instructions work for me!
> Looks short and sweet.
>
>
>
> On Fri, Feb 16, 2018 at 1:21 PM, doug moen <[hidden email]> wrote:
>>
>> Hans: Thanks, that's nice code.
>>
>> NateTG: Yes, it was the example that I tried, a few years back.
>>
>> On 16 February 2018 at 14:48, NateTG <[hidden email]>
>> wrote:
>>>
>>> > In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3,
>>> > due
>>> to slowness of CSG operations. An order 4 sponge has 160,000 subcubes,
>>> which
>>> is a lot of triangles.
>>>
>>> Did you try the old example?
>>>
>>>
>>> https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad
>>>
>>>
>>>
>>> --
>>> 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
>>
>
>
> _______________________________________________
> 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: L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
In reply to this post by davidconeff
It was a pain to get libfive running on Ubuntu 16.04, because I couldn't use Ubuntu packages for Qt. Maybe Hans' new docs would have helped.

It doesn't seem likely that libfive will get ported to Windows any time soon. The C++ library has been ported, but studio won't run because there are serious problems in porting Guile to Windows.

On 16 February 2018 at 16:07, David Coneff <[hidden email]> wrote:
Curv looks quite interesting
https://github.com/doug-moen/curv

From the history/rationale section, looks like you have tried to fill a gap I was feeling very sorely last year when I got started on the 3D modelling/printing. The first model I wanted to re-create was a klein bottle that I found on thingiverse, however it's non-trivial to make a wire-frame of one, and the shape is easily defined as an f-rep but not easily translated into even a continuous-surface model from OpenSCAD primitives. I ended up giving up and trying some other stuff. I imagine curv would be able to do it nearly instantly if I plugged in the right equation - really glad you focused on GPU rendering vs. multi-threaded CPU. It's been my feeling that this type of code is what we really need to be using for scientific visualization as well since the inherent resolution of any data is preserved rather than obscured by rasterization processes - being able to deep-zoom is a big deal. Guess I'll be getting Ubuntu going soon so I can try this out rather than prioritizing Keeter's stuff. From the sound of it, would be much more of a pain in the ass to get his installed if it's requiring the latest ubuntu releases and unusual library packages. I'm not enough of a linux/low-level programmer guy to navigate all the errors that happen trying to get that stuff working. Hopefully your build instructions work for me! Looks short and sweet.



On Fri, Feb 16, 2018 at 1:21 PM, doug moen <[hidden email]> wrote:
Hans: Thanks, that's nice code.

NateTG: Yes, it was the example that I tried, a few years back.

On 16 February 2018 at 14:48, NateTG <[hidden email]> wrote:
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due
to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which
is a lot of triangles.

Did you try the old example?

https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad



--
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



_______________________________________________
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: L-systems demo. Fractal designs, interpreter performance stress testing

doug.moen
In reply to this post by davidconeff
David Coneff said: "a klein bottle ... is easily defined as an f-rep ... I imagine curv would be able to do it nearly instantly if I plugged in the right equation"

Unfortunately, you can't plug an arbitrary distance function into an F-Rep system and expect it to work. Different F-Rep systems place different restrictions on the structure of a distance field in order to make rendering possible. Curv and Libfive have different restrictions, which makes them good for different classes of distance functions.

Curv is good for deep zooms into fractals, but not good for algebraic surfaces like the Klein bottle immersion into R^3.

Libfive is good for algebraic surfaces (the klein bottle "just works"), but bad for fractals (the Menger sponge demo in libfive fails to render for order 4 and greater).

In either system, it's possible to modify a bad distance field to make it renderable, but this has multiple levels  of difficulty. I managed to get Menger 4 and 5 to work in Libfive (it gets exponentially slower as the order increases). So far, I only have an approximate solution to the Klein bottle in Curv.

In the case of libfive, the menger sponge demo uses high level CSG operations, but still fails to render. In Curv, with the Klein bottle example, you are defining a new distance field from scratch using math, which intrinsically requires a higher level of skill than just plugging CSG operations together. A well designed F-Rep system will provide a set of basic CSG operations and primitives that are guaranteed to produce good distance functions: this is something that is available in Curv, but not possible in Libfive.


On 16 February 2018 at 16:07, David Coneff <[hidden email]> wrote:
Curv looks quite interesting
https://github.com/doug-moen/curv

From the history/rationale section, looks like you have tried to fill a gap I was feeling very sorely last year when I got started on the 3D modelling/printing. The first model I wanted to re-create was a klein bottle that I found on thingiverse, however it's non-trivial to make a wire-frame of one, and the shape is easily defined as an f-rep but not easily translated into even a continuous-surface model from OpenSCAD primitives. I ended up giving up and trying some other stuff. I imagine curv would be able to do it nearly instantly if I plugged in the right equation - really glad you focused on GPU rendering vs. multi-threaded CPU. It's been my feeling that this type of code is what we really need to be using for scientific visualization as well since the inherent resolution of any data is preserved rather than obscured by rasterization processes - being able to deep-zoom is a big deal. Guess I'll be getting Ubuntu going soon so I can try this out rather than prioritizing Keeter's stuff. From the sound of it, would be much more of a pain in the ass to get his installed if it's requiring the latest ubuntu releases and unusual library packages. I'm not enough of a linux/low-level programmer guy to navigate all the errors that happen trying to get that stuff working. Hopefully your build instructions work for me! Looks short and sweet.



On Fri, Feb 16, 2018 at 1:21 PM, doug moen <[hidden email]> wrote:
Hans: Thanks, that's nice code.

NateTG: Yes, it was the example that I tried, a few years back.

On 16 February 2018 at 14:48, NateTG <[hidden email]> wrote:
> In OpenSCAD, I didn't succeed in rendering a sponge greater than N=3, due
to slowness of CSG operations. An order 4 sponge has 160,000 subcubes, which
is a lot of triangles.

Did you try the old example?

https://github.com/openscad/openscad/blob/4a0ac7b2fa6e8ca390e3b95e1c2d2541cf9d77af/examples/Old/example024.scad



--
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



_______________________________________________
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
12