### Inverse tree generation (escape-time like)

• 33 Replies
• 1115 Views

0 Members and 1 Guest are viewing this topic.

#### msltoe #### Inverse tree generation (escape-time like)

« on: September 30, 2018, 02:43:57 AM »
A few years back I presented a 3d program to generate Romanesco/tree fractals using a generative method, i.e., generate a list of spheres, then render them.

It occurred to me today if it would be possible to generate trees in reverse (kinda like escape-time). Given a pixel, can we determine whether it's in the tree set? True escape-time doesn't quite work, because there's not a one-to-one mapping (usually) between each pixel and where it belongs on the tree. However, if you're willing to stretch the idea of escape-time to more of a recursion, then it looks like it is possible.

Here's the code in Python. C would be much faster, I know. But, I'm getting lazy in my old age.

Code: [Select]
import numpy as npimport matplotlib.pyplot as pltdef tree(x, y, dx, dy, factor0,  c1, s1,iteration, imax):    x = x * factor0    y = y * factor0    factor = 1.04    r2 = x*x + y*y    if (r2 < 0.001):        return True    if (r2 > 2):        return False    if (iteration < imax):        dx1 = dx # (c1*dx - s1*dy)        dy1 = dy #(s1*dx + c1*dy)        flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,                    iteration+1,imax)        if ((not flag) and ((iteration % 10)==9)):             dx1 = (c1*dx - s1*dy)             dy1 = (s1*dx + c1*dy)             factor = 1.45             flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,                         iteration+1,imax)        if ((not flag) and ((iteration % 10)==4)):             s1 = -s1             dx1 = (c1*dx - s1*dy)             dy1 = (s1*dx + c1*dy)             factor = 1.5             flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,                         iteration+1,imax)               return flag    M = 1600N = 1600imax = 200A = np.zeros((M,N))c1 = np.cos(0.6)s1 = np.sin(0.6)for i in range(M):    x = 1.4*(i / M - 0.5)    if (i % 10) == 0: print (i)    for j in range(N):        y = 1.4*(j / N - 0.5)        if tree(x,y-0.65,0,0.05,1.0,c1,s1,0,imax):            A[i,j] = 1            plt.imshow(A.T,cmap='gray')plt.show()

#### msltoe #### Re: Inverse tree generation (escape-time like)

« Reply #1 on: September 30, 2018, 06:07:53 AM »
A fun little variation...

BTW, here's the C code, which is a lot faster...

Code: [Select]
#include <stdio.h>#include <stdlib.h>#include <math.h>unsigned int tree(double x, double y, double dx, double dy,          double factor0,          double c1, double s1,          double c2, double s2,          unsigned int iteration, unsigned int imax){    x = x * factor0;    y = y * factor0;    double factor = 1.01;    double r2 = x*x + y*y;    //if ((fabs(x)<0.03) && (fabs(y)<0.03))    if (r2 < 0.001)     {return 1;}    if (r2 > 2) {return 0;}    if (iteration >= imax) {return 0;}    double dx1 = (c2*dx - s2*dy);    double dy1 = (s2*dx + c2*dy);    unsigned int flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,c2,s2,iteration+1,imax);    if ((!flag) && ((iteration % 17)==16)){       dx1 = (c1*dx - s1*dy);       dy1 = (s1*dx + c1*dy);       s2 = -s2;       factor = 2.0;       flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,c2,s2,                   iteration+1,imax);    }/*    if ((!flag) and ((iteration % 10)==4)){             s1 = -s1;             s2 = -s2;             dx1 = (c1*dx - s1*dy);             dy1 = (s1*dx + c1*dy);             factor = 1.5;             flag = tree(x+dx1,y+dy1,dx1,dy1,factor,c1,s1,c2,s2,                         iteration+1,imax);    }*/    return flag;}int main() {unsigned int M = 3200;unsigned int N = 3200;unsigned int imax = 500;unsigned int *A = (unsigned int *) malloc (M*N*sizeof(unsigned int));double c1,s1,c2,s2;c1 = cos(0.0);s1 = sin(0.0);c2 = cos(0.06);s2 = sin(0.06);for (int i=0;i<M;i++){    double x = 1.3*(i / (double) M - 0.5);    if ((i % 10) == 0) {printf ("%d\n",i);}    for (int j=0;j<N;j++){        double y = 1.3*(j / (double) N - 0.5);        A[i*N+j] = tree(x+0.4,y-0.2,0,0.025,1.0,c1,s1,c2,s2,0,imax);    }}FILE *f1 = fopen("temp.ppm","w");fprintf(f1,"P3\n");fprintf(f1,"#comment\n");fprintf(f1,"%d %d\n",M,N);fprintf(f1,"255\n");for (int j=0;j<M;j++){    for (int i=0;i<N;i++){      int c = A[i*M+j]*255;      fprintf(f1,"%d %d %d ",c,c,c);    }    fprintf(f1,"\n");}}

#### Adam Majewski #### Re: Inverse tree generation (escape-time like)

« Reply #2 on: September 30, 2018, 08:23:37 AM »
Beatiful. Can you post it ( with code ) to commons ?

#### Sabine62 #### Re: Inverse tree generation (escape-time like)

« Reply #3 on: September 30, 2018, 10:24:11 AM »
Beautiful! To thine own self be true

#### mclarekin #### Re: Inverse tree generation (escape-time like)

« Reply #4 on: October 01, 2018, 06:00:46 AM »   #### Alef #### Re: Inverse tree generation (escape-time like)

« Reply #5 on: October 01, 2018, 05:23:55 PM »
Nice one, especialy the second picture. First one is OK, but a bitt plain;) I hadn't looked on algorithms. But if it escape time then it can be made into UF.
« Last Edit: October 01, 2018, 05:54:51 PM by Alef »
catalisator of fractals

#### gerson #### Re: Inverse tree generation (escape-time like)

« Reply #6 on: October 01, 2018, 08:16:22 PM »
I think already saw something similar using context free and janus fractal softwares.

#### hobold #### Re: Inverse tree generation (escape-time like)

« Reply #7 on: October 02, 2018, 11:58:57 AM »
Does this method generalize to 3D trees? Rendering would be inefficient, but possible with something like Syntopia's brute force ray sampler.

#### claude #### Re: Inverse tree generation (escape-time like)

« Reply #8 on: October 02, 2018, 01:21:20 PM »
GLSL disallows recursion, so you would have to implement your own stack using arrays.  I did this once, performance was poor...

#### FractalDave #### Re: Inverse tree generation (escape-time like)

« Reply #9 on: October 02, 2018, 06:10:26 PM »
Related formula for UF:

mmf4.ufm:3D IFS

Essentially everything is there so it can easily be modified to do dragon trees e.g. an old modified personal version (that I can't find at this minute) produced:
http://www.fractalforums.com/index.php?action-gallery;sa=view;id=13260

NB. the UF formula needs mmf4.ucl:3D colouring direct
NB2. You may have to paste that link into a new tab, it doesn't work directly for me while I'm logged in here....
The meaning and purpose of life is to give life purpose and meaning.

#### msltoe #### Re: Inverse tree generation (escape-time like)

« Reply #10 on: October 02, 2018, 06:36:13 PM »
Hobold: I'm pretty sure this can be generalized to 3-D. I once coded up a recursive "escape time" in my never ending quest to find the 3D Mandelbrot, and as you would expect, it was slow.

David: Was your UF script recursive?

Claude: Too bad recursion is not available in GLSL.

The one benefit that I see with this "new" formalism vs. what I did before, is the potential to arbitrarily zoom in, since it's pixel-based.

#### FractalDave #### Re: Inverse tree generation (escape-time like)

« Reply #11 on: October 02, 2018, 07:56:20 PM »
David: Was your UF script recursive?

Yes but I have seen the idea for an algorithm for tree traversal that doesn't require recursion if programmed correctly. it just requires a loop coded to choose the next transform each time round according to the max depth/scaling and the number of transforms involved - however it does need a little info from previous loops but the amount is invariant per iteration for a given fractal.
The drawback is that unlike the version I implemented in UF using recursion which allows early out based on doing things in the correct order, the version without recursion will always have to traverse the entire tree (I think), though I'm not certain as I haven't tried it in practice.

#### FractalDave #### Re: Inverse tree generation (escape-time like)

« Reply #12 on: October 02, 2018, 09:56:15 PM »
Edit: I think my solution below is flawed Actually I just remembered that the technique is a little like the gray code in a very roundabout way For a 2 transform system using transforms 0 and 1 to depth 4, starting with a point to test if on the fractal you can perform the sequence:

000010001100101011011110

Which covers all 16 combinations to 4 depths, i.e. the equivalent of 64 transforms if all done from the top in just 24.
There are drawbacks, the first being to write the algorithm to get the best sequence for a given number of transforms to given depth/s especially if the depth varies from one tree branch to another. In addition because we don't always start at the top the accumulated scaling testing must be adjusted so tests are correct for the position within the tree branch versus the position in the sequence calculated.
I'm assuming it's possible to get a decent generic algorithm for the sequence to calculate for a given fractal such that it's also possible to know what to test and how to adjust the bailout within the sequence calculation loop Just realised how to fix the bailout scaling (I think!) - e.g. in the above for the sequence 1110 the calculated distance to test needs to be divided by the scale (or distance?) prior to 1110 i.e. after 00001000110010101101. These are all preset sequence positions for a given fractal so as long as the code is correct in the loop there shouldn't be a need for recursion/arrays.
NB. Will not work for non-affine IFS !!
« Last Edit: October 02, 2018, 10:46:56 PM by FractalDave »

#### FractalDave #### Re: Inverse tree generation (escape-time like)

« Reply #13 on: October 02, 2018, 10:12:49 PM »
*If* the GLSL frag code has enough space and enough variables then you can avoid the recursion issue by having a loop with counter and explicitly having code for each depth storing stuff to remember for each depth in different explicit variables (if test), of course all depth sections would know the variables from the others - no use of arrays NB. My recursive code for UF essentially only has one-dimensional arrays of max required entries either depth of tree or depth of tree + 1 (I forget).

#### FractalDave #### Re: Inverse tree generation (escape-time like)

« Reply #14 on: October 02, 2018, 11:53:42 PM »
Another possible method is to pre-calculate and store a single combined transform for every tree branch to the required depth/scaling and you then can just use that set of transforms for every point to test i.e. just a straight run through a pre-stored set for each pixel...of course the efficiency/storage of this is very dependent on the number of transforms and depths/scales required but it does simplify the actual per-pixel frag code considerably.
Also the same method can be used in a more restricted manner to limit the maximum transforms to use e.g. expand a 2 transform system into a 64 trasform one by computing all the depth 6 transforms - of course you'd still have a tree to traverse somehow if requiring more than 6 depths...
« Last Edit: October 03, 2018, 12:07:21 AM by FractalDave »

### Similar Topics ###### Escape Time Blur

Started by AlexH on Share a fractal

0 Replies
287 Views August 15, 2018, 05:42:06 AM
by AlexH ###### escape-time fractals (et) - instalation problem
2 Replies
389 Views May 31, 2018, 03:08:41 PM
by Adam Majewski ###### Fourier series in escape time fractals

Started by v on Fractal Mathematics And New Theories

0 Replies
185 Views December 19, 2018, 07:32:09 PM
by v ###### Julia sets: True shape and escape time

Started by marcm200 on Fractal Mathematics And New Theories

18 Replies
561 Views Today at 12:59:36 PM
by claude ###### Modified inertia gravity escape time fractals

Started by daplinster on Fractal Mathematics And New Theories

16 Replies
556 Views February 28, 2019, 02:57:47 PM
by daplinster