Geometrisches Programmieren leicht gemacht

Inhaltsverzeichnis

Die Geometrische Algebra ermöglicht eine intuitive Formulierung geometrischer Probleme. Sie verspricht, Aufgaben aus Bereichen wie Grafik, Computer-Vision, Robotik und weiteren Wissenschafts- oder Ingenieursdisziplinen einfach zu lösen.

Grundsätzlich gibt es zwei Möglichkeiten, Geometrische Algebra in Programmiersprachen zu nutzen: die direkte Nachbildung der Operationen in Standard-Syntax [1] oder die Einbettung mit sogenannten domänenspezifischen Sprachen (DSLs). Letzteres bietet deutlich mehr Optimierungspotenzial als das direkte Nachbilden der Operationen in Standard-Syntax, die besonders in modernen GPU-orientierten Ansätzen (OpenCL, CUDA) schwierig und wenig performant wäre.

Im Folgenden wird daher eine DSL benutzt und anhand eines einfachen Beispiels die praktische Anwendbarkeit demonstriert.

Erste Schritte auf mathematischem Boden

Die Geometrische Algebra ermöglicht ein geometrisch intuitives Arbeiten. Der Preis dafür ist eine höherdimensionale mathematische Struktur. Die folgenden Ausführungen sollen anhand der fünfdimensionalen (sogenannten konformen) Geometrischen Algebra kurz mit ihr vertraut machen.

Die fünfdimensionale Geometrische Algebra hat die Basisvektoren e₁, e₂, e₃, e_∞ und e₀. Hierbei lässt sich e_∞ (lies "e-infinity") als Punkt im Unendlichen und e₀ als Ursprung interpretieren. Durch die Kombination der Basisvektoren durch das sogenannte äußere Produkt "∧" ergeben sich 32 algebraische Basiselemente, sogenannte Blades, die in Abbildung 1 zu finden sind.

Eine eindeutige Kombination liefern die folgenden drei Regeln:

1. Die Blades sind nach der Anzahl der enthaltenen Basisvektoren aufsteigend sortiert (z. B. e₃ vor e₁∧e₂).
2. Bei gleichen Anzahlen wird nach der Reihenfolge der Basisvektoren sortiert (z. B. e₁∧e₂ vor e₂∧e₀ ).
3. Innerhalb eines Blades sind die Basisvektoren nach ihrer Reihenfolge sortiert (z. B. e₁∧e₂∧e_∞ und nicht e₁∧e_∞∧e₂ ).

Eine Linearkombination (gewichtete Summe) von Blades nennt man einen Multivektor.

Multivektoren und Blades sind die mathematischen Grundlagen der Geometrischen Algebra. Ihr wahrer Vorteil offenbart sich aber erst bei der Betrachtung der geometrischen Bedeutung einiger spezieller Multivektoren, die in Abbildung 2 aufgeführt sind.

Es existieren drei lineare Produkte, die sich auf Multivektoren anwenden lassen: Das innere Produkt "⋅" (lies "dot", eine Art erweitertes Skalarprodukt), das äußere Produkt "∧" (lies "wedge") und das geometrische Produkt "*".

Die Tabelle (Abb. 2) zeigt für jedes geometrische Objekt jeweils zwei Repräsentationen, mit denen es sich darstellen lässt. Die Repräsentationen sind jeweils dual zueinander, das heißt, es gibt einen Dualisierungsoperator "*", der eine Repräsentation in die andere umrechnet, und umgekehrt.

Mit den beiden Repräsentationen kann eine Kugel entweder durch das äußere Produkt von vier Punkten P₁, P₂, P₃, P₄ erstellt werden oder unter Angabe des Mittelpunkts P und des Radius r. So rechnet *(P₁∧P₂∧P₃∧P₄) die duale Repräsentation der Kugel in ihre Standardrepräsentation S=P-(1/2)r²e_∞ um.

Während die duale Repräsentation eine Konstruktion von Objekten aus Punkten ermöglicht, lässt sich mit der Standardrepräsentation eine geometrische Interpretation nach Parametern wie Radius r, Normale n oder dem Abstand vom Koordinatenursprung d umsetzen. Durch den Dualisierungsoperator können die Vorteile beider Repräsentationen genutzt werden.

Das äußere Produkt dient in der Standardrepräsentation auch als Schnittoperator, der beispielsweise zwei Ebenen π₁ und π₂ miteinander verschneiden kann (L=π₁∧π₂), wodurch eine Schnittgerade L entsteht. Beim Verschnitt dreier Kugeln P_p=S₁∧S₂∧S₃ ergibt sich hingegen ein Paar aus zwei Punkten Pp. Ein Kreis Z entsteht durch den Schnitt Z=S₁∧S₂ zweier Kugeln S₁ und S₂. Liegen drei Punkte vor, lässt sich mit dem äußeren Produkt der Kreis in dualer Repräsentation ermitteln, den sie beschreiben (s. Abb. 3).

Grundsätzlich erlaubt die Geometrische Algebra ein völlig in sich abgeschlossenes Rechnen mit den oben definierten geometrischen Objekten. Auch nicht explizit aufgeführte Operationen wie der Schnitt einer Ebene mit einem Kreis sind in der Algebra enthalten.

Das innere Produkt hilft beim Berechnen von Abständen, beispielsweise zwischen zwei Punkten, zwischen Punkt und Ebene oder Punkt und Kugel [2]. Transformationen wie Rotationen, Translationen und Skalierungen lassen sich durch das Verwenden des geometrischen Produkts durchführen. Die Eleganz der geometrischen Algebra spiegelt sich hier besonders darin wider, dass sich dieselbe Transformationsformel (siehe [2], Kapitel 3.5) für alle Multivektoren benutzen lässt. Dabei ist es nicht relevant, ob der Multivektor einen Punkt, eine Ebene oder eine Kugel darstellt.

Aus einem gegebenen Punktpaar, Kreis oder Kugel können auch die jeweiligen Radien und Mittelpunkte durch Geometrische Algebra berechnet werden [2].

Die Programmierung in Geometrischer Algebra

Es existiert eine Vielzahl von Tools mit dazugehörigen DSLs für die Geometrische Algebra. Solche DSLs bilden einen Algorithmus mit Geometrischer Algebra in ASCII-Text ab. Einige entsprechende Tools sind CLUCalc, Gaigen, Gaalet [1] und GMac. So ermöglicht zum Beispiel das Tool CLUCalc eine einfache und interaktive Visualisierung auf Grundlage seiner domänenspezifischen Sprache namens CLUScript.

CLUCalc bildet aufgrund seiner Ausgereiftheit, insbesondere in puncto Visualisierung, eine solide Grundlage für weitere Arbeiten. Zu beachten ist jedoch, dass die aktuelle Version nur für Windows verfügbar ist. Ältere Versionen gibt es hingegen als Quellcode, CLUCalc ist potenziell also auf vielen anderen Betriebssystemen lauffähig. Eine Orientierung an der domänenspezifischen Sprache CLUScript, die ein integraler Bestandteil von CLUCalc ist, liegt deshalb nahe. Im weiteren wird eine Skriptsprache benutzt, die stark an CLUScript angelehnt ist.

DSLs wie CLUScript können dabei helfen, mathematische Aufgaben leichter in Algorithmen zu überführen. Allerdings stellt sich die Frage der Weiterverwertbarkeit: Zwar ist der Code, der mit solchen "Hilfssprachen" entsteht, in vielen Fällen leichter nachvollziehbar, für den industriellen Einsatz sind hingegen in C, C++ oder Java implementierte Anwendungen üblich. Um dennoch nicht auf die Möglichkeiten von CLUScript und ähnlichen Sprachen verzichten zu müssen, gibt es Werkzeuge zum Einbinden solcher Quelltexte in gängige Sprachen. Ein Beispiel hierfür ist der kostenlose Gaalop Precompiler, mit dem sich CLUScript automatisch in C++ oder OpenCL-Code übersetzen lässt.