Print Page - Fractal generation from infinite sum

Title: Fractal generation from infinite sum
Post by: ballaw on January 25, 2013, 09:37:39 PM

I found a project description on a course website for computer graphics. I am trying to complete the project for fun.

Here is the link to the problem description:

http://www.pdfhost.net/index.php?Action=Download&File=901bc7785bef41364b3a40f6f4493926

Below is my code. The problem I am running in to is that the terms of the series grow so fast I can't map the points to the screen correctly. From the problem description it says the points will be mappable within a -2 - 2 square but the difference in value between the points is so huge that normalizing by the largest would collapse most of the points to a single pixel.

I assume I have a fundamental misunderstanding that I can't identify. Any help or insight would be appreciated!

int w = 800, h = 600;
int numTimes = 10, cSize = 5;
float xr = 2, yr = 2;

void setup() {
size(w,h);
}

void draw() {
background(255);

Complex v = new Complex(mouseX*(xr/w) - (xr/2), mouseY*(yr/h) - (yr/2));
Complex[] exps = new Complex[numTimes];

for (int i = 0; i < numTimes; i++) {
exps = complexExp(v,i);
}

ellipse(w/2, h/2, cSize, cSize);
for (int i = 0; i < numTimes; i++) {
drawSeries(new Complex(0,0), exps, i, i);
}
}

void drawSeries(Complex vToDraw, Complex[] exps, int count, int clrTrunc) {
if (count == 0) {
Complex v = exps[0];

float progress = float(clrTrunc) / float(numTimes);
fill(255*progress, 180, 255 - 255*progress);

vToDraw.add(v);
ellipse(vToDraw.r*(w/xr) + (w/2), vToDraw.i*(h/xr) + h/2, cSize, cSize);
vToDraw.sub(v);
vToDraw.sub(v);
ellipse(vToDraw.r*(w/xr) + (w/2), vToDraw.i*(h/xr) + h/2, cSize, cSize);
} else {
Complex v = exps[count];

vToDraw.add(v);
drawSeries(vToDraw, exps, count - 1, clrTrunc );
vToDraw.sub(v);
vToDraw.sub(v);
drawSeries(vToDraw, exps, count - 1,clrTrunc );
}
}

Complex complexExp(Complex v, int times) {
if (times == 0) {
return new Complex(1, 1);
} else if ( times == 1) {
return new Complex( v.r*v.r - v.i*v.i, 2*v.r*v.i );
} else {
return complexExp( new Complex( v.r*v.r - v.i*v.i, 2*v.r*v.i ), times - 1 );
}
}

class Complex {
float r, i;

Complex() {
this.r = 0;
this.i = 0;
}

Complex(float r, float i) {
this.r = r;
this.i = i;
}

void add(Complex nv) {
this.r += nv.r;
this.i += nv.i;
}

void sub(Complex nv) {
this.r -= nv.r;
this.i -= nv.i;
}
}

Title: Re: Fractal generation from infinite sum
Post by: eiffie on January 29, 2013, 05:33:30 PM

I actually had a great deal of fun with this "assignment" turning it into a distance estimate. Ballow I'm not familiar with Processing but it looks like your ComplexExp function is performing c=c*c when you want c=c*firstc. But now for my fun "ride".

My new year's resolution was to be more like knighty so I decided to come up with a distance estimate for this fractal.
A distance estimate tells the distance from the point in question (p) to the fractal.
The fractal formula is...
c^0±c^1±c^2±c^3... where c is a complex number
So to find the distance we want to minimize the funtion:
p-c^0±c^1±c^2...
The length of the remainder after minimizing is the distance to the fractal.
But how can we minimize without recursively going down each branch?
If we take each term (c^n) and choose the path that brings us closer to 0,0 we will get close but unfortunately
we will get trapped in local minima and lose some of the fractal. I will leave it for the real knighty to find a better
method and use this as a start.
We use the dot product to determine whether to add or subtract c.
if(dot(p,c)>0.0)//c pushes p farther from the origin
p-=c;
else
p+=c;

A script in Fragmentarium looks like this...

Code:

#include "2D.frag"
#include "Complex.frag"
#group thingy
uniform int  Iterations; slider[1,50,320]
uniform int FirstPower;slider[0,7,10]
uniform float JuliaX; slider[-1,0.78,1]
uniform float JuliaY; slider[-1,-0.36,1]
uniform float Radius; slider[0.0,0.002,0.05]
uniform bool Mirror; checkbox[true]

vec3 color(vec2 p) {
	if(Mirror)p.x=abs(p.x);
	for(int i=FirstPower;i<Iterations;i++){
		vec2 c=cPower(vec2(JuliaX,JuliaY),float(i));//these can be pre-calculated
		p+=faceforward(c,p,c);//bad name - make c face OPPOSITE direction of p
	}
	return vec3(float((length(p)-Radius)>0.0));//only plotting last iter is enough for shape
}

The missing pieces actually make it more appealing IMHO.

But wait I've seen this fractal before!
Here is a hint:
The complex number (c) is used to create a scaled and rotated offset. We can achieve the exact scaling and rotation by
inverting the operations and applying them to p. You then get...

Code:

mat2 RMat2(float a){return mat2(cos(a),sin(a),-sin(a),cos(a));}
float scale=1.0/sqrt(JuliaX*JuliaX+JuliaY*JuliaY);
mat2 rmx=RMat2(-atan(JuliaY,JuliaX));

vec3 color(vec2 p) {
	float dr=1.0;
	for(int i=0;i<Iterations;i++){
		p*=rmx*scale;dr*=scale;
		if(p.x<0.0)p=-p;
		p-=vec2(1.0,0.0);
	}
	return vec3(float((length(p)-Radius)/dr>0.0));
}

Its kali's dragon kifs in 2d. This may give me some insite into how to correct the DE. Maybe not. But it was a fun exercise to see the many ways we can produce the same fractal.

Title: Re: Fractal generation from infinite sum
Post by: knighty on February 02, 2013, 12:15:13 AM

Quote from: eiffie on January 29, 2013, 05:33:30 PM

My new year's resolution was to be more like knighty ...

I don't think this is a good idea. :gum: :no:

Quote from: eiffie on January 29, 2013, 05:33:30 PM

... so I decided to come up with a distance estimate for this fractal.

err... OK! It is always good to share ideas! :joy:

Seriously,

Quote from: eiffie on January 29, 2013, 05:33:30 PM

The fractal formula is...
c^0±c^1±c^2±c^3... where c is a complex number
So to find the distance we want to minimize the funtion:
p-c^0±c^1±c^2...
The length of the remainder after minimizing is the distance to the fractal.
But how can we minimize without recursively going down each branch?

AFAIK, the answer is: there is no way to avoid recursion. Finding the distance to an IFS requires a stack or a priority list.
The example you gave can be written in recursive form (IIRC these are related to Littlewood polynomials - those which coefficients are either +1 or -1):

P_n+1=c*P_n±1.

The DE is computed for each branche then we take the minimum:
DE=(|P_n|-bvr)/|c|ⁿ.
bvr is the bounding volume of the fractal.
We compute the DE when the norm of P_n is grater than a bailout value. Fortunately, in general, because the norm of P_n grows rapidly and go beyond the bailout before n reaches the max recursion depth, the total number of "iteration" is not exponential when the norm of c is large enought.

Another method is to use a priority queue.
(see attached scripts for details. They are 2D. Converting to 3D is straightforward).

Regarding performance. Hart's raytracing method is much faster (I think it is the method David Makin is using). The advantage of the DE approache is that we can use nonlinear transforms. I've also attached a very simple script for illustration purpose (see the first picture).

Title: Re: Fractal generation from infinite sum
Post by: eiffie on February 07, 2013, 06:29:29 PM

Thanks Ballaw for posting this assignment - I just keep learning little bits from it.
Thanks Knighty for explaining the proper way but also for this...

Quote

the answer is: there is no way to avoid recursion

Whenever I see a statement like that - even when it is true as in this case - I hear it as "must find a way to avoid recursion!!"
So I made a way that doesn't use recursion - actually the DE steps act as a kind of recursion and again parts of the fractal branchs are cut off - just no visual discontinuity - a nice clean pruning. Your scripts really did help.
http://www.fractalforums.com/ifs-iterated-function-systems/dragonkifs-promising-formula-but-help-needed/ (http://www.fractalforums.com/ifs-iterated-function-systems/dragonkifs-promising-formula-but-help-needed/)

Welcome to Fractal Forums

Fractal Software => 3D Fractal Generation => Topic started by: ballaw on January 25, 2013, 09:37:39 PM