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

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/

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 <thehans@gmail.com> 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

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 <doug@moens.org> 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 <thehans@gmail.com> 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 >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>

Take a look at the CSG tree of your recursion code. Em 15 de fev de 2018 18:27, "Hans L" <thehans@gmail.com> 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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 > >>> Discuss@lists.openscad.org > >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >> > >> > >> _______________________________________________ > >> OpenSCAD mailing list > >> Discuss@lists.openscad.org > >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

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 <rcmpersiano@gmail.com> wrote: > Take a look at the CSG tree of your recursion code. > > Em 15 de fev de 2018 18:27, "Hans L" <thehans@gmail.com> 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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 >> >>> Discuss@lists.openscad.org >> >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> >> >> >> _______________________________________________ >> >> OpenSCAD mailing list >> >> Discuss@lists.openscad.org >> >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >

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 <rcmpersiano@gmail.com> wrote: > Take a look at the CSG tree of your recursion code. > > Em 15 de fev de 2018 18:27, "Hans L" <thehans@gmail.com> 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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 >> >>> Discuss@lists.openscad.org >> >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> >> >> >> _______________________________________________ >> >> OpenSCAD mailing list >> >> Discuss@lists.openscad.org >> >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

> 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 <thehans@gmail.com> 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 <rcmpersiano@gmail.com> wrote: >> Take a look at the CSG tree of your recursion code. >> >> Em 15 de fev de 2018 18:27, "Hans L" <thehans@gmail.com> 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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 >>> >>> Discuss@lists.openscad.org >>> >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >> >>> >> >>> >> _______________________________________________ >>> >> OpenSCAD mailing list >>> >> Discuss@lists.openscad.org >>> >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >> >>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>

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 <david.coneff@gmail.com> 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 <rcmpersiano@gmail.com> > wrote: >> >> Take a look at the CSG tree of your recursion code. >> >> Em 15 de fev de 2018 18:27, "Hans L" <thehans@gmail.com> 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 <thehans@gmail.com> 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 <doug@moens.org> 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 <thehans@gmail.com> 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 >>> >>> Discuss@lists.openscad.org >>> >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >> >>> >> >>> >> _______________________________________________ >>> >> OpenSCAD mailing list >>> >> Discuss@lists.openscad.org >>> >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >> >>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >