Warning! Some information on this page is older than 5 years now. I keep it for reference, but it probably doesn't reflect my current knowledge and beliefs.

Thu

10

Dec 2009

I've been playing recently with Mandelbrot and Julia sets. These are fractals rendered in the completely different way that my last experiments with IFS (Iterated Function Systems). In IFS I had a set of points with given (x,y) positions and I've been transforming their positions iteratively by some functions before I rendered them. I'll blog more about IFS another time. Rendering Mandelbrot and Julia fractals is more like writing a pixel shader - for every pixel on the screen with its (x,y) coordinates we do some computations to calculate final color. I didn't extend my framework to render such things yet, but instead I've been doing my experiments in EvalDraw (where I can freely pan and zoom the view) and AMD RenderMonkey (where I can write pixel shaders executed on GPU).

**Complex Numbers for Game Developers :)**
Fractal is a mathematical concept and so there is lots of hardcore math involved in the foundation of these beautiful objects. But fortunately we don't have to understand all that stuff to be able to render them. Mandelbrot and Julia fractals are created using complex numbers, but for us they can be thought of just as float2/D3DXVECTOR2 2-component (x,y) vectors with some operations defined:

- Addition: (x1, y1) + (x2, y2) = (x1+x2, y1+y2)
- Muliplication: (x1, y1) * (x2, y2) = (x1*x2 - y1*y2, y1*x2 + x1*y2)
- Square: (x, y)^2 = (x, y) * (x, y) = (x*x - y*y, 2*x*y)

That's actually all we need to render Mandelbrot and Julia fractals. The general formula for both of them is: z = z^2 + c where z and c are complex numbers, c is a constant and z is recalculated many times through this function. It was a mystery for me for a long time how to apply this formula. Now it turned out that when we calculate it many times for each pixel with staring z_start = (0, 0) and c dependant on pixel position in range (-2..2, -2..2) and draw all the pixels for which z is bounded and do not go to infinity, we get the shape of the Mandelbrot fractal. Of course we are not going to iterate this function inifinite times in our computers like mathematicians do in their heads, so instead we do it several times and treat all pixels for which length(z_final) < 2 as being "inside" the shape. Here is a draft made in EvalDraw. Unfortunately we meet some limitations of floating point numbers here, like limited precision and infinites and that's why the space outside is white.

To render Julia set we do something similar, but this time we use pixel position as starting z and set c to some constant, like (-0.1, 0.7). Different constants make different images.

A question arises about how to render a fractal - how to map a complex number to pixel color? The algorithm I like the most is called Escape Time Algorith and it goes like this: recalculate z for several iterations, but only while the length of z=(x,y) vector is less than 2 (that is zx*zx + zy*zy < 2*2). If the loop reached the iteration count limit, this pixel is inside the fractal - draw in in black. If not, then color of this pixel depends on number of iterations done.

Here are my implementations of these fractals in EvalDraw and RenderMonkey. They are very simple so the whole source code is visible on the screenshots. You can also download the code here:
Fractals_for_RenderMonkey.rfx,
Mandelbrot_for_EvalDraw_1.kc,
Julia_for_EvalDraw_1.kc,
Multibrot_for_EvalDraw_1.kc.
You can find more screenshots in my
**fractals gallery**.

Some variations of these fractals have also been discovered. For example when we do absolute value of z components before every iteration in Mandelbrot fractal, we get an interesting shape called Burning Ship.

Alternatively, if we raise z to any real power instead of 2, we make Mandelbrot fractal "unfolding", having more and more "bulbs" as the exponent grows. It is called Multibrot set. Raising a complex number to power with any real exponent is a little bit more complicated, as it has to use polar form (HLSL-like pseudocode here):

float2 ComplexPow(float2 v, float n) { float len = sqrt(x*x + y*y); // Standard 2D vector length float n_fi = n * atan2(y, x); return pow(len, n) * float2( cos(n_fi), sin(n_fi) ); // scalar * vector }

Comments | #rendering #math #fractals Share

Copyright © 2004-2021