{"id":296,"date":"2012-02-11T15:13:43","date_gmt":"2012-02-11T14:13:43","guid":{"rendered":"http:\/\/jaran.de\/goodbits\/?p=296"},"modified":"2012-02-14T21:50:32","modified_gmt":"2012-02-14T20:50:32","slug":"rendering-a-gigapixel-buddhabrot","status":"publish","type":"post","link":"http:\/\/jaran.de\/goodbits\/2012\/02\/11\/rendering-a-gigapixel-buddhabrot\/","title":{"rendered":"Rendering a Gigapixel Buddhabrot (Part One)"},"content":{"rendered":"

This is a followup to my What is a Buddhabrot anyway?<\/a>-post where I only described the mathematical backgrounds of the Mandelbrot Set and its relationship to Buddhabrot renderings. This post will describe how I actually created the images.<\/p>\n

As described in the linked article above one needs to find such points for which the Mandelbrot iteration becomes unbounded. Then one draws each point of such an unbounded iteration, repeats that for lots of other points and gets a Buddhabrot.<\/p>\n

While the words sound easy enough, there are certain problems: how does one know that an iteration becomes unbounded when unbounded basically means that “it never ends up somewhere”. And then how do we find those interesting points and moreover lots of them within a lifetime?<\/p>\n

Luckily it has been found out that if the continued iteration results in points that are farther than 2 units away from the origin of the coordinate system, that this iteration is unbounded. That means that if we started with a point that leads to an unbounded iteration we will sooner or later know it and can stop iterating.
\nHowever, if we started with a point that leads to a bounded iteration it will never lead to points farther than 2 units away from the origin and if we don’t stop using some other criterion we will have an infinite loop. This other criterion is quite simple: set some maximum iteration count and whenever you exceed it consider the iteration bounded and thus not interesting for the Buddhabrot rendering.
\n
\nWith those ingredients in mind one can now start evaluating different starting points, check if those points will “escape” within a certain amount of iterations and if they do so use them (and their eventual escaping orbits) to draw the Buddhabrot.<\/p>\n

Additionally we also want to only look at such points that don’t escape “too early” but do create longer orbits that may or may not be more interesting than an iteration that “flies out of the picture” after just a few steps.<\/p>\n

So I wrote a simple Java program, started it and waited for interesting orbits to come out. And they came… one by one… very slowly… too slowly…<\/p>\n

A simple approach<\/h2>\n

And with “simple program” I meant that it basically did the following: start with a random point, Mandel-iterate it, hope it escapes (then draw it’s Mandel-orbit if it has a minimum length) and if it doesn’t escape after a million iterations: throw it away. Then go on with some other random point.<\/p>\n

Before trying to think of algorithmic optimizations friends I chatted with at the time offered their CPU cycles and even some kind of “who finds the most orbits”-challenge broke lose. And why not? So the next step was to create a distributed computing project out of it.<\/p>\n

Distributed computing<\/h2>\n

Since all the simple algorithm did was selecting random points and calculating their orbits all that was necessary to do was to setup a simple data collecting website that was called from the distributed orbit collector programs whenever an interesting orbit was found and store the results in the database.<\/p>\n

So what happened next was that a multi-threaded client was handed out to several friends that sent results into a database on my server via some simple PHP website.<\/p>\n

At the same time the first algorithmic improvement was made: since the Mandelbrot sets most prominent visible features, its body and its head are of simple geometric nature one could easily check if the chosen random starting point lies within those features. If that was the case the starting point was thrown away because we know that all points within the Mandelbrot set lead to bounded iterations and are therefore not interesting for the Buddhabrot.<\/p>\n

The distributed approach worked wonderfully and hundreds of interesting orbits poured in. This resulted in the first experimental renderings. However, to draw a Buddhabrot in the gigapixel range some more results were needed and somehow I suspected that rather than using brute force (that is CPU cycles) maybe some algorithmic improvements would help.<\/p>\n

A more intelligent search<\/h2>\n

So when the results from the distributed version came in I exported them into a spreadsheet and just drew those points and not their orbits. The result was astonishing:<\/p>\n

\"high<\/p>\n

With a bit of thinking it became less astonishing and more clear though: within the Mandelbrot set we have a bounded iteration and thus uninteresting starting points. However, the farther we move away outside the faster the iteration will escape and thus become uninteresting too because we want orbits that do have a certain minimum length. And quite clearly as this reasoning and the graphics suggests: the most interesting values are just on the border between being inside or outside the Mandelbrot set.<\/p>\n

So a more intelligent approach would be to not just use random starting points and check those but instead to use points that are near but still outside of the border of the Mandelbrot set. The problem with that border is: due to the fractal nature of the set it is infinitely long. So how to find good starting points on a border that is infinitely long but hence also “infinitely thin”?<\/p>\n

My approach was to put a mesh over the coordinate system, dividing it into a multitude of cells. Then for each cell I checked if the four corners are either all inside or all outside the Mandelbrot set. If that is the case then I considered the cell to be not interesting and went on with the next cell so that in the end I had a list of cells where at least one corner was within and one corner was outside the Mandelbrot set effectively meaning that the border line went right through the cell.<\/p>\n

The following diagram visualizes the whole concept:
\n\"finding<\/p>\n

This is of course only an approximation as it doesn’t find all cells that contain the border. Just look at the leftmost cells in the left diagram above: the border line “sneaks in or out” on one of the sides of the cell and leaves or comes back on the same side without any corners being “on the other side”. Additionally some cells are also mostly inside or mostly outside. By reducing the cell size the approximation can be improved (see right part of the diagram) and absolute exactness doesn’t matter anyway as we don’t need all cells that contain the border but only want to find better starting points to replace the purely-random approach of before.<\/p>\n

Choosing a small cell size I pre-calculated a list of interesting cells and used random starting values only from within those cells. That basically sped up the process of finding interesting orbits by a factor of more than 100 and made the distributed computing approach superfluous. Or so I thought, because now I could increase the maximum iteration length before giving up and considering a sample to be uninteresting to a couple of millions.<\/p>\n

Rendering<\/h2>\n

So finally I had a database full of starting points of which I knew that they had some minimum length and that they would in time become unbounded and thus be fit for the Buddhabrot. So now the evolution went basically from choosing points at random to choosing points from within “interesting” cells to now finally grabbing points of a database of known “good” points. Their orbits were drawn into a 16-bit map and then exported as a PNG file to be coloured in an editing program.<\/p>\n

The details, the program code, will be made available in a follow-up to this post some time later. In the meantime here’s a rendering of an orbit that took more than 8 million steps to finally escape:
\n\"the<\/p>\n

Not very pretty alone but in conjunction with many more of such orbits and some colour and contrast editing one can get pictures like this:
\n\"a<\/p>\n

That being said I still haven’t found the “perfect” rendering that I want to print out in poster-size and hang up my wall. I still need to work on the post-processing, especially in bringing out details with more contrast.<\/p>\n

Anyway, the next Buddhabrot post will contain actual code and maybe some statistics.<\/p>\n","protected":false},"excerpt":{"rendered":"

This is a followup to my What is a Buddhabrot anyway?-post where I only described the mathematical backgrounds of the Mandelbrot Set and its relationship to Buddhabrot renderings. This post will describe how I actually created the images. As described …<\/p>\n

Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[27,5,8,9],"tags":[],"_links":{"self":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/296"}],"collection":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/comments?post=296"}],"version-history":[{"count":15,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/296\/revisions"}],"predecessor-version":[{"id":362,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/296\/revisions\/362"}],"wp:attachment":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/media?parent=296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/categories?post=296"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/tags?post=296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}