Re: Accelerating the Buddhabrot with the Metropolis-Hastings algorithm


Steckles wrote:
Hi Guys,

Last weekend, I got to wondering if the Metropolis-Hastings sampling
algorithm (http://en.wikipedia.org/wiki/Metropolis-Hastings_algorithm)
couldn't be used to render zoomed in regions of the Buddhabrot quickly.
Metropolis sampling has been used to great effect in the acceleration
of global illumination ray tracing algorithms, and rendering of small
sections of the Buddhabrot is a very similar kind of problem.

I went ahead and banged out a quick program and was surprised at just
how well it works. It's no more efficient than the "dumb" method for
renderings of the entire set, but will render high magnifications (I've
gone up to 10000x without problems) with little loss of speed.

Rather than select points at random, the program works by finding a
point whose orbit passes through the screen and then sampling nearby
points. New "mutations" to the initial point are proposed and then
accepted or rejected based upon some kind of crazy statistical voodoo.
Many of the parameters (the transition probability in particular) have
been chosen on an ad-hoc basis, and I'm sure that someone with a bit
more grounding in this stuff could come up with better ones.

Anyway, I'm not sure if the Metropolis-Hastings algorithm has been
applied to calculating the Buddhabrot before, although a quick search
on my part indicated that it either hasn't or has not be widely
discussed. I've uploaded a few images and the source for a simple
program in the hopes that someone will find it useful. I'm sure there
are a few lurking buglets in the program, but it should serve for
demonstration purposes.

You can find everything at http://www.steckles.com/buddha

-Alex

Hi Steckles.

Few days ago I discussed with Damien Jones how difficult it is to
compute zoomed images of the buddhabrot... I think your idea is very
nice, and I'm sure you're the first one to try something like this. Now
that you opened the door, you can expect few zooming-in-the-budhabrot
videos in the near future (I just have to finish my works in the
appartment and plug again the computer). Really, very good post.
Regards!

Inigo Quilez

.

Relevant Pages