Unterstützende Datenstrukturen
In diesem Kapitel werden Klassen vorgestellt, die elementare Funktionen für die Implementierung dieser Diplomarbeit bereitstellen.
Als erstes werden verschiedene Klassen für die Verwaltung von Listen gezeigt. Diese Listen mit doppelter Verkettung verwaltet. Die Implementierung erfolgte dabei durch die in C++ spezifizierten Templates, die eine größere Flexibilität erlauben, als es durch andere Mechanismen zu erreichen wäre.
Zum zweiten stellen Vektoren sehr wichtige Objekte dar. Ein wichtiger Punkt dabei ist die Bereitstellung von einfachen Operatoren, mit denen es möglich ist Vektoren zu addieren, subtrahieren, Skalarprodukte und Kreuzprodukte zu bilden.
Um Vektoren manipulieren zu können, vor allem in Hinsicht auf Transformationen, wird eine weitere Klasse erstellt. Diese Klasse bildet eine Rotations- und Translationsmatrix nach. Deren Operatoren können einen Vektor so manipulieren, daß eine geometrische Transformation des Vektors bewerkstelligt wird.
Direkte Verweise
Im folgenden können die einzelnen Kapitel und Unterkapitel direkt durch das Anklicken des entsprechenden Feldes angewählt werden.
Für die Vereinfachung und Vereinheitlichung der Listenverwaltung können verschiedene Klassen verwendet werden. Die Basis für die Listenverwaltung stellt der Knoten dar. Im Falle einer doppelt verketteten Liste könnten dies die Zeiger auf den Nachfolger und Vorgänger sein. Weiterhin sind Zugriffsfunktionen vorhanden, mit deren Hilfe die oben angesprochenen Abhängigkeiten abgefragt werden können.
Die Verwaltung aller Knoten einer Liste übernimmt eine weitere Klasse, die Liste. Durch die Listenklasse können Knoten angehängt, gelöscht oder falls notwendig die gesamte Liste umgehängt werden. Dazu sind Zugriffsfunktionen vorgesehen, welche diese Aufgaben übernehmen.
Bei einer weiteren Listenklasse handelt es sich um Iteratoren, mit deren Hilfe man sich auf einfache Weise durch eine Liste bewegen kann, dazu werden überladene Operatoren zur Verfügung gestellt. Durch diese überladenen Operatoren wird die von C++ vertraute Zeiger-Syntax nachgebildet.
Damit eine Klasse die Eigenschaften eines Knotens erhält, muß diese von Node abgeleitet werden. Dies geschieht bei der Klassendefinition, wobei die Klasse durch die Vererbung die Eigenschaften eines Node erhält. Dadurch ergibt sich folgende Klassendefinition für eine listenfähige Klasse MyNode:
class MyNode : public Node
Zu den Eigenschaften eines Node zählen die Zugriffsfunktionen, mit deren Hilfe Informationen über den aktuellen Zustand des Knotens abgefragt werden. Ebenso kann mit entsprechenden Methoden der vorhergehende oder der nachfolgende Knoten ermittelt werden, wozu die Methoden pred() oder succ() verwendet werden können. Diese Methoden liefern einen Zeiger auf den jeweiligen Knoten zurück.
Da bei den Methoden Node::pred() und Node::succ() Zeiger auf einen Node zurückgegeben werden, ist es notwendig bei einer Zuweisung MyNode = (MyNode*)MyNode.succ() den Rückgabewert auf einen Zeiger des Typs MyNode zu wandeln. Um typsichere Listen zu erhalten werden Templateknoten bereitgestellt. Es ändert sich die Klassendefinition für eine von einem Templateknoten abgeleitete Klasse wie folgt:
class MyNode : public TNode<MyNode>
Ein typsicherer Knoten wird erzeugt, dessen Rückgabewerte der Methoden pred() und succ() immer ein Zeiger auf eine Klasse MyNodeist. Da TNode eine von Node abgeleitete Klasse darstellt, deren typunsichere Methoden überschrieben wurden, ergibt sich die gleiche Funktionalität wie die der Klasse Node.
Diese Liste dient zur Verknüpfung von Listen bestehend aus Knoten vom Typ Node. Diese Liste wird direkt in der Form
List MyList;
instanziiert.
Die Liste MyList erbt somit sämtliche Methoden einer Liste. Dazu zählen verschiedene Methoden, wie die Methode Node* List::Append( Node* node ). Mit dieser Methode kann ein Knoten an die Liste angehängt werden. Ähnlich arbeitet die Methode Node* List::Insert( Node* after, Node* node ). Sie fügt den Knoten node in die Liste nach dem Knoten after ein. Die gegenteilige Funktion hat die Methode Node* List::Remove( Node* node ). Sie hängt den Knoten node aus der Liste aus, ohne ihn aber zu löschen.
Um das erste oder letzte Element der Liste abzufragen, können die Methoden Node* List::first() oder Node* List::last() verwendet werden.
Bevor eine typunsichere Liste deinstanziiert werden kann, müßen alle Knoten aus der Liste entfernt werden.
Die typsichere Version stellt eine Erweiterung der typunsicheren Liste dar. Sie verknüpft Knoten vom Typ TNode in einer Liste. Die Klasse für eine typsichere Liste wird folgendermaßen deklariert:
TList<MyNode> MyList;
Da TList von List abgeleitet ist, stehen der typsicheren Liste die gleichen Methoden, wie die der typunsicheren Liste zur Verfügung.
Für die Deinstanziierung der Liste müßen alle enthaltenen Knoten aus der Liste entfernt werden.
Im Gegensatz zu den beiden obengenannten Listen besitzt die Liste TSmartList eine erweiterte Funktionalität. Damit ein Knoten aus der Liste gelöscht wird, muß die Methode void TSmartList::Delete( T* node ) verwendet werden. Der Destruktor löscht zusätzlich alle Knoten die in der Liste enthalten sind.
Um eine Liste vom Typ TSmartList zu erzeugen muß diese Klasse wie folgt deklariert sein:
TSmartList<MyNode> MyList;
Da TSmartList von TList abgeleitet ist, stehen alle Methoden von TList auch TSmartList zur Verfügung.
Der Iterator stellt verschiedene Operatoren zu Verfügung, die es ermöglichen sich auf einfache Weise durch eine Liste zu bewegen. Dazu dienen die beiden überladenen Postfix-Inkrement-Operatoren ++ und --. Ebenso überladen wird der Operator ->. Entsprechend der Verkettung können die überladenen Operatoren eines Iterators verwendet werden, als ob er ein Zeiger wäre.
Die Instanziierung erfolgt direkt in der folgenden Form:
Iterator MyIterator;
Durch den template-Iterator wird eine typsichere Variante eines Iterators bereitgestellt. Dazu werden die drei im vorigen Abschnitt beschriebenen überladenen Operatoren überschrieben, so daß als Rückgabewert der korrekte Typ des Knotens verwendet wird. Durch die Ableitung vom typunsicheren Iterator besitzt er dessen Funktionalität.
Die Deklaration eines typsicheren Iterators geschieht wie folgt:
TIterator<MyNode> MyIterator;
Die Klasse Vector3D implementiert verschiedene Operatoren für die Anwendung von analytischer Geometrie im 3-dimensionalen Vektorraum. Aus Gründen der Effizienz nur die Operatoren +=, -= und *= implementiert. Die anderen Operatoren (+, - und *) legen ein zusätzliches Element vom Typ Vector3D auf dem Stack ab, was zu einem zusätzlichen Zeitverbrauch führt.
Der Vergleichsoperator erlaubt den direkten Vergleich von zwei Vektoren. Der Operator vergleicht die Komponenten der Vektoren und gibt bei einer Übereinstimmung aller drei Komponenten TRUE zurück.
Definition der Operators:
BOOL Vector3D::operator ==( const Vector3D& v )
2.1.2.a Vektoraddition
Der Additionsoperator addiert die Komponenten eines zweiten Vektors zu den eigenen Komponenten hinzu.
Definition des Operators:
Vector3D& Vector3D::operator +=( const Vector3D& v )
2.1.2.b Vektorsubtraktion
Der Subtraktionsoperator ist bis auf das Vorzeichen identisch mit dem Additionsparameter.
Definition des Operators:
Vector3D& Vector3D::operator -=( const Vector3D& v )
Für die Multiplikation werden verschiedene Operatoren bereitgestellt. Zu diesen zählen das Skalarprodukt, das Kreuzprodukt sowie die Multiplikation mit einem Skalar oder einer Translationsmatrix.
2.1.3.a Multiplikation mit Skalar
Bei der Multiplikation mit einem Skalar werden die einzelnen Komponenten des Vektors mit dem Skalar multipliziert.
Definition des Operators:
Vector3D& Vector3D::operator *=( double scalar )
2.1.3.b Multiplikation mit einer RotLat
Eine RotLat wird auf den Vektor angewendet. Dadurch kommt es zu einer Transformation der Vektorkoordinaten.
Definition des Operators:
Vector3D& Vector3D::operator *=( RotLat& r )
2.1.3.c Kreuzprodukt
Das Kreuzprodukt mit einem zweiten Vektor wird gebildet. Das Ergebnis wird anschließend in den Vektor rückgespeichert.
Definition des Operators:
Vector3D& Vector3D::operator *=( Vector3D& v )
2.1.3.d Standard-Skalarprodukt
Das Skalarprodukt mit einem zweiten Vektor wird berechnet und zurückgeliefert.
Definition des Operators:
double Vector3D::operator *( CONST Vector3D& v )
Durch den Aufruf der Methode wird der Vektor auf die euklidische Länge +1 normiert.
Definition der Methode:
Vector3D& Vector3D::Normalize()
Die Komponenten des Vektors können durch die folgenden Accessoren abgefragt werden.
Definition der Accessoren:
double Vector3D::GetX()
double Vector3D::GetY()
double Vector3D::GetZ()
Durch den folgenden Accessor kann die Länge eines Vektors erfragt werden.
Definition des Accessors:
double Vector3D::GetNorm()
Für die Erleichterung der Anwendung von geometrischen Transformationen, wird die Klasse RotLat zur Verfügung gestellt. Diese Klasse bildet eine Translationsmatrix nach. Sie ist zusammengesetzt aus einer 3x3 orthonormalen Rotationsmatrix R und einem 1x3 Translationsvektor T. Im allgemeinen wird eine Transformationsmatrix durch eine 4x4 Matrix dargestellt. Da die 4. Zeile aber eine auftretende Scherung oder perspektive Transformation darstellt und diese nicht gebraucht wird, wird nur die obere 4x3 Matrix verwendet. Dies führt zu keiner Beschränkung in der Anwendung der Transformationsmatrix.
Für eine Änderung der Transformationsvorschrift stehen Manipulatoren zur Rotation und Translation zur Verfügung. Weitere Manipulatoren können die Matrix in einen definierten Zustand überführen oder mit einer zweiten RotLat gleichsetzen.
|
| |
r11 |
r12 |
r13 |
| |
|
| |
t14 |
| |
|
|
| R = |
| |
r21 |
r22 |
r23 |
| |
, T = |
| |
t24 |
| |
, M = [R|T] |
(Gl. 3.1) |
|
| |
r31 |
r32 |
r33 |
| |
|
| |
r34 |
| |
|
|
Nach [ Fole90, Seite 217-222] kann diese Matrix auch als ein Koordinatensystem betrachtet werden, wobei die Spalten der Rotationsmatrix R die neuen Koordinatenachsen angeben. Der Ursprung wird durch den Translationsvektor T angegeben. Dabei sind die Vektoren die Basisvektoren des lokalen Koordinatensystems in Koordinaten des Weltsystems.
Mittels Operatoren kann eine RotLat-Matrix auf Vektoren angewendet werden. Dabei ist es möglich die Matrix oder die inverse Matrix auf den Vektor anzuwenden, was der Hin- bzw. Rücktransformation entspricht.
Nach [ Meyb90, Seite 318f] können die Abbildungsmatrizen der Drehungen um die verschiedenen Achsen durch die folgenden Drehmatrizen beschrieben werden. Die neu entstandene Drehmatrix D wird durch den Manipulator von links an die Matrix der RotLat-Klasse multipliziert. Der Drehsinn der Rotation ist gleich dem mathematischen Drehsinn, d.h. blickt man in Richtung des Achsenvektors erfolgt eine positive Drehung (Drehwinkel w>=0) im Uhrzeigersinn.
3.1.1.a Rotation um eine beliebige Achse
Die Drehung um einen beliebigen Achsenvektor a = (a1, a2, a3)T <> 0 wird durch die Abbildungsmatrix
|
| |
cosw-(1-cosw)a12 |
(1-cosw)a1a2-a3sinw |
(1-cosw)a1a3+a2sinw |
| |
|
| D(w) = |
| |
(1-cosw)a1a2+a3sinw |
cosw-(1-cosw)a22 |
(1-cosw)a2a3-a1sinw |
| |
(Gl. 3.2) |
|
| |
(1-cosw)a1a3-a2sinw |
(1-cosw)a2a3+a1sinw |
cosw-(1-cosw)a32 |
| |
|
beschrieben. Der Betrag des Richtungsvektors |a| ergibt den Winkel w der Drehung um den Achsenvektor in Bogenmaß.
Definition des Manipulators:
RotLat& RotLat::Rotate( CONST Vector3D& rot )
Die Drehmatrizen für die Drehungen um die drei Koordinatenachsen können als Sonderfall der Drehung um eine beliebige Achse angesehen werden. Diese Drehmatrizen können leicht aus der allgemeinen Drehmatrix nach Gleichung 3.2 ermittelt werden, sollen aber der Vollständigkeit halber im folgenden mit angegeben werden.
3.1.1.b Rotation um die x-Achse
Die Rotation um die x-Achse ist gleichbedeutend mit der Drehung um die Achse a = (1, 0, 0)T. Daraus ergibt sich aus Gleichung 3.2 mit a1 = 1, a2 = 0 und a3 = 0 die Abbildungsmatrix
|
| |
1 |
0 |
0 |
| |
|
| DX(w) = |
| |
0 |
cosw |
-sinw |
| |
(Gl. 3.3) |
|
| |
0 |
sinw |
cosw |
| |
|
Definition des Manipulators:
RotLat& RotLat::RotateX( double phi )
3.1.1.c Rotation um die y-Achse
Für die Rotation um die y-Achse ergibt sich der Achsenvektor zu a = (0, 1, 0)T. Dies führt zu der Abbildungsmatrix
|
| |
cosw |
0 |
sinw |
| |
|
| DY(w) = |
| |
0 |
1 |
0 |
| |
(Gl. 3.4) |
|
| |
-sinw |
0 |
cosw |
| |
|
Definition des Manipulators:
RotLat& RotLat::RotateY( double phi )
3.1.1.d Rotation um die z-Achse
Als letzter Sonderfall ist die Rotation um die z-Achse zu nennen, mit dem Achsenvektor a = (0, 0, 1)T. Dadurch ergibt sich die Abbildungsmatrix zu
|
| |
cosw |
-sinw |
0 |
| |
|
| DZ(w) = |
| |
sinw |
cosw |
0 |
| |
(Gl. 3.5) |
|
| |
0 |
0 |
1 |
| |
|
Definition des Manipulators:
RotLat& RotLat::RotateZ( double phi )
Bei der Translation wird im Gegensatz zur Rotation nur die letzte Spalte einer RotLat T = (t14, t24, t34)T verändert. Der neue translatorische Anteil wird zu dem entsprechenden Element addiert. Für die verschiedenen Translationen ergibt sich folgende allgemeine Vorschrift für den Manipulator:
T' = T+t
3.1.2.a Translation entlang einer beliebigen Achse
Wie bei der Rotation läßt sich für die Translation ein allgemeiner Fall angeben. Der Translationsvektor für eine Verschiebung entlang einer beliebigen Achse kann durch
|
| |
dx |
| |
|
| t(dx,dy,dz) = |
| |
dy |
| |
(Gl. 7.6) |
|
| |
dz |
| |
|
beschrieben werden. Die Koordinaten des Verschiebungsvektors geben die einzelnen Verschiebungen entlang der jeweiligen Koordinatenachse an: v = (dx, dy, dz)T
Definition des Manipulators:
RotLat& RotLat::Translate( CONST Vector3D& v )
3.1.2.b Translation entlang der x-Achse
Bei der Verschiebung entlang der x-Achse sind die Elemente dy und dz des Verschiebungsvektors v gleich Null (tx = (dx, 0.0, 0.0)T). Daher ist es nur notwendig das Element dx zu übergeben.
Definition des Manipulators:
RotLat& RotLat::TranslateX( double dx )
3.1.2.c Translation entlang der y-Achse
Bei der Translation entlang der y-Achse wird dx und dy gleich Null (ty = (0.0, dy, 0.0)T). Es muß somit nur dy übergeben werden.
Definition des Manipulators:
RotLat& RotLat::TranslateY( double dy )
3.1.2.d Translation entlang der z-Achse
In diesem Fall ist nur dz ungleich Null (tz = (0.0, 0.0, dz)T).
Definition des Manipulators:
RotLat& RotLat::TranslateZ( double dz )
Zur Invertierung der Matrix wird ein entsprechender Manipulator zur Verfügung gestellt. Da die Rotationsmatrix orthonormal ist, vereinfacht sich deren Invertierung wesentlich. Die Rotationsmatrix R und der Translationsvektor T können unabhängig voneinander betrachtet werden. Aufgrund der Orthonormalität der Rotationsmatrix ist deren Inverse gleich ihrer Transponierten, d.h. R -1 = RT.
y = [R|T]·x
y = R·x + T
x = R-1·(y-T)
x = R-1y + (-R-1·T)
x = RTy + (-RT·T)
Definition des Manipulators:
RotLat& RotLat::Invert()
Damit die Matrix in einen definierten Zustand überführt werden kann, gibt es die Möglichkeit die Matrix zurückzusetzen. Dabei werden die Diagonalelemente der Rotationsmatrix r11, r22 und r33 mit dem Wert eins gleichgesetzt. Alle anderen Elemente werden auf Null gesetzt. Dadurch ergibt sich eine identische Transformation, d.h. die Koordinaten eines Vektors werden nicht verändert.
M = [E|0]
Definition des Manipulators:
RotLat& RotLat::Identity()
Eine zweite RotLat M" kann zu der bestehenden Matrix der RotLat hinzu multipliziert werden, wodurch Transformationsketten verwirklicht werden. Die Multiplikation von M" erfolgt von links an die bestehende Matrix M.
M' = M"·M
Definition des Manipulators:
RotLat& RotLat::operator *= ( CONST RotLat& rotlat )
Für die Zuweisung mit einer zweiten RotLat M" kann der Zuweisungsoperator verwendet werden. Durch den Zuweisungsoperator werden die Elemente der RotLat mit denen der zweiten RotLat gleichgesetzt.
M' = M"
Definition des Manipulators:
RotLat& RotLat::operator = ( CONST RotLat& rotlat )
Durch das Anwenden der Matrix auf einen Vektor, kann dieser Vektor transformiert werden. Zur Bewerkstelligung dieser Transformation wird der Vektor von rechts an die Matrix multipliziert. Diese Transformation wandelt die Koordinaten des Vektors aus den Koordinaten des lokalen Systems in die Koordinaten des Weltystems um.
v' = M·v
Definition des Aktors:
RotLat& RotLat::Apply( Vector3D& vector )
Mit der Anwendung der inversen Matrix auf einen Vektor, kann dieser ebenfalls transformiert werden. Die Richtung der Transformation ist gegensätzlich zu der Anwendung der Matrix. Zur Multiplikation wird die Rotationsmatrix transponiert und mit der Differenz aus dem Vektor und dem Translationsvektor multipliziert. Durch diese Transformation werden die Koordinaten des Vektors aus dem Weltkoordinatensystem in das lokale Koordinatensystem transformiert.
v' = M-1·v
v' = [R|T]-1·v
v' = [RT|(-RT·T)]·v
v' = RT·v - RT·T
Definition des Aktors:
RotLat& RotLat::ApplyReverse( Vector3D& vector )
Für die Implementierung wurden weitere Klassen verwendet, welche eine vereinfachte Gestaltung des Sourcecodes ermöglichen sollten. Der Vollständigkeit halber sollen sie hier vorgestellt werden. Eine ausführliche Beschreibung findet sich in der Referenz.
Aufgabe der String-Klasse ist es eine einfache und einheitliche Verwaltung von Zeichenketten. Unter Zeichenkette soll ein Array von char-Werten zu verstehen sein. In den verschiedenen Konstruktoren können Argumente unterschiedlicher Typen angegeben werden, wodurch die interne Zeichenkette der String-Klasse entsprechend initialisiert wird. Als weiteres verfügt die String-Klasse über Zuweisungsoperatoren, welche es gestatten, daß die String-Klasse mit einer Zeichenkette oder einer weiteren String-Klasse gleichgesetzt wird. Als wichtigste Operatoren sind Vergleichsoperatoren mit einer Zeichenkette oder String-Klasse enthalten.
Für die Bewertung der Zuverlässigkeit eines Objektzustandes stellt die Klasse Time eine Grundlage dar. In der Klasse wird zu diesem Zweck eine Repräsentation der aktuellen Uhrzeit gehalten.
Die Klasse Vertex dient zum Verketten von Vektoren in einer Liste, wozu die Klasse von einem Templateknoten TNode<Vertex> public abgeleitet ist. Das einzige Datenelement eines Vertex ist somit vom Typ Vector3D. Abgefragt werden kann der Vektor über die Methode point().
Die abstrakte Klasse Face3D definiert eine gemeinsame Schnittstelle für Sichthindernisse. Die abstrakten Methoden GetLen(), GetVertex(), GetId() und die virtuelle Methode GetNormalVector() stellen die gemeinsame Schnittstelle für abgeleitete Klassen dar. Der Accessor GetLen() liefert dabei die Anzahl der Eckpunkte der Fläche zurück, wobei durch die Methode GetVertex( int i ) der i-te Eckpunkt der Fläche erfragt werden kann. Sie müssen daher durch die abgeleitete Klasse überschrieben werden. Der Accessor GetId() gibt eine Id der Fläche zurück. Der letzte Accessor GetNormalVector() schließlich gibt den Normalvektor einer Fläche zurück. Dieser Accessor ist bereits so implementiert, daß er den Normalenvektor der Fläche aus vorhandenen Daten berechnet, kann aber überschrieben werden, um z.B. einen bereits im voraus berechneten Normalenvektor zurückzugeben.
Ebenfalls wie die Klasse Face3D stellt die Klasse Line3D eine abstrakte Klasse dar, deren Aufgabe es ist eine Schnittstelle für Linien zu definieren. Die beiden abstrakten Methoden GetStart() und GetEnd() bilden die gemeinsame Schnittstelle für Linien, sie müssen daher von abgeleiteten Klassen überschrieben werden. Sie liefern den Start- und den Endpunkt der Linie zurück.
Als letzte abstrakte Klasse soll die Klasse Point3D kurz beschrieben werden. Sie definiert die Schnittstelle für eine Klasse zur Repräsentation eines Punktes. Als einzige Methode muß GetPoint() von einer abgeleiteten Klasse überschrieben werden, welche den Ortsvektor zurückliefert, dessen Spitze den Standort des Punktes beschreibt.
| [Meyb90] |
Meyberg, Kurt - Vachenauer,Peter: |
| Höhere Mathematik 1 |
| Differential- und Integralrechnung, Vektor- und Matrizenrechnung |
| Berlin: Springer, 1990 |
| [Fole90] |
Foley, James - van Damm, Andries - Feiner, Steven - Hughes, John:
|
| Computer Graphics |
| Principles and practice |
| New York: Addison - Wesley, 1990 |
Stefan Unterholzner
Lehrstuhl für Prozessrechner
Technische Universität München
$Id: daten.htm,v 1.1 1996/03/08 13:58:13 uholzner Exp uholzner $