Zbiór Mandelbrota - przyspieszanie działania

0

Dzień dobry
Ostatnio poczytałem trochę o fraktalach i chciałem sobie klepnąć programik programik który generowałby takowe. Natrafiłem na problem w postaci czasu generowania obrazu. Czy istnieje jakaś szybka metoda wyznaczania granic funkcji rekurencyjnych dla liczb zespolonych ? Teraz po prostu iteruje z jakimś tam swoim przybliżeniem i sprawdzam czy punkt należy do zbioru (tz. jak chcę obrazek fraktalu 600x600 to jest for(i=0;i<360 000) i liczę czy punkt leży w zbiorze dla danego piksela). Aktualnie sytuacja wygląda tak:

 /* Contains */

            ComplexNumber z = new ComplexNumber(realPart,imaginaryPart);

            for (int i=0;i<accuracy;i++)
            {
                if(z.ModulusSquare >= 4)
                    return false;
                z.SquareIt();
                z.Add(realPart,imaginaryPart);
            }

            return true; 
  Bitmap image = new Bitmap(size.Width,size.Height);
            BitmapEditor editor = new BitmapEditor(image);

            editor.LockBits();
            //Main fractal iterations
            for (int iter = 0; iter < accuracy; iter++)
            {
                ProcessAccuracyLayer(ref image,iter,area,editor);

                if (RenderCompleteCall != null)
                {
                    RenderCompleteCall(iter);
                }
            }

            editor.UnlockBits();

            return image;

Tutaj: "ProcessAccuracyLayer"

  Position coordinate;
            Size imgSize = new Size(img.Width,img.Height);
            UnitConverter converter = new UnitConverter();

            // real & imaginary (width/height) iterations on complex plain
            for (int r = 0; r < img.Width; r++)
            {
                for (int i = 0; i < img.Height; i++)
                {
                    coordinate = converter.ConvertToPlainPoint(area, imgSize, r, i);
                    if (Contains(new ComplexNumber(coordinate.X, coordinate.Y), iteration))
                    {
                        editor.SetPixel(r, i, _colorPalette.GetColor(iteration));
                    }
                }
            }

Czy da się to zrobić innym sposobem - czytałem artykuły o generowaniu zbioru i niestety nic nie znalazłem.

Pozdrawiam
Astrocyt

1

Sprawdź czy taka szybkość Ci odpowiada. http://bogdan.students.wmi.am[...]tion/fraktale/Mandelbrot.html
To jest aplet Javy, musisz mieć zainstalowaną Javę i zezwolić przeglądarce na uruchamianie apletów.
Jeżeli Twój kod działa bardzo wolno, to pewnie masz za duża wartość zmiennej accuracy (obliczasz zbyt dużo wyrazów ciągu).

1

Wykorzystaj CUDA/OpenCL, to idealny przykład.

2
  1. zła kolejność pętli iterowania po pikselach. Skaczesz ciągle po różnych fragmentach pamięci co powoduje częsty cache miss i prowadzi do bardzo dużych problemów z wydajnością. Sama zamiana tych pętli poprawi znacznie wydajność
  2. Wyciągnij te new tak by nie było tworzone na nowo dla każdego pixela, a również uzyskasz poprawę wydajności.
0

Wywaliłem new ComplexNumber(...) i działa tak na oko o 35-40% szybciej więc jest dużo lepiej.

@MarekR22

Mógłbyś rozwinąć o co chodzi z tą złą kolejnością iterowania i skakania po pamięci ?

Cała klasa BitmapEditor pochodzi z tej strony : http://www.codeproject.com/Ti[...]ith-bitmap-faster-with-Csharp
I jeszcze mam takie pytanko. Czy zamiana zmiennych w pętli na wskaźniki i ogólnie zrobienie całej klasy MandelbrotSet na wskaźnikach (wszystkie zmienne) dadzą poprawę wydajności czy to już będą cuda na kiju ?

Dziękuję za pomoc.
Pozdrawiam
Astrocyt

3

Profiler. Serio. NIGDY nie próbuj optymalizować "na jana". Odpal profiler i zobacz co zabiera tyle czasu. Zaoszczędzisz sobie troche czasu, nerwów i pieniędzy które przepuściłbyś u wróżbity macieja.

1
Astrocyt napisał(a):

Mógłbyś rozwinąć o co chodzi z tą złą kolejnością iterowania i skakania po pamięci ?

To proste, dostęp do pamięci odbywa się z pomocą cache, który jest bardzo szybki. Jeśli procesor odnosi się do pamięci sekwencyjnie lub w ramach małego fragmentu pamięci (zwykle jest kilka takich fragmentów pamięci) to cache jest wykorzystywany optymalnie co znacznie przyspiesza aplikację.
Bitmapy są zorganizowane w ten sposób, że pojedynczy wiersz (y) jest jednym ciągłym kawałkiem pamięci, w którym znajdują się kolejne piksele dla kolejnych wartości x. Jeśli wewnętrzna pętla iteruje po x, to program częściej odnosi się do kolejnych komórek pamięci, więc zalicza mniej cache miss i aplikacja będzie działać szybciej.

1

z.SquareIt();
z.Add(realPart,imaginaryPart);

Nie licz na liczbach zespolonych. Traktuj je jako parę liczb (x+iy) i z tej postaci wyprowadź dwa wzory, ile wynosi nowe x i nowe y.
W ten sposób wykonasz mniej działań w każdej iteracji.

Jeżeli

z := z^2+c\qquad z, c\in\mathbb{C}

to

(x+iy) = (x_z+iy_z)^2+(x_c+iy_c)

wymnażasz pamiętając że i^2=-1 i wyciągasz x i y.

0

Dzięki wielkie. Prędkość wyznaczania znacznie wzrosła. Na koniec (ktoś może kiedyś będzie szukać czegoś podobnego) napiszę w skrócie o zmianach.

 for (int i = 0; i < img.Height; i++)
            {
                for (int r = 0; r < img.Width; r++)
                {
                    coordinate = converter.ConvertToPlainPoint(area, imgSize, r, i);
                    if (Contains(coordinate.X,coordinate.Y, iteration))
                    {
                        editor.SetPixel(r, i, ColorPalette.GetColor(iteration));
                    }
                }
            }

Tak jak pisał Marek.

Wywaliłem klasę ComplexNumber a w klasie MandelbrotSet zrobiłem (prawdopodobnie ? ) tak jak Azarien napisał czyli :

   if((x*x) + (y*y) >= 4)
                    return false;
                double X;
                X = (x*x) - (y*y) + realPart;
                double Y = (2*(x*y))+imaginaryPart;
                x=X;
                y=Y;

Średnia szybkość wyznaczania

Rozmiar Dokładność Czas
400x400 15 2.62
400x400 20 3.51
400x400 41 8.85
600x600 15 6.19
600x600 20 8.35
600x600 41 19.22

Mam dość starego kompa i może mi trochę mulić, ale na nowszych maszynach powinno być trochę lepiej.

Tutaj programik w fazie testowej (można powiększać a w razie za małej dokładności wyrenderować jeszcze raz z inną dokładnością)

http://www.filedropper.com/astrocytorigin

Dzięki za pomoc
Pozdrawiam
Astrocyt

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0