Fractional Fun

Some links in this article have expired and have been removed.

This blog post will not be totally game related, but more about the engine and a recent obsession of mine. Do not fear though! It should hopefully still be interested and I will also provide some nice images! Hopefully it will also be able to evoke a sense of wonder too. Read on to find out!

Ten years or so ago I wrote a paper for school about Fractals. These constitute a large variety of objects but what they all have in common is that they have several levels of self similarity. Nature consists of tons of fractals, for example trees and mountains. In games the term fractal landscape was quite common at time and was a way of generating terrain. Although not heard of as much today it is still a part of game making. Below are some examples of fractals, note how the same type of shape appears over and over again:

Now, while doing the paper for school I came across a weird thing called the Mandelbrot Set. This is a certain function that when iterated and mapped (drawn to screen) creates a fractal. The function for the set is very simple and is based around this formula:

N(0) = c
N(n+1) = N(n)^2 + c

What this means is that one starts of with a number c, then multiply by itself and finally add c to get the next number in the sequence. If done with normal numbers, one gets something like this:

1 + 2 + 5 + 26 + … and so on towards infinity

However, there is a twist to this formula when creating the Mandelbrot set, instead of using a normal number for c, a complex number is used. A complex number has a real and imaginary part and is written like this: c = 3 + 2i (the imaginary parts gets i behind it). When using the above formula on a complex number, it gets slightly more complicated and is (kinda) analogous to a 2d vector being rotated by itself.
Now, to get the Mandelbrot set, one “simply” checks if a certain c makes N go toward infinity or not. If it it does not, then it is part of the set. In practice one just iterates (does the same thing over and over) the formula a fixed number of times and see if it has reached a certain limit value. If it has it is said to be not part of the set.

Hopefully the math part made sense and was not too boring, but I felt it was needed for full understanding of what makes the Mandelbrot set so amazing. And to see why it is amazing one has to visualize it. This is done by letting c be a point on the screen where the x coordinate is the real part of the y coordinate the imaginary. Then one colors the pixel black if it is part of the set, and if not color it depending on how many iterations it took to reach the limit value. Doing so will generate this picture:

I gotta say that that is a pretty damn detailed picture one gets from just iterating some boring function! If someone had just shown me the formula I would never have guess it could produce such a wonderful result!

It gets even better still! If one zooms in on this image, the details just keep coming and they never repeat! As with the other fractals same kind of shapes return again and again, but never in the exact form. The beauty of it is breathtaking! Here are some examples of zoomed in parts:

When I made my own Mandelbrot program I could not stop searching the set. It felt like I was exploring some kind of alien world and it feels so weird that such a simple formula can create a cosmos of infinite detail. If you want to explore it yourself, here is a pretty nice web application for just that.

Fast forward to present day. Last Friday Luis sent me a link to this page of someone who managed to create a 3d version of the Mandelbrot set. Naturally this was irresistible for me and inspired by the works of Iñigo Quilez (I had his presentation “Rendering World with Two Triangles” as a reference throughout this project) I set out to create a real time application that could explore this world .

My idea was to use some kind of ray tracer to render out depth, then use that depth to generate normals and just plug that into the deferred shader and let it add ssao, nice light and fog. I thought about this for a while and came up with the idea to use the same method as when rendering high quality parallax. This technique is called relief mapping and works by first making a rough linear search for an intersection and then a binary search to pin the exact location down. Hopefully this would prove fast enough to do a nice 3D Mandelbrot in real time! What I ended up with was an algorithm that could render arbitrary mathematical functions, so I tested this on some functions and got pretty nice results:

Some metaballs rendered and animated. This is not the fastest way to do this, but proved that stuff worked!
Here is an animated “Sine Landscape” that is just a bunch of sine curves added together.

What was left now was to attack the Mandelbrot set! The formula for getting hold of the 3D version is a little bit different from the 2D one and is not really THE 3D Mandelbrot either, but it surely the closest I have seen! It was discovered by Daniel White and works by using spherical coordinates. Remember how I said that the 2D Mandelbrot formula was kind of like rotating a vector by itself. Well, in the 3D version one rotates a 3D vector around itself by using spherical coordinates instead of polar (skipping formula, but if anyone is interested I can give more details!). Also, to make it look good in 3D, one has to have a power of 8 in the formula, meaning that one spins the coordinate around by itself 8 times!

It took quite some time get this working as the 3D-card did not do what I want to and so on. But finally I got it all working and boy was it worth it!!! Here are some screens:

At the edge of a hole. Perhaps some strange creatures live in those burrows?
This is a 3D version of a Julia set! Looks like some alien space ship flying through the vacuum.

Once I got this far I could not stop using it! It was so much fun exploring the weird world of the 8th degree Mandelbrot fractal! Because of some limitations in the ray tracing method I added a new version of the renderer that builds up the image in slices and can use a lot more iterations when checking if it is in the set or not (more iterations = more details). It is slower, but creates more details in the images and it is fun to use it when one discovers some extra interesting shape and want it enhanced. Here is a video of me exploring the set:

Now the best of all this is that YOU can explore this strange world yourself! To do so, just download the MathFuncRenderer and get going!

(ShaderModel 3 capable card required) Windows, Mac and Linux version below.
Note that you need OpenAL installed for it to run.

(Link might change so please do not hotlink)

EDIT 26.11.2009: A Linux version of the MathFuncRenderer has now been built and uploaded!

All this has been possible because of our Edward Rudd who makes all porting for Frictional Games.

(Link might change so please do not hotlink)

EDIT 27.11.2009:

Finally, to end our fractal-odyssey, the MathFuncRenderer has come to Mac!

As with the Linux version, Edward Rudd is that man behind the port.

(Link might change so please do not hotlink)

(Also note that because of some nvidia driver issues in OSX, some nvidia card will not work properly, 7300 GT on leopard is known and there might be more.)

I am very anxious to see what kinda of strange pictures you all can take so have opened up a post for this in the forum. I have already posted more of my own images there.