Inverse tree generation (escape-time like)

  • 33 Replies
  • 858 Views

0 Members and 1 Guest are viewing this topic.

Offline msltoe

  • *
  • Fractal Fanatic
  • ***
  • Posts: 27
    • My cheesy music
« 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 np
import matplotlib.pyplot as plt

def 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 = 1600
N = 1600
imax = 200
A = 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()

Offline msltoe

  • *
  • Fractal Fanatic
  • ***
  • Posts: 27
    • My cheesy music
« 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");
}
}

Offline Adam Majewski

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

Offline Sabine62

  • *
  • Fractal Frogurt
  • ******
  • Posts: 459
  • It's just a jump to the left...
    • sabine62.deviantart.com
« Reply #3 on: September 30, 2018, 10:24:11 AM »
Beautiful!  :thumbs:
To thine own self be true

Offline mclarekin

  • *
  • Fractal Fluff
  • *****
  • Posts: 378
« Reply #4 on: October 01, 2018, 06:00:46 AM »
 O0 O0 O0

Offline Alef

  • *
  • Fractal Phenom
  • ****
  • Posts: 52
  • catalisator of fractals
    • My deviant art page
« 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

Offline gerson

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

Offline hobold

  • *
  • Fractal Phenom
  • ****
  • Posts: 57
« 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.

Offline claude

  • *
  • 3c
  • ***
  • Posts: 895
    • mathr.co.uk
« 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...

Offline FractalDave

  • *
  • Uploader
  • *
  • Posts: 167
    • Makin Magic Fractals
« 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.

Offline msltoe

  • *
  • Fractal Fanatic
  • ***
  • Posts: 27
    • My cheesy music
« 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.

Offline FractalDave

  • *
  • Uploader
  • *
  • Posts: 167
    • Makin Magic Fractals
« 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.

Offline FractalDave

  • *
  • Uploader
  • *
  • Posts: 167
    • Makin Magic Fractals
« 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 »

Offline FractalDave

  • *
  • Uploader
  • *
  • Posts: 167
    • Makin Magic Fractals
« 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).

Offline FractalDave

  • *
  • Uploader
  • *
  • Posts: 167
    • Makin Magic Fractals
« 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 »


clip
Escape Time Blur

Started by AlexH on Share a fractal

0 Replies
214 Views
Last post August 15, 2018, 05:42:06 AM
by AlexH
clip
Fourier series in escape time fractals

Started by v on Fractal Mathematics And New Theories

0 Replies
107 Views
Last post December 19, 2018, 07:32:09 PM
by v
xx
escape-time fractals (et) - instalation problem

Started by Adam Majewski on Fractal Programs Discussion, Help, & Support

2 Replies
331 Views
Last post May 31, 2018, 03:08:41 PM
by Adam Majewski
xx
Inverse Mandelbrot

Started by gerrit on Fractal Mathematics And New Theories

0 Replies
120 Views
Last post July 11, 2018, 06:11:02 AM
by gerrit
xx
A ripple in time

Started by 1bryan1 on Fractal Image Gallery

0 Replies
61 Views
Last post April 20, 2018, 07:58:56 AM
by 1bryan1