Tuesday, 17 November 2009

Fractional Fun

(Programs and Mandelbulb screensshots available at the end of the post!)

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:

Large versions: here, here and here.


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. Get that here:
http://connect.creativelabs.com/openal/Downloads/Forms/AllItems.aspx

Winodws:
http://unbirthgame.com/MathFuncRenderer.zip
(Link might change so please do not hotlink)

Linux:
http://unbirthgame.com/MathFuncRenderer-Linux.zip
(Link might change so please do not hotlink)

Mac:
http://unbirthgame.com/MathFuncRenderer-Mac.zip
(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.

http://www.frictionalgames.com/forum/thread-3044.html


44 comments:

  1. This is awesome! You should remove all your ugly architecture in Amnesia and add this fractal 3D thing everywhere ;). It is really beautiful. Your next game should be based on this. I always wanted to play (or make) a game that focus on exploration with unlimited levels that are never same. I will gonna try to make some cool screenshots in MathFuncRenderer. Good job ;)

    ReplyDelete
  2. I am totally astounded, not to mention completely baffled. You used a set of numbers to just...draw the world's most complex illustration?

    Ugh, I suck at math...I'm usually good at understanding the theory, but this is just about going to burst my head wide-open.

    Still, those are some pretty awesome renderings you have there.

    ReplyDelete
  3. /me signs up for the Linux version ;-).

    ReplyDelete
  4. Great Job!
    Waiting for Linux version.

    ReplyDelete
  5. I just updated the program so that the details denhancements are faster and voxel builder more accurate. Screen showing off:
    http://www.unbirthgame.com/files/DesertValley.jpg

    As for linux version, Edward has it working so should be shortly!

    ReplyDelete
  6. Where is the linux version? Is the source code available?

    ReplyDelete
  7. Linux version should come today or tomorrow.

    Source code will not be available, but all shader code is easy to play with and the algo is described here:
    http://www.gamedev.net/community/forums/topic.asp?topic_id=553643

    ReplyDelete
  8. is this open source btw?

    ReplyDelete
  9. I've been playing for hours and hours. Thanks so much for writing this app because I had no idea how to even start after reading the original text on the mandelbulb.

    At this point I'd kill for a 'save' feature that saves the current camera location and the state of the rendering parameters. If you're not too busy. :)

    ReplyDelete
  10. Glad to hear you enjoyed it!!

    I will try and fix a new version this weekend. Have some ideas on how to speed up the thingie and also add few tweaks to generate nicer colors! Will post a new entry when I have new version done (as well as the linux and mac ones). So subscribe it to your RSS feed to know when new stuff is up :)

    Also, if anyone else has suggestions: Post and I will see what I can do!

    ReplyDelete
  11. Looks wonderful; a Mac version would be appreciated.

    ReplyDelete
  12. I tried to run the program, but it just gives me this "Windows Error" :(
    In the hgl.log there are no error or warning, the window comes up without a title and then error - closed.

    Is a 8800GT too old for this shaders to work ?

    ReplyDelete
  13. Sven:
    The only thing I can think of is that u might need to update your graphic card drivers. Go to the Nvidia site, download and install. The 8800GT should work fine!

    ReplyDelete
  14. Thanks for the Tip, my GPU-Driver only had Cuda 1.x something, I updated and now I am surfing the bulb :) Sweet

    Thank you sooo much for making such a wonderful program.

    If my job wasn't so stressful I might had time to learn all this CUDA, which seems pretty sweet, definitly reading up on it now.
    I'm stuck in Java-World at the moment (databases and enterprise solutions ... crap), time to dust off the C++ books.

    ReplyDelete
  15. awesome, hoping for a Linux version since my win machine is a 1.7Mhz laptop while my main machine is a i7 920 running 64bit Linux Mint

    ReplyDelete
  16. Check out this little mod. It looks best in voxelBuliding mode.

    //float fPhiCos = cos(fPhi);
    float fPhiCos = cos(fPhi/fR);

    The world it creates is immense, I've been exploring for hours.

    ReplyDelete
  17. Mac version would definitely be great. Thanks for sharing this exciting tool!

    ReplyDelete
  18. +1 for the linux version !
    It's an amazing discovery this 3D mandelbrot by Daniel White.

    ReplyDelete
  19. WOW Nice.. Another request for a linux version here.
    Or the source under some useable licence and I'll help make a linux version.

    ReplyDelete
  20. Thanks for the Linux version! Unfortunately, it's too slow to even use on my computer. I couldn't get movement controls nor menus to respond. Lots of lag between the rendered mouse pointer and my actual pointer. Oh well, I'm sure it will improve in the future. Keep it up!

    ReplyDelete
  21. gruppler:
    The the algo is very demanding and the SSAO used is on maximum quality, which is quite expensive. Try opening the cfg file and turn down resolution to 640x480 or something and it might work better.

    ReplyDelete
  22. I was so excited about the Mac version, but unfortunately I doesn't work at all. I directly quits after starting the app. Anyway, thanks for your efforts...

    ReplyDelete
  23. Check the log and see what it says. What graphics card do you have?

    ReplyDelete
  24. Thomas,

    I have a Nvidia GT120. I've already seen that esp. Nvidia cards cause trouble. Here's what the log says:

    dyld: Library not loaded: @executable_path/../Frameworks/SDL.framework/Versions/A/SDL
    Referenced from: [...]MathFuncRenderer.app/Contents/MacOS/MathFuncRenderer
    Reason: image not found
    Trace/BPT trap

    Thanks for your help!

    ReplyDelete
  25. Looks awesome yes, but it crashes on startup, gets the error message: "MathFuncRenderer.exe has encountered a problem and needs to close. We are sorry for the inconvenience." I have a HP Laptop with AMD turion 64 X2, NVIDIA GeForce Go 7600, 2 GB of RAM and Windows XP Media Center Edition Version 2002 Pack 3. I don't know if the graphics card is ShaderModel 3 capable.
    Is this the most likely problem?

    Best regards
    Hans Jakob

    ReplyDelete
  26. Hans:
    Check the hpl.log that is created, there should be a line that says:
    ShaderModel 3: 1
    if shader model 3 is created.
    Also make sure to update your graphic card drivers and install OpenAL:
    http://connect.creativelabs.com/openal/Downloads/Forms/AllItems.aspx

    ReplyDelete
  27. To update the graphic card driver did the trick. And it's still awesome! But it's still slow, not the Open GL render, it's not smooth but gives a nice preview and a good navigation feel for such complex objects as a mandelbulb. It's the user interface that is slow, much slower than on your demo movie above. Maybe it's my machine, I'm going to try it out on my professional 3D workstation at work some time soon. Some first impressions: The close button does not work, not even the force quit with ctrl/alt/delete. The first few times I had to restart the computer to make the program quit until I discovered that the esc-button did the job. But then I had made some changes to the lighting and they were gone when I restarted the program. It would be nice if it could save or remember settings from previous sessions! Resizing the window with the cfg-file was easy. One thing I'like to see is an orbit function, around the center or maybe around a chosen part of the object. It's easy to see that the program has great potential, taken into consideation that the mandelbulb has been around for a couple of months. I'm really looking forward to coming versions, maybe with shadows, (ambient occlusion?) more formulas etc. I'w been a betatester for XenoDream almost since the beginning (It's got Juliabulbs in the latest beta, but has some serious limitations). If you need a betatester for MathFuncRenderer I'll happily do my share.

    Best regards

    Hans Jakob

    ReplyDelete
  28. Wow, this is great! You just navigate to an interesting area, you sit back and the program start detailing, beautiful details... Be sure not to move the mouse because you're still in navigation mode (a bit confusing, getting used to?) When you do, some of the details are lost, but not nearly all, and it continues from a higher level. I can't help asking, will it continue detailing forever if I don't interfere? After some time smooth areas are substituted with new shapes and texture, but there are also some color banding (shades of gray) in certain areas and also some flat relatively uninteresting areas that seems to lay themselves on top of previous details. Will these go away in the end replacing details with higher resolution ones? And what is the difference between the detail created with voxel building and those I get from just waiting in raytrace mode? I suppose a manual does not exist yet, but maybe later?

    ReplyDelete
  29. Hans:
    Thanks for the feedback and to make the menu faster, try turning off the SSAO. When I have time to update the program I will try and do the stuff u requested!

    Anonymous:
    Voxel is slower but can give more details since it uses more iterations in the alogrithm.

    ReplyDelete
  30. The Mac version crashes at launch.
    Looking the report I found it was missing the SDL.framework inside the bundle, so I grabbed it from another application. Now it works.

    ReplyDelete
  31. Thanks for your effort, but it crashes on my 64-bit debian

    Inconsistency detected by ld.so: dl-open.c: 643: _dl_open: Assertion `_dl_debug_initialize (0, args.nsid)->r_state == RT_CONSISTENT' failed!

    Matthias

    ReplyDelete
  32. Hi everyone at Frictional Games!!!! First of all, my congrats for this fine piece of automated surrealistic horror generator :D

    I would like to suggest you 3D views of 4D objects as another interesting geometric construct to explore. What do you think?

    ReplyDelete
  33. Thomas, any chance for one of the following?
    1. A universal binary build for OS X, rather than x86 only
    2. or the source released under some licence, so we can get it compiling under OS X / PowerPC

    With most of the number crunching done in shader programs, it should not take rocket science to get your techdemo up and running on non-x86 architectures that have SM3.0 compatible GPUs.

    Cheers,
    IBelanszky

    ReplyDelete
  34. IBelanszky:
    Cannot promise anything. I am not the one building the mac versions and we hard at work with the game at this point, so not sure there will be any time Im afraid.

    Perhaps a lil later!

    ReplyDelete
  35. Thomas, have your time, and thank you in advance. Whenever the time comes, and in case your OS X build maintainer has no experience with PowerPC, I would gladly supply a few proven and solid suggestions.

    - On ppc64 architectures 64bit binary performance is impacted by a small overhead, so unless your code massively uses double-width precision ops it is preferable to provide a single 32bit ppc binary for all "G4"/"G5" Macs.

    - Only SIMD-equipped (Altivec/VMX) ppc Macs can have SM3.0 compatible GPUs, and unfortunately only a small part of them actually has such a GPU (PS2.0 is more widely available). What I am getting at is, there is no need to build for very obsolete ppc targets (601-750), because GCC creates even more crappy binaries for them than for recently obsoleted 74xx-970 CPUs -- compiler auto-vectorization and advanced code optimizations only take a couple of compiler flags to enable and provide 25-75% extra performance without any code change, when heavy number crunching is involved.

    - For ppc architectures with Altivec/VMX SIMD units, the best free compiler to use under OS X is powerpc-apple-darwin9-gcc-4.0.1, part of XCode 3. Later versions of XCode (like 3.1.4 and 3.2.x) use a more recent GCC that no longer contains Apple's proprietary ppc+Altivec auto-vectorization patches or even the ppc64+VMX stuff contributed to vanilla GCC by IBM, but provides better support for 64bit x86, so it was a fair trade-off for Apple due to the intel transition.

    - Apple's auto-vectorization in their own version of GCC 4.0.1 can be enabled by the cflag "-fast" (ppc64+VMX only) or "-fast -mcpu=7450" (any ppc+Altivec/VMX); binaries resulting from the latter are compatible with all 74xx-970 ppc Macs (even the earliest XPC7400). Basically, if you don't want to change a single line of your code, and it already compiles for OS X / PPC, this is the way to get the best performance. For non-math-heavy code "-Os -mcpu=G4" is very safe to use and is still much better than "-O2", but given that Altivec/VMX can also accelerate memory ops, string matching and so on I suggest "-fast -mcpu=7450" to be used generally, resorting to "-Os -mcpu=G4" only in the unlikely case of some code getting broken by aggressive auto-vectorization.

    - You can have XCode 3 and a more recent version concurrently installed on your OS X build box, see XCode release notes.

    - If you always build inside the XCode IDE, see the following two dox on enforcing specific cflags rather than just flipping the "Autovectorization" and "Universal Binary" switches on the XCode 3 build panel:
    http://cocoawithlove.com/2008/06/hidden-xcode-build-debug-and-template.html#compilersettings
    http://developer.apple.com/mac/library/documentation/DeveloperTools/Conceptual/XcodeBuildSystem/300-Build_Settings/bs_build_settings.html#//apple_ref/doc/uid/TP40002691-SW3

    Best Luck with your project,
    Istvan Belanszky

    ReplyDelete
  36. How do I run this under ubuntu? Im a noob at linux.
    Windows version works for me well, Ive spent hours in front of my PC.

    ReplyDelete
  37. Works on Linux, thanks.
    VoxelBuilding does not seem to work... displays just the background.
    Another issue is it renders details but then seems to reset and starts over again...
    http://omploader.org/vNGMzaQ (sry for bad quality)
    Window was even inactive so no input events from me.


    Will you make it use OpenCL?

    Also screenshot is not really working. First time it segfaulted, second time it just freezed (and took input focus with it).

    ReplyDelete
  38. Mac version crashed for me too, but I fixed it. Previous comments do not explain the fix in adequate detail, so here we go:

    Select "MathFuncRenderer.app", and Show Package Contents. In Contents/Framework there is a "SDL_ttf.framework" but this is the wrong name -- the program is trying to link to "SDL.framework" so it crashes with the "com.frictionalgames.MathFuncRenderer ... dyld: Library not loaded..." message.

    Rather than try to rename the SDL_ttf, which would probably not work, go to http://www.libsdl.org/download-1.2.php and download SDL-1.2.14.dmg then open it, then copy the "SDL.framework" folder to the same place where the "SDL_ttf.framework" is (so now there are two SDL frameworks, alongside ALUT, Ogg, Theora and Vorbis). Now you can close the window that was opened by Show Package Contents, and "MathFuncRenderer.app" will actually launch. Imagine that.

    Also, as reported elsewhere, the "Quit" menu command does nothing, and "readme.txt" gives no hint. USE THE ESCAPE KEY.

    ReplyDelete
  39. Hello, fascinating reading, any, absolutely any way this can workl on a mac intel with snowleopard ??,
    would be wounderfull
    thank you
    hansi

    ReplyDelete
  40. Installed the MathFunction Renderer on my HP CQ50 Notebook PC with Intel Graphics Media Accelerator Driver for Mobile. Unfortunately, it doesn't run, saying it couldn't open the OA. Any clues? I'd appreciate some hints. Thanks.

    ReplyDelete
  41. You might want to edit the link to the forum post at the end of the post; it currently links to an irrelevant thread titled "Humble bundle serial".

    ReplyDelete
  42. What's a valid login for the creativelabs site to dl OpenAL ?

    ReplyDelete

SiteMeter