Rotationen im Raum

Hallo zusammen,

ich lege mir jetzt schon seit 3 Tagen die Karten bei einem bestimmten Problem. Eventuell kann mit hier ja jemand helfen.

Ich möchte ein Foto im Raum frei drehen. Dazu habe ich ein Ergebnisbild der Größe X,Y in die das Foto passend skaliert wird. Sind nun alle 3 Winkel 0°, ist das Ergebnisbild = Foto*Skalierungsfaktor. Der Einfachheit halber nehme ich an, dass die Mitte des Fotos mein 0-Punkt ist. Daraus ergibt sich, daß die linke obere Ecke meines Bildes {-FotoWidth/2,-FotoHeight/2,0} ist, die rechte obere {FotoWidth/2,-FotoHeight/2,0} etc. Nun drehe ich diese 4 Punkte im Raum (Mit Hilfe einer Matrix soweit kein Problem) und erhalte meine neuen 4 Punkte. Theoretisch könnte ich einfach jeden Punkt des Fotos rotieren und dann entsprechend auf das Ergebnisbild projezieren und dabei einen fiktiven Fluchtpunktfaktor einrechnen. Das geht aber nicht, da die Berechnung viel zu lange dauern würde wenn das Foto ein 10MPixel Bild ist.

Also muss ich anders herum eine Lösung finden. Ich muss für jedes Pixel meines Ergebnisbildes, den passenden Pixel im Foto finden. (Klar das es u.U. keinen gibt wenn das Bild z.B. um die X-Achse gedreht wird bekommt mein Ergebnisbild oben und unten schwarze Balken). Mein Ansatz war, daß ich quasi wie ein Raytracer eine Gerade definiere die in einem fiktiven Betrachterpunkt entspringt und durch das Ergebnispixel geht. Nun muss ich den Schnittpunkt der Geraden mit meinem Foto finden und habe das richtige Pixel.

Mein Lösungsansatz sieht folgendermassen aus:

Zunächst rotiere ich die 3 Ecken des Fotos x1,y1 - x2,y2 - x3,y3 im Raum mit der Formel:

// Z-Achse

x=(x*cosz-y*sinz)
y=(x*sinz+y*cosz)

// X-Achse

y=(y*cosx-z*sinz)
z=(y*sinz+z*cosz)

// Y-Achse

x=(x*cosy+z*siny)
z=(x*-siny+z*cosy)

Daraus berechne ich mir die Ebenengleichung

e: {x1,y1,z1}+ r * { (x2-x1),y2-y1),(z2-z1) } + s * { (x3-x1),(y3-y1),(z3-z1) }

Der Normalenvektor daraus ist:

n: { (y2-y1)*(z3-z1)-(z2-z1)*(y3-y1), -((x2-x1)*(z3-z1))-((z2-z1)*(x3-x1)) , (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1) }

Da diese alles Konstanten sind kann ich diese berechnen und nenne sie nun

n: {xn,yn,zn}

Daraus folgt die Gleichung für die Ebene ist

x*xn+y*yn+z*zn=(x1*xn+y1*yn+z1*zn)

Nun definiere ich eine Gerade die von {0,0,z} (wobei z ein fester Fixpunkt als Betrachterpunkt ist und natuerlich negativ) durch das jeweile Ergebnisbild Pixel geht {x,y,0}

g: {0,0,z} + t*{ x,y,-z}

daraus folgt

x=t*x;y=t*y;z=z-t*z

Setze ich nun diese Werte in meine Ebenengleichung ein erhalte ich:

t*x*xn+t*y*yn+(z-t*z)*zn=(x1*xn+y1*yn+z1*zn)

aufgelöst nach t:

t=(x1*xn+y1*yn+z1*zn-z*zn)/(x*xn+y*yn-z*zn)

Diesen Wert setze ich dann wieder in meine Geradengleichung ein und erhalte somit den Schnittpunkt der Gerade mit der Ebene.

Wenn ich dieses gefundene Pixel nun in mein Ergenisbild projeziere erhalte ich ein nicht befreidigendes Ergebnis da sich das Bild nicht gänzlich dreht und bei Drehung um zwei Achsen gleichzeitig sogar vollkommen falsch ist.

Wo ist also der Denkfehler

Schonmal Danke für das Lesen dieses langen Posts.

Gruß

Claus

Inverse Matrix
Hallo Claus,

Nun drehe ich diese 4
Punkte im Raum (Mit Hilfe einer Matrix soweit kein Problem)
und erhalte meine neuen 4 Punkte.

Genau.

Also muss ich anders herum eine Lösung finden. Ich muss für
jedes Pixel meines Ergebnisbildes, den passenden Pixel im Foto
finden.

Andersherum, also die Umkehrmatrix der obigen Matrix. Da Du sie ja durch die Drehungen konstruiert hast, kannst Du das Zielbild ja zurückdrehen und da die Zurückdrehmatrix konstruieren. Diese MAtrix sagt Dir dann für jedes Pixel des Zielbildes, welches Pixel des Ausgangsbildes Du dorthin kopieren musst.

Mein Ansatz war, daß ich quasi wie ein
Raytracer

Ein Raytracer macht in diesem Fall das gleiche mit mehr Rechnerei.

Viele Grüße
Stefan

Hi Stefan,

schonmal danke für Deine schnelle Antwort, aber leider weiß ich nicht genau was Du mir damit sagen willst.

Soll das heißen, daß ich wenn ich diese Umkehrmatrix erstelle ich einfach in diese Matrix meine x,y,z Werte des Ergebnisbildes (wobei z ja immer =0 ist) einsetze und das entsprechende FotoPixel bekomme ? Kann ich mir dann den ganzen Rechenaufwand mit der Ebene und der Geraden sparen oder muss ich das weiterhin machen und nur die Werte aus der Umkehrmatrix dort einsetzen statt der der normalen Matrix ?
Wie genau mache ich das mit der Umkehrmatrix ? Ich multipliziere erst meine 3 Rotationsmatrixen fuer die drei Achsen und bilde aus dem Ergebnis dann die Umkehrmatrix ? Das wird aber ein extremer Wust an Zahlen :wink:

Gruß

Claus

Moin moin,

besteht das Problem noch? Wenn ja, musst Du es wohl noch etwas genauer schildern.
Du hast ein Bild in der x-y-Ebene bei z=0, richtig? Und das wird jetzt im Raum gedreht. Um welche Winkel und Achsen?

Daraus berechne ich mir die Ebenengleichung

e: {x1,y1,z1}+ r * { (x2-x1),y2-y1),(z2-z1) } + s * {
(x3-x1),(y3-y1),(z3-z1) }

Das soll doch bestimmt die Ebene sein, in der das gedrehte Bild liegt.
Und jetzt?
Dein Raytracing-Ansatz scheint mir auch nicht logisch zu sein. Stell Dir vor, die berechnete Ebene ist eine Projektionsfläche und Dein Originalbild ein Dia, und da wo Dein Auge ist ist eine Projektionslampe. Was siehst Du auf der Leinwand? Doch wohl das Originalbild, oder? Genau das müsste doch bei Deinem Verfahren rauskommen.
Du willst doch aber dass das Bild wirklich gedreht wird. Kannst Du nicht für alle Punkte auf dem Rand (Umfang) die neuen Koordinaten berechnen und dann für alle Punkte innerhalb irgendwelche Verhältnisgleichungen aufstellen?

Olaf

Hallo

Ich
multipliziere erst meine 3 Rotationsmatrixen fuer die drei
Achsen und bilde aus dem Ergebnis dann die Umkehrmatrix ? Das
wird aber ein extremer Wust an Zahlen :wink:

IMHO nicht. Eine Rotation im Raum (oder sonstwo) kann
man immer so auffassen, als würde man seinen Punkte-
salat um einen Raumvektor drehen, der im Ursprung
beginnt. V{0,0,0 -> vx,vy,vz} = V(px,py,pz)(normiert)

Die Drehung um diesen Vektor läßt sich durch eine
einzige Rotationsmatrix beschreiben, siehe dazu:
[Drehung mit beliebigem Einheitsvektor v=(v1,v2,v3)T als Drehachse:]
http://de.wikipedia.org/wiki/Drehmatrix

Hat man nun seine Raumachse festgelegt un einen
Winkel bestimmt, um den alles gedreht werden soll,
so erhält man die Rotationsmatrix nach der o. ange-
gebenen Formel. In C-Pseudocode sieht das etwa so aus:

 Matrix setrotmatrix(double theta, Vektor axis) {
 double x = axis.x, y = axis.y, z = axis.z;
 double c = cos(theta), s = sin(theta), t = 1.0 - c;
 Matrix m;
 m[0][0] = t \* x \* x + c;
 m[0][1] = t \* x \* y + s \* z;
 m[0][2] = t \* x \* z - s \* y;
 m[1][0] = t \* x \* y - s \* z;
 m[1][1] = t \* y \* y + c;
 m[1][2] = t \* y \* z + s \* x;
 m[2][0] = t \* x \* z + s \* y;
 m[2][1] = t \* y \* z - s \* x;
 m[2][2] = t \* z \* z + c;
 return Matrix;
 }

Jetzt wird nur noch jeder Pixel p(xk,yk,zk) mit
der Matrix multipliziert und man erhält die
Pixel p(xl,yl,zl), die man dann (z.B. durch
weglassen von zl bei der Anzeige) auf die
x/y-Bildschirmebene projiziert.

Möglicherweise ist es sinnvoll, eine
Art „Schwerpunkt“ des Bildes zu bestimmen
und „im Schwerpunkt“ zu rotieren, das
erhält man durch temporäre Transformation
der Bildkoordinaten +/ Schwerpunktkoordinaten
vor/nach der Rotation.

C-Pseudo:

 Vektor rotate(Vektor Pixel, Matrix m, Vektor Schwerpunkt)
{ 
 double x = Pixel.x-Schwerpunkt.x, 
 y = Pixel.y-Schwerpunkt.y, 
 z = Pixel.z-Schwerpunkt.z;

 Vektor PixNeu;
 PixNeu.x = m[0][0]\*x + m[0][1]\*y + m[0][2]\*z;
 PixNeu.y = m[1][0]\*x + m[1][1]\*y + m[1][2]\*z;
 PixNeu.z = m[2][0]\*x + m[2][1]\*y + m[2][2]\*z;

 return PixNeu+Schwerpunkt;
}

Oder so ähnlich …

Grüße

CMБ

Hi Semjon,

danke für Deine Antwort, aber das hilft mir nicht weiter. Das ist ja genau die Projektion vom Quellbild auf das Ergebnisbild die ich nicht machen kann. Das hat zwei Gründe:

  1. Erhalte ich kein flächenfüllendes Ergebnisbild. Es kann vorkommen, je nach Winkel, das der Abstand zwischen den Quellpixeln auf das Ergenispixel projeziert größer als 1 ist und ich somit im Ergebnisbld „Löcher“ habe.

  2. Ich muss die Berechnung für jedes Quellpixel anwenden. Das bedeutet bei einem 10MPixel Bild einen viel zu hohen Rechenaufwand.

Noch einmal zur Verdeutlichung meines Problems.

Ich habe ein Digitales Foto mit z.B. ca. 12MPixel und einer Auflösung von ca. 4000x3000 Pixeln. Dieses Foto stelle ich auf dem Rechner dar in einem Fenster von 800x600 Pixeln. Soweit recht einfach indem man ensprechend skaliert.
Nun drehe ich das Foto um alle 3 Achsen gleichzeitig um seinen Mittelpunkt. Das ganze soll natürlich animiert sein, also kein fester Winkel, sondern von Winkel 0° bis Winkel x° wobei max wx=wy=90° und max wz=360°. Nun muss ich für jedes Pixel in meinem Fenster, also 800x600 Pixel den entsprechenden Pixel aus dem Foto errechnen. Bei wx=90° oder wy=90° würde ich dann z.B. kein Pixel mehr finden, da ja das Foto „flach“ liegt.

Gruß

Claus

Hi Olaf,

danke für Deine Antwort,

ich habe im Thread weiter unten nochmal versucht mein Problem genauer zu beschreiben.

Gruß

Claus

Hallo

danke für Deine Antwort, aber das hilft mir nicht weiter. Das
ist ja genau die Projektion vom Quellbild auf das Ergebnisbild
die ich nicht machen kann. Das hat zwei Gründe:

  1. Erhalte ich kein flächenfüllendes Ergebnisbild. Es kann
    vorkommen, je nach Winkel, das der Abstand zwischen den
    Quellpixeln auf das Ergenispixel projeziert größer als 1 ist
    und ich somit im Ergebnisbld „Löcher“ habe.

  2. Ich muss die Berechnung für jedes Quellpixel anwenden. Das
    bedeutet bei einem 10MPixel Bild einen viel zu hohen
    Rechenaufwand.

Sehe ich nicht so. Du brauchst ja nicht die 10MPixel zu drehen
sondern lediglich das auf 800x600 heruntergerechnete „Anzeigebild“,
das wären 480,000 Matrix/Vektor-Operationen pro freiem Drehschritt.

Schaffst Du das nicht - oder ist dir das zu langsam, bleibt imho
nur die Verwendung einer Technik aus der ‚texture mapping‘-Welt,
ggf. in der Grafikkartenhardware (über OpenGL).
z.B.: http://gpwiki.org/index.php/OpenGL:Tutorials:Tutoria…

Noch einmal zur Verdeutlichung meines Problems.
Ich habe ein Digitales Foto mit z.B. ca. 12MPixel und einer
Auflösung von ca. 4000x3000 Pixeln. Dieses Foto stelle ich auf
dem Rechner dar in einem Fenster von 800x600 Pixeln. Soweit
recht einfach indem man ensprechend skaliert.
Nun drehe ich das Foto um alle 3 Achsen gleichzeitig um seinen
Mittelpunkt.

Ich vermute mal, du „drehst die Rotationsachse“ um eine
Kombination von x/y und/oder z (x/y reicht in 3D) und
berechnest aus dieser Rotationsachse und der daraus
sich ergebenden Matrix die neuen Bildkoordinaten.

Die Berechnung könnte auch so erfolgen, daß Du nicht sukzessive
die Pixel „zeilenweise“, sondern in „Abständen“, also
zuerst punkt (0,0), dann Punkt (0,32), (0,64) … (32,0), (32,32)
usw. berechnest und dann schrittweise auffüllst. Also eine
Art „Mip-Map“-Technik verwendest. So entstünde das Bild
sehr schnell „grob“ und würde beim Draufschauen immer
genauer erscheinen, beim Drehen aber nur schemenhaft
angezeigt werden.

Das ganze soll natürlich animiert sein, also kein
fester Winkel, sondern von Winkel 0° bis Winkel x° wobei max
wx=wy=90° und max wz=360°. Nun muss ich für jedes Pixel in
meinem Fenster, also 800x600 Pixel den entsprechenden Pixel
aus dem Foto errechnen. Bei wx=90° oder wy=90° würde ich dann
z.B. kein Pixel mehr finden, da ja das Foto „flach“ liegt.

Diese Winkel beziehen sich aber auf die Rotationsachse,
vermute ich mal.

Grüße

CMБ

Hi,

ich sehe schon das Ganze wird nichts wenn ich nicht die Gesamtidee erkläre die dahinter steckt :wink:

Das ganze wird leider etwas länger.

Das Ergebnis meiner Berechnung soll eine Kamerafahrt über ein Foto werden aus dem ich ein Video berechne. Ich habe bereits eine Software geschrieben, die das in 2D kann. Das ist ja auch relativ einfach. Dazu kann ich mich mit Hilfe eines Splines über das Bild bewegen und für jeden Stützpunkt des Splines einen Zoomfaktor (Skalierung) angeben. Somit kann ich mich beliebig über das Bild bewegen und rein und rauszoomen. (Dabei berücksichtige ich natürlich noch die verschiedenen Pixelaspekte und Videonormen, Foto 1:1 und Video 4:3 bzw 16:9 oder HDV, PAL/NTSC etc). Jeder Stützpukt des Splines hat noch eine Zeit wie lange es dauern soll um sich von Punkt A nach B zu bewegen und eine Beschleunigung, bzw Abbremsgeschwindigkeit. Dann rechne ich 50 Vollbilder pro Sekunde aus und mache daraus mein Video mit 50 Halbbildern (PAL) indem ich nur die ensprechenden geraden ooder ungeraden Zeilen benutze. Das muss nicht in Echtzeit geschehen, aber es sollte auch nicht viel länger als 10s für 1s Video brauchen, also ca 5 Vollbilder pro Sekunde sollten machbar sein.

Nun möchte ich das ganze erweitern, so daß ich das Foto auch drehen kann. Dadurch entsteht bei einer Bergkette z.B. ein schöner Effekt als wenn ich über die Berge fliegen würde.

Das bedeutet aber, ich sehe z.B. bei Zoomfaktor 1 nur einen Ausschnitt meines Fotos (720*576 Pixel in PAL 4:3) solange ich das Foto nicht gedreht habe. Drehe ich das Foto jetzt um die X-Achse, würde aber der bisher verdeckte obere Teil des Fotos natürlich sichtbar werden.

Deshalb muss ich der Geschwindigkeit halber nur die Punkte errechnen die ich für das Zielbild auch wirklich brauche, kann aber keinen Fusch machen, da jedes Bild 100%tige Qualität haben muss.

So, jetzt bin ich gespannt ob da jemand einen guten Lösungsansatz hat :wink:

Gruß

Claus

Hallo,

ich habe im Thread weiter unten nochmal versucht mein Problem
genauer zu beschreiben.

leider verstehe ich Deine Raytracing-Idee immer noch nicht.
Auf jeden Fall muss es eine einfache Lösung geben, weil es ja jedes Spielprogramm irgendwie in Echtzeit schafft. Allerdings finden die Berechnungen meist im Grafik-Chip statt.

Kannst Du nicht erstmal berechnen, welche Koordinaten die 4 Eckpunkte Deines Bildes nach der Drehung haben? Dann legst Du den Punkt des Betrachters fest (das Auge) und ziehst einen „Sehstrahl“ zwischen Auge und dem jeweiligen Eckpunkt. Und da, wo dieser Sehstrahl Deinen Bildschirm schneidet, ist die Projektion des Eckpunktes auf Deinen Bildschirm. Und für alle weiteren Punkte des Bildes müsste sich doch was mit (quadratischer oder kubischer) Interpolation machen lassen, oder?

Olaf

Hi,

Nun möchte ich das ganze erweitern, so daß ich das Foto auch
drehen kann. Dadurch entsteht bei einer Bergkette z.B. ein
schöner Effekt als wenn ich über die Berge fliegen würde.

Hmm, also doch noch etwas komplexer als ich dachte …

Immerhin hat „ImageMagick“ eine ‚distort‘-Funktion,
mit der sich auch 3D-Dreheffekte nähern lassen.
Vielleicht wäre das für erste Versuche nützlich?

http://www.imagemagick.org/script/command-line-optio…

Grüße

CMБ

Ok,

versuche ich es mal so zu veranschaulichen:

Halt Dir ein Blatt vor die Augen und drehe es gleichzeitig um X und Y. Dann wird das Blatt umso weniger sichtbar, je mehr du drehst und damit kleiner. Genau diesen Effekt kann ich auf die Art erreichen, wenn ich den Betrachterpunkt irgendwo bei -z setze und Deine Mehtode verwende.

Ich brauche aber einen anderen Effekt. Nämlich den, daß das Blatt quasi auf deinem Aufapfel klebt und dann gedreht wird, wobei Dein Aufapfeln quasi 800x600 Pixel sehen kann. Drehe ich jetzt das Blatt, dann verschwinden die Pixel die in den Minus Bereich von Z gehen (Nach vorne wandern) und die die in den positiven Z-Bereich gehen wandern in die Mitte und von aussen kommen neue Pixel des Blattes, die ich vorher nicht sehen konnte, nach.

Gruß

Claus

Ich brauche aber einen anderen Effekt. Nämlich den, daß das
Blatt quasi auf deinem Aufapfel klebt und dann gedreht wird,
wobei Dein Aufapfeln quasi 800x600 Pixel sehen kann.

Also das mag ich mir jetzt nicht mehr vorstellen, dass irgendwas auf meinem Augapfel klebt…

Trotzdem glaube ich, dass ich Dich verstanden habe. Wenn ein Eckpunkt des gedrehten Bildes bei negativen z-Werten liegt, dann ist das Bild eben nicht vollständig zu sehen. Du willst so einen Kameraflug an einem Foto vorbei machen.
Geht es Dir denn eigentlich ums Programmieren oder nur um das Ergebnis? Ein anständiges Video-Bearbeitungsprogramm sollte das nämlich können, z.B. schon das kostenlose MovieXOne.
Und jedes 3D-Programm (z.B. Realsoft3D) sollte das auch können. Einfach das Bild als Textur auf einen Quader mappen, den Quader beliebig animieren und die Kamera beliebig fliegen lassen.
Vielleicht fragst Du mal im Videobrett.

Olaf