Computergrafik: Kap. 6a (Transformationen)

6. Koordinaten, Transformationen, Perspektive

Bei Grafik-Applikationen sind neben Modellierung der darzustellenden Objekte und Algorithmen zum Zeichnen auch Manipulationsmöglichkeiten von großer Bedeutung:

Animation von Objekten (kontinuierliche Veränderung der Lage und Größe)
interaktives Editieren (Drehen, Ändern der Größe, Spiegeln, Verzerren...)

Behandlung von Transformationen mittels vektorieller Geometrie (lineare Algebra)

Die meisten wichtigen Transformationen sind mathematisch lineare Abbildungen:

Eigenschaft: f(cx+y) = c f(x) + f(y)

Eine lineare Abbildung ist vollständig bekannt, wenn die Bilder der Vektoren einer Basis bekannt sind (z.B. die Bilder der Standard-Basisvektoren ).

Darstellung der linearen Abb. f durch ihre zugehörige Matrix M_f:
in den Spalten von M_f stehen die Bilder der Standard-Basisvektoren unter f.

Allgemein besteht eine Matrix aus p´ q Skalaren m_ij .

Anwendung einer linearen Abbildung f auf einen Vektor durch Multiplikation der Matrix M_f mit dem Vektor
(dabei Schreibweise des Vektors als Spaltenvektor und Multiplikation der Matrix von links an den Vektor wichtig!):

Nacheinander-Anwendung (Komposition) zweier linearer Abbildungen f ° g: wende erst g an, dann f.

f ° g (x) = f(g(x))

Die Komposition wird beschrieben durch das Produkt der zugehörigen Matrizen:

M_f° g = M_f × M_g

mit

Beachte: Das Matrizenprodukt ist nichtkommutativ
(d.h. i. allg. ist N× M ¹ M× N).

Lineare Abbildungen eines Vektorraums (z.B. des R²) in sich selbst heißen auch Endomorphismen. Darstellung durch n´ n-Matrizen (n = Dimension des Vektorraumes).
Eindeutig umkehrbare (bijektive) Endomorphismen heißen Automorphismen. Ihnen entsprechen die regulären Matrizen:
f bijektiv Û M_f regulär Û det(M_f) ¹ 0

Die regulären n´ n-Matrizen (bzw. die Automorphismen des Rⁿ) bilden eine Gruppe, die allgemeine lineare Gruppe GL(n).

(math. Begriff der Gruppe:

Abgeschlossenheit gegenüber der Verknüpfungsoperation
Assoziativgesetz (MN)P = M(NP)
Existenz eines neutralen Elements E: EM = ME = M

(hier die Einheitsmatrix )

zu jedem Element M Existenz eines Inversen M^-1.)

Beispiele für bijektive lin. Abbildungen: Drehungen um den Nullpunkt, zentrische Streckungen mit einem Faktor ¹ 0 vom Nullpunkt aus.
Beispiel für eine nicht-bijektive lin. Abb.: Projektion entlang der x-Achse auf die y-Achse.

Wichtiger Spezialfall der bijektiven lin. Abb.:
orthogonale Abbildungen.
Entsprechend: orthogonale Matrizen.

M orthogonal Û M^T× M = E (d.h. die Transponierte ist die Inverse)
Û die Spaltenvektoren von M bilden eine Orthonormalbasis (paarw. senkrecht u. Länge 1)
Û (Skalarprodukt-Invarianz)
Û (Längen-Invarianz)

Für alle orthogonalen Matrizen hat ferner die Determinante den Betrag 1.
(Die Umkehrung gilt nicht: Beispiel Scherungsmatrizen.)

Die orthogonalen n´ n-Matrizen bilden eine Untergruppe von GL(n), die orthogonale Gruppe O(n).
Alle Elemente von O(n) mit Determinante +1 bilden wiederum eine Untergruppe von O(n), die spezielle orthogonale Gruppe SO(n).

Es gilt:
M Î SO(n) Û M ist Produkt einer geraden Anzahl von Spiegelungen (an Hyperebenen durch den Nullpunkt).

Beispiele:

Drehungen um den Nullpunkt gehören zu SO(n).

Spiegelungen an Geraden durch den Nullpunkt (im R²) bzw. an Ebenen durch den Nullpunkt (im R³) sind orthogonal, aber gehören nicht zu SO(n).

Streckungen mit Streckfaktor c ¹ 1 sind nicht orthogonal.

Einschränkung: für jede lineare Abbildung f gilt (Nullpunkt ist Fixpunkt).

wichtige Transformationen, die nicht zu den linearen Abbildungen gehören:
Translationen (Verschiebungen).

Verschiebungen rechnerisch:
v' = t(v) = v + d_t, d.h. Addition eines konstanten Vektors d_t.

Affine Abbildungen:
alle Abbildungen a, die sich darstellen lassen als

a(v) = f(v) + d mit einer linearen Abbildung f,

d.h. als Komposition einer linearen Abb. und einer Translation.

Es gilt: d = a(0), f(v) = a(v) - a(0) Þ f und d sind eindeutig bestimmt.

Beispiele:

Drehungen um beliebige Punkte
Streckungen mit beliebigen Streckzentren
Schraubungen im R³
Spiegelungen an beliebigen Geraden im R² oder an beliebigen Ebenen im R³
Parallelprojektionen auf beliebige Ebenen im R³

usw.
(lineare Abbildungen und Translationen als Spezialfälle mit enthalten!)

Die bijektiven affinen Abbildungen des Rⁿ in sich bilden eine Gruppe, die affine Gruppe Aff(n).

Eine affine Abb. a heißt Bewegung oder Kongruenzabbildung, wenn ihre zugehörige lineare Abbildung f orthogonal ist,
und eigentliche Bewegung, wenn f sogar in SO(n) liegt.

Beispiele:
Drehungen, Schraubungen, Translationen: eigentliche Bewegungen
Spiegelungen, Drehspiegelungen: uneigentliche Bewegungen
Streckungen: keine Bewegungen, da f(v) = c× v nicht orthogonal (wenn |c|¹ 1).

Bew(n): Gruppe der Bewegungen des Rⁿ (= Untergruppe von Aff(n))

Bew⁺(n): Untergruppe der eigentlichen Bewegungen.

Eine Ähnlichkeitsabbildung ist eine affine Abb. a, die Abstände stets um einen festen Faktor c > 0 verändert:
d(a(u), a(v)) = c × d(u, v).

Ähnlichkeitsabbildungen liegen "zwischen" den affinen Abbildungen und den Kongruenzabbildungen (Bewegungen)
(für Bewegungen ist c = 1).

Jede Ähnlichkeitsabb. hat die Form a(v) = c × M × v + d mit einer orthogonalen Matrix M und c > 0.

Ae(n): Gruppe der Ähnlichkeitsabb. des Rⁿ.
Beispiele: Streckungen, Streckspiegelungen, Drehstreckungen.

Untergruppen-Diagramm:

Man kann affine Abbildungen aus bestimmten Grundoperationen zusammensetzen
Beispiel: Drehung um einen beliebigen, vorgegebenen Punkt P im R²

verschiebe den Drehpunkt in den Nullpunkt
wende Drehung um den Nullpunkt an
mache Verschiebung wieder rückgängig

Man benötigt für Bewegungen im R²:

alle Translationen
Drehungen um den Nullpunkt um alle Winkel
eine Spiegelung

im R³:

alle Translationen
Drehungen um die 3 Koordinatenachsen (alle Winkel)
eine Spiegelung an einer Ebene

Wichtige Grundoperationen im R² sind somit:

(a) Translationen
v' = v + d

(b) Drehungen (Rotationen)

q ist der Drehwinkel
Orientierung im math. positiven Sinne (gegen den Uhrzeigersinn)
Angabe manchmal auch in Bogenmaß:
Winkel [Bogenmaß] = Winkel [Grad] × p / 180.

Spiegelung an der x-Achse:
Vorzeichenwechsel in der y-Koordinate
also
Spiegelung an der y-Achse:
analog,

(d) Skalierungsoperationen
oft mit unterschiedlichen Skalierungsfaktoren in x- und in y-Richtung gebraucht (keine Kongruenzabb.!):

Proportionen und Winkel bleiben nur erhalten, wenn s_x = s_y
(dann liegt eine Ähnlichkeitsabb. vor)
andernfalls Verzerrung des abgebildeten Objekts:

Manchmal benötigt man auch
(e) Scherungen (engl.: shear)

Scherungen sind flächenerhaltend, aber nicht orthogonal (Figuren werden verzerrt).
Matrix einer Scherung in x-Richtung:

für die y-Richtung analog.

Im R³ analoge Grundoperationen;

anstelle der Spiegelung an Koordinatenachsen: Sp. an Koordinatenebenen (xy, xz, yz)

anstelle der Drehung um den Nullpunkt: Drehungen um die Koordinatenachsen R_x,a , R_y,a , R_z,a

Rückführung einer Drehung um eine beliebige Achse AB mit Winkel q auf diese Grund-Drehungen:

1.	Translation der Achse um -A zum Nullpunkt	T_-A
2.	Rotation der Drehachse r in die yz-Ebene (drehe um die y-Achse mit Winkel -a )	R_y,-a
3.	Rotiere die Drehachse auf die z-Achse (drehe um die x-Achse mit Winkel b )	R_x,b
4.	Rotiere um die z-Achse mit Winkel q	R_z,q
5.	Invertiere Transformation von Schritt 3	R_x,-b
6.	Invertiere Transformation von Schritt 2	R_y,a
7.	Invertiere Transformation von Schritt 1	T_A

Veranschaulichung der Schritte 2 und 3. r ist der Richtungsvektor der Rotationsachse, um die die Rotation erfolgen soll. Links: Drehung um die y-Achse, die r in die yz-Ebene dreht (Ergebnis r'). Rechts: Drehung von r' um die x-Achse, so dass er in Richtung der positiven z-Achse zeigt.

Die Winkel a und b lassen sich durch trigonometrische Beziehungen aus den Koordinaten von A und B berechnen.

Koordinatentransformationen

Oft muss man von einem Koordinatensystem in ein anderes umrechnen

Beispiel:
Weltkoordinaten ® normierte Koordinaten ® Gerätekoord.

Koordinatentransformation: komplementär zur Transformation von Objekten

Objekttransformation:	Objekt ändert seine Lage (und evtl. seine Form) Koordinatensystem bleibt fest
Koordinatentransformation:	Objekt bleibt fest Koordinatensystem ändert seine Lage (u. evtl. seine Form)

rechnerisch selber Formalismus:
Multiplikation des Koordinatenvektors mit Transformationsmatrix, ggf. + Translationsanteil (wenn Ursprünge der Koordinatensysteme unterschiedlich)

wenn Translationsanteil entfällt:
Spalten der Matrix = Basisvektoren des alten Koordinatensystems, ausgedrückt durch Koordinaten im neuen System

PostScript: Befehle translate, rotate, scale
ändern das Koordinatensystem

Unterschiede zu Objekttransformationen:

Reihenfolge von Objektkonstruktion und Transformation vertauscht
Änderung des Koordinatensystems beeinflusst alle nachfolgenden Konstruktionen

Homogene Koordinaten

Darstellung affiner Abbildungen und Koordinatentransformationen in der Form M× v+d macht Berechnungen schwerfällig.
Idee: alles in der Form M× v darstellen
Þ bei Komposition von Transformationen nur noch Matrixmultiplikationen,
einheitliche Form aller affinen Abb.

dies wird erreicht durch Hinzunahme einer weiteren Koordinate

aus (x, y) wird (x, y, 1)
aus (x, y, z) wird (x, y, z, 1)

dafür werden Vektoren, die sich nur um einen festen Faktor w¹ 0 unterscheiden, miteinander identifiziert (Klassenbildung).

"homogene Koordinaten"

dem homogenen Vektor (x, y, w) entspricht der kartesische Vektor (x/w, y/w).

Jeder Punkt auf der Geraden durch den Nullpunkt und durch (x/w, y/w, 1) repräsentiert im homogenen Koordinatensystem denselben kartesischen Punkt (x, y) aus dem gewöhnlichen 2D-Koordinatensystem:

In der Tat lassen sich nun die Translationen gleichwertig mit allen anderen affinen Abb. als Produkte "Matrix mal Vektor" berechnen:

Beispiel:

Verschiebe mittels homogener Koordinaten den Punkt (2; 3) um den Vektor (7; 5) und drehe anschließend das Ergebnis um 90° um den Ursprung.
T(7; 5): , entspr. (9; 8)
R(90°): sin 90° = 1, cos 90° = 0, somit
, entspr. (-8, 9)
zusammen: v‘ = R(90°)× T(7;9)× v.

Analog im dreidimensionalen Fall:
vierte, homogenisierende Koordinate,
Darstellung der affinen Transformationen durch 4´ 4-Matrizen.

Grund-Transformationen:

Anwendung dieser Transformationen in Szenengraphen
3D-Szenen werden oft in gerichteten, azyklischen Graphen abgelegt, den sog. Szenengraphen, die durch Aufrufe einer Spezialbibliothek erzeugt werden
z.B. in OpenInventor, VRML, Java3D
(® spätere Übung)

Typisches Szenengraphen-Format (es gibt zahlreiche Varianten!):

Graphische Primitive (grundlegende Objekte: Würfel, Kugel, Kegel etc.) mit default-Eigenschaften (Position am Koordinatenursprung, Einheitsvolumen...) bilden Blattknoten des Graphen
Attribute (Farbe, Textur etc.) und Transformationen sind ebenfalls Knoten des Graphen und werden auf Objektknoten je nach deren Lage im Graphen angewandt.

Beispiel (aus vanDam 2001):

im folgenden Szenengraphen beeinflusst Transformation t0 alle Objekte,
aber t2 beeinflusst nur obj2 und eine Instanz von group3 (welche je eine Instanz von obj3 und obj4 enthält).
t2 wirkt nicht auf obj1 und auf die andere Instanz von group3.

Transformationsknoten enthalten normalerweise mindestens eine Matrix (für homogene Koordinatendarstellung), die die Transformation beschreibt; evtl. noch weitere Parameter.

Bestimmung der Komposition der Transformationsmatrizen (CTM: composite transformation matrix), die auf einen Objektknoten anzuwenden ist:
Multiplikation der Matrizen in den Transformationsknoten bei top-down-Durchlauf des Baumes
(Details abhängig vom Grafikpaket).

Beispiel (aus vanDam 2001):

CTM(o1) = m1
CTM(o2) = m2 × m3
CTM(o3) = m2 × m4 × m5
für einen Punkt v im Objekt o3 errechnet sich seine Position im Weltkoordinatensystem (gültig an der Wurzel des Baumes) als:
CTM× v = (m2 × m4 × m5) × v.

Transformations-Knoten in VRML 97:

In VRML 97 greift man gewöhnlich nicht auf eine allgemeine 4´ 4-Matrixdarstellung für Transformationen zurück, sondern verwendet eine Skalierung S, eine Rotation R und eine Translation T(t) in fester Folge:

(Krömker 2001)

Letzte Änderungen: 19. November 2001.