Monday, January 09, 2012

Mandelbrot fractals

I've always loved fractals... I mean, who doesn't?

Last Wednesday, after watching this video on Vimeo (which I suggest that you check out with your speakers on) I recalled I had written a Mandelbrot set explorer program once on my 386. It was some time ago, back in 1997 I guess. It took me a while back then.

This time I started from this pseudocode provided by Wikipedia's 'Mandelbrot set' page, which implements the so called "escape time" algorithm. You set a maximum number of iterations and do some math. If after those iterations the resulting point still falls very close to the axis origin (0,0) the algorithm will color the point in black. If the point leaves the area, it will instead mark the point using a different color, depending on how many iterations were needed before leaving the origin's surrounding area.

You wouldn't expect to see such amazing images, really.

The program I made starts showing a small area around the origin: from (-2.5,-1.5) to (+1.5,+1.5)... this gives the first image. Clicking on any point of the touchscreen, it will start recalculating a new image, taking the touched point as a new center of the image and zooming in 2x. After 5 clicks you will see for instance what's shown on the second image. Not bad, right?

Then you can press any of the two shoulder buttons to zoom out, or click on the start button to reset the program to the initial setting.

Anyway the Nintendo DS has some limitations. Of course it doesn't feature a superscalar quadcore 2GHz+ processor. It only has a 67 MHz ARM946E, which also has no floating point unit at all, so each operation on floating point variables doesn't turn into a single (co)processor opcode, but into a series of integer operation. So, to keep the image generation time acceptable, I had to limit the number of maximum iterations of the aforementioned algorithm (actually to a very small value: 32). I also had to opt for single precision floating point variables, the fastest choice available.

The following two images show both the limits. After some zooming, you won't see any other color following the 'pink, cyan, green' sequence... and if you keep on zooming in, you'll see that the calculations will start to lose precision, and the resulting image quality will become poor.

Of course I might consider working on a version that increases the number of iterations upon request OR 'when necessary'. I might also consider switching from single precision floating point variables to double precision... or, maybe even better, consider using an arbitrary precision floating point numbers library, such as GMP (The GNU Multiple Precision Arithmetic Library).

Well, let's see :)

In the meanwhile, if you want to play it yourself, you can download the program here.

Fell free to leave a comment about it if you want.


6 comments:

  1. Oh wow, nice!

    I made a mandelbrot renderer for the DS some time ago. Here are some suggestions to optimize it!

    First, you can use fixed-point precision numbers. They're fast as shit because the processor can do operations on them as if they were simple integer numbers.

    Second, you can use this method to skip calculating "flat" areas of the fractal: http://mrob.com/pub/muency/successiverefinement.html

    With both of these, I've been able to get decent generation times (2-3 seconds) with 256 iterations :D

    Dirbaio

    ReplyDelete
    Replies
    1. Thanks for your comment!
      I'll be surely checking the link you provided :)
      About using fixed-point math... well, I also thought about it. The problem, anyway, is that the precision would be very limited since I would need to keep at least 3 bit for the integer part, plus 1 bit for the sign. This would leave only 28 bits for the fractional part and they won't be enough to store a number such as (1/2)^29 for instance, while a single precision variable is able to store numbers like (1/2)^120, thus giving much more zoom chances...

      Delete
  2. Love this ! Would be nice to be able to load tape images (unless I missed this part somehow).

    ReplyDelete
    Replies
    1. Thanks! Unfortunately I'm not really sure I understand what you mean... :(

      Delete
  3. Interesting! It would be great if you continued working on this project, there are far too few homebrews like this out there. I've always been intrigued by fractals, so reading about this new project was fascinating. Keep up the good work!

    Here's a couple of sites your work has already been distributed on:
    http://www.nintendomax.com/viewtopic.php?p=36596
    http://www.dcemu.co.uk/vbulletin/threads/401401-Mandelbrot-Set-Explorer
    http://pdroms.de/nintendods/mandelbrot-set-explorer-09-01-2012-nds-misc
    http://www.ds-scene.net/?s=viewtopic&nid=11646

    ReplyDelete
    Replies
    1. Thanks Nathan! I'm not currently working on this project, but I might return to it later and expand it if I find some good ideas...

      Delete