Hallo,
obwohl einige Forumnutzer schon von meinen "kontextlosen Mathematikfragen" (Zitat!) genervt sind, gibt es noch ein Thema mehr, zum Ärgern!
Mit richtiger Mathematik hat es aber weniger zu tun.

Ich habe versucht den Diamond-Square-Algorithmus (de.wikipedia.org/wik...d-square_Algorithmus) nur mit Delphi, ohne Open GL, umzusetzen, um ein Bild zu erzeugen, dass einem Plasma ähnelt.
Nach dem Start des beiliegenden Programms kann man eine Farbpalette auswählen, das Bild zeichnen und anschließend die Farben "rotieren" lassen, wodurch, meiner Meinung nach, der Plasmaeindruck noch deutlicher hervortritt.

Entsprechend des Algorithmus wird die Darstellung rekursiv erzeugt. Und hier ist mein Problem.
Die Konstruktion des Plasmas dauert einige Zeit, da ich im Moment keine Möglichkeit sehe, mit Scanline oder Ähnlichem den Algorithmus zu beschleunigen. Würde man die Pixel zeilenweise generieren, so wäre Scanline optimal. Die Farben der Pixel werden aber durch die Rekursion als Randpunkte von Rechtecken erzeugt.
Vielleicht sieht jemand von Euch eine Möglichkeit, die Bilderzeugung zu beschleunigen. Danke.

Beste Grüße
Mathematiker

Rev 3: Deutlich schnelleres Zeichnen des Bildes (ohne Scanline, durch Einführung eines Feldes).
Rev 4: Etwas schneller und (hoffentlich) einen Fehler beseitigt.
Rev 5: Weitere verschiedene Änderungen.
Rev 6: Etwas ASM, aber vor allem hoher Geschwindigkeitsgewinn durch Austausch von canvas.pixels. Jetzt ist es richtig schnell!
Rev 7: Ohne Assembler-Code, der wahrscheinlich fehlerhaft ist.
Rev 8: Code etwas optimiert. Die Größe des Programmfensters ist veränderbar. Der Assembler-Text ist enthalten, wird aber noch nicht aufgerufen.
Rev 9: Erhebliche Verringerung der Berechnungsanzahl.
Rev 10: Die Berechnungszahl ist gleich der Punktzahl, zumindest für etwa quadratische Zeichenflächen.
Rev 11: Korrigierte Version.
Rev 12: Das Programm enthält wahlweise die Fensterroutine von Horst_H und meine. Berechnungen können gezählt werden. Bild wird bei Größenänderung automatisch neu erstellt.
Rev 13: Die Farbpaletten sind in die Exe als Ressource integriert.
Rev 14: verschiedene Änderungen, u.a. dfm-Datei im binary-Format
Rev 15: Sauberer Bildaufbau auch bei Windows XP und 2000, außerdem weitere Beschleunigung (rund 10%) durch Entfernung von real-Variablen.
Rev 16: weitere Beschleunigung: Bildaufbau in weniger als 50 ms (auf meinem PC).

So ganz verstehe ich das Problem nicht.

Wenn man über die Combobox eine Farbpalette auswählt, ist nach kurzer Verzögerung das Startbild präsent. Man kann es sich über "Darstellung" noch einmal (oder ein ähnliches?) erzeugen lassen (das ist in der Tat ziemlich langsam), doch wozu? Die Farbrotation als eigentliches Demonstrationsobjekt dieses Programmes wird davon nicht berührt.

Die Rekursion scheint nicht bis zur Größe eines Pixels hinab zu arbeiten (neudeutsch: herunterzubrechen). Benutzt Du dazu den Rectangle-Befehl? Der ist m.E. schon ziemlich schnell.

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

Man kann es sich über "Darstellung" noch einmal (oder ein ähnliches?) erzeugen lassen (das ist in der Tat ziemlich langsam), doch wozu? Die Farbrotation als eigentliches Demonstrationsobjekt dieses Programmes wird davon nicht berührt.

Genau die Erzeugung des Bildes ist mir zu langsam. Dass jedes Mal über den Schalter Darstellung ein neues Bild gezeichnet wird, wollte ich eigentlich auch haben. Mitunter weichen die Bilder doch erheblich ab, vor allem wenn der Faktor geändert wird.

Delphi-Laie hat folgendes geschrieben :

Die Rekursion scheint nicht bis zur Größe eines Pixels hinab zu arbeiten (neudeutsch: herunterzubrechen). Bemutzt Du dazu den Rectangle-Befehl? Der ist m.E. schon ziemlich schnell.

Meinst Du das, dass das letzte Pixel rechts unten fehlt? Oder fehlen auf Deinem Computer auch im Bild einzelne Punkte? Dann stimmt an meiner Umsetzung was nicht und ich muss den Fehler suchen.

Um die neuen Pixel zu berechnen, benötige ich von dem jeweiligen Rechteck die Farbwerte der Randpunkte. Diese ermittle ich im Moment noch über die Farbnummern in der Palette und setze den neuen Punkt mit pixels[]. Und das bremst aus.
Ein Rechteck wird nicht gezeichnet, sondern nur dessen Eckpunkte als neuer Bereich gewählt.
Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

Meinst Du das, dass das letzte Pixel rechts unten fehlt? Oder fehlen auf Deinem Computer auch im Bild einzelne Punkte? Dann stimmt an meiner Umsetzung was nicht und ich muss den Fehler suchen.

Nein, da fehlt nichts, ich meine die Rekursion generell, wenn sie in der untersten Stufe angelangt ist. Das Bild ist nicht so feinpixelig, als daß ich den Eindruck hätte, daß sich die niedrigste Rekursionsstufe mit der Größe eines Pixels befassen würde. Nur mein erster Eindruck, ich sah nicht in den Quelltext.

Mathematiker hat folgendes geschrieben :

Ein Rechteck wird nicht gezeichnet, sondern nur dessen Eckpunkte als neuer Bereich gewählt.

Ja, und wie wird eben dieser "Bereich" gefüllt - pixelweise oder per Rectangle-Befehl?

Das Prinzip, Rechtecke recht großzügig zu füllen, wenn alle 4 Eckpunkte die gleiche Farbe haben und damit anzunehmen, daß darin nichts anderes vorhanden ist (und sich damit aber eben auch manchmal zu irren), kenne ich von einem Fraktalzeichenprogramm (noch aus DOS-Zeiten). Füllt natürlich schnell, doch sollte sich doch ein kleines Subfraktalchen darin befinden, hat es keine Chance, erkannt und gezeichnet zu werden.

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

Das Bild ist nicht so feinpixelig, als daß ich den Eindruck hätte, daß sich die niedrigste Rekursionsstufe mit der Größe eines Pixels befassen würde.

Das wird wohl daran liegen, dass nur 256 verschiedene Farben zum Zeichnen verwendet werden. Diese Einschränkung ist aber notwendig, damit ich die Farben zyklisch austauschen kann.

Delphi-Laie hat folgendes geschrieben :

Ja, und wie wird eben dieser "Bereich" gefüllt - pixelweise oder per Rectangle-Befehl?

Es wird pixelweise gefüllt. Aber die Idee, die Punkte eines sehr kleinen Bereiches ohne Neuberechnung gleichartig zu füllen, werde ich testen. Danke für den Hinweis.
Beste Grüße
Mathematiker

Nachtrag: Ein erster Test, kleine Bereiche gleich zu färben, ergibt ein deutlich schlechteres Bild. Vor allem beim Tauschen der Farben sieht man das. Schade.

Eal ob Du einzelne Pixel raussammelst und neu schreibst oder ganze Zeilen bearbeitest, ScanLine ist wesentlich schneller. Noch schneller wäre die Verwendung eines Rasters. Also ein von Dir selber angelegtes Stück Speicher was die Größe des Bildes hat und in dem Du das Bild aufbaust und es dann via Scanline hinkopierst wo Du es hinhaben willst.

Ich habe mal mit einem Wert gespielt:




dann wird das Bild zwar nicht schneller, aber auf einmal aufgebaut. Probier mal. Ansonsten liegt es wohl an dem, was mein Vorgänger schrieb.

P.S.: Die Routine "Farbmitte" wird ca. 2 Mio mal aufgerufen. Die Routine "Fenster" 390.000 mal. Zweitere hat etwa eine Prozedurzeit von 6 µs. Da stört schon sehr die Ermittlung der Prozedurzeit. Es käme allein dabei schon 2,4 s heraus. Auch erstere Prozedur benötigt ca. 0,2 µs pro Aufruf. Wenn überhaupt ist dort der Optimierungsbedarf.

Ich bin gerade dabei, beim Programm "durchzublicken".
Der Aufbau wirkt auf mich chaotisch, die vielen begin - end ergeben vermutlich keinen Sinn und verlangsamen das Programm zusätzlich.

Ich muss hathor zustimmen, das Programm wirkt in der Form chaotisch, besonders die ganzen Globalen Variablen sollte man mal überdenken. Wenn man es aber korrekt formatiert und einrückt ergeben die begin-end auch einen Sinn. Es sind einige lokale Funktionen in lokalen Funktionen:

Auch haben Begin - End keinen Einfluss auf die Performance des Programms, da diese nur zur Strukturierung des Delphi Code dienen und nicht im kompilierten Programm auftauchen.

Wie ich schon schrieb. Die Prozeduren Fenster (390000 mal) und Farbmitte (2 Mio mal) begrenzen schon die Schnelligkeit des Programms. Ich weiß nicht, ob da nicht durch weniger Aufrufe (geschicktere Programmierung) eine Beschleunigung möglich wäre. Dazu müsste man aber den genauen Algorithmus zur Farberzeugung haben. Vielleicht ist da was veränderbar. Denn selbst wenn eine Prozedur nur 0,1 µs dauern würde, wären das bei 2 Mio Aufrufe schon 0,2 s. Schlimmer noch, wenn sie dann 6 µs dauert. Und der Aufbau dauert insgesamt (bei meinem Rechner) 1,5 - 1,6 s.

Ich habe nochmals mit dem vorhergenden Wert gespielt:


n = 1 : Dauer ca. 274 s
n = 10 : Dauer ca. 27 s
n = 100 : Dauer ca. 2,7 s
n = 10000 : Dauer ca. 1,6 s
das (ca. 1,53 s) ist bei mir die Untergrenze. Die Draw-Prozedur scheint das Ganze sehr zu verlangsamen, je öfter sie aufgerufen wird.

Hallo,
Dank an Alle für die vielen Hinweise.
Zuerst habe ich den Quelltext entspechend Euer Hinweise umformatiert. Ich hoffe, dass er jetzt besser lesbar ist.
Es war aber kein begin oder end zuviel. Alle sind notwendig.
Die globalen Variablen habe ich unter private von TForm1 untergebracht.

Tranx hat folgendes geschrieben :

Und der Aufbau dauert insgesamt (bei meinem Rechner) 1,5 - 1,6 s. ... Die Draw-Prozedur scheint das Ganze sehr zu verlangsamen, je öfter sie aufgerufen wird.

Gratulation zu Deinem Rechner. Bei mir sind es mehr als 6 s.
Den Aufruf der Draw-Prozedur habe ich auf 10000 Schritte geändert, wodurch es, wie Du gesagt hast, schneller wird. Viel mehr geht da aber nicht, denn ich möchte eigentlich, dass man auf Wunsch das Zeichnen auch relativ schnell abbrechen kann.

Tranx hat folgendes geschrieben :

Dazu müsste man aber den genauen Algorithmus zur Farberzeugung haben.

Wenn oben P1, P2 und unten P3, P4 die Eckpunkte eines Rechtecks sind und n1 bis n4 deren Farbnummer in der Palette, wird wie folgt vorgegangen.
Der Mittelpunkt zwischen P1 und P3 des Rechtecks erhält die Farbe
farbnummer = (n1+n3)/2 + 1/2 Zufallsabweichung
wobei die Zufallsabweichung eine Zufallszahl aus dem Intervall [0, Rechteckhöhe] ist.
Für den Mittelpunkt P1P2 werden n1,n2 und Rechteckbreite, für P2P4 n2,n4 und Höhe, für P3P4 n3,n4 und Breite herangezogen.
Für den Mittelpunkt des Rechteck wird der Palettenindex als arithmetisches Mittel der 4 neuen Farbnummern ermittelt.
Klingt vielleicht etwas wirr, funktioniert aber.

Auf jeden Fall werde ich noch einmal prüfen, ob das Ersetzen von Pixels[] durch Scanline bei dem Hauptbitmap etwas bringt.

Beste Grüße
Mathematiker

Nachtrag: Ich habe alle Pixels[] durch Scanline ersetzt, z.B.

mit dem Ergebnis, dass die Zeichnung das Mehrfache(!) an Zeit benötigt. Irgendetwas mache ich falsch.

Zwei Dinge hier kosten richtig Zeit:
a) Scanline[..] ist eine sehr zeitintensive Funktion. Am einfachsten vor Ausführen von fenster
ein Array mit den Ergebnissen aller auftretenden Scanlines anlegen und dieses verwenden.
b) colorlist.items kostet auch viel Zeit da hier eine vollständige TLIST-Implementierung vorliegt. Am besten durch ein Array ersetzen.

Hallo Mandras,

mandras hat folgendes geschrieben :

Zwei Dinge hier kosten richtig Zeit: a) Scanline[..] ist eine sehr zeitintensive Funktion. Am einfachsten vor Ausführen von fenster ein Array mit den Ergebnissen aller auftretenden Scanlines anlegen und dieses verwenden. b) colorlist.items kostet auch viel Zeit da hier eine vollständige TLIST-Implementierung vorliegt. Am besten durch ein Array ersetzen.

Genau das ist es .
Ich habe Scanline komplett entfernt und dafür ein Feld für die Farbnummern eingeführt. Ergebnis auf meinem Rechner: nur noch 1/3 der ursprünglichen Zeit. (siehe Rev 3)
Auf deutlich schnelleren Computern als meinem, kann in der procedure fenster auch das Kopieren des Zwischenergebnisses aller 10000 Schritte auf höhere Werte geändert werden. Das verkürzt die Berechnungszeit noch einmal.
Colorlist brauchte ich nur für die Farbänderung. Nach dem Entfernen blieb die Farbsimulaton gleich, dafür wurde der Quelltext einfacher. Auch nicht schlecht.

Beste Grüße
Mathematiker

Mathematiker, die Darstellung wirkt tatsächlich schneller, wenn man auf die gleichnamige Schaltfläche drückt. Worin die Beschleunigung liegt, ist mir nicht ganz klar, aber es scheint, als sei der Zugriff von VCL- auf Nicht-VCL-Elemente verlagert worden zu sein. Arrays sind jedenfalls Nicht-VCL-Elemente und ziemlich schnell.

Ich probierte mit dem Faktor und - siehe da - das Bild wird viel fein(pixelig)er, also wird tatsächlich bis zum Bildpunkt "heruntergebrochen".

Allerdings hatte ich beim Wählen einer Farbpalette und / oder beim Klick auf "Darstellung" nunmehr einen Fehler (Exeption 103?), bekomme ich jetzt leider nicht reproduziert.

Und wen man die Darstellung eines Bildes abbricht, so wird bei Wahl einer anderen Farbpalette das neue Bild nur soweit dargestellt, wie das Bild davor bis zum Zeitpunkt des Abbruches gezeichnet wurde. Soll das etwa so sein?

Hallo Delphi-Laie,

Delphi-Laie hat folgendes geschrieben :

Worin die Beschleunigung liegt, ist mir nicht ganz klar, aber es scheint, als sei der Zugriff von VCL- auf Nicht-VCL-Elemente verlagert worden zu sein. Arrays sind jedenfalls Nicht-VCL-Elemente und ziemlich schnell.

Es liegt wohl daran, dass das bisherige Scanline, auch wenn es schnell ist, praktisch für jedes Pixel zweimal aufgerufen wurde und immer die ganze Zeile liest. Da jetzt die Daten im Feld liegen und nur das Feldelement abgefragt wird, geht es deutlich schneller.

Delphi-Laie hat folgendes geschrieben :

Allerdings hatte ich beim Wählen einer Farbpalette und / oder beim Klick auf "Darstellung" nunmehr eine Fehler (Exeption 103?), bekomme ich jetzt leider nicht reproduziert.

Das ist nicht gut. Bisher war so etwas bei mir noch nicht aufgetreten. Da muss ich wohl viel testen.

Delphi-Laie hat folgendes geschrieben :

Und wen man die Darstellung eines Bildes abbricht, so wird bei Wahl einer anderen Farbpalette das neue Bild nur soweit dargestellt, wie das Bild davor bis zum Zeitpunkt des Abbruches gezeichnet wurde. Soll das etwa so sein?

Eigentlich nicht, es ergibt sich aber aus der Berechnungsroutine. Im Moment muss man (noch) den Darstellungsschalter erneut wählen.

Außerdem habe ich noch ein paar weitere Prozent an Geschwindigkeit gewonnen, durch Entfernung der _getpixel-Prozedur und einer veränderten Berechnung der farbe5. Vielleicht geht es sogar noch etwas schneller und dann gibt es die Revision 4.

Beste Grüße
Mathematiker

Nachtrag: In der Hoffnung, den Fehler beseitigt zu haben, füge ich im ersten Eintrag eine neue Version ein.

Kleiner Zusatz: bringt zwar nicht viel, aber verkleinert die Funktion Farbmitte erheblich:



Max bewirkt, dass der größte der beiden Werte 1, oder der berechnete Wert übergeben wird.
and 255 ist klar: nur die Bits 0 - 7 werden berücksichtigt. D.h. aus einer Zahl >256 wird dann eine Byte-Zahl < 256;
"and 255" ist scheinbar etwas schneller als "mod 256".

div 2 durch shr 1 zu ersetzen bringt nichts, außer Laufzeitfehlern. Shr ist die Bitweise Verschiebung der Bits einer Integer-Zahl nach rechts. Entspricht eine Ganzzahldivision / 2.

Die ganzen Berechnungen habe ich einfach mal in eine zusammengefasst. Alle Abfragen falle weg und die lokalen Variablen.

Eine völlige Ersetzung des Fuktionsaufrufs durch die Berechnungsformel bringt nichts. Habe ich schon getestet. Eine weitere Verbesserung bringt m.E. nur eine Reduzierung der Berechnungsanzahl. Aber da wirst Du selber wohl keine Chance sehen, oder?

Nun sind es bei mir so zw. 0,90 und 0,92 s. Außerdem ist interessanterweise nun die Abhängigkeit von der Anzahl der Draw-Aufrufe nicht mehr ganz so dramatisch (zwischen 1000 und 100000) passiert fast nichts.

Komischerweise geht bei mir das Ganze in der Delphiumgebung schneller als beim Aufruf der Programmdatei (0,9 statt 0,98 s).

Hallo Tranx,

Tranx hat folgendes geschrieben :

Kleiner Zusatz: bringt zwar nicht viel, aber verkleinert die Funktion Farbmitte erheblich: markieren Delphi-Quelltext     1: 2: 3: 4:     function farbmitte(f1, f2, abweich: integer): byte;     begin       Result := max(1,((f1 + f2 - abweich) div 2 + random(abweich)) and 255); // Unith Math in Uses mit einbinden!!     end;

ich habe es gleich ausprobiert, mit dem Ergebnis, dass es etwas schneller wird. Nicht schlecht.
Interessant ist, dass Deine Formel nicht ganz die gleichen Werte liefert, wie meine.
(f1 + f2 - abweich) div 2 ist für einige Werte ungleich (f1 + f2) div 2 - abweich div 2.
Ich habe es getestet: In rund 8 % der Fälle ist Dein Wert größer und in 42 % kleiner. Dennoch entstehen Bilder, die kaum voneinander zu unterscheiden sind.

Tranx hat folgendes geschrieben :

Komischerweise geht bei mir das Ganze in der Delphiumgebung schneller als beim Aufruf der Programmdatei (0,9 statt 0,98 s).

Das ist mir noch gar nicht aufgefallen. Aber, Du hast recht. So etwas hatte ich noch nie.
Erste Idee war, die windowsxp.res zu entfernen. Die hat ja ohnehin nur kosmetischen Charakter. Und sofort ist bei mir wieder alles normal: Die Programm-Exe läuft ohne Delphiumgebung wieder schneller, wie es sich gehört.

Beste Grüße
Mathematiker

Der Unterschied kommt möglicherweise durch den Unterschied:

a div 2 + b div 2 <> (a + b) div 2,

da im linken Fall erst die Ganzzahloperation der Einzelergebnisse erfolgt und dann die Addition, während beim anderen Fall die Addition zuerst erfolgt und dann die Ganzzahloperation

3 div 2 + 5 div 2 = 1 + 2 = 3, (3+5) div 2 = 8 div 2 = 4

Hallo,
durch ein paar kleinere Änderungen, z.B. copyrect statt draw, dürfte die Konstruktion des Bildes noch etwas schneller sein (siehe Rev 5).
Mein Eindruck ist, dass nun eine andere Grundidee notwendig ist, um eine weitere deutliche Beschleunigung zu erzielen.
Vielleicht sieht auch jemand von Euch eine Möglichkeit, die Berechnung der Farbmitte durch Assembler zu beschleunigen. Leider habe ich keine Ahnung von ASM.

Beste Grüße
Mathematiker

Hallo,

ist nicht die Funktion random nicht die Wurzel allen Übels in der Funktion Farbmitte?
Einfach mal weglassen und testen.

Gruß Horst