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/
Eric,
The probabilities in your code does not agree with the definition found in
Wikipedia https://en.wikipedia.org/wiki/Barnsley_fern . 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/
Ronaldo said: " Anyway, as this fractal may be generated without recursion
that would
be 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+1
depends 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
enabled
in Preferences.
So, I would try generating all of the coordinates into a list, using a
C-style for loop
inside a list comprehension. And I'd use a simpler polygon for each point,
to further
reduce resource consumption: like a triangle, square, or hexagon.
On 12 September 2018 at 11:42, Ronaldo rcmpersiano@gmail.com wrote:
Eric,
The probabilities in your code does not agree with the definition found in
Wikipedia https://en.wikipedia.org/wiki/Barnsley_fern . 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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<index; i=i+1,
r = rands(0,1,1)[0],
q =
r <= 0.01 ?
f1(q) :
r > 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:
http://forum.openscad.org/file/t1275/BarnsleyFern_200000.png
That is a detail look:
http://forum.openscad.org/file/t1275/BarnsleyFern_200000_detail.png
--
Sent from: http://forum.openscad.org/
Nice work.
On 12 September 2018 at 13:54, Ronaldo rcmpersiano@gmail.com 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<index; i=i+1,
r = rands(0,1,1)[0],
q =
r <= 0.01 ?
f1(q) :
r > 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:
http://forum.openscad.org/file/t1275/BarnsleyFern_200000.png
That is a detail look:
http://forum.openscad.org/file/t1275/BarnsleyFern_200000_detail.png
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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/
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/
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/
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.
Torsten,
I partially disagree. I don't know the intrinsic processes of OpenSCAD but,
from the running times I got, I deduct that the iterative step of
generating one element of a list in the C-style solution is constant time
in contrast with the linear time the *concat *is done in the tail recursion
elimination strategy due to the successive copies. However, I don't see any
way to write a tail recursion solution to generate a list without resorting
to concat. So, tail recursion will be generally less competitive than
iterations for list generations.
Em qui, 13 de set de 2018 às 18:02, Torsten Paul Torsten.Paul@gmx.de
escreveu:
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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org