Mandelbrot-Menge optimieren

[Namenloser]

Zitat von Delphi-Laie:

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 von NamenLozer:

Und was genau sollte daran schneller sein?

Die oft fehlenden Iterationen.

Zitat von NamenLozer:

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 von NamenLozer:

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 von Delphi-Laie:

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 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

[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? 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.