Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Kugelspiegelung


Mathematiker - Di 28.07.15 21:34
Titel: Kugelspiegelung
Hallo,
als großer Fan von Maurits C.Escher [http://www.mcescher.com/] wollte ich versuchen, "ähnliche" Kugelprojektionen [http://www.mcescher.com/gallery/] zu erzeugen, wie der geniale Künstler.
D.h., ich möchte ein Bitmap Pixel für Pixel auf die Oberfläche einer Kugel transformieren, in der Form, dass eine Reflexion vorgetäuscht wird.
kugelp

Mein bisheriger Algorithmus ist die Projektion auf eine Riemannsche Zahlenkugel [https://de.wikipedia.org/wiki/Riemannsche_Zahlenkugel].
Die Koordinaten des Bildes werden als komplexe Zahlen x+yi in der Gaußschen Ebene interpretiert und dann auf die Zahlenkugel transformiert. Ich zeichne nur die Punkte, die auf der unteren Halbkugel liegen.
So weit, so gut.
Ich werde aber das Gefühl nicht los, dass die Projektion irgendwie komisch aussieht. Hat jemand von euch mit so etwas Erfahrung? Ist "mein" Algorithmus einigermaßen korrekt oder liege ich völlig falsch?

Außerdem habe ich wieder ein Geschwindigkeitsproblem. Trotz Scanline benötigt die Darstellung einige Sekunden. Sieht jemand eine Möglichkeit das zu beschleunigen?

Das Beispielprogramm ist nur ein einfacher Test. Z.B. habe ich es nicht hinbekommen, dass das Image auch jpg nimmt. Scanline will da nicht so richtig.
Als erstes Beispiel dürfte es aber funktionieren.

Beste Grüße und Danke für evtl. Hilfe
Mathematiker

Rev 1: Vorschläge von user profile iconHorst_H und user profile iconNarses eingebaut.


jfheins - Di 28.07.15 22:07

Ich denke, das sollte sich halbwegs realistisch machen lassen:

1. Das Bild links-rechts spiegeln ("umdrehen")
2. In der Ebene platzierst du nun mittig die Kamera. Als würde man durch ein Loch in einer Wand gucken, und auf der Wand ist das Bild.
3. Eine reflektierende Kugel vor der Kamera vorstellen
4. Einen Maßstab festlegen, der die "Pixel des Zielbilds" in den Winkel des Strahls überführt
5. Für jeden Pixel die Distanz zur Mitte ausrechnen und transformieren (Winkel in Polarkoordinaten bleibt gleich)

In der Seitenansicht sollte das dann ungefähr so ausschauen:
kugel

Jetzt kannst du für jeden Punkt des Zielbild den Winkel berechnen (orange). Die Reflektion sollte sich ebenfalls berechnen lassen, und damit die Koordinate des Ursprungsbilds, mit der der eine Pixel gefärbt wird. Die werden natürlich krumm werden, da am besten min. bilinear interpolieren. Die Parameter R und d sollten dann Parameter der Transformation werden. Dann so Einstellen, dass was halbwegs realistisches bei 'rum kommt.


Horst_H - Di 28.07.15 22:41

Hallo,

ich habe mal die Berechnung leicht modifiziert, und sq == Summe der Quadrate eingesetzt.
zk < 0.5 kann man vorher schon testen.
Round ist bei Turbo Delphi sehr langsam und ich setze jetzt einfach pf32bit voraus-> pIntegerArray ohne RGB Umrechnung.
SpinEdit hat Turbo Delphi nicht.


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
procedure TForm1.Button1Click(Sender: TObject);
const bb=960;
var i,j,waagerecht,senkrecht:integer;
    xk,yk,zk,q,xi,yi,sq :double;
    xm,ym:integer;
    bitmap:tbitmap;
    rect:trect;
    P : PINTEGERArray;
begin
   Button1.Caption := 'Warte';
   //Verschiebung des Spiegelsmittelpunkts
   waagerecht:=bb;//spinedit1.value;
   senkrecht:=bb;//spinedit2.value;

   bitmap:=tbitmap.Create;
   bitmap.width:=bb;
   bitmap.height:=bb;
   //Abbildung auf doppelte Größe strecken
   rect.left:=0;
   rect.Top:=0;
   rect.right:=bb;
   rect.Bottom:=bb;
   bitmap.canvas.copyrect(rect,image1.picture.bitmap.Canvas,image1.clientrect);
   //Mittelpunkt
   xm:=paintbox1.Width div 2;
   ym:=paintbox1.height div 2;
   paintbox1.Canvas.Brush.Color:=clwhite;
   paintbox1.Canvas.Rectangle(-1,-1,961,961);
   //zeilenweise pixel ermitteln
   for i:=0 to bb-1 do begin
     P := BitMap.ScanLine[i];
     yi:=(2*i-senkrecht)/bb;
     for j:=0 to bb-1 do begin
       //Umwandeln in komplexe Koordinaten
       xi:=(2*j-waagerecht)/bb;
       //Transformation auf die Riemann-Kugel
       sq := sqr(xi)+sqr(yi);
       IF sq < 1.0 then
       begin
         q:=1/(1+sq);
         zk:=sq*q;
         xk:=xi*q;
         yk:=yi*q;
         //nur zeichnen, wenn in unterer Hälfte der Riemann-Kugel
//        if zk<0.5 then
//         paintbox1.Canvas.pixels[trunc(xm+480*xk),trunc(ym+480*yk)]:=rgb(p[4*j+2],p[4*j+1],p[4*j]);
         paintbox1.Canvas.pixels[trunc(xm+480*xk),trunc(ym+480*yk)]:=p[j];
       end;
     end;
   end;
   Button1.Caption := 'Start';
   bitmap.free;
end;


Wenn ich waagerecht oder senkrecht ändere ist die Kreisform weg.

user profile iconjfheins Vorschlag sieht doch sehr einleuchtend aus, aber auch nicht leicht zu berechnen.

Gruß Horst


Narses - Di 28.07.15 22:42

Moin!

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Z.B. habe ich es nicht hinbekommen, dass das Image auch jpg nimmt. Scanline will da nicht so richtig.
Das liegt daran, dass Scanline nur mit Bitmaps (unkomprimierte Bilder) funktioniert. :idea: ;) Das JPG hält die Daten intern komprimiert vor und dekomprimiert sie bei jedem .Draw(). :shock: Also intern in ein Bitmap konvertieren (Bitmap gleicher Größe anlegen und dann das JPG draufzeichnen -> klar, braucht mehr Speicher, aber so ist das eben :nixweiss:) und dann geht auch Scanline.

cu
Narses


Mathematiker - Di 28.07.15 23:12

Hallo jfheins,
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Ich denke, das sollte sich halbwegs realistisch machen lassen: ...

Das von dir beschriebene Verfahren ist einleuchtend und werde ich einmal ausprobieren. Das es etwas mehr Rechnung wird, als bei meiner Idee, habe ich mir schon fast gedacht.
Danke für den Vorschlag.

Hallo Horst,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
ich habe mal die Berechnung leicht modifiziert, und sq == Summe der Quadrate eingesetzt.
zk < 0.5 kann man vorher schon testen.
Round ist bei Turbo Delphi sehr langsam und ich setze jetzt einfach pf32bit voraus-> pIntegerArray ohne RGB Umrechnung. ...

Danke für die Änderungen. Damit wird es schneller, was sehr schön ist.
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Wenn ich waagerecht oder senkrecht ändere ist die Kreisform weg.

Das war auch der Grund warum ich mit meiner Lösung nicht glücklich war.

Hallo Narses,
user profile iconNarses hat folgendes geschrieben Zum zitierten Posting springen:
Also intern in ein Bitmap konvertieren (Bitmap gleicher Größe anlegen und dann das JPG draufzeichnen -> klar, braucht mehr Speicher, aber so ist das eben :nixweiss:) und dann geht auch Scanline.

Danke. War eigentlich klar, aber ich war wohl wieder mal etwas verwirrt.

Beste Grüße
Mathematiker

Nachtrag:
@Horst
PIntegerArray mit der Zuweisung p[j] liefert bei Farbbildern verschobene Farben. Komisch. :nixweiss:

@Narses
Also ist stelle mich offensichtlich saudämlich an. Mit

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
   bitmap2:=tbitmap.create;
   bitmap2.width:=image1.Width;
   bitmap2.height:=image1.height;
  
   bitmap2.canvas.draw(0,0,image1.picture.Bitmap);
oder
   rect2.left:=0;
   rect2.Top:=0;
   rect2.right:=bitmap2.width;
   rect2.Bottom:=bitmap2.height; 
   bitmap2.canvas.copyrect(rect2,image1.picture.Bitmap.canvas,rect2);
bekomme ich bei einem jpg in image1 nur ein Bitmap2, das schwarz oder weiß ist. Nach der Kugelprojektion ist das Image1 auf einmal leer.
Noch verrückter ist, dass

Delphi-Quelltext
1:
   bitmap2.canvas.copyrect(image1.clientrect,image1.canvas,image1.clientrect);                    
den Laufzeitfehler
Zitat:
Ein Bild kann nur geändert werden, wenn es ein Bitmap enthält.
liefert. Wo ändere ich hier das Image?
Ich bin heute zu nichts zu gebrauchen.


Narses - Mi 29.07.15 01:15

Moin!

Du hast das Pixel-Format nicht definiert, also wird da irgendwas genommen (monochrom? keine Ahnung). ;) Hab jetzt grad kein Delphi zur Hand, aber Google liefert Code dieser Art (ungetestet):

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
jpeg: TJPEGImage;
bmp: TBitmap;

  jpeg := TJPEGImage.Create;
  jpeg.LoadFromFile(Filename);
  bmp := TBitmap.Create;
  bmp.Assign(jpeg);
  bmp.PixelFormat := pf32bit; // sicherheitshalber erzwingen (default für jpg ist vermutlich pf24bit)

cu
Narses


Mathematiker - Mi 29.07.15 08:39

Hallo,
ich habe jetzt die Vorschläge von user profile iconHorst_H und user profile iconNarses eingebaut. JPG-Bilder; vier zu Auswahl; können jetzt geladen werden.
Merkwürdig ist nur, dass es so funktioniert, nicht aber, wenn ich schon zur Entwurfszeit das JPG in das Image lade.

Durch die Verwendung eines 3.Bitmaps wurde es noch einmal etwas schneller. PIntegerArray habe ich wieder durch PByteArray ersetzt. Irgendwie kam es zu Farbänderungen.
Die Idee von user profile iconjfheins erweist sich als komplizierter als ich gedacht habe. Im Moment fehlt mir noch eine mathematische Idee, wie ich den Punkt/den Winkel auf der Kugel finde. Aber das wird noch.

Beste Grüße
Mathematiker


jfheins - Mi 29.07.15 21:52

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

Die Idee von user profile iconjfheins erweist sich als komplizierter als ich gedacht habe. Im Moment fehlt mir noch eine mathematische Idee, wie ich den Punkt/den Winkel auf der Kugel finde. Aber das wird noch.

Vielleicht kann ich da noch etwas helfen. Anbei findest du eine Skizze mit den verwendeten Bezeichnern (maßstabsgetreu):
skizze

Hier die Berechnung von x, ausgehend von alpha, R und d:


PHP-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
d = 70; % Distanz der Kugel
R = 30; % Kugelradius
alpha = 6*pi/180; % Bogenmaß

% Sinussatz
beta =  asin(sin(alpha)*(d+R)/R); % Winkel oben im Dreieck zwischen Kamera,
                  % Kugelmittelpunkt und Reflexpunkt                 
% asin gibt hier das "kleine" Ergebnis aus, wir brauchen aber das Große...
beta = pi-beta;

gamma = pi - alpha - beta; % Innenwinkelsumme Dreieck

% pi - beta ist der Winkel zwischen dem Lot und dem Eingangssttrahl.
% Eingangswinkel = Ausgangwinkel, daher verdoppeln
phi = 2*(pi - beta);

% Ausgangsstrahllänge bis zum Schnittpunkt mit der Kugel
c = R * sin(gamma)/sin(alpha);

theta = pi/2 - alpha; % Komplementärwinkel
psi = pi - theta - phi; % Wenn negativ, Spiegelung nicht mehr in der Ebene

x = c * sin(phi)/sin(psi) % Distanz an der "Wand"


Bei mir kommt da am Ende auch x = 56.729 heraus :-D
Nicht ganz sauber ist die Lösung für den ersten arcsin, aber das ist letztlich alles nur Geometrie in Dreiecken. Die Kunst ist, die Dreiecke zu finden ^^


Mathematiker - Mi 29.07.15 23:00

Hallo jfheins,
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Vielleicht kann ich da noch etwas helfen. ...

Vielen Dank. Das hilft auf jeden Fall weiter.
Meine Idee war von x auszugehen und den Winkel Alpha zu ermitteln, d.h. gerade andersherum. Und da kam ich nicht weiter.
Morgen probiere ich deinen Vorschlag gleich aus.

Beste Grüße
Mathematiker


Horst_H - Do 30.07.15 07:58

Hallo,

so richtig "ekelig" wird es doch erst, wenn man ein paar Grad links und rechts vom "Hauptsichtstrahl" schaut, also die den Ort der Bildecken auf der Kugel finden will.
Dann brauche ich sicher 3D Vektoren.
Ich hatte mir schon überlegt, man könnte das Bild mit der Kugel rotieren, um im Fadenkreuz bei x= 0 oder y= 0 also in der Ebene zu bleiben, und dann wieder die Drehung zurückrechnen.
Aber ob dass funktioniert?

Gruß Horst


Boldar - Do 30.07.15 10:15

Naja, im Prinzip sind das ja die Grundzüge eines einfachen Raytracers. Die Vektormathematik dabei ist auch nicht wirklich kompliziert - letztendlich sind das stehts nur Spiegelungen von Strahlen unter Berücksichtigung eines Normalenvektors. Schon schwieriger ist dann die Ermittlung des Normalenvektors und der Entsprechenden Einfallswinkel. Dafür muss entweder der Schnittpunkt ermittelt werden, oder wie in diesem Fall, der einfallende Strahl, denn der Schnittpunkt ist ja quasi Vorgegeben durch den Pixel, den man gerade berechnet. Das bedeutet, man muss den einfallenden Strahl zurücktracen, d.h. vom Punkt auf der Kugeloberfläche ausgehend den Strahl "rückwärts" verfolgen bis zum Schnittpunkt mit der Objektebene, um dort den Farbwert im Ursprungsbild zu ermitteln. Dafür braucht man dann neben den 3D-Koordinaten des Schnittpunktes (zu errechnen aus den Pixelkoordinaten und der Lage+Größe der Kugel) auch die beiden Raumwinkel des einfallenden Strahles, welche natürlich wiederum auch vom Abstand zum Betrachter abhängen.

Um mal auf user profile iconMathematikers ersten Post einzugehen - Zwischen einer Spiegelung und einer Projektion auf die Riemansche Kugel gibt es übrigens bedeutende Unterschiede - das wird schon klar, wenn man sich überlegt, was am Pol passiert - bei der Riemann-Kugel steht am Pol unendlich, während bei einer Spiegelung die "unendliche Bildkoordinate" schon auf dem 45. Breitengrad liegt.

Für den einfachen Fall einer Kugel (selbst mit beliebiger Lage im 3D-Raum zu Objektebene und Bildebene) sollte sich evtl. auch noch analytisch eine Transformationsformel finden lassen, wenn man das nur mal ohne einzusetzen durchrechnet. Letztendlich sind das ja "nur" verschachtelte Trigonometrische Funktionen, da sollte sich recht einfach eine Formel finden lassen, die die Koordinatentupel transformiert.


Mathematiker - Do 30.07.15 14:13

Hallo,
user profile iconBoldar hat folgendes geschrieben Zum zitierten Posting springen:
Für den einfachen Fall einer Kugel (selbst mit beliebiger Lage im 3D-Raum zu Objektebene und Bildebene) sollte sich evtl. auch noch analytisch eine Transformationsformel finden lassen, wenn man das nur mal ohne einzusetzen durchrechnet.

Habe ich gemacht, mit dem Ergebnis
x =
(2(d+r) sin(arcsin((d+r)sin(alpha)/r)-alpha) sqrt(r^2-(d+r)^2 sin(alpha)^2))/(r cos( 2 arcsin((d+r)sin(alpha)/r)-alpha)

Weiter vereinfachen geht nicht. Zumindest habe ich nichts gefunden.
Ein Versuch, die Gleichung nach Alpha umzustellen, geht schief. Eine analytische Auflösung nach Alpha existiert nicht. Schade.

Beste Grüße
Mathematiker


Horst_H - Do 30.07.15 15:07

Hallo,

in der Formel sehe ich nur d,r,alpha, wie bei user profile iconjfheins
Wie kann das eine beliebige Lage im Raum widerspiegeln.Müsste da nicht noch die Verschiebung des Kugelmittelspunktes irgendwo hineinspielen.
Oder ist das gegeben durch die Verbindungslinie Auge -- Kugelmittelpunkt und dass sich das betrachtete Objekt unter anderen Winkel darstellt.
Mit einer Linie kann ich aber keine neue Bezugsebene aufspannen.
Es knotet sich im Hirn...

Gruß Horst


Mathematiker - Do 30.07.15 15:20

Hallo,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
in der Formel sehe ich nur d,r,alpha, wie bei user profile iconjfheins

Du hast recht. Ich habe auch nur auf user profile iconBoldars Hinweis die Formeln zusammengefasst. Die Umrechnung auf den Raum fehlt hier noch.

Beste Grüße
Mathematiker


Martok - Do 30.07.15 15:24

Falls ihr irgendwann keine Lust mehr drauf habt, das von Hand auszurechnen: das Problem nennt sich Cubemap [http://wiki.delphigl.com/index.php/Cubemap] und ist in OpenGL in Hardware verfügbar (Tutorial [http://wiki.delphigl.com/index.php/Tutorial_Cubemap]).

Lernt man natürlich viel weniger bei ;)


Mathematiker - Do 30.07.15 15:34

Hallo,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Falls ihr irgendwann keine Lust mehr drauf habt, das von Hand auszurechnen: das Problem nennt sich Cubemap [http://wiki.delphigl.com/index.php/Cubemap] und ist in OpenGL in Hardware verfügbar

Danke für den Hinweis, aber ... jetzt erst recht! :zwinker:
Was OpenGL kann, können wir in der EE schon lange. :mrgreen:

Beste Grüße
Mathematiker


Horst_H - Do 30.07.15 15:38

Hallo,

der wichtigste Link funktioniert nicht:
Zitat:

Wer übrigens eine tiefergehende Beschreibung zu diesem Thema sucht, die auch auf andere Reflexionsmethode eingeht (allerdings in Englisch), sollte sich mal dieses ausführliche Tutorial von Nvidia http://developer.nvidia.com/object/cube_maps.html ansehen.


Gruß Horst


Martok - Do 30.07.15 16:00

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
der wichtigste Link funktioniert nicht:
Zitat:

Wer übrigens eine tiefergehende Beschreibung zu diesem Thema sucht, die auch auf andere Reflexionsmethode eingeht (allerdings in Englisch), sollte sich mal dieses ausführliche Tutorial von Nvidia http://developer.nvidia.com/object/cube_maps.html ansehen.
Auf der polnischen Seite ist er noch drauf: http://www.nvidia.pl/object/cube_maps.html. Ist aber nicht wirklich interessant. Eher hilft da der hier [http://www.nvidia.ru/object/cube_map_ogl_tutorial.html], aber ist auch nicht viel mehr als im DGL-Wiki steht.


Mathematiker - Do 30.07.15 19:48

Hallo,
ich muss noch einmal zurückkommen auf
user profile iconBoldar hat folgendes geschrieben Zum zitierten Posting springen:
Zwischen einer Spiegelung und einer Projektion auf die Riemansche Kugel gibt es übrigens bedeutende Unterschiede - das wird schon klar, wenn man sich überlegt, was am Pol passiert - bei der Riemann-Kugel steht am Pol unendlich, während bei einer Spiegelung die "unendliche Bildkoordinate" schon auf dem 45. Breitengrad liegt.

Die Argumentation ist klar.
Weiter gedacht bedeutet das aber auch, dass es gar nicht geht, ein endliches(!) Ausgangsbild auf eine Halbkugel zu projizieren. Die Randbereiche wären Bilder aus dem "Unendlichen" und nur für uns sichtbar, wenn wir selbst unendlich weit entfernt wären.
Damit können wir nur eine Kugelkappe erzeugen und sehen. M.C.Eschers Darstellungen sind aber Halbkugeln. D.h., er hat somit auch keine physikalisch korrekte Projektion genutzt. Der spezielle Effekt einer korrekten Projektion entsteht durch die spezielle Wahl seiner Ausgangsbilder, d.h. durch die Genialität des Künstlers.

Meine Vermutung: Escher verwendete die inverse stereografische Projektion. Evtl. hat er auch "nur" eine reale Spiegelung "abgezeichnet". Da Escher ein guter Mathematiker war; man denke nur an seine unmöglichen Körper und die Parkettierungen (Symmetriegruppen); glaube ich das erste.
Die inverse stereografische Projektion erlaubt die Projektion einer Ebene auf eine Kugel. Die unter https://www.physicsforums.com/threads/inverse-of-the-stereographic-projection.108175/ genannten Gleichungen entsprechen aber den von mir verwendeten. Ohne es zu wissen, habe ich diese Projektionsart genutzt.
Ganz verkehrt ist es also nicht.

Allerdings löst das noch nicht die Aufgabe, eine exakte(!) Reflexion hinzubekommen.
Trotz des guten Vorschlags von user profile iconjfheins gelingt es mir nicht für die Kugel(!) vernünftige Werte zu bestimmen, sobald ich mich zu den Polen bewege.
D.h. nicht, dass ich jetzt aufgebe, aber ich war wohl doch etwas großkotzig, als ich verkündete: Jetzt erst recht.

Beste Grüße
Mathematiker

Nachtrag: In "Geometrie und ihre Anwendungen" (http://www1.uni-ak.ac.at/geom/buecher_geom_probeseiten.php) von Georg Glaeser Seite 157 steht:
Zitat:
Wählt man als Projektionsebene der stereografischen Projektion statt pi die Tangentialebene in S (Südpol), werden alle Bildlängen verdoppelt ...
P und P* sind invers bezüglich des Kreises ...
Die ... Inversion der Ebene [an der Kugel] ist für ein dreidimensional denkendes Lebewesen etwas ganz Einfaches, nämlich die Spiegelung einer Kugelhälfte an der Berandungsebene.
Das 'missing link' ist eine stereografische Projektion. ...

Meine Lösung ist also korrekt, wenn das Ausgangsbild die Kugel berührt.
Ein paar Seiten später wird ausgeführt, dass für einen Abstand > 0 zwischen Ebene und Kugel für jeden Punkt eine Gleichung 4.Grades zu lösen ist.
Nebenbei (Achtung! Werbung!): Das genannte Buch von Glaeser ist hervorragend.


user32 - Do 30.07.15 23:16

Aha. Bitmap Optimierung. Hat mich jemand gerufen? ;]

Folgende Version ist um den Faktor 100 (Hundert) schneller.

Wenn man dein paintbox1.Canvas.Draw(0,0,bitmapz); in der ersten Schleife drin lässt, immer noch um den Faktor 10.
Kannst du dir aussuchen. So viel sieht man da jetzt nicht.

Habe alle Canvas-Funktionen rausgeschmissen, sowie deine Double-Variablen gegen Singles getauscht.
Bei Grafikbearbeitung brauch man selten doppelte Präzision und rechnen mit 64-bit-Fließkomma ist eben deutlich langsamer als mit 32-bit.


Mathematiker - Do 30.07.15 23:41

Hallo,
user profile iconuser32 hat folgendes geschrieben Zum zitierten Posting springen:
Aha. Bitmap Optimierung. Hat mich jemand gerufen? ;]
Folgende Version ist um den Faktor 100 (Hundert) schneller.

Ich bin ehrlich gesagt fasziniert. Wie geht denn so etwas? 100fach schneller. :!:
Vielen, vielen Dank!
Ich habe es gerade getestet: Deine Lösung ermöglicht ja sogar in Echtzeit die waagerechte bzw. senkrechte Verschiebung des Mittelpunktes, d.h. die Kugel kann man drehen! :D

Darf ich dich für weitere Programme "anstellen"? :mrgreen:

Beste Grüße
Mathematiker


Horst_H - Fr 31.07.15 08:04

Hallo,

jau, das jede Zeile das Bild neu gezeichnet wird ist suboptimal...
Das es bei 960 Zeilen nur 100 mal schneller wird ist erstaunlicher ;-), wieso ist mir das nicht aufgefallen?
Ich habe das Program unter wine laufen und habe access violation:
capture29363

Gruß Horst
P.S:
Unter Win7 habe ich keine Fehler..
Ich habe keine Verbesserung gefunden, obwohl ich keine Unterschiede zwischen single und double habe ( Turbo Delphi ).es dauert bei mir 0.01265 Sekunden pro Bildberechnung.Die Ausgabe auf die Paintbox ist nicht drin.
Für wine/Lazarus musste ich ExtractFilePath nutzen, weil er sonst die Bilder nicht findet.Aber dabei hatte ich kein umgerechnetes Bild.Scanline will da nicht so recht.

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
procedure TForm1.Button1Click(Sender: TObject);
var
    bitmap,bitmap2,bitmapz:tbitmap;
    T1,T0 : TDatetime;
    rect:trect;
    P : PByteArray;
    p2: ^byte;
    p3,px: ^byte;

    i,j,n,k,waagerecht,senkrecht,bmw:integer;
    xm,ym:integer;
    bbinv,
    xk,yk,q,xi,yi,sq:single;

procedure ladejpg(const FileName: String; Bild: TBitMap);
var Jpeg: TJpegImage;
begin
  Jpeg:=TJpegImage.Create;
  jpeg.LoadFromFile(filename);
  Bild.Assign(Jpeg);
  jpeg.free;
end;
begin

   ladejpg(ExtractFilePath(application.ExeName)+combobox1.text+'.jpg',image1.Picture.Bitmap);
   application.ProcessMessages;

   //Verschiebung des Spiegelsmittelpunkts
   waagerecht:=bb;
   senkrecht:=bb;

   bitmap2:=tbitmap.create;
   bitmap2.assign(image1.Picture.Bitmap);
   bitmap2.PixelFormat:=pf32bit;

   bitmap:=tbitmap.Create;
   bitmap.width:=bb;
   bitmap.height:=bb;
   //Abbildung auf doppelte Größe strecken
   rect.left:=0;
   rect.Top:=0;
   rect.right:=bb;
   rect.Bottom:=bb;
   bitmap.canvas.copyrect(rect,bitmap2.Canvas,image1.clientrect);
   //Mittelpunkt
   xm:=paintbox1.Width div 2;
   ym:=paintbox1.height div 2;

   bitmapz:=tbitmap.Create;
   bmw :=paintbox1.Width;
   bitmapz.Width:= bmw;
   bitmapz.height:=paintbox1.height;
   bitmapz.PixelFormat:=pf32bit;

   bitmapz.Canvas.Brush.Color:=clwhite;
   bitmapz.Canvas.Rectangle(-1,-1,961,961);
   //version 2
   //zeilenweise pixel ermitteln
   bbinv := 1/bb;
   T0 := now;
For n := 1 to runden do
Begin
   P2 := BitMap.ScanLine[0];
   P3 := bitmapz.ScanLine[0];

   for i:=0 to bb-1 do begin
     yi:=(2*i-senkrecht)*bbinv;  //yi:=(2*i-senkrecht)/bb;
     for j:=0 to bb-1 do begin
           //Umwandeln in komplexe Koordinaten
           xi:=(2*j-waagerecht)*bbinv;
           //Transformation auf die Riemann-Kugel
           sq := xi*xi + yi*yi;
           //nur zeichnen, wenn in unterer Hälfte der Riemann-Kugel
           if sq<1.0 then begin
             q:=480/(sq+1.0);
             px := p3;
             dword(px) := dword(px) -((trunc(yi*q)+ym)*bmw + trunc(xi*q)+xm)*4;
             pDword(px)^ :=  pDword(p2)^;
{           //fuer pf24Bit mal als Gedanke
             k := pDword(p2)^ AND $00FFFFFF;
             pDword(px)^ := pDword(px)^ AND $FF000000 OR k;
}

           end;
           inc(p2,4);
     end;
     dec(p2, 8*bitmap.Width);
   end;
End;
   T1 := now;
   paintbox1.Canvas.Draw(0,0,bitmapz);

   bitmap.free;
   bitmap2.free;
   bitmapz.free;
   Label1.Caption := Format('%10.5f',[(T1-T0)/n*86400.0]);
end;


user32 - Fr 31.07.15 18:40

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,
user profile iconuser32 hat folgendes geschrieben Zum zitierten Posting springen:
Aha. Bitmap Optimierung. Hat mich jemand gerufen? ;]
Folgende Version ist um den Faktor 100 (Hundert) schneller.

Ich bin ehrlich gesagt fasziniert. Wie geht denn so etwas? 100fach schneller. :!:
Vielen, vielen Dank!
Ich habe es gerade getestet: Deine Lösung ermöglicht ja sogar in Echtzeit die waagerechte bzw. senkrechte Verschiebung des Mittelpunktes, d.h. die Kugel kann man drehen! :D

Darf ich dich für weitere Programme "anstellen"? :mrgreen:

Beste Grüße
Mathematiker


Sicher, wenn ich helfen kann immer gerne :tongue:
Wobei ich mich selbst noch als Optimierungs-Newbie sehe..

Joa, Canvas-Funktionen wie LineTo oder Pixels, sind sehr einfach und praktisch, aber bei Software Rendering kann man es echt vergessen.
Einzelnd aufgerufen okay, aber sobald eine Schleife dabei ist....


user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

jau, das jede Zeile das Bild neu gezeichnet wird ist suboptimal...
Das es bei 960 Zeilen nur 100 mal schneller wird ist erstaunlicher ;-), wieso ist mir das nicht aufgefallen?
Ich habe das Program unter wine laufen und habe access violation:
[Bild: capture29363]

Gruß Horst
P.S:
Unter Win7 habe ich keine Fehler..
Ich habe keine Verbesserung gefunden, obwohl ich keine Unterschiede zwischen single und double habe ( Turbo Delphi ).es dauert bei mir 0.01265 Sekunden pro Bildberechnung.Die Ausgabe auf die Paintbox ist nicht drin.
Für wine/Lazarus musste ich ExtractFilePath nutzen, weil er sonst die Bilder nicht findet.Aber dabei hatte ich kein umgerechnetes Bild.Scanline will da nicht so recht.

Du meinst Lazarus kennt nicht Single/Double? :shock: Oder nur keinen Geschwindigkeitsunterschied gemessen?
Ich vermute das kommt wohl auf den Compiler an.
Bei mir läuft das ursprüngliche Programm, alleine durch Umstellen auf Single, ca 33% schneller.
Deswegen hab ich auch Sachen wie sq() gegen x*x getauscht, weil diese Funktionen meistens mit Extended rechnen und zudem ja noch zusätzlich eine externe Funktion aufgerufen wird.
Würde mich mal interessieren, ob wenn du die FPU manuell auf 32-bit setzt, das immer noch gleich schnell ist.


Horst_H - Fr 31.07.15 23:52

Hallo,

natürlich kennt Lazarus wie Turbo Delphi single und double.
Es ändert das Tempo bei mir nicht.
Das ich kein Bild unter Linux/wine bekomme liegt einfach nur am geänderten Aufbau der Bitmaps.
Unter Windows ist die oberste Zeile 0 im hohen Speicherbereich und die anderen kommen im Speicher davor.
Man wandert von Zeile zu Zeile zu kleineren Speicheradressen.
Unter Linux ist es genau andersherum.
Zeile 0 ist oben auf dem Bildschirm und die niedrigste Postion im Speicher und man wandert im Speicher zu höheren Adressen.
Deshalb stimmt die Bestimmung von px nicht mehr, weil die Zeilen jetzt falsch berechnet werden zudem von der falschen Startposition.Das gibt nur deshalb nicht immer eine Zugriffsverletzung, weil das Bitmap das davor erzeugt ist auch oft genau davor liegt und völlig überschrieben wird, was keiner sieht, es wird ja nicht zur Anzeige gebracht.

Gruß Horst


user32 - Sa 01.08.15 04:05

Moderiert von user profile iconNarses: Komplettzitat des vorigen Beitrags entfernt.

Ja, stimmt. Ich wusste garnicht, dass es bei Linux anders ist. Naja, man könnte sagen Linux hat es richtig gemacht und Microsoft falsch :)
Aber wenn du die Pointer Adressen umstellst, sollte es bei Linux ja dann auch gehen.


SMO - So 02.08.15 01:45

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
bekomme liegt einfach nur am geänderten Aufbau der Bitmaps.
Unter Windows ist die oberste Zeile 0 im hohen Speicherbereich und die anderen kommen im Speicher davor.
Man wandert von Zeile zu Zeile zu kleineren Speicheradressen.
Unter Linux ist es genau andersherum.


Stimmt, unter Windows sind Bitmaps gewöhnlich "bottom-up". Aber man kann auch "top-down" Bitmaps anlegen, dafür muss man einfach eine negative Höhe angeben. Delphis TBitmap Kapselung unterstützt das allerdings nicht, d.h. man müsste die Windows-API direkt benutzen.
Wenn man ordentlich programmiert, dann ist der Speicheraufbau von Bitmaps eigentlich irrelevant. Entweder ruft man für jede Zeile TBitmap.Scanline auf um den passenden Pointer zu bekommen, oder man ermittelt initial den "Pitch" (Schrittweite von einer Scanline zur nächsten, im Fall von Windows eben ein negativer Wert) und addiert ihn nach jeder Zeile auf den aktuellen Scanline-Pointer.