Geometrisches Programmieren leicht gemacht

Werkzeuge  –  11 Kommentare
Anzeige

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.

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.

Blade-Liste der 5d-konformen Algebra. Sie sind die Bausteine der Multivektoren (Abb. 1).

Die fünfdimensionale Geometrische Algebra hat die Basisvektoren e1, e2, e3, e und e0. Hierbei lässt sich e (lies "e-infinity") als Punkt im Unendlichen und e0 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. e3 vor e1e2).
  2. Bei gleichen Anzahlen wird nach der Reihenfolge der Basisvektoren sortiert (z. B. e1e2 vor e2e0 ).
  3. Innerhalb eines Blades sind die Basisvektoren nach ihrer Reihenfolge sortiert (z. B. e1e2e und nicht e1ee2 ).

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 P1, P2, P3, P4 erstellt werden oder unter Angabe des Mittelpunkts P und des Radius r. So rechnet *(P1P2P3P4) 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.

Mit diesen Formeln lassen sich geometrische Objekte einfach als Multivektoren ausdrücken. Fett geschriebene Variablen bezeichnen 3d-Vektoren, zum Beispiel x=x1e1+x2e2+x3e3 (Abb. 2).

Das äußere Produkt dient in der Standardrepräsentation auch als Schnittoperator, der beispielsweise zwei Ebenen π1 und π2 miteinander verschneiden kann (L=π1π2), wodurch eine Schnittgerade L entsteht. Beim Verschnitt dreier Kugeln Pp=S1S2S3 ergibt sich hingegen ein Paar aus zwei Punkten Pp. Ein Kreis Z entsteht durch den Schnitt Z=S1S2 zweier Kugeln S1 und S2. 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].

Aus drei Punkten P1, P2 und P3 lässt sich ein Kreis Z*=P1∧P2∧P3 in dualer Repräsentation eindeutig beschreiben (Abb. 3).

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.

Anzeige