Mandelbrot-Menge optimieren

[MrMooed]

Hallo DP ich bin es mal wieder.


Ich bin vor ein Paar Tagen von meiner Informatiklehrerin auf das Apfelmännchen aufmerksam gemacht worden. Als ich es das erste mal gesehen habe, dachte ich einfach nur 'wow! :shock: so geil kann Mathe aussehen ?' Habe den relativ simplen Algorithmus auch umgesetzt und dargestellt.

Nun wollte ich das ganze noch etwas schneller rechnen lassen. Zunächst habe ich über Multithreading nachgedacht, aber dann wurde mir bewusst, dass ich damit nicht mein eigentliches Problem löse sondern nur auf die Prozesorkerne auslagere :?
Nun wollte ich hier mal nachfragen ob evtl. jemand Tipps hat was ich an meiner Berechnung schneller machen (bzw. optimieren) kann.

Delphi-Quellcode:

function Mandelbrot.rechne(X_Ko, Y_Ko, X, Y, A: double; i: Integer): Integer;
var
  nX, nY, nA: double;
begin
  if (i < 50) and (A < 2)
    then begin
           nX := (X*X) - (Y*Y) + X_Ko;
           nY := 2*X*Y + Y_Ko;
           nA := SQRT(nX*nX + nY*nY);
           result := rechne(X_Ko, Y_Ko, nX, nY, nA, i+1);
         end;
end;

Erklärung:
der Rückgabewert wird später zur Darstellung der Farben benutzt.
i ist die Anzahl der Iterationen. Je höher desto genauer das Bild.
(X_Ko | Y_Ko) sollen mit dem Punkt (X | Y) verglichen werden. (normalerweise ist dies der Ursprung (0 | 0)
A bzw. nA sind der Abstand zu (X | Y) - Satz des Pythagoras, wenn ich das nicht falsch verstanden habe :D

Aufruf:
Aufrufen tue ich die Funktion mit einer case .. of Anweisung.

Delphi-Quellcode:

case rechne(x, y, 0, 0, 0, 0) of
          0..10:  Bild.Canvas.Pixels[x,y] := clBlack;
          11..20: Bild.Canvas.Pixels[x,y] := clOlive;
          21..30: Bild.Canvas.Pixels[x,y] := clYellow;
          31..40: Bild.Canvas.Pixels[x,y] := clLime;
          41..50: Bild.Canvas.Pixels[x,y] := clGreen;
          else    Bild.Canvas.Pixels[x,y] := $000000;

Und bei einem hohen 'i' hat mein Rechner dann ein bisschen viel zu rechnen..

Danke im Voraus schonmal.

Was ist ein Apfelmännchen ?

[Valle]

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen. (das nennt man Buffer) Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Liebe Grüße,
Valentin

[MrMooed]

Zitat:

Zitat von Valle (Beitrag 1185083)

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen.

:oops: Habe wohl vergessen zu erwähnen, dass 'Bild' eine TBitMap ist die anschließend auf die Form gemalt wird :lol:

Zitat:

Zitat von Valle (Beitrag 1185083)

Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Ok werde ich mir direkt mal ansehen :thumb:

Zitat:

Zitat von Valle (Beitrag 1185083)

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Prinzipiell sollten Iterative und Rekursive Algorithmen doch gleichschnell sein oder ?:shock:
So etwas wird einem leider in der Schule nicht vermittelt und habe mir das "Wissen" selbst angeeignet, kann sein dass ich mich da total irre:roll:

[Valle]

Beim Aufruf einer Funktion müssen alle zu übergebenden Variablen auf den Stack geschoben werden. Das allein kostet schon Zeit. Die Frage sollte also sein, ob der iterative Overhead das ausgleichen kann. Es gibt hier aber sicher einige mit abgeschlossenem Informatikstudium, die dir das besser erklären können als ich. Des Weiteren hat man bei Rekursion das Problem, dass es eine maximale Rekursionstiefe hat, die die Menge an verschachtelten Aufrufen stark beschränkt.

Rekursive Lösungen sind meist viel lesbarer und "schöner" als ihre iterativen Pendanten.

Ob das in der Praxis bei deinem Beispiel wirklich viel Unterschied macht kann ich dir nicht sagen. Aber wenn es dich interessiert kannst du es natürlich herausfinden. Es gibt Möglichkeiten, die Zeit einer Berechnung zu messen. Das kannst du für beide Verfahren durchführen, wenn du magst. Theoretisch meinte selbst der Prof an der FH, an der ich ein Semester lang ein Frühstudium abgelegt habe, dass die rekursive Variante unschlagbar toll wäre. Praktisch hatte er aber öfter mal Unrecht.

[MrMooed]

Tatsache :o
Nach meinen Messungen beträgt die Mittlere Zeit um 20 mal das Selbe Bild zu rechnen:

Rekursiv: 423,55ms
Iterativ: 412,65ms

kleiner aber feiner Unterschied :? Werde das ganze nachher nochmal testen wenn ich auf ScanLine umgestellt habe.

[Neutral General]

Hi,

Scanline wird dir einen großen Geschwindigkeitsschub geben.
Mit Multithreading lässt sich das auch beschleunigen.
Du teilst das bild einfach unter den Kernen auf und jeder Kern berechnet einen Teil des Bildes.
Im Hauptthread fügst du die Teile zusammen und zeichnest (Das Zeichnen ist normalerweise leider nicht threadsafe)

[MrMooed]

Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere :roll:

Nun gut .. ich würde es dann so machen, dass jeder Thread einen Streifen des Bildes rechnen muss. Also 'Fensterbreite / CPUKerne' dann muss ich ihm noch den ganzen Algorithmus und die Zeichenfunktion in den Thread packen oder ?
Somit muss dem Thread dann noch übergeben werden von welchem xMin - xMax er rechnen soll.
Aber auf meine Form kann der Thread nicht selber zeichnen - eine TBitMap als Rückgabe :?:

Hatte vor langer Zeit mal einen Link zum multithreading gefunden, vllt kennt jemand etwas noch verständlicheres ?:oops:
Multithreading

[Valle]

Zitat:

Zitat von MrMooed (Beitrag 1185100)

Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere :roll:

Richtig so! :thumb:

Vielleicht machst du es auch gleich in zwei Schritten. Erst die Threads alle Werte berechnen lassen und in einem Array zwischenspeichern. Und dann den Main-Thread alles zeichnen lassen. Letzteres lässt sich ja via Multithreading vermutlich sowieso nicht beschleunigen. Höchstens noch via OpenGL, aber das ist ... weit gegriffen. ;-)

[Namenloser]

Ich habe mal Mandelbrot programmiert, auch mit Multithreading. Ich habe einfach ein Bitmap genommen und dann jeden Thread jeweils die n-te, n+1-te, n+2-te usw. Scanline berechnen lassen. Also z.B. bei 4 Threads wäre der 1. Thread zuständig für die 0, 4, 8, ... Scanline, der 2. Thread für die 1, 5, 9, ..., der 3. für die 2, 6, 10, ..., und der 4. für die 3, 7, 11, ...

Das ist leicht zu implementieren und hat den Vorteil, dass die Threads alle in etwa gleich viel Arbeit verrichten müssen (wenn man das ganze Bild nur in 4 große Teile aufteilen würde, könnte es sein, dass auf 3 Teilen fast nichts zu berechnen ist und dann doch wieder nur ein Thread die ganze Arbeit macht).

Man sollte das Bild übrigens auf jeden Fall in Zeilen aufteilen, nicht in Spalten wie in #7 impliziert, da das Bild zeilenweise im Speicher liegt, d.h. man spart dadurch eine Menge TBitmap.Scanline-Aufrufe und außerdem reduziert man Cache-Misses.

[sx2008]

Das Wurzelziehen mit SQRT() sollte man bei der Mandelbrotmenge unbedingt vermeiden, denn es kostet viel Zeit.
In der rekursiven Variante wird ja auf (A < 2) abgefragt.
Lässt man das Wurzelziehen weg, dann muss auch die Konstante quadriert werden (2*2=4):

Delphi-Quellcode:

if (nX*nX + nY*nY) >= 4.0 then
  exit;

[MrMooed]

dumme Frage, aber können die Threads gleichzeitig auf die TBitMap zeichnen ? Denn sie sollten dank ScanLine ja niemals in der selben Zeile sein :?:

Ansonsten habe ich nachgedacht die Zeilen in Abhängigkeit von den Kernen zu erstellen, da es evtl. zu viel Aufwand ist X-kleine Threads zu erstellen als z.B. 8 die etwas mehr zu rechnen haben. Diese 8 Streifen könnten jeweils eine eigene BitMap haben, die dann im MainThread zusammengeklebt werden :idea:

Zitat:

Zitat von sx2008 (Beitrag 1185104)

Das Wurzelziehen mit SQRT() sollte man bei der Mandelbrotmenge unbedingt vermeiden, denn es kostet viel Zeit.
In der rekursiven Variante wird ja auf (A < 2) abgefragt.
Lässt man das Wurzelziehen weg, dann muss auch die Konstante quadriert werden (2*2=4):

Also ich habe gerade mal die Abbruchbedingung durch 4 ersetzt und die Wurzel entfernt - nun habe ich hübsche bunte Balken aber kein Apfelmänchen :lol:

Delphi-Quellcode:

  if (i < 100) and (A < 4)
    then begin
           nX := (X*X) - (Y*Y) + X_Ko;
           nY := 2*X*Y + Y_Ko;
           nA := nX*nX + nY*nY;
           result := rechne(X_Ko, Y_Ko, nX, nY, nA, i+1);
         end;

//Edit:
Kann die .Execute nicht auf andere Methoden zugreifen ? Schutzklassen sollten da ja keine Probleme bereiten .. aber wenn ich meine 'rechne' function in der .Execute aufrufe passiert nichts - kopiere ich die function hinein läuft es ?!

[sx2008]

Zitat:

Zitat von MrMooed (Beitrag 1185105)

Also ich habe gerade mal die Abbruchbedingung durch 4 ersetzt und die Wurzel entfernt - nun habe ich hübsche bunte Balken aber kein Apfelmänchen :lol:

Dann hast du irgendwo noch einen anderen Fehler.
Was ich über das Wurzelziehen und dessen Vermeidung geschrieben habe ist richtig und ist eigentlich in jedem Code so umgesetzt.
Z.B. auf Wikipedia http://de.wikipedia.org/wiki/Mandelb...es_Bildpunktes

[MrMooed]

komischer weise tritt dieses Fehlverhalten nur bei der Rekursiven Variante auf :shock:
Das finde ich dann doch sehr seltsam .. kann mich da jemand aufklären was mein Denkfehler bei der Rekursion ist ?
Strange..

[Delphi-Laie]

Zitat:

Zitat von MrMooed (Beitrag 1185078)

Nun wollte ich hier mal nachfragen ob evtl. jemand Tipps hat was ich an meiner Berechnung schneller machen (bzw. optimieren) kann.

Wollte? Willst du es jetzt nicht mehr?

Tue es doch einfach!

Ehe du es tust, um es abzukürzen: Ein gewaltiges Beschleunigungspotential ergibt sich dadurch, daß man (mehr oder weniger) kleine (rechteckige, am besten quadratische) Flächen gleich komplett färbt: Sind ihre 4 Eckpunkte, die man als erstes berechnet, gleichfarbig, so ist es mit großer Wahrscheinlichkeit das gesamte von ihnenn eingehüllte Viereck. Um Irrtümer anzahlig zu reduzieren, kann man ja auch rekursiv vorgehen und in größeren Vierecken kleinere auf gleiche Weise prüfen und ggf. füllen. Dagegen sind Scanline und Threads läppisch, obwohl beide natürlich auch ihre Berechtigung und Vorteile haben.

[Namenloser]

Zitat:

Zitat von Delphi-Laie (Beitrag 1185136)

Ehe du es tust, um es abzukürzen: Ein gewaltiges Beschleunigungspotential ergibt sich dadurch, daß man (mehr oder weniger) kleine (rechteckige, am besten quadratische) Flächen gleich komplett färbt: Sind ihre 4 Eckpunkte, die man als erstes berechnet, gleichfarbig, so ist es mit großer Wahrscheinlichkeit das gesamte von ihnenn eingehüllte Viereck. Um Irrtümer anzahlig zu reduzieren, kann man ja auch rekursiv vorgehen und in größeren Vierecken kleinere auf gleiche Weise prüfen und ggf. füllen.

Und was genau sollte daran schneller sein? Bei einem Fraktal muss sowieso der Wert für jeden Pixel einzeln berechnet werden, und die Anzahl der zu füllenden Pixel wird so auch nicht reduziert.

[Delphi-Laie]

Zitat:

Zitat von NamenLozer (Beitrag 1185138)

Und was genau sollte daran schneller sein?

Die oft fehlenden Iterationen.

Zitat:

Zitat von NamenLozer (Beitrag 1185138)

Bei einem Fraktal muss sowieso der Wert für jeden Pixel einzeln berechnet werden,

"Muss" muß gar nicht. Es gibt in vielen Flächenfraktalen, so auch dem Apfelmännchen, viele (ziemlich) einfarbige Gebiete, bei denen man mit hoher Treffsicherheit eben annehmen (neupseudodeutsch "davon ausgehen") kann, daß 4 gleichfarbige Eckpunkte ein komplett gleichfarbiges Gebiet umschließen.

Fällt nun der Groschen?

Ausgedacht habe ich mir das nicht, sondern schon vor ca. 20 Jahren (!) in einem DOS-Fraktalprgramm wahrgenommen.

Zitat:

Zitat von NamenLozer (Beitrag 1185138)

und die Anzahl der zu füllenden Pixel wird so auch nicht reduziert.

Wer behauptet denn anderes?

[Namenloser]

Ich kann mir nur schwer vorstellen, dass dabei keine Artefakte auftreten...

[MrMooed]

Zitat:

Zitat von Delphi-Laie (Beitrag 1185136)

Sind ihre 4 Eckpunkte, die man als erstes berechnet, gleichfarbig, so ist es mit großer Wahrscheinlichkeit das gesamte von ihnenn eingehüllte Viereck.

also nehme ich einfach irgendwo ein Quadrat und berechne die Eckpunkte ? Halte ich irgendwie für ziemlich spekulativ :oops: Ich habe mal in einem Bild markiert was passiert wenn man die falschen 4 Punkte erwischt (die trotzdem die selbe Farbe haben) Dann wäre nämlich der Inhalt futsch obwohl noch Fraktale vorhanden wären.

[Bummi]

Mein Versuch die Auswirkung von Threads bei bestimmten Randbedingungen zu untersuchen ...

[Neutral General]

Zu der Sache mit dem Bitmap und den der Aufteilung der Arbeit unter den Threads nach Scanlines:

Unabhängig davon ob man das (bzgl. Threadsicherheit) so machen kann/darf:

Ich habe dem Benutzer (aus Spaß) die Möglichkeit gegeben das Mandelbrot selbst einzufärben. Also je nachdem bei wie vielen Iterationen der Pixel "rausfliegt" diesen Pixel anders einfärben zu lassen. Wenn man in der Palette 10 Einträge hat dann bekommt ein Pixel der nach 11. Iterationen rausfliegt wieder die 1. Farbe.

Das Wechseln der Palette ist um einiges leichter und schneller wenn man nicht direkt auf ein Bitmap zeichnet sondern die Anzahl der Iterationen pro Pixel in einem 2D-Array speichert. So kann man das Mandelbrot schnell und einfach neu einfärben ohne alles neu berechnen zu müssen :)

Ist jetzt natürlich kein Tipp mit dem man die Performance der Berechnung steigern kann, aber falls du sowas vorhast, dann ist das Zwischenspeichern in einem Array sicher zu empfehlen ;-)

Edit: Ich hoffe mein Text ist nicht zu verwirrend geschrieben :mrgreen:

[Medium]

Was Delphi-Laie da so unsympathisch beschreibt, ist der erste Schritt zu einem Quad-Tree. Dieser erste Schritt kann, bei passend feiner Unterteilung und etwas Glück, relativ artefaktfrei sein - kann aber auch hässlich werden. Praktisch alle Verfahren, die die Iteration von Zwischenpixeln auslassen, haben mit Artefakten zu kämpfen. Manche weniger auffällig, andere sind ganz gut kaschierbar, aber es bleibt ein Behelf. Auch ein Quad-Tree ist hier noch als Krücke anzusehen, da man für die "Ich muss weiter unterteilen"-Bedingung ja doch wieder eine Auswahl an Punkten in den Quadraten durchitereiren muss - und an dieser Auswahl hängt dann, ob man es nicht doch hier und da zu grob getrieben hat.

Iterativ machen, Verwendung von Scanline (das vor allen Dingen! .Pixels[] macht vieeeeel zunichte!) und Multithreading sollte schon einen mächtigen boost geben. Man kann zwar relativ gefahrfrei Scanlines des selben Bitmaps in mehreren Threads beschreiben (so lange man sich immer strikt die Zeilen getrennt hält), aber ich würde hier auch zu einem Array als Zwischen-Puffer tendieren. Eben schon allein für die Möglichkeiten der variablen Farbgebung ohne Neuberechnung.

Und WENN man schon multithreaded, warum nicht gleich ganz freaky werden? :mrgreen: Das ganze ist ein Paradeeinsatz für GPGPU. Jeder Pixel wird unabhängig von allen anderen berechnet, also hat man eine wunderbare und feine Granularität des Problems. Anfangs die ganzen Bildkoordinaten in eine float/float Textur gießen, einen Shader-Kernel machen der eine Iteration macht, und das Ergebnis in eine zweite Textur schreibt. Texturen tauschen, und nochmal durch den Shader jodeln - bis zur gewünschten Iterationstiefe. Die finale Textur kann dann ähnlich des o.g. Arrays als Basis zum Farbbild dienen - auch das ließe sich als hübscher Kernel realisieren. Aber das ist eher Stufe 9,5.