[OpenSCAD] Barnsley Fern recursive

Ronaldo rcmpersiano at gmail.com
Wed Sep 12 19:56:00 EDT 2018


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/



More information about the Discuss mailing list