# Barnsley Fern recursive

22 messages
12
Open this post in threaded view
|

## Barnsley Fern recursive

 It's probably a crazy idea but I've created a simple script for the Barnsley Fern fractal. The script works but it brings my PC, an 2011 iMac, to it's knees (OpenSCAD takes over 10Gb of memory with the script below and I want to increase the number of objects even further). I was wondering if someone has any suggestions to improve/optimize the script and make it less memory hungry. Or is OpenSCAD not suitable for this kind of work. Thanks. m1 = [[0,0],[0,0.16]]; c1 = [0,0]; m2 = [[0.85,0.04],[-0.04,0.85]]; c2 = [0, 0.16]; m3 = [[0.2,-0.26],[0.23,0.22]]; c3 = [0,1.6]; m4 = [[-0.15,0.28],[0.26,0.24]]; c4 = [0,0.44]; function f1(p) = m1 * p + c1; function f2(p) = m2 * p + c2; function f3(p) = m3 * p + c3; function f4(p) = m4 * p + c4; module plotCircle(p) {     translate(100 * p) circle(r=0.5,\$fn=50); } module BarnsleyFern(p,index) {     r = rands(0,1,1)[0];     plotCircle(p);     if (r <= 0.01) {         BarnsleyFern(f1(p), index-1);     }     else if (r > 0.01 && r <=0.86) {         BarnsleyFern(f2(p),index-1);     }     else if (r > 0.86 && r <=0.94) {         BarnsleyFern(f3(p),index-1);     }     else if (r > 0.94 && r < 0.99) {     BarnsleyFern(f4(p),index-1);     } } p = [0,0]; BarnsleyFern(p,20000); -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 If you are just drawing, consider using a different tool, such as processing.org It avoids the extra effort of maintaining an ‘object’. If you want an object, then I would generally look to do the numerical processing elsewhere and import the shapes for rendering. Others may have better ideas. Colin --------------------------------- Colin Smart (07968 049660) > On 11 Sep 2018, at 21:06, Eric Buijs <[hidden email]> wrote: > > It's probably a crazy idea but I've created a simple script for the Barnsley > Fern fractal. The script works but it brings my PC, an 2011 iMac, to it's > knees (OpenSCAD takes over 10Gb of memory with the script below and I want > to increase the number of objects even further). I was wondering if someone > has any suggestions to improve/optimize the script and make it less memory > hungry. Or is OpenSCAD not suitable for this kind of work. Thanks. > > m1 = [[0,0],[0,0.16]]; > > c1 = [0,0]; > > m2 = [[0.85,0.04],[-0.04,0.85]]; > > c2 = [0, 0.16]; > > m3 = [[0.2,-0.26],[0.23,0.22]]; > > c3 = [0,1.6]; > > m4 = [[-0.15,0.28],[0.26,0.24]]; > > c4 = [0,0.44]; > > function f1(p) = m1 * p + c1; > > function f2(p) = m2 * p + c2; > > function f3(p) = m3 * p + c3; > > function f4(p) = m4 * p + c4; > > module plotCircle(p) { >    translate(100 * p) circle(r=0.5,\$fn=50); > } > > module BarnsleyFern(p,index) { >    r = rands(0,1,1)[0]; >    plotCircle(p); >    if (r <= 0.01) { >        BarnsleyFern(f1(p), index-1); >    } >    else if (r > 0.01 && r <=0.86) { >        BarnsleyFern(f2(p),index-1); >    } >    else if (r > 0.86 && r <=0.94) { >        BarnsleyFern(f3(p),index-1); >    } >    else if (r > 0.94 && r < 0.99) { >    BarnsleyFern(f4(p),index-1); >    } > } > > > p = [0,0]; > BarnsleyFern(p,20000); > > > > > > > > -- > 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
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 In reply to this post by Eric Buijs That exact script takes less than a second for me and memory does not grow over 350MB when running multiple times (using the latest nightly build on Linux). ciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 yet another good reason for a binary somewhere - even if its not a release... I'm on Windows. On 9/12/2018 9:11 AM, Torsten Paul wrote: > That exact script takes less than a second for me and memory does > not grow over 350MB when running multiple times (using the latest > nightly build on Linux). > > ciao, >   Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 On 09/11/2018 11:18 PM, Mark Schafer wrote: > yet another good reason for a binary somewhere - even if > its not a release... I'm on Windows. > What's wrong with the one from the official download page? http://www.openscad.org/downloads.html#snapshotsciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 This post was updated on . In reply to this post by tp3 Thanks Thorsten, I will try the latest development snapshot and will let you know the result. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list Discuss@lists.openscad.org http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

Open this post in threaded view
|

## Re: Barnsley Fern recursive

 In reply to this post by tp3 You're right Torsten, I've tried the latest experimental build for OSX and it makes a huge difference in memory. I've updated the code because I hadn't been very thoughtful about the base case (see below for updated code). One more thing. The recursive loop refuses to go beyond 1300 (or so). After that I get the message: ERROR: Recursion detected calling module 'BarnsleyFern' Any thoughts on that. Thanks guys. m1 = [[0,0],[0,0.16]]; c1 = [0,0]; m2 = [[0.85,0.04],[-0.04,0.85]]; c2 = [0, 0.16]; m3 = [[0.2,-0.26],[0.23,0.22]]; c3 = [0,1.6]; m4 = [[-0.15,0.28],[0.26,0.24]]; c4 = [0,0.44]; function f1(p) = m1 * p + c1; function f2(p) = m2 * p + c2; function f3(p) = m3 * p + c3; function f4(p) = m4 * p + c4; module plotCircle(p) {     translate(100 * p) circle(r=0.5,\$fn=50); } module BarnsleyFern(p,index) {     r = rands(0,1,1)[0];     plotCircle(p);     //echo(r,index);     if (r <= 0.01) {         BarnsleyFern(f1(p), index-1);     }     else if (r > 0.01 && r <=0.86) {         BarnsleyFern(f2(p),index-1);     }     else if (r > 0.86 && r <=0.94) {         BarnsleyFern(f3(p),index-1);     }     else if (index > 0) {         BarnsleyFern(f4(p),index-1);     } } p = [0,0]; BarnsleyFern(p,1400);   -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 This post was updated on . In reply to this post by Oakapple Colin, thanks for your reply. I use P5.js (which is similar to Processing but uses Javascript instead of Java) from time to time. However I like to 'torture' OpenSCAD to see where it's limits are ;-) -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list Discuss@lists.openscad.org http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 In reply to this post by Eric Buijs On 09/12/2018 11:20 AM, Eric Buijs wrote: > One more thing. The recursive loop refuses to go beyond 1300 > (or so). After that I get the message: ERROR: Recursion detected > calling module 'BarnsleyFern' Any thoughts on that. Thanks guys. > That means it's running out of stack space, while not perfect, it's trying to catch this issue before it just crashes. I'm not sure if MacOS allows for changing the stack size available to applications, but if it does, OpenSCAD tries to pick up that limit. Something to try would be running from a terminal window:  > ulimit -s 65532  > /Applications/OpenSCAD.app/Contents/MacOS/OpenSCAD ciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 Thanks again but unfortunately I'm not able to increase the recursive loop with this (on OSX). -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 In reply to this post by Eric Buijs Eric, The probabilities in your code does not agree with the definition found in Wikipedia  . Besides, a full recursion stop rule is missing in the recursive module so regardless the memory allocation size you will always get a stack overflow with probability one. Anyway, as this fractal may be generated without recursion that would be a preferable path to go. Finally, you would need a very large number of circles to get a reasonable picture of the fractal and this may surpass the limits of the OpenSCAD node tree. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 Ronaldo said: " Anyway, as this fractal may be generated without recursion that wouldbe a preferable path to go."Yes, but how do you code it without recursion in OpenSCAD?The Barnsley Fern is an Iterated Function System, where the result at iteration i+1depends on the result of iteration i.The only language feature that supports this kind of iteration, without using recursion,is the C-style for loop, which is only available in list comprehensions, not in modules.For this, you need a development snapshot with the "C-style for" option enabledin Preferences.So, I would try generating all of the coordinates into a list, using a C-style for loopinside a list comprehension. And I'd use a simpler polygon for each point, to furtherreduce resource consumption: like a triangle, square, or hexagon.On 12 September 2018 at 11:42, Ronaldo wrote:Eric, The probabilities in your code does not agree with the definition found in Wikipedia   . Besides, a full recursion stop rule is missing in the recursive module so regardless the memory allocation size you will always get a stack overflow with probability one. Anyway, as this fractal may be generated without recursion that would be a preferable path to go. Finally, you would need a very large number of circles to get a reasonable picture of the fractal and this may surpass the limits of the OpenSCAD node tree. -- 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
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 doug.moen wrote > The only language feature that supports this kind of iteration, without > using recursion, > is the C-style for loop, which is only available in list comprehensions, > not in modules. > For this, you need a development snapshot with the "C-style for" option > enabled > in Preferences. You are right, Doug, and the following code takes that path. The nested for in the module BarnsleyFern was needed to circumvent the OpenSCAD for limit of at most 9999 elements. Anyway, this code is valid to at most 9999x9999 iterations. m1 = [[0,0],[0,0.16]]; c1 = [0,0]; m2 = [[0.85,0.04],[-0.04,0.85]]; c2 = [0, 1.6]; m3 = [[0.2,-0.26],[0.23,0.22]]; c3 = [0, 1.6]; m4 = [[-0.15,0.28],[0.26,0.24]]; c4 = [0, 0.44]; function f1(p) = m1 * p + c1; function f2(p) = m2 * p + c2; function f3(p) = m3 * p + c3; function f4(p) = m4 * p + c4; module dot(p) translate(100 * p) square(); module BarnsleyFern(index) {   q = BarnsleyFern([0,0],index);   echo(len=len(q));   for(i=[0:9999:len(q)-1]) {     r = len(q)-i;     for(j=[0:min(r,9999)-1])       dot(q[i+j]);   } }   function BarnsleyFern(p,index) =   [ for(i=0, q=p; i 0.01 && r <=0.86?           f2(q) :         r > 0.86 && r <=0.93?           f3(q) :           f4(q) )       q ]; BarnsleyFern(200000); The code generated the following image in 25sec: That is a detail look: -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 Nice work.On 12 September 2018 at 13:54, Ronaldo wrote:doug.moen wrote > The only language feature that supports this kind of iteration, without > using recursion, > is the C-style for loop, which is only available in list comprehensions, > not in modules. > For this, you need a development snapshot with the "C-style for" option > enabled > in Preferences. You are right, Doug, and the following code takes that path. The nested for in the module BarnsleyFern was needed to circumvent the OpenSCAD for limit of at most 9999 elements. Anyway, this code is valid to at most 9999x9999 iterations. m1 = [[0,0],[0,0.16]]; c1 = [0,0]; m2 = [[0.85,0.04],[-0.04,0.85]]; c2 = [0, 1.6]; m3 = [[0.2,-0.26],[0.23,0.22]]; c3 = [0, 1.6]; m4 = [[-0.15,0.28],[0.26,0.24]]; c4 = [0, 0.44]; function f1(p) = m1 * p + c1; function f2(p) = m2 * p + c2; function f3(p) = m3 * p + c3; function f4(p) = m4 * p + c4; module dot(p) translate(100 * p) square(); module BarnsleyFern(index) {   q = BarnsleyFern([0,0],index);   echo(len=len(q));   for(i=[0:9999:len(q)-1]) {     r = len(q)-i;     for(j=[0:min(r,9999)-1])       dot(q[i+j]);   } } function BarnsleyFern(p,index) =   [ for(i=0, q=p; i 0.01 && r <=0.86?           f2(q) :         r > 0.86 && r <=0.93?           f3(q) :           f4(q) )       q ]; BarnsleyFern(200000); The code generated the following image in 25sec: That is a detail look: -- 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
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 In reply to this post by Ronaldo Ronaldo, first I take my hat of for that code. It works perfectly (once I translated the < to smaller than, <). I wasn't even aware of the C-style for option in OpenSCAD and therefore discarded the possibility to use iteration. The Barnsley Fern looks pretty neat taking only 1 minute and 18 seconds on my old computer. Thank you all guys. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 The C-style for loop available for list comprehension is not the only way to address the Barnsley Fern fractal drawing because its building process is tail recursive. As OpenSCAD is able to eliminate recursion of some forms of tail recursive functions (not modules), it is in principle possible to have an iteration written in a recursive way. Find bellow an alternative recursion to the function and module defined in my previous post. module BarnsleyFern(index) {   q = BarnsleyFern(index);   for(i=[0:9999:len(q)-1]) {     r = len(q)-i;     for(j=[0:min(r,9999)-1])       dot(q[i+j]);   } }   function nextP(p) =   let(r =  rands(0,1,1)[0])   r <= 0.01 ?     f1(p) :   r > 0.01 && r <=0.86?     f2(p) :   r > 0.86 && r <=0.93?     f3(p) :     f4(p) ; function BarnsleyFern(index, bag=[[0,0]]) =   index==0 ?     bag :     BarnsleyFern(index-1, concat( [nextP(bag[0])], bag )); Although exploring the tail recursion elimination in an elegant solution, this approach is not so efficient as the previous one. My previous code have a linear behavior: the running time is approximately proportional to the parameter index (O(n)). For my surprise, although the above code run as an iteration, its running time is O(n2). A closer look solves the apparent mystery: the main operation in the function BarnsleyFern is a concat of a single element list with a growing list (bag); possibly concat operates by rewriting the output list from the input lists so the total number of operations of all concats is O(n2). This approach would benefit from a better implementation of concat. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 Ronaldo, a nice comparison of iterative vs tail recursive. The latter took almost half an hour to finish on my PC, indeed not so efficient. Thanks. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Barnsley Fern recursive

 On 09/13/2018 03:14 PM, Eric Buijs wrote: > Ronaldo, a nice comparison of iterative vs tail recursive. The latter took > almost half an hour to finish on my PC, indeed not so efficient. Thanks. > That is not the fault of the tail recursion elimination. This part is pretty much the same as a normal loop. As Ronaldo mentioned the slowness comes from the part where it generates the data by copying everything for each iteration. ciao,    Torsten. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org -- Torsten