Print Page - Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark

Title: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: ker2x on October 21, 2017, 02:10:39 PM

Friendly greetings !

Over the year and with your help i developed some formula to help quickly rejecting point that are "for sure" (as far as we know?) inside the Mandelbrot set.
Thank you my new software i'm developing and it's super awesome pipeline architecture i can do easy benchmark of formula and know the performance of each stage.

benchmark at 20000 iteration on standard buddhabrot :
with full quick rejection filtering : ~220 full orbit per ms.
without filter : ~13 !

with main cardiod filter only : ~57
with main left bulb filter only : ~15 (this one is pretty much useless at low iteration)
with 2nd left bulb filter only : ~13 (same)
with smaller bulb on top and bottom of cardiod : ~13 (same)
with all bulb, except main cardiod : ~16

each builb filter may not add much but the effect is cumulative.
The numbers a kind of weird but the app is heavily multithreaded (more thread than available core) so by having to do more full iteration test i'm starving my other threads with a huge bottleneck on the full iteration test.
Also, my pipelined thread architecture have a significant overhead so the numbers are not perfect, but it show a significant performance improvement anyway.

for more accurate number i leave it to you to develop single threaded app. 88)

The full code ("continue" mean the point is reject because it's in the set):

Code:

         public static void quickRejectionFilter(BlockingCollection<Complex> input, BlockingCollection<Complex> output)
         {
            foreach(var item in input.GetConsumingEnumerable())
            {
                if ((Complex.Abs(1.0 - Complex.Sqrt(Complex.One - (4 * item))) < 1.0)) continue;
                if (((Complex.Abs(item - new Complex(-1, 0))) < 0.25)) continue;
                if ((((item.Real + 1.309) * (item.Real + 1.309)) + item.Imaginary * item.Imaginary) < 0.00345) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary - 0.744) * (item.Imaginary - 0.744)) < 0.0088) continue;
                if ((((item.Real + 0.125) * (item.Real + 0.125)) + (item.Imaginary + 0.744) * (item.Imaginary + 0.744)) < 0.0088) continue;

                //We tried every known quick filter and didn't reject the item, adding it to next queue.
                output.Add(item);
            }
         }

The stage after this one simply is the full iteration check. (iterate until it reach max iteration of leave the 2.0 radius).

I'll publish the full code of my app soon(c)(r)(tm)

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: ker2x on October 21, 2017, 02:22:11 PM

with 2 million iteration :
full filter : 3.1 orbit/ms
no filter : 0.15 orbit/ms

But this test is kind of messed up. i don't have an automagic thread scheduler / pipeline balancer yet.
If i add more thread for the later stage because of the high iteration :
full filter : 10 orbit/ms
no filter : 0.4 orbit/ms

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: ker2x on October 21, 2017, 02:35:00 PM

And for the fun of it, if i remove the iteration test and only leave the quick test, i have some kind of odd incomplete anti-buddhabroth.
running at around 1000 orbit/ms for 2000 iteration.

(https://i.imgur.com/QSPYumv.jpg)

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: claude on October 21, 2017, 06:17:35 PM

https://mathr.co.uk/blog/2014-11-02_practical_interior_distance_rendering.html shows how to do general interior checking. the "biased" method is a big speed improvement, but relies on the previous pixel being "nearby". my (anti-)buddhabrot renderer renders lots of randomly oriented pixel grids, so that it can use the "biased" interior checking method for each grid. it doesn't do zooming efficiently however.

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: ker2x on October 21, 2017, 07:34:16 PM

Thx for the link. i did a quick read and didn't really understood it but i'll check it again tomorrow.
I'll keep it as a future possible improvement. I have a lot more to implement, mostly the Metropolis–Hastings algorithm which i don't really understand but is implemented anyway in another software i co-developed and it's going to give me some headache for sure :D

If i remember correctly (it old code i copy/paster over the years) the filters i posted here aren't perfect, they are very conservative and don't take any chance of false positive.
They could be better and still have 0% of false positive.

Also, you probably noticed it's a mix of complex computation (with native complex support) and "decomplexed" computation (for language with no support for complex).
An ugly patchwork i'll have to fix.

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: ker2x on October 22, 2017, 06:03:38 AM

Another filter i have is rejecting orbit that escape before a minimum iteration.
I compute a ration of rand/orbit ratio.
with "orbit" being a point that passed all filter and is now considered an interesting orbit fit for display.

with a max iteration of 2000.
min of 2 : ratio is 1.33
min of 5 : ratio is 3.42
min of 10 : ratio is 13.07
min of 25 : ratio is 47.7
min of 50 : ratio is 107
min of 100 : ratio is 233
min of 200 : ratio is 500
min of 500 : ratio is 1500
min of 1000 : ratio 4800 (EDITED, i got the last number wrong so the graph below is wrong for the last number too)

(https://i.imgur.com/gpFH8ed.jpg)

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: Adam Majewski on October 22, 2017, 08:00:40 AM

Quote from: claude on October 21, 2017, 06:17:35 PM

Here is also method based on the derivative :
https://www.math.univ-toulouse.fr/~cheritat/wiki-draw/index.php/Mandelbrot_set#Interior_detection_methods
https://gitlab.com/adammajewski/mandelbrot_wiki_ACh

HTH

Title: Re: Quick (non iterative) rejection filter for mandelbrot/buddhabrot with benchmark
Post by: Chris Thomasson on October 23, 2017, 07:49:24 PM

Have to try this out: Thank you for posting it. O0

Fwiw, remember having trouble zooming in on a Buddhabrot I did:

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=17279

I needed to compute the whole damn plane instead of just my zoomed viewport. Here is an example of a zoom:

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=17288

The detail in the main bulb gets cut off because I am not iterating the field lines that are not within the view port plane.

Welcome to Fractal Forums

Fractal Math, Chaos Theory & Research => (new) Theories & Research => Topic started by: ker2x on October 21, 2017, 02:10:39 PM