Search code examples
javaalgorithmfractals

Rendering Barnsley Fern fractal without the probabilities

I was making a program that renders a mutation of the Barnsley Fern fractal. My program works flawlessly and generates exactly the output which I want it to generate. I went further into reading about the Iterated Function Systems and read that these fractals can be renders without the use of probabilities and performing all the four Affine Transformations in each iteration. I know that this will increase the computation time but I want to know how can we remove the probabilities out of picture?

For example the probability for the four functions that draw my fern are 2%, 84%, 7% and 7% respectively.

Here is the question again in bold for those who say, "I cannot find the question in the post." : How do we use all the four functions in every iteration instead of choosing one of the four, based on probability?

Here is the relevant code:

AffineTransformation.java 

public class AffineTransformation
{
    private double[][] transformation=new double[2][2];
    private double[][] translation=new double[2][1];
    public AffineTransformation(double a,double b,double c,double d,double e,double f)
    {
        transformation[0][0] = a;
        transformation[0][1] = b;
        transformation[1][0] = c;
        transformation[1][1] = d;
        translation[0][0] = e;
        translation[1][0] = f;
    }
    public Point transform(Point point)
    {
        double x = point.getX();
        double y = point.getY();
        double u = 0.0;
        double v = 0.0;
        u = transformation[0][0]*x + transformation[0][1]*y;
        v = transformation[1][0]*x + transformation[1][1]*y;
        u = u + translation[0][0];
        v = v + translation[1][0];
        return new Point(u,v);
    }
}

The rendering loop 

AffineTransformation f1 = new AffineTransformation(0,0,0,0.25,0,-0.4);
AffineTransformation f2 = new AffineTransformation(0.95,0.005,-0.005,0.93,-0.002,0.5);
AffineTransformation f3 = new AffineTransformation(0.035,-0.2,0.16,0.04,-0.09,0.02);
AffineTransformation f4 = new AffineTransformation(-0.04,0.2,0.16,0.04,0.083,0.12);
Point point = new Point(0.5,0.0);
int N=Width*Height;
for(int i=0;i< N*25;i++)
{
    Point newpoint = new Point();
    double probability = Math.random();
    if(probability < 0.02)
    {
        newpoint = f1.transform(point);
        color=new Color(0x002147);
    }
    else if(probability < 0.86)
    {
        newpoint = f2.transform(point);
        color=new Color(0x120A8F);
    }
    else if(probability < 0.93)
    {
        newpoint = f3.transform(point);
        color=new Color(0x002147);
    }
    else
    {
        newpoint = f4.transform(point);
        color=new Color(0x002147);
    }
    point = newpoint;
    int X=((int)(point.getX()*W/3)+W/2)/2 + W/4-1;
    int Y=(int)(point.getY()*H/8) + H/9 -1;
    image.setRGB(X,Y, color.getRGB());
}

EDIT
The main thing I wanted to achieve by discarding probs. was test my own transformation functions for which obviously I would not know the probability except by trial and error. Any help there?

To elaborate, suppose I have four other functions and I don't know what probability to use, is there a method to know the probability except by trial and error.

Solution

  • Alright, I found a way to determine the probabilities that should be used for a perfect image using the Affine Transformation functions. The method which requires the probabilities for rendering is called the Random Iteration Algorithm.

    The method I am about to describe here has been taken from Michael F. Barnsley's book, Fractals Everywhere (Chapter 3, under the heading: TWO ALGORITHMS FOR COMPUTING FRACTALS FROM ITERATED FUNCTION SYSTEMS).

    Each Affine transformation function can be represented as:

    Affine Transformation

    Now if we use N functions for drawing a fractal, the probability Pi to be used for each function is given by:

    Probability function

    where |det. Ai| is the absolute value of determinent of the matrix Ai which is given by: |a.d - b.c|

    If, for some i, we get Pi=0 the we assign Pi a small positive value like 0.001.

    While finally using the probabilities for rendering it should be noted that ∑ Pi=1

    Example:

    Suppose we have four Affine Transformation functions with matrix values (a,b,c,d) as follows:

    A1 = (0, 0, 0, 0.25)
    A2 = (0.95, 0.005, -0.005, 0.93)
    A3 = (0.035, -0.2, 0.16, 0.04)
    A4 = (-0.04, 0.2, 0.16, 0.04)

    Now:

    |det. A1| = |(0*0.25)-(0*0)| = 0
    |det. A2| = |(0.95*0.93)-(0.005*-0.005)| = 0.883525
    |det. A3| = |(0.035*0.04)-(-0.2*0.16)| = 0.0334
    |det. A4| = |(-0.04*0.04)-(0.2*0.16)| = 0.0336

    And summation of all Ais = (0 + 0.883525 + 0.0334 + 0.0336) = 0.950525

    And then the probabilities are:

    P1 = 0 ≈ 0.01
    P2 = 0.883525/0.950525 = 0.929512637 ≈ 0.93
    P3 = 0.0334/0.950525 = 0.0351384761 ≈ 0.03
    P4 = 0.0336/0.950525 = 0.0353488861 ≈ 0.03

    So, the final probabilities are: 1%, 93%, 3%, 3% which sum up to 100% which can used as a check.

    By the way, these four functions generate a mutation of Barnsley Fern.