Tutorial OpenGL3 Lineare Algebra

Vorwort

Lineare Algebra ist ein Teilgebiet der Mathematik und beschäftigt sich mit Vektorräumen. Die für OpenGL wichtigen Unterbereiche sind Vektoren und Matrizen. Der größte Teil der 3D Programmierung beschäftigt sich mit Linearer Algebra, daher sollte auch diese Grundlage eine besondere Aufmerksamkeit gewidmet werden. Sollte der Inhalt vieleicht zu viel für einmal sein, dann wäre es ratsam in mehreren Etappen zu bewältigen aber es sollte auf jedenfall vollständig verstanden werden, bevor man sich ernsthaft mit OpenGL auseinander setzen will.

Vektor

Ein Vektor kann mit einem Array oder einer Liste vergleicht werden, wenn man z.B. einen 3-dimensionalen Vektor meint, dann wäre es ein Array mit 3 Elementen. Die übliche Schreibweise eines Vektors sieht wie folgt aus.

Eine entsprechende C++ Representation wäre z.B. folgende

template<typename T,unsigned int DIMENSION>
class TVector
{
  public:
    T m_Vec[ DIMENSION];
};
//typedef Vec4 TVector<float,4>;

OpenGL verwendet auf der Grafikkarte immer 4-dimensionale Vektoren, auch wenn nur 1 oder 3 benötigt werden. Die restlichen Elemente des Vektors werden dann mit 0 aufgefüllt. Vektoren werden in OpenGL in 2 Arten verwendet, als absoluter und als relativer Wert. Absolute Werte wären z.B. Positionen und Farbwerte wärend relative Werte z.B. eine Transformation wäre. Der OpenGL Vektor sieht wie folgt aus.

Einheitsvektor

Ein besondere Form eines Vektors ist der Einheitsvektor, welcher immer eine Länge von 1 ergibt. Der Einheitsvektor wird normalerweise als klein e gekennzeichnet.

Die Berechnung eines Einheitsvektors wird später in der der Magnitude und Normalisierung Funktion näher erläutert. Einheitsvektoren sind als Normalen/Richtungsvektoren in OpenGL im Einsatz und ist die Basis für Rotationen.

Addition

Die Addition wird Komponentenweise ausgeführt, was bedeutet, man kann sich eine Addition von Vektoren als eine Addition von jeden einzelnen Element mit dem entsprechenden Element im anderem Vektor Vorstellen.

Die Addition von Vektoren kann man sich sehr einfach Vorstellen, in dem man die einzelnen Vektoren als Bewegungsbefehle sieht. Wenn man also 2 schritte vorwärts,einen schritt seitwärts laufen soll und danach ein halben Schritt vorwärts und ein Schritt seitwärts, dann kann man diese beiden Befehle auch zu einem Befehl zusammen fassen. Laufe 2 1/2 Schritte vorwärts und 2 Schritte Seitwärts und wir stehen am gleichen Punkt und dieser Befehl wäre dann unser Ergebnis Vektor c.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
TVector<T,DIMENSION> operator+(const TVector<T,DIMENSION>& b)
{
  TVector<T,DIMENSION> c;
  for (unsigned int i=0;i<DIMENSION,i++)
    c.m_Vec[i]=this->m_Vec[i]+b.m_Vec[i];
  return c;
}
//...
};
//Vec4 a,b,c; c=a+b;

Subtraktion

Hier gilt gleiches, wie bei der Addition, nur das Komponentenweise Subtrahiert wird.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
TVector<T,DIMENSION> operator-(const TVector<T,DIMENSION>& b)
{
  TVector<T,DIMENSION> c;
  for (unsigned int i=0;i<DIMENSION,i++)
    c.m_Vec[i]=this->m_Vec[i]-b.m_Vec[i];
  return c;
}
//...
};
//Vec4 a,b,c; c=a-b;

Magnitude

Magnitude ist der Englische Begriff für die Berechnung des Betrags eines Vektors oder auch die Länge. Die Länge des Vektors wird benötigt, wenn man einen Vektor Normalisieren will oder fest stellen möchte ob ein Vektor ein Einheitsvektor ist.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
T Magnitude(){
  T len=T(0);
  for (unsigned int i=0;i<DIMENSION,i++)
    len+=this->m_Vec[i]*this->m_Vec[i];
  return sqrt(len);
}
//...
};
//Vec4 a; float len; len=a.Magnitude();

Skalarprodukt

Das Skalarprodukt erlaubt uns die Berechnung, des Winkels, zwischen 2 Vektoren. Hierfür müssen allerdings beide Vektoren Normalisiert sein, also jeweils einen Betrag von 1 ergeben. Sonnst muss dies noch nachträglich getan werden.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
T DotProduct(const TVector<T,DIMENSION>& b)
{
  T alpha=T(0);
  for (unsigned int i=0;i<DIMENSION,i++)
    alpha+=this->m_Vec[i]*b.m_Vec[i];
  return c;
}
//...
};
//Vec4 a,b; float c; c=a.DotProduct(b);

Kreuzprodukt

Das Kreuzprodukt errechnet einen Vektor, der senkrecht zu den Vektoren a und b steht, wenn a und b den selben Ursprung haben. Dieses Verhalten wird genutz, um die Normale einer Fläche zu errechnen.

template<typename T,unsigned int DIMENSION>
class TVector
{
...
TVector<T,DIMENSION> Crossproduct(const TVector<T,DIMENSION>& b)
{
  TVector<T,DIMENSION> c;
  unsigned int prev,next;
  for (unsigned int i=0;i<DIMENSION,i++)
  {
    prev=i==0?DIMENSION-1:i-1;
    next=i+1 % DIMENSION;
    c.m_Vec[i]=this->m_Vec[next]*b.m_Vec[prev]-this->m_Vec[prev]*b.m_Vec[next];
  }
  return c;
}
...
};
//Vec4 a,b,c; c=a/b;

Normalisieren

Bei der Normalisierung wird der Betrag eines Vektors mit dem Vektor dividiert und man erhält ein Vektor, der in die Gleiche Richtung zeigt aber auf eine Länge 1 skaliert ist.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
TVector<T,DIMENSION> Normalize(){
  TVector<T,DIMENSION> c;
  c=(*this)/this->Magnitude();
  return c;
}
//...
};
//Vec4 a,c; c=a.Normalize();

Matrix

Eine Matrix kann man sich als 2-dimensionalen Array mit n und m Länge.

OpenGL verwendet 4x4 große Matrizen und kann aus 4 Vektoren mit einer Länge von 4 konstruiert werden.

template<typename T,int DIMENSION> 
class TMatrix 
{ 
  protected: 
    Tvector<T,DIMENSION> m_Matrix[DIMENSION]; //Erlaubt uns das nutzen von der eigenen Vektorklarsse.
    T m_Array[DIMENSION*DIMENSION]; //für die LoadMatrix Funktion von OpenGL
  public:
    Tvector<T,DIMENSION>& operator [](const int Index) 
    { 
      return m_Matrix[Index]; 
    }

    const T* GetMatrix1DArray() 
    { 
      int size=sizeof(T)*DIEMNSION; 
      for (int i=0;i<DIMENSION;i++)
        memcpy(&m_Array[i*4],&m_Matrix[i][0],size); 
      return &m_Array[0]; 
    }
};
//typedef Mat Tmatrix<float,4>

Für Matrizen brauchen wir nicht so viele Funktionen wie bei Vektoren, um genau zu sagen brauchen wir 2 Operationen. Diese Operationen lauten Transponieren und Multiplikation. Bei der Matrix benötigen wir einige Konstruktionsfunktionen und zwar Identity, Translate, Rotate und Scale Matrix. Diese Matrizen machen die ganze Arbeit für uns, wenn man sich in einem 3D Raum bewegen möchte.

Transponieren

Transponieren wird durch ein großes T über der Matrix dargestellt. Diese Funktion tauscht die Werte einer Matrix miteinander aus, so das aus einer Spalten konstruierten Matrix eine Zeilenweise konstruierte Matrix wird. Diese Funktion kann Hilfreich sein, wenn man zwischen Direct3D und OpenGL Daten austauschen will, denn nicht jeder nutzt spalten orientierte Matrizen.

void Transpose() //Transponieren für 4x4 Matrizen
{ 
  swap(m_Matrix[0][1],m_Matrix[1][0]); //swap kopiert b in tmp, kopiert a in b und tmp in a
  swap(m_Matrix[0][2],m_Matrix[2][0]); 
  swap(m_Matrix[0][3],m_Matrix[3][0]); 

  swap(m_Matrix[1][2],m_Matrix[2][1]); 
  swap(m_Matrix[1][3],m_Matrix[3][1]); 

  swap(m_Matrix[2][3],m_Matrix[3][2]); 
}

Multiplikation

Multiplikation ist die wichtigste Operation bei Matrizen, wenn wir uns mit OpenGL beschäftigen. Dies liegt daran, dass OpenGL 2 verschiedene Matrizen verwendet, um Vektoren in Bildschirmkoordinaten um zu wandeln. Damit dies Funktioniert muss jeder Vektor mit diesen Matrizen jeweils multipliziert werden. Um eine Matrix zu manipulieren wird diese mit einer Konstruierten Matrix multipliziert. Diese Operation die ist meist ausgeführte Operation sowohl in der OpenGL Pipeline als auch in einem Spiel. Seit OpenGL3 gibt es kein Matrizen support mehr, was bedeutet, dass man diese selber implementieren muss und dann die fertigen Matrizen an OpenGL übergibt. Die lässt viel Raum für Optimierung und kann somit ein OpenGL3 Programm schneller machen als ein OpenGL2 Programm, wenn man zuvor die glTranslate,glRotate und weiteren Funktionen verwendet hat. Es ist also ratsam sich eine sehr Performance Bibliothek zu laden oder mit einem Performance Analyzer bewaffnet den eigenen Code zu optimieren.

Multiplikation mit einem Vektor

TVector<T,DIMENSION>& operator *(TVector<T,DIMENSION>& V) 
{ 
  TVector<T,DIMENSION> v=m_Matrix[0]*V[0]+m_Matrix[1]*V[1]+m_Matrix[2]*V[2]+m_Matrix[3]*V[3];
  return v; 
}

Multiplikation mit einer Matrix

Tmatrix<T,DIMENSION>& operator *(TMatrix<T,DIMENSION>& M) 
{ 
  TMatrix<T,DIMENSION> M1((*this)*M[0]), (*this)*M[1], (*this)*M[2], (*this)*M[3]); 
  return M1; 
}

Exkurs in die Optimierung

Vektoren

Man hat oft den Fall, dass man auf der CPU mehrere Werte multiplizieren, dividieren, addieren, subtrahieren muss z.B. bei Bildbearbeitung.

Dieses kann man Optimieren, indem man Vektoren verwendet, dabei wird ein Pixel als Vektor interpretiert und nun kann man alle Farbkanäle mit einen einzigen Aufruf verarbeiten lassen, indem man die Vektoroperationen verwendet. Wenn die Vektoren mit einer CPU Extension wie SSE oder MMX implementiert wurden, dann werden die 4 Komponenten eines Vektors sogar gleichzeitig verarbeitet. Sollte man nur 2 oder 3 Komponenten verwenden, dann füllt man die restlichen Komponenten mit 0 auf bzw. ignoriert sie einfach beim auslesen der Komponenten.

Multiplikation

Die Multiplikation von 2 Vektoren miteinander ist eigentlich nicht definiert, da es wenig Sinn macht aber wir haben nun einen Verwendungszweck gefunden und definieren ihn. Bei dieser Operation gilt das gleiches, wie bei der Addition und Subtraktion, nur mit einem Mulltiplikations Operator. Die Bildverarbeitung wird sich mit mehr Geschwindigkeit bedanken.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
TVector<T,DIMENSION> operator*(const TVector<T,DIMENSION>& b)
{
  TVector<T,DIMENSION> c;
  for (unsigned int i=0;i<DIMENSION,i++)
    c.m_Vec[i]=this->m_Vec[i]*b.m_Vec[i];
  return c;
}
//...
};
//Vec4 a,b,c; c=a*b;

Division

Bei der Division muss man aufpassen, dass keiner der Element im Divisor 0 ist, da sonnst eine Division mit 0 entsteht. Eine Division mit 0 hat ein Interrupt zufolge, welcher das Programm zum beenden bittet. Also sollte man dies Vorher überprüfen oder bei einer Division den Aufruf mit einer entsprechenden Routine den Fehler abfangen. Sonnst verhält es wie bei der Multiplikation.

template<typename T,unsigned int DIMENSION>
class TVector
{
//...
TVector<T,DIMENSION> operator/(const TVector<T,DIMENSION>& b)
{
  TVector<T,DIMENSION> c;
  for (unsigned int i=0;i<DIMENSION,i++)
    c.m_Vec[i]=this->m_Vec[i]/b.m_Vec[i];
  return c;
}
//...
};
//Vec4 a,b,c; c=a/b;

Programmiersprache,Compiler und CPU Extension

Die Optimierung ist von Programmiersprache und Compiler stark abhängig. Wärend Delphi, Freepascal und MS VSC++ Compiler man nur aufwändig SSE,MMX und weitere CPU Extension implementieren kann, hat der GCC eine Vektorextension und seit Version 4.x auch eine Funktionsoptimierung. Die Vektorextension von GCC ist ein Parser Erweiterung, welche einen Typ als ein bestimmten Vektortyp(z.B. Float Länge 4) bestimmt und dann entsprechend alle Operationen in SSE1-4 oder MMX Code umwandelt. Seit Version 4.x gibt es eine Funktionsoptimierung, welche erlaubt im Quellcode mehrere Optimierungen gleichzeitig zu nutzen. Die bedeutet, dass man eine Funktion, wie Vektor.Magnitude() mehrfach implementiert und dann jeweils eine andere Optimierungs Aktiviert. Also Vektor.Magnitude_sse(), Vektor.Magnitude_mmx(),... und dann die jeweilige Funktion mit SSE,MMX oder ohne Optimierung markiert. Der Compiler optimiert dann diese Funktion für die jeweilige CPU Extension und man kann dann im Programmcode entsprechend der gegebenen Hardware auf die beste Mögliche Funktion umlenken. Dies hat den Vorteil, dass man nur noch eine Binary hat und alle CPUs(mehr Kern, ein Kern, Intel Petium1-4, AMD Athlon und so weiter) der gleichen Architektur Optimiert Unterstützen kann. Dies ist ist nützlich, wenn man alte CPUs unterstützen will. Es würde sich also lohnen, wenn man sich viel Ärger und Code sparen will, den Code in GCC als Bibliothek zu implementieren und statisch oder dynamisch zu linken.

Templates und Generics

Eine Optimierung die sich bei C++ stark auswirkt sind Templates, da diese die Eigenschaft aufweisen vom Compiler generiert zu werden. Dies bedeutet je nach Qualität des Compilers kann dieser Code starke Performanceschübe bekommen, wenn man die Operationen in Templates verpackt, da der Compiler oft Optimierungen machen kann, die man selber nicht kennt oder gar nicht machen will(Kompatibilität und Übersichtlichkeit). Templates entrollen z.B. konstante For Schleifen und wie schon vorher in den Codeschnipseln zu sehen war, haben wir davon einige in den Vektor Operationen. Das Entrollen von Schleifen entfernt eine menge Balast(Counter,Prüfung,..) welche sich auf die Performance auswirkt. Templates reduziert den Codeaufwand, da man viele weitere Implementierungen einspart(Vektor von Typ float, int, unsigned short, unsigned int, double, ...).

Testen testen testen

Wenn man Performance Test macht, dann sollte man verschiedene Test machen und einer der teilweise oft unterschätzt wird ist der Create und Free Test. Sobald man eine Klasse benutzt wird beim erstellen des Objektes immer ein Speicher alloziert und dann der Konstruktor aufgerufen, was Zeit kostet. Man sollte also einmal ein Test durchführen, der Vektoren und Matrizen erstellt und zerstört. Die Operation Test sollten die Vektoren und Matrizen vorher erstellen und in der Schleife wiederverwendet werden und nach beenden des Performance Trackings erst zerstört werden.