Starting out with Fractals (direction needed)

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
mister_m
Posts: 34
Joined: Fri Feb 04, 2011 2:51 am UTC

Starting out with Fractals (direction needed)

Postby mister_m » Wed Oct 05, 2011 2:32 am UTC

I want to write something multi threaded. I really haven't before outside of a silly little server for class, so I checked out the "Embarrassingly Parallel" problems list on wikipedia, and I saw that fractals were among these problems suited for a multi threaded solution. The article says "The Mandelbrot set and other fractal calculations, where each point can be calculated independently." What does it mean by each 'point'?

I don't really know much about fractals or the math behind them, but I thought that this particular one looked pretty neat and might be fun to try: Dragon Curve - specifically the "Twin Dragon". The twin dragon is described as follows: "The twindragon (also known as the Davis-Knuth dragon) can be constructed by placing two Heighway dragon curves back-to-back. It is the limit set of the following iterated function system:"
Image
Image

What does "the limit set of the following iterated function system mean exactly? I see some imaginary numbers in there, so I am certainly completely out of my element here. How can I make sense of that and get a fractal generator up and running?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Starting out with Fractals (direction needed)

Postby EvanED » Wed Oct 05, 2011 2:57 am UTC

Ah, fractals are a topic near and dear to my heart; I spent some time working on a fractal generator many years ago. (That was the project where I first (and only time, I think) spent a few hours debugging an if(x=0)-type issue and consequently got into my "enable all the warnings!" habit.)

Anyway, dragon curves (Koch curves, etc.) I actually don't know much about in terms of how you'd generate them. What I'm familiar with are Mandelbrot/Julia Set-style fractals.

The way those work is they basically "live" in the complex plane. (If you're unfamiliar, it's a 2D plane; each point is a complex number. The x coordinate is the real part, and the y coordinate is the imaginary part. It's possible to do these things with only a light knowledge of complex arithmetic; if you can't figure something out just ask and someone will fill you in.)

Each point of the plane either belongs to the fractal or not. See this image; black points are in the fractal, and white points are not. It is possible to compute whether each point is a member or not completely independently, and this is why the problem winds up being embarrassingly parallel.

Here's how you do it. (Remember that point is complex, as is temp)

Code: Select all

def is_in_mandelbrot_set(point):
    temp = 0 + 0i
    while you are not bored:
        temp = temp**2 + point
        if magnitude(temp) > 2:
            return False
    return True


Basically this is iterating the equation temp = temp2 + point and approximating whether it diverges. The point point is in the Mandelbrot Set if and only if temp will never diverge. If the magnitude of temp grows beyond the 2, then temp is guaranteed to diverge, so we can stop at that point.

In practice, while you are not bored is replaced by some counted loop that goes up to, say, 50 iterations, and if temp hasn't diverged by that point it is assumed to not.

Fancier pictures -- those with colors -- have pixels outside of the formal Mandelbrot set colored with fancy colors. Since those points are outside the set, temp diverges in those cases; the color is generally picked by how long it takes for temp to diverge.

Finally, you can twerk that code just a tiny bit and be able to render Julia Sets. The Mandelbrot set is just one set, but the Julia sets are actually a family of sets, parameterized by some complex constant C. Here is how to tell whether a point is in the Julia set with a given constant:

Code: Select all

def is_in_julia_set(point, c):
    temp = point   ## was temp = 0
    while you are not bored:
        temp = temp**2 + c  ## was temp = temp**2 + point
        if magnitude(temp) > 2:
            return False
    return True

Note that only two lines change.

An interesting fact is that C is in the Mandelbrot set if and only if the Julia set with constant C is connected. One fun thing you can do with Julia sets is provide a way for the user to click on a point (perhaps while the Mandelbrot set is displayed) and then draw the Julia set corresponding to the point they selected. That makes it easy to explore around different values of C and find ones that give you neat fractals.

I lied. One more thing. Watch this video. But the instructions are wrong and describe how to create Julia sets, not the Mandelbrot set. :-)

User avatar
mister_m
Posts: 34
Joined: Fri Feb 04, 2011 2:51 am UTC

Re: Starting out with Fractals (direction needed)

Postby mister_m » Wed Oct 05, 2011 4:00 am UTC

EvanED wrote:Basically this is iterating the equation temp = temp2 + point and approximating whether it diverges. The point point is in the Mandelbrot Set if and only if temp will never diverge. If the magnitude of temp grows beyond the 2, then temp is guaranteed to diverge, so we can stop at that point.

In practice, while you are not bored is replaced by some counted loop that goes up to, say, 50 iterations, and if temp hasn't diverged by that point it is assumed to not.


Firstly, thank you for the humongous response. That was very helpful. I was wondering if you could tell me a little more about the temp=temp2 + point divergence test. I suppose there are some significant gaps in my mathematical understanding of what is going on here, but what does it mean for a number to "diverge"? I remember the term from a Calculus class that I took a long time ago, but I can't remember much of anything else.

Also, in your pseudo code for the mandelbrot fractal, temp is initially assigned to temp = 0 + 0i, what does the term 0i represent? Later on there is temp=temp2 + point, what does point refer to?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Starting out with Fractals (direction needed)

Postby EvanED » Wed Oct 05, 2011 4:35 am UTC

mister_m wrote:
EvanED wrote:Basically this is iterating the equation temp = temp2 + point and approximating whether it diverges. The point point is in the Mandelbrot Set if and only if temp will never diverge. If the magnitude of temp grows beyond the 2, then temp is guaranteed to diverge, so we can stop at that point.

In practice, while you are not bored is replaced by some counted loop that goes up to, say, 50 iterations, and if temp hasn't diverged by that point it is assumed to not.


Firstly, thank you for the humongous response. That was very helpful. I was wondering if you could tell me a little more about the temp=temp2 + point divergence test. I suppose there are some significant gaps in my mathematical understanding of what is going on here, but what does it mean for a number to "diverge"? I remember the term from a Calculus class that I took a long time ago, but I can't remember much of anything else.

Basically one of two things will happen. Either the magnitude of temp will remain bounded no matter how many times you iterate (in the case of the Mandelbrot set, it will be bounded by 2; it may even be sqrt(2), I don't remember), or it will start off on a trip to become infinitely larger. In the former case, it will bounce around on the complex plane within the circle of radius 2. It doesn't necessarily converge to a single point, but it stays within that circle. (To see this just take point=-1. On the first iteration, temp=0. On the second, temp=0^2 + (-1) = -1. On the third, temp=(-1)^2 + (-1) = 0.)


Also, in your pseudo code for the mandelbrot fractal, temp is initially assigned to temp = 0 + 0i, what does the term 0i represent?

That's just emphasizing that it's a complex number. Just "0" would have worked just as well, or I could have said that temp starts off with the point (0,0).

Later on there is temp=temp2 + point, what does point refer to?

In both algorithms, point is the point which you are testing to see whether it is a member of the fractal. It too is a complex number -- or alternately a point.

The parallelness of the algorithm comes in because you can call is_in_julia_set or is_in_mandelbrot_set in parallel with as many points as you want. If you had as many processors as pixels in your image, you could compute them all at once. :-) (Of course communication overhead would make it not worth it.)

User avatar
mister_m
Posts: 34
Joined: Fri Feb 04, 2011 2:51 am UTC

Re: Starting out with Fractals (direction needed)

Postby mister_m » Wed Oct 05, 2011 6:22 am UTC

I'd be interested in learning more about the underlying mathematics involved in the process. Complex numbers isn't something I've talked about since high school algebra, and I can't say with a straight face that I even really comprehended them at the time. Are there any resources that you would recommend that are specifically written with fractals in mind?

EDIT: Here is a Dr. Math Link that I just found for anyone interested.

IIAOPSW
Posts: 131
Joined: Sat Dec 27, 2008 1:52 am UTC

Re: Starting out with Fractals (direction needed)

Postby IIAOPSW » Wed Oct 05, 2011 3:59 pm UTC

I feel compelled to quote the Johnathon Coulton song "Mandelbrot set" as perhaps it will give you some insight.


you take a point called c in the complex plane
let z1 be z^2 + c
z2 is z1^2+c
z3 is z2^2+c
and so on
if the series of z will always stay
close to c and never trend away
that point is in the mandelbrot set
mandelbrot set your a roschact test on fire
your a flaming teradactyl
your a heart shaped box of springs and wires
your one badass fucking fractal!
-President of the peoples republik of the internet.

screw your coffee, i download my java!

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Starting out with Fractals (direction needed)

Postby EvanED » Wed Oct 05, 2011 4:45 pm UTC

IIAOPSW wrote:I feel compelled to quote the Johnathon Coulton song "Mandelbrot set" as perhaps it will give you some insight.


you take a point called c in the complex plane
let z1 be z^2 + c
z2 is z1^2+c
z3 is z2^2+c
and so on
if the series of z will always stay
close to c and never trend away
that point is in the mandelbrot set
mandelbrot set your a roschact test on fire
your a flaming teradactyl
your a heart shaped box of springs and wires
your one badass fucking fractal!

And then you take a closer look at his lyrics and realize that he's describing the Julia sets. :-)

It's easy to fix though. Just change "take a point called z" to "take a point called c", and replace "let z1 be z^2 + c" with "let z1 be zero plus c".

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Starting out with Fractals (direction needed)

Postby You, sir, name? » Wed Oct 05, 2011 5:04 pm UTC

Margin note: Some variants of the mandelbrot (specifically the buddhabrot) is less trivial but still fairly easy to parallelize, as it requires thread safe atomic increments if calculated in parallel. Fun project to do though. I played with this last summer, and ended up with half gigapixel-resolution renders that were almost impossible to view because.

Here's a tiny corner of a 400 mpix render (this is about .15% of the full picture).
Spoiler:
Image
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Starting out with Fractals (direction needed)

Postby jestingrabbit » Wed Oct 05, 2011 8:10 pm UTC

mister_m wrote:What does "the limit set of the following iterated function system mean exactly?


Do you know what limits are?

Assuming you do, for some sets of functions, if you take a random point in the plane and then randomly apply one or orther of your functions over and over again, you (almost always) end up with a series of points that converges to a point in some particular set. That set is the limit set.

Put another way, if you have a set, A, such that f1(A) union f2(A) is a subset of A, then the limit set is the smallest non empty, (topologically) closed set with this property.

mister_m wrote:I see some imaginary numbers in there, so I am certainly completely out of my element here.


First things first, don't panic, wikipedia can probably tell you how to do basic complex arithmetic pretty well. Secondly, to make things easier, you can replace f1 and f2 with

f1(x,y) = ((x-y)/2, (x+y)/2)
f2(x,y) = ((x-y+1)/2, (x+y-1)/2)

mister_m wrote:How can I make sense of that and get a fractal generator up and running?


Well, going back to the limit set, you can start with x[0]=(0,0). Then do

Code: Select all

i=0
while(you want more points):
    r = random number between 0 and 1
    if r< 1/2:
        x[i+1] =  f1(x[i])
    else:
        x[i+1] =  f2(x[i])
    i = i+1


Then draw all of your points. This will be a good approximation of you limit set.

This is called the chaos game and it works okay if you get enough points. You can also get rid of your first hundred or so points if you start with a random point in the plane (you might pick something that is way away from your fractal, so those points aren't going to be that interesting, and they're not going to have many points clustering around them). Another way to go is to plot twenty or so points at a time, and see how they start to cluster and form the shape that you're expecting.

You can then start playing around with your f's. What does changing the amount that you divide by (atm its 2) do? or changing the offsets in f2 (from 1 and -1) to whatever you want, or adding a function that maps (x,y) to (ax+by+e, cx+dy+f) where you pick your constants (before you start iterating) randomly from (-1,1).

Just have fun with it.
Last edited by jestingrabbit on Thu Oct 06, 2011 5:27 pm UTC, edited 1 time in total.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Maelstrom.
Posts: 76
Joined: Tue Oct 21, 2008 12:18 pm UTC

Re: Starting out with Fractals (direction needed)

Postby Maelstrom. » Thu Oct 06, 2011 6:08 am UTC

Ill try to explain things with out using too much mathematical notation. Fractals are a very mathematical construct, but it is possible to play around with them without understanding too much of the maths behind them. I highly encourage you to learn more of the maths behind them, but you may find the maths easier to comprehend once you have a working example you can play around with.

Firstly, some definitions:
  • A set of things is merely a group of things. Nothing very special.
  • A complex number consist of two components. A real component and the imaginary part
  • A 2D point consists of two parts. An x component and a y component

The Mandelbrot function has many wonderful properties and interesting things to study. Right now, those are unimportant. The bit we are interested in is whether a complex number passes what I will call "The Mandelbrot Test". If any given complex number passes "The Mandelbrot Test", then that complex number is in the Mandelbrot set.

"The Mandelbrot Test" is very simple to perform. EvanED provided an example earlier:

Code: Select all

    def is_in_mandelbrot_set(complex_number):
        temp = 0 + 0i
        while you are not bored:
            temp = temp**2 + complex_number
            if magnitude(temp) > 2:
                return False
        return True


As EvanED stated, 'while you are not bored' can be replaced by something such as a counter. If the counter passes 50, you have become bored. If 'is_in_mandelbrot_set' returns True, then the complex number has passed "The Mandelbrot Test".

Now, to diverge for a minute. Lets just say that you had an image, made up of a two dimensional grid of pixels. These pixels had an x and a y component. Say you had a test that returned true or false when supplied with a point. For every pixel, you ran this test. If the test returned true, then you coloured the pixel black. If the test returned false, you coloured the pixel white. You would then have a black and white image that graphically showed which points passed this test that you supplied. You have just become an artist!

Combining the two ideas above, you would pretend that every pixel in an image is actually a complex number. You would run "The Mandelbrot Test" for the complex number that corresponds to each pixel in the image. You would then have an image that graphically represents the Mandelbrot set

One final hint before you give this a go: The Mandelbrot lives at the origin of the complex plane [ (0, 0) or 0 + 0i ], and has a range of about ±2.0 in each direction. You will need to convert from your 'image space' to the 'complex space' where the Mandelbrot set lives. If you directly mapped between complex space and image space with no transformation, the Mandelbrot set would take up about 4 pixels in the upper left corner.

User avatar
zed0
Posts: 179
Joined: Sun Dec 17, 2006 11:00 pm UTC

Re: Starting out with Fractals (direction needed)

Postby zed0 » Thu Oct 06, 2011 9:07 am UTC

Partly based on this thread, partly based on something I started a while ago I've written a terminal based fractal explorer in c++ (https://github.com/zed0/fracview), this currently only views the Mandlebrot set, but as stated above can be trivially modified to show Julia sets instead.

Some images are here: http://zed0.uwcs.co.uk/Misc/fractals/

My main problem is that once I've zoomed in to a magnification of around 2.8e+14 the accuracy of a double ceases to be sufficient to distinguish between pixels.

Does anyone know any neat tricks to accurately calculate small areas with doubles or do I have to start using more complex datatypes?

(mods: I think this fits here but feel free to split this if you think it should be a new thread)

Turtlewing
Posts: 236
Joined: Tue Nov 03, 2009 5:22 pm UTC

Re: Starting out with Fractals (direction needed)

Postby Turtlewing » Thu Oct 06, 2011 2:53 pm UTC

It might be worth noting that typical renderings of the Mandelbrot set color code the points that aren't in the set based on how many iterations it took to place them outside the set.

The pretty pictures are typically a zoomed in and cropped view of an edge of the set so you can see all the colors.

User avatar
PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Starting out with Fractals (direction needed)

Postby PM 2Ring » Thu Oct 06, 2011 3:31 pm UTC

zed0 wrote:My main problem is that once I've zoomed in to a magnification of around 2.8e+14 the accuracy of a double ceases to be sufficient to distinguish between pixels.

Does anyone know any neat tricks to accurately calculate small areas with doubles or do I have to start using more complex datatypes?

You need to use a datatype with more precision. It's not just the inability to distinguish between pixels - rounding error means that the iteration loop starts producing garbage. Unfortunately, arbitrary precision floating point arithmetic is much slower than hardware-supported arithmetic. So things get very slow, and such deep zooms are slow anyway, since the interesting stuff tends to happen in areas where you need a high iteration limit.

But you can compromise: rather than using arbitrary precision arithmetic, you can almost double your precision using pairs of doubles to hold a single number, which will allow you to zoom in a bit more.

Double-double_arithmetic wrote:A common software technique to implement nearly quadruple precision using pairs of double precision values is sometimes called double-double arithmetic.[1][2][3] Using pairs of IEEE double precision values with 53-bit significands, double-double arithmetic can represent operations with at least[1] a 2×53=106-bit significand (and possibly 107 bits via clever use of the sign bit[4]), only slightly less precise than the 113-bit significand of IEEE binary128 quadruple precision. The range of a double-double remains essentially the same as the double precision format because the exponent has still 11 bits,[1] significantly lower than the 15-bit exponent of IEEE quadruple precision (a range of 1.8×10^308 for double-double versus 1.2×10^4932 for binary128).

In particular, a double-double/quadruple-precision value q in the double-double technique is represented implicitly as a sum q=x+y of two double-precision values x and y, each of which supplies half of q's significand.[2] That is, the pair (x,y) is stored in place of q, and operations on q values (+,−,×,...) are transformed into equivalent (but more complicated) operations on the x and y values. Thus, arithmetic in this technique reduces to a sequence of double-precision operations; since double-precision arithmetic is commonly implemented in hardware, double-double arithmetic is typically substantially faster than more general arbitrary-precision arithmetic techniques.[2][1]

With Mandelbrot calculations, we don't need to worry about the exponent issue mentioned above. Our values aren't huge, so we never need large positive exponents, and we know that the pixels close to the origin are black, so we never need large negative exponents.

I just had a quick look at your code. You can get rid of the sqrt() calls in viewport.cpp on lines 43 & 53. The first one is incorrect, according to the usual definition of the Mandelbrot Set, and it will cause your loop to do one more iteration than necessary. (You should change the initial value of your iteration counter, too).
The second one is redundant, since for real x >= 0, sqrt(x) <= 1 implies x <= 1.

I'm glad to see that you are using the PPM format. :) I sometimes generate fractals in PGM, then translate that to colour as a separate step, as it makes it easier to select from a variety of palettes.

Here's a Mandelbrot explorer I wrote a few months ago in JavaScript that uses the HTML5 Canvas. It features semi-automatic adjustment of the maximum iteration parameter, and colour palette cycling.

Code: Select all

<!DOCTYPE html>
<html>
<head>
<title>Mandelbrot</title>
<meta http-equiv="Content-Script-Type" content="text/javascript">
<style type="text/css">
h { text-align: center; }
#mycanvas { border: 1px solid black; cursor: crosshair;
    margin-left: 1%; margin-right: 1%; }
</style>
<script>
var canvas, ctx, canvasData, pixels, palette, palsize = 1 + 6*255, grid,
imax, width, height, ou, ov, ox, oy, cmul, imul, go = false, timeout, kcount;

var zoom =
{
    //str, value, delta, depth, scale,
    set: function(s)
    {
        switch(s)
        {
            case 'out':
                this.str = s; this.value = 2.0; this.delta = -1; break;
            case 'pan':
                this.str = s; this.value = 1.0; this.delta = 0; break;
            case 'in':
                this.str = s; this.value = 0.5; this.delta = 1; break;
            case 'reset':
                this.str = 'in'; this.value = 0.5; this.delta = 1;
                this.depth = -1; this.scale = 6.5 / width;
        }               
    },
   
    update: function()
    {
        if (this.delta)
            set_imax(this.delta);
        this.depth += this.delta;
        this.scale *= this.value;
    }       
};

function byId(id) { return document.getElementById(id); }

function show(s) { byId("output").innerHTML = s; }

//Convert hue t to RGB. 0 <= t < 1
function hue2RGB(t)
{
    var m = 255, i, j, h;

    i = Math.floor(m * t);
    j = Math.floor(((i % 43) / 43) * m);
    switch(Math.floor(i / 43))
    {
        case 0: h = [  m,   j,   0]; break;
        case 1: h = [m-j,   m,   0]; break;
        case 2: h = [  0,   m,   j]; break;
        case 3: h = [  0, m-j,   m]; break;
        case 4: h = [  j,   0,   m]; break;
        case 5: h = [  m,   0, m-j]; break;
    }
    return h;
}

function create_palette(n)
{
    var i, p = new Array(n);

    p[0] = [0, 0, 0];
    for (i=1; i<n; i++)
        p[i] = hue2RGB(i / (n-1));
    return p;
}

/* Convert pixel number to real */
function u2x(u){ return ox + zoom.scale * (u - ou); }
function v2y(v){ return oy + zoom.scale * (ov - v); }

function ev_mouse(evt)
{
    var u, v;

    //Ignore right mouse button.
    if (evt.button > 1) return;

    // Get the mouse position.
    if (evt.layerX != undefined)
    {
        // Firefox
        u = evt.layerX;
        v = evt.layerY;
    }
    else if (ev.offsetX != undefined)
    {
        // Opera
        u = evt.offsetX;
        v = evt.offsetY;
    }
    else return;
   
    //Convert the position so it's relative to the canvas element.
    u -= canvas.offsetLeft;
    v -= canvas.offsetTop;

    //Convert from pixel co-ord to complex
    ox = u2x(u); oy = v2y(v);
    window.status = u + ', ' + v + '->' + ox + ', ' + oy;   
    do_mandel();
}

function ev_key(evt)
{
    var ch;

    if (!evt.charCode) return;

    switch(ch = String.fromCharCode(evt.charCode))
    {
        case 'd': set_imax(-1); break;
        case 'D': set_imax(1); break;

        case 'm': imul -= 1; break;
        case 'M': imul += 1; break;

        case 'c': cmul -= 1; break;
        case 'C': cmul += 1; break;

        case 'i': zoom.set('in'); break;
        case 'I': zoom.set('in');
            ox = u2x(ou); oy = v2y(ov); do_mandel(); break;
        case 'o': zoom.set('out'); break;
        case 'O': zoom.set('out');
            ox = u2x(ou); oy = v2y(ov); do_mandel(); break;
        case 'p': zoom.set('pan'); break;
        case 'P': zoom.set('pan'); do_mandel(); break;
       
        case 'r': update_canvas(); break;

        case 'y': toggle_timer(); break;
        case 'Y': cmul = -cmul; break;
        case 'Z':
        case 'z': init_mandel(); do_mandel(); break;

        default: alert("Unknown key command [" + ch + "]");
    }
    show_status();
}

//Set maximum number of iterations
function set_imax(m)
{
    var iscale = 1.1;   
   
    switch(m)
    {
        case -1: imax = Math.floor(0.5 + imax / iscale);
        case 0: imax = 145;
        case 1: imax = Math.floor(0.5 + imax * iscale);
    }   
}

function show_status()
{
    show("zoom = " + zoom.str + "<br>"
    + "zoom depth = " + zoom.depth + "<br>"
    + "iteration <u>d</u>epth = " + imax + "<br>"
    + "palette <u>m</u>ultiplier = " + imul + "<br>"
    + "colour c<u>y</u>cling = " + (go ? "on" : "off") + "<br>"
    + "<u>c</u>ycle multiplier = " + cmul + "<br>"
    );
}

function toggle_timer()
{
    if(go = !go)
        timer();
    else
        window.clearTimeout(timeout);
}

function init_mandel()
{
    ox = -0.5; oy = 0; kcount = 0; cmul = 13; imul = 31;
    set_imax(0); zoom.set('reset');
}

/* Find iteration count value for a single mandelbrot pixel */
function mandelpoint(cx, cy)
{
    var i, x = cx, y = cy, x2, y2;

    for(i=0; i<imax; i++)
    {
        x2 = x * x;
        y2 = y * y;
        if(x2 + y2 > 4.)
            break;

        /* Do actual Mandelbrot calculation */
        y = 2. * x * y + cy;
        x = x2 - y2 + cx;
    }
    /* Point is in Mandelbrot set if i==imax */
    return i < imax ? i : -1;
}

function do_mandel()
{
    var i = 0, d, x, y, u, v, x0, y0;   
   
    zoom.update();
    show_status();   
    d = zoom.scale;   
    x0 = u2x(0);
    y0 = v2y(0);
    for (y=y0, v=0; v<height; v++, y-=d)
        for (x=x0, u=0; u<width; u++, x+=d)
            grid[i++] = mandelpoint(x, y);

    update_canvas();
}

function timer()
{
    if (go)
    {
        update_canvas();
        if (++kcount == palsize) kcount = 0;
        timeout = window.setTimeout("timer()", 40);
    }
}

function update_canvas()
{
    var i, j, p, g,
    ps = palsize - 1,
    kc = (kcount * cmul) % ps;

    //Copy grid to pixel array
    for (j=i=0; i<grid.length; i++, j+=4)
    {
        g = grid[i];
        p = palette[g < 0 ? 0 : 1 + (ps + (kc + g * imul) % ps) % ps];
        pixels[j] = p[0];
        pixels[j+1] = p[1];
        pixels[j+2] = p[2];
    }
    ctx.putImageData(canvasData, 0, 0);
}

function show_image()
{
    var w = window.open('about:blank'), data = canvas.toDataURL('image/png');
   
    w.document.write('<img src=' + data + '><br>'
        + '<textarea cols="80" rows="12">' + data + '</textarea>');
    w.document.close();
}

function setup()
{
    canvas = byId('mycanvas');
    if (canvas.getContext)
    {
        //Get window height & calculate canvas dimensions for a 4:3 aspect
        height = 6 * Math.floor(0.92 * window.innerHeight / 6);
        //height = 120;
        canvas.height = height;
        canvas.width = width = 4 * height / 3;
        ou = width / 2;
        ov = height / 2;

        //Initialize temporary pixel grid
        grid = new Array(width*height);

        palette = create_palette(palsize);
        ctx = canvas.getContext('2d');
        canvasData = ctx.createImageData(width, height)
        pixels = canvasData.data;

        //Make all canvas pixels opaque
        for (var i=0; i<grid.length; i++)
            pixels[4*i + 3] = 255;

        init_mandel();
        zoom.update();
        canvas.addEventListener('mousedown', ev_mouse, true);
        window.addEventListener('keypress', ev_key, false);       
        show("Ready<br>Press z to start.");
    }
    else alert("Sorry, I can't set up the canvas!");
}
</script>
</head>
<body onload="setup();">
<table><tr><td>
<canvas id="mycanvas" oncontextmenu="return true;">
If you can read this, your browser does not support the HTML5 Canvas.
</canvas>

<td><table><tr><td>
<h4>Status</h4>
<div id="output"></div>
<hr>
<h4>Key commands</h4>
i, I: zoom <u>i</u>n<br>
o, O: zoom <u>o</u>ut<br>
p, P: <u>p</u>an<br>

z, Z: reset to ground <u>z</u>ero<br>
<br>

d: iteration <u>d</u>epth decrease <br>
D: iteration <u>D</u>epth increase <br>
<br>

m: palette <u>m</u>ultiplier decrease <br>
M: palette <u>M</u>ultiplier increase <br>

y: toggle colour c<u>y</u>cling<br>
Y: reverse colour c<u>Y</u>cling<br>
c: <u>c</u>ycle speed decrease<br>
C: <u>C</u>ycle speed increase<br>
r: <u>r</u>epaint <br>
<input type="button" value="Show image" onclick="show_image();">
</table></table>

<hr>

<h3>Mandelbrot generator</h3>
This JavaScript program allows you to explore the Mandelbrot set. It has a
fixed colour palette, but you can achieve some variation by using the
palette multiplier commands. It also has variable speed palette cycling.
<br>
Colour calculations are performed after the Mandelbrot set data is calculated, so
the current image can be viewed with different palette multipliers without being
recalculated. The display will be automatically updated to the new palette multiplier
if colour cycling is turned on. If colour cycling is off, just press r to repaint the
image with the new parameters.

<h5>Zooming</h5>
The lower case i, o &amp; p keys select zooming via the mouse. Wherever you
click the left mouse button on the canvas will become the centre of the new image.
<br>
The upper case I, O &amp; P keys cause the image to zoom at the canvas centre point.
<br>
When zooming in or out, the maximum iteration depth will automatically be scaled, but
it may be desirable to adjust this manually (with d &amp; D), depending on the
location you're zooming to.
<br>
The z key resets the program to the initial default values and displays the whole
Mandelbrot set.

</body>
</html>


Mandelbrot programs can be made much faster if when you zoom you reuse iteration counts that were determined during the previous phase. And there are various tricks that can be used to avoid calculating large slabs of black pixels inside the M Set, but such optimizations tend to look ugly and are probably too confusing to post in a thread aimed at people who are just starting out with fractal programming.
Last edited by PM 2Ring on Wed Nov 26, 2014 12:50 am UTC, edited 1 time in total.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Starting out with Fractals (direction needed)

Postby EvanED » Thu Oct 06, 2011 4:25 pm UTC

One thing that I always wanted to do when I was working on that was video output. (Or more realistically, output a bunch of individual frames then combine them later.)

There are a ton of numerical parameters when generating a fractal: x and y bounds, the iteration depth, the mapping from number of iterations to the color (depending on how you represent this, it can easily be numeric), for Julia sets the constant value, you could add a rotation, and who knows what else. It's easy to imagine interpolating between any of these: zoom in while increasing the iteration count, or pan around while changing the color, etc, and making a video of any of these.

User avatar
PM 2Ring
Posts: 3715
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Starting out with Fractals (direction needed)

Postby PM 2Ring » Thu Oct 06, 2011 7:12 pm UTC

EvanED wrote:One thing that I always wanted to do when I was working on that was video output. (Or more realistically, output a bunch of individual frames then combine them later.)

There are a ton of numerical parameters when generating a fractal: x and y bounds, the iteration depth, the mapping from number of iterations to the color (depending on how you represent this, it can easily be numeric), for Julia sets the constant value, you could add a rotation, and who knows what else. It's easy to imagine interpolating between any of these: zoom in while increasing the iteration count, or pan around while changing the color, etc, and making a video of any of these.


Real-time zooming into Mandelbrot & related fractals is feasible on modern machines. Check out xaos. If you use Linux, it's quite probably in your repository.

Apart from colour-cycling stuff, I've done a few animated things with Julia sets, eg setting the Julia constant to values on a line, circle, ellipse or Lissajous figure in interesting regions of the M set. The easiest way to do that is to generate the Julia set images using a command-line program in C (or other compiled language) and feed it the Julia constants for the path using a script in something like Python or awk. That way, it's very easy to experiment with a wide variety of path-making functions.

Another fun thing to do with Julia sets is to generate them using reverse iteration. Instead of using z' = z^2 + c, you use z' = ±sqrt(z - c), randomly choosing the plus or minus root at each step. You can use any point you like for the initial z, but you need to discard the first couple of dozen or so iterations, to give z enough time to get close to points in the Julia set, and then you just plot each value of z that comes out of the loop, possibly keeping track of how many times each pixel gets landed on. Images produced this way just give you the boundary of the Julia set, rather than the richer structure that's visible in the escape-time plotting method, but it's very fast.

I've used this reverse iteration technique to produce 3D Julia set images, where either the real or imaginary component of the Julia constant varies along the 3rd dimension, and I also did a couple of "4 dimensional" ones, using time for the 4th dimension, so I could vary both the real and the imaginary component of the constant . But that was quite a few years ago, on the Amiga, so rendering speed wasn't particularly fast. :)

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Starting out with Fractals (direction needed)

Postby You, sir, name? » Thu Oct 06, 2011 7:47 pm UTC

PM 2Ring wrote:I've used this reverse iteration technique to produce 3D Julia set images, where either the real or imaginary component of the Julia constant varies along the 3rd dimension, and I also did a couple of "4 dimensional" ones, using time for the 4th dimension, so I could vary both the real and the imaginary component of the constant . But that was quite a few years ago, on the Amiga, so rendering speed wasn't particularly fast. :)


The real awesome comes when you do a 2D projection of the 4D fractal and apply a 4-dimensional rotation.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests