Buddhabrot

[Eichhoernchen]

Es ist noch kein fertiges Programm was ich euch hier Präsentieren möchte, es sind eher Codeschnipsel mit nem schnell gebastelten Programm zusammen!

Und zwar geht es um die Buddhabrotmenge...(nicht Butterbrot)

Es ist ein Fraktal(denke ich zumidest, ist ja schwer zu definieren)

Hier estmal ein paar Bilder wie das aussieht:
BILD1 (Gefärbt)
Bild2
Bild3
Bild4
Missglückter färbeversuch

Den Namen hat es wegen seiner Buddha ähnlichen Form.
Also ich finde das recht cool.

So erstmal zum Buddhabrot, es hat was mit der Mandelbrotmenge zu tun, wie man glaub ich sehen kann.

Und zwar ist die Buddhabrotmenge sowas wie eine Karte der Punkte C der Mandelbrotmenge die Divergieren(d.h. nicht zur Menge gehören).
Als erstes sucht man sich ein zufälliges C, danach lässt man dieses C den Mandelbrotmengen Algorithmus durchlaufen, wenn das C nach N Iterationen noch zur Menge gehört, wird ein neues C gesucht und von vorne gestartet, wenn das C aber nicht dazu gehört, wird die Iteration wiederholt, und alle Atraktoren, die Punkte die z anspring( z = z² + c) werden markiert, bzw. das array an dieser Stelle wird um 1 erhöht.

Leider entstehen erst brauchbare Bilder wenn man dies sehr oft tut. Bei ca 5 Millionen Iterationen des Hauptalgorithmus, also nicht von der Mandelbrotmenge entsteht ein brauchbares schwarz/weiß Bild. Wenn man jetzt noch gern ein farbiges Bild hätte benötigt man gleich 3 Arrays (r, g, b). Für farbige Bilder sind Fluchtiterationen(die Iterationen der Mandelbrotmenge) deutlich höher zu setzen als für schwarz/weiß Bilder. Bsp.: 10000 Fluchtiteratioen, wenn der Punkt C unter 100 Iterationen divergiert gehört er zum Rot teil der Menge und das Rot array wird erhöht. Wenn C unter 1000 und über 100 Iterationen divergiert gehört C zum Gelb teil und das Gelb array wird erhöht. Und das Blaue bei 10000 und > 1000.
Anschließend wird nur noch duch ein einfaches verfahren die arrays als r, g, b Teil eines Bildes dargestellt.

Für grobe Bilder wie Bild3 oder Bild2 kann man mit einer Rechenzeit von ca 10-20 Minuten rechnen(AMD 3000+) mit Bildern wie Bild 1 muss man schon mit 1,5 Stunden Rechenzeit rechnen. Und das Bild was ich zur Zeit berechne ist schon seit 3 Stunden am Rendern (und noch nichtmal uir hälfte fertig).

Naja ihr könnt euch ja mal den Code anschauen, ich habe noch andere Färbeversuche jetzt im Programm, diese sollten aber kein Problem sein wegzudenken!

[MiniKeks]

Ich hab mal den Code Geguckt..

Geiles Teil ;)

Aber wenn du die Progressbar rausnimmst, wird es Deutlich (!) Schneller ;)

[MiniKeks]

Ich könnte sonst mal meinen 2 PC Ein richtig grosses Teil Rechnen lassen, wenn du mir die Werte sagst, die ich Eingeben soll ;)

[Eichhoernchen]

hmm ja wenn die Progressbar raus ist weiß ich aber net wie weit ich bin, kann ganz schön doof sein sag ich dir!


Hmm also ich mache gerade mit 500000000 Buddhaiterationen und 10000 Fluchtiterationen und ab 20 iterationen soll aufgemalt werden!

Bin jetzt ca. bei der Hälfte. Bin echt gespannt was da noch so rauskommt!


Ich bin mir auch nicht sicher ob die Progressbar mir nicht alles versaut weil die kann ja glaub ich nur interger und ich hab ja einfach ganz braun auf int64 gesetzt. Nicht das mir das gleich wegen dem ollen Ding abnippelt.(und das tollste ist wenn das autodefrag anspring und meint die CPU gehöre ihm ganz alleine, dann ist es langsam, aber der ganze PC da musste es erstmal schaffen eins von beiden zu killen!)

Ich hab schon überlegt so ne art Net-Render zu bauen damit ich mehrere PC's gleichzeitig rendern lassen kann...
Ein PC gibt die C's vor und die andern rechnen sie aus, aber da kümmer ich mich rum fals ich die Farbgebung so hinbekomme wie ich das gern hätte.

[Eichhoernchen]

Und morgen mach ich mal das Gegenteil, da zeichne ich auf diese Art mal alle Punkte die dazugehören auf. Da solle ja ne mandelbrotmengen ähnliches gebilde rauskommen. Nur das auf dem Mandelbrotkörper große Ballungsräume sein müssen. Ich hab noch nen anderes Programm geschrieben das zeigt mit Punkten an wenn man mit der Maus über die mandelbrotmenge geht wo, die Punkte hinspringen, so wie das hier: Atraktorsprünge

ohh da ist bei wikipedia sowas wie ich meine so ne umgekehrte Buddhamenge wohl aussehen wird: Umgekehrt?!

[paresy]

Wär cool, wenn du das Programm auf Multithreading/MultiCPU optimierst, damit ich meinen Dual Xeon 3Ghz mal vollständig auslasten kann ;)

Grüße, paresy

[turboPASCAL]

Zitat:

Zitat von Eichhoernchen

Es ist noch kein fertiges Programm was ich euch hier Präsentieren möchte, es sind eher Codeschnipsel mit nem schnell gebastelten Programm zusammen!

Hm, na ja, also ich habe es getestet und wusste erst gar nicht so recht welchen Knopf ich wann und wo drücken soll.

Du solltest die From im OI unter Position poScreenCenter einstellen oder zumindest poDefaultPosOnly einstellen. Es haben nicht alle einen 21" grossen Monitor ;)

Die Eingabe von Werten kann zu Gleitkommafehlern führen... Ausserdem fehlt ein Abbruchknopf.

Das soll keine Kretik sein, nur eine Anregung. ;)

Zitat:

Zitat von Eichhoernchen

Und zwar geht es um die Buddhabrotmenge...(nicht Butterbrot)

:gruebel: Mandelbrot oder Sesambrotchen ?

[dizzy]

Schönes Programm :) Mit Fraktalen triffst du bei mir immer den richtigen Nerv. :thumb:

Ich habe an dem Teil mal ein wenig gefummelt. Es ist nun erheblich schneller. Folgende Dinge habe ich geändert:

• Du hast jeden Punkt 2 Mal iteriert. Ein mal um zu sehen ob er escaped, und das 2. Mal wenn nötig für die Darstellung. Ich habe es nun so gemacht, dass bei der Escape-Berechnung alle Punkte in einem Array schon gespeichert werden, so dass im Falle des Zeichnens nur noch das Array durchgegeangen wird. Das spart unheimlich!
• Sämtliches "Extended" und "Int64" rausgeschmissen. Wir brauchen keine hoch wissenschaftliche Genauigkeit. Das ganze ist reines Eye-Candy, und einen sichtbaren Unterschied gibt's nicht. Gerade das Rechnen mit Extended ist (gegenüber Single wie jetzt) eine sehr starke Bremse.
• Ich habe das mit dem Random entfernt. Jetzt wird das Bild Pixelweise durchlaufen, die diese dann als Startwerte "c" umrechnet. "Buddahiterationen" wurde zu "Genauigkeit", womit sich nun einstellen lässt ob nun pro Pixel 1 (1) oder pro Pixel 2 (2) Samples itereiert werden sollen etc. (sind Floats, also gehts auch < 1). Das führt zudem zu einer symmetrischen Darstellung, auch bei kleiner Genauigkeit.
• Umstellung auf Graphics32. Das aber eigentlich nur, weil ich es lieber mag als mit Scanline rumzudoktern :mrgreen:
• Diverse Aufrufe von "StrToX" in Schleifen aus der Schleife raus gezogen, und im Vorhinein in passende Variablen geschrieben. Auch nicht zu unterschätzen beim Speed ;). (Bei der Farbberechnung hab ich für Methode 1 die Editfelder ganz raus gelassen, und fix 255 eingebaut. Das war, weil ich zu faul war das in eine Variable zu packen =). Der Unterschied zu vorher ist irre. Die anderen Methoden habe ich im Wesen nicht geändert.)
• Für die Iterationsberechnungen habe ich meine "QMath.pas" eingesetzt (die auch in meinem CQParser mitspielt). Gibt auch noch mal einen kleinen Boost, da handmade Assembler (macht aber den Kohl nicht fett...).
• (Code ein wenig Styleguidekonformität verpasst. Macht ihn zur Runtime nicht schneller, aber schneller zu lesen 8))

Und ich fange auch schon wieder zu spinnen an :D. Man könnte das Teil mit meinem CQParser bauen, und somit ließe sich nicht nur die klassische Mandelbrotmenge mit z0=z1²+c verwursten, sondern man könnte beliebige Formeln nehmen (lassen!). Und mit Juliasets dürfte das doch im Grunde auch gehen...
Ach menno - nun hab ich wieder schlaflose Nächte :lol:

Schönen Gruss,
Fabian

[Eichhoernchen]

Ja, den erste Punkte habe ich genauso umgesetzt wie du im Nachhinein, ich wusste nicht wie lange es dauert ein Array nochmal durchzugehen und in ein anderes zu schreiben!
2. Hmm, wusste ich nicht
3. Ja das zu entfernen hab ich auch schon gemacht, hab aber keinen geschwindigkeitsunterschieg gemerkt!
4. Man kanns auch übertreiben ;)
5. war meine faulheit^^
6.
7. So wie es da geschrieben ist hab ich es in der Schule gelernt und wenn man sicht das 1 mal angewöhnt hat macht man es so und der code ist auch gut zu lesen find ich persönlich, aber das ist ja geschmackssache!!


Ich find es aber cool das das so viele Interessiert!!!

[Eichhoernchen]

So, hab jetzt gerade mal durch einen code geflogen, das mit der schreibweise mag ich gar nicht :P^^

Aber gut find ich das die itertation wo abgebrochen wir gemert wird un dann nur bis da,
gefallen tut mir nicht so der Typ TComplex, das macht es einiges schwerer zu verstehen finde ich, denn ich weiß net das TComplex so ist^^. Hab jtezt leider keine Zeit mehr ich muss in die Schule

[Eichhoernchen]

Zitat:

Zitat von paresy

Wär cool, wenn du das Programm auf Multithreading/MultiCPU optimierst, damit ich meinen Dual Xeon 3Ghz mal vollständig auslasten kann ;)

Grüße, paresy

Gern, wenn du mir sagt wie das geht^^

[shmia]

Die Trennung der Units QTypes und QMath macht softwaretechnisch keinen Sinn, da Datenstrukturen
(TComplex & TQuad) und Funktionen (die darauf angewendet werden) zusammengehören.
Ich würde alles in QMath packen.

[CADdy]

@dizzy:

ich wollte das Programm testen, bekomme aber beim Compilieren eine Fehlermeldung:

[Fataler Fehler] Unit1.pas(7): Datei nicht gefunden: 'GR32.dcu'

Was ist "GR32.dcu"? Ich hab Delphi 7 enterprise.

Servus
Peter

[turboPASCAL]

@CADdy GR32.dcu gehört zu einer Grafikkomponente für Delphi.
Such hier mal im Forum gr32 bzw. http://g32.org oder http://sourceforge.net/projects/graphics32

[Hador]

gehört zur Graphics32 Kompo

[CADdy]

danke für die hilfreichen Links!

Servus
Peter

[dizzy]

Zitat:

Zitat von shmia

Die Trennung der Units QTypes und QMath macht softwaretechnisch keinen Sinn, da Datenstrukturen
(TComplex & TQuad) und Funktionen (die darauf angewendet werden) zusammengehören.
Ich würde alles in QMath packen.

Es machte in Verbindung mit meinem Parser, und mit meiner 2. nicht asm-optimierten QMath durchaus Sinn. Die beiden Files sind hier nur aus diesem Verbund heruasgerissen.

@Eichhoernchen: Das mit dem random hatte ich weniger der Geschwindigkeit wegen entfernt, als viel mehr um ein gleichmäßigeres Ergebnis zu erhalten. Gerastert finde ich hat man aber auch trotzdem schneller ein recht ansehnliches Bild imho.
Der Typ TComplex ist ein Record. Einfach deine Variablen "zr" und "zi" (z.B.) zusammengefasst. Das macht keinen Geschwindigkeitsvorteil, ich find's nur besser Werte die zu derselben Zahl gehören untern einen Hut zu packen - und nicht zuletzt erwartet die QMath ihre Parameter so, und die hatte ich nunmal schon fertig :)
Die Schreibweise ist zum größten Teil an den (halb-)(in-)offiziellen (:)) Styleguide von Borland angelehnt, den ich in weiten Teilen für sinnvoll halte. Sicherlich ist es am Ende geschmackssache, nur in einem Betrieb nicht mehr wo mehrere Leute an einem Code arbeiten müssen... aber das Thema hatten wir hier schon ab und an mal, und es gibt mannigfaltig Meinungen dazu :D. Am Ende machts eh jeder wie er will ^^
Zu Punkt 5: Extrem teure Faulheit in diesem Fall :zwinker:

Gruss,
Fabian

[Ultimator]

@dizzy: Jetz hab ich so n schönes Bild gerendert und dann krieg ich DAS wenn ich speichern will: :(

Zitat:

---------------------------
Project1
---------------------------
TBitmap32 kann nicht zu TJPEGImage zugewiesen werden.
---------------------------
OK
---------------------------

[dizzy]

:oops: Um das Speichern hab ich mich null gekümmert... Wollte nur den Algo an sich optimieren.

[Eichhoernchen]

Soo, ich hab auch nochmal nen bisschen was gemacht,
man brauch hierfür keine weiteren Units oder sonstwas geht alles mit dem Standart zeug.

Und dank der Verbesserungen die ihr hier gepostet habt nun auch einiges schneller!

Hab ne kleine Render funktion eingebaut, sodass man vielleicht mal nen Desktophintergrund machen kann!

Alles nur auf die schnelle hab heute viel zu tun...

Ihr könnt ja mit der Programmversion auch mal vergleichen, den Unterschied zwischen random und den Bildschirm abgehen, random ist schöner :P

[Eichhoernchen]

Hmm ich bekomme immer wenn ich ne 2 Buddhabrotmenge berechnen will ne Exception, ich weiß aber nicht woran es liegt!

Wisst ihr es vielleicht?

[dizzy]

Japp. Den selben Effekt hatte ich bei meinem Umbau auch ;)

Du setzt FAttraktors (bei mir FOrbits) auf die Länge N, und greifst aber später auch auf das Element N zu, dass ja garnicht existiert. Also entweder das Array um eins größer machen, oder die Schleife um eins kürzer. Klassischer Fehler. Passiert doch jedem immer wieder gern :D

Bei mir hat's sogar schon am Ende der Berechnung beim ersten Versuch geknallt.


Gruss,
Fabian

[Eichhoernchen]

Ich dachte mir schon das es was mit dem ollen Array zu tun hat!

Danke *schnell änder*


Edit: Jetzt klappts, ich trottel

[Torpedo]

Das Programm gefällt mir :mrgreen:

Wenn die Genauigkeit auf 0 steht, sollte man abbrechen, sonst:


---------------------------
Project1
---------------------------
Ungültige Gleitkommaoperation.
---------------------------
OK
---------------------------

[Khabarakh]

Mit etwas Verspätung :mrgreen: stelle ich mal meine Version vor.
Was mich etwas überrascht hat, ist, dass das Programm etwa dreimal so schnell wie dizzys Version ist.
Die Oberfläche ist in zwei Teile aufgeteilt: Links die Berechnung des Arrays, rechts die Darstellung (entweder per PixelF oder StretchTransfer - konnte mich nicht entscheiden *g*). Ich hänge mal meinen aktuellen Desktophintergrund an.

[Eichhoernchen]

Hey, das gefällt mir!
Ist aber nicht mit den Delphi eigenen Bitmap funktionen?! oder?

Ist die Berechnung mit zufälligen C's oder wird der Bildschirm abgegangen?

Wenn du Lpust hast kannste ja auch mal den Source posten, würde mich schon interessieren!

[Khabarakh]

Zitat:

Zitat von Eichhoernchen

Hey, das gefällt mir!
Ist aber nicht mit den Delphi eigenen Bitmap funktionen?! oder?

Wie in dizzys Version mit der GR32-Lib.

Zitat:

Ist die Berechnung mit zufälligen C's oder wird der Bildschirm abgegangen?

Ebenfalls wie in dizzys Version :mrgreen: für jedes Pixel.

Zitat:

Wenn du Lpust hast kannste ja auch mal den Source posten, würde mich schon interessieren!

Ich stelle ihn mal rein, auch wenn dir zum Kompilieren ein paar Units fehlen werden.

[Eichhoernchen]

hey das hab ich ja noch gar nicht gesehen das man da noch reinzoomen kann bei dir, das ist ja überlst geil mit dem kleinen Image wo die mandelbrotmenge drauf ist, *auch haben will*, wie geht das das die Berechung da so fix ist? da kann ich ja fast realtime zoomen?

[Khabarakh]

Danke. Schau dir mal diesen Thread von mir an, besonders die Demo.

[Eichhoernchen]

Das ist ja absulut cool *runterladundinprogrammeinbau*

[Eichhoernchen]

hmmm ich hab das mal so getestet mit den units von dizzy und selbst geschriebenes Zeugs.

Ich muss sagen dissys Zeug ist in der Handhabung echt klasse, jedoch ist es langsamer musste ich feststellen.
Was sich bei meiner Berechnung in 1ner Sekunde ausschlägt, so wie ich es geschrieben hab dauerte die Rechnung ca 5 sekunden und mit dizzys Befehlen brauchte sie ca 6 sekunden.
Ich habe anstatt z.B.:

sqrC(c) das hier geschrieben:

Delphi-Quellcode:

c.x := c.x * c.x - c.y * c.y;
c.y := 2 * c.x * c.y;

und es ist schneller, woran liegt das, ich meine dizzys Zeug ist doch fast alles in asm geschrieben.
Außerdem ist auch das normale quadieren mit sqr langsamer als x * x zu rechnen. Kann mir das einer erklären, oder liegt es einfach daran das ich ne funktion aufrufe und das die Zeit nimmt?

[Khabarakh]

Zitat:

Delphi-Quellcode:

c.x := c.x * c.x - c.y * c.y;
c.y := 2 * c.x * c.y;

So wird das aber nichts :wink: :

Delphi-Quellcode:

TempX := z.x;
z.x := z.x * z.x - z.y * z.y;
z.y := 2 * TempX * z.y;

Ich habe mir mal eine Testanwendung geschrieben, im Schnitt kamen überall etwa die gleichen Zeiten heraus (CSqr eher langsamer).

Delphi-Quellcode:

function sqrC(const C: TComplex): TComplex;
const two: double = 2.0;
asm
  fld  C.x;
  fmul C.x;
  fld  C.y;
  fmul C.y;
  fsubp;
  fstp result.x;

  fld  C.x;
  fmul C.y;
  fmul two;
  fstp result.y;
end;

function CSqr(const C: TComplex): TComplex; inline;
begin
  Result.x := Sqr(C.x) - Sqr(C.y);
  Result.y := 2 * C.x * C.y;
end;

procedure CSqr2(var C: TComplex); inline;
var
  TempX: Single;
begin
  TempX := C.x;
  C.x := C.x * C.x - C.y * C.y;
  C.y := 2 * TempX * C.y;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Start: Cardinal;
  i, ii: Integer;
  TempX: Single;
  z: TComplex;
begin
  Start := GetTickCount;
  for ii := 0 to 1000000 do
  begin
    z.x := Sqrt(0.5);
    z.y := Sqrt(0.5);
    for i := 0 to 50 do
      z := sqrC(z);
  end;
  ShowMessage(Format('%d', [GetTickCount - Start]));

  Start := GetTickCount;
  for ii := 0 to 1000000 do
  begin
    z.x := Sqrt(0.5);
    z.y := Sqrt(0.5);
    for i := 0 to 50 do
      z := CSqr(z);
  end;
  ShowMessage(Format('%d', [GetTickCount - Start]));

  Start := GetTickCount;
  for ii := 0 to 1000000 do
  begin
    z.x := Sqrt(0.5);
    z.y := Sqrt(0.5);
    for i := 0 to 50 do
    begin
      TempX := z.x;
      z.x := z.x * z.x - z.y * z.y;
      z.y := 2 * TempX * z.y;
    end;
  end;
  ShowMessage(Format('%d', [GetTickCount - Start]));

  Start := GetTickCount;
  for ii := 0 to 1000000 do
  begin
    z.x := Sqrt(0.5);
    z.y := Sqrt(0.5);
    for i := 0 to 50 do
      CSqr2(z);
  end;
  ShowMessage(Format('%d', [GetTickCount - Start]));

end;

[dizzy]

Zitat:

Zitat von Eichhoernchen

Kann mir das einer erklären, oder liegt es einfach daran das ich ne funktion aufrufe und das die Zeit nimmt?

Genau daran wird es wohl liegen. Deinen Code schreibst du direkt in die Schleife, wärend du im anderen Fall einen Funktionsaufruf hast, der leider etwas Overhead erzeugt. Der Gewinn ist bei der Lesbarkeit und Wiederverwendbarkeit. Ich bemängel jedoch schon länger, dass Delphi im Gegensatz zu C kein Inlining unterstützt womit beide Fliegen mit einer Klappe geschlagen wären. (Jaja, D2005 kann das, aber das hab ich nicht und will es nicht ;).)

In Khabarakhs Messung kommen beide Varianten auf fast gleiche Ergebnisse, weil auch beides in Funktionen ausgelagert ist. Zudem ist mein asm-code nicht so viel anders als der den Delphi aus deinem generiert. Mir fielen da nur gelegentlich kleine Dinge auf die nicht 100%ig optimal waren, und deshalb hatte ich gleich alles was ich konnte in asm gebaut. Da weiss man wenigstens was man hat ^^

\\edit: Khabarakh, du hast die asm-funktion nicht ge-inlined ;)

[Khabarakh]

Zitat:

Zitat von dizzy

\\edit: Khabarakh, du hast die asm-funktion nicht ge-inlined ;)

Inlining wird für Assembler-Routinen nicht unterstützt :wink: . Ich mache heute noch einen größeren Test, dann werde ich sie auch per Hand inlinen.

Hab gerade die neueste Version meines MathBitmaps hochgeladen, zusammen mit der Unit im Anhang (und natürlich der GR32-Lib) sollte sich mein Programm nun kompilieren lassen.

[Eichhoernchen]

Zitat:

Zitat von Khabarakh

Zitat:

Delphi-Quellcode:

c.x := c.x * c.x - c.y * c.y;
c.y := 2 * c.x * c.y;

So wird das aber nichts :wink: :

Delphi-Quellcode:

TempX := z.x;
z.x := z.x * z.x - z.y * z.y;
z.y := 2 * TempX * z.y;

Jaja, aber man wusste was ich meinte^^

Habe mir jetzt ma gr32 und Konsorten besorgt und ich muss sagen: Nicht schlächt...



Hmm es müsste mal ne Delphi version im Stil von D 5,6,7 rauskommen die aber solche "mängel" beseitigt.
Ich hab mir die D2005 Demo gerade von der Borland Website geladen und ich muss sagen: Wer da beim Start nicht einschlaft....
Und die Oberfläche ist kacke, nicht mehr so schön freischwebend, kann man zwar umstellen, ist aber nicht genauso.
Fazit: Neues Delphi 7 mit verbessertem Compiler^^ (da kann ich lange drauf warte)