In dieser zweiteiligen Serie soll das Open-Source-Projekt PalletJS vorgestellt werden, das ausschließlich auf Basis von JavaScript und explizit ohne weitere Abhängigkeiten eine Palettenvisualisierung implementiert. Beginnen wollen wir mit einem Aspekt, der in diesem Kontext häufig von externen Bibliotheken übernommen wird: dem Rendering mit WebGL.

Es finden sich viele Ressourcen, die sich mit der Visualisierung von Paletten im Web beschäftigen, diese sind jedoch meistens entweder Closed Source oder von existierenden Bibliotheken wie Three.js oder ähnlichen abhängig. Letzteres ist vor allem in Anbetracht von Quellcodeverwaltung, Robustheit und für den Fall, dass die Software auf Low-End-Geräten zum Einsatz kommen soll, von Nachteil. Hier soll PalletJS ansetzen: Eine abhängigkeitsfreie Open-Source-Software zur Visualisierung von Paletten in 3D, die frei vom Nutzer spezifiziert werden können. Die Applikation befindet sich derzeit in der Endphase der Entwicklung. Nach dem Ende dieser Artikelserie wird der gesamte zugehörige Code unter [1] zur Verfügung stehen. Dort findet sich die vollständige WebGL-Applikation aus diesem Artikel. Abbildung 1 zeigt die Visualisierung einer Beispielpalette in der derzeitigen Version von PalletJS.

In diesem Teil beschäftigen wir uns mit der Theorie und Implementierung des grundsätzlichen Rendering-Prozesses von WebGL, während in der nächsten Ausgabe auf dieses Rendering aufbauend die Konzeption und Implementierung der gesamten Palettenvisualisierung behandelt wird. Auch wenn hierbei Vorwissen im Bereich von Geometrie, Algebra und Grafik zum Verständnis hilfreich ist, richtet sich der Artikel in erster Linie an Personen ohne großen mathematischen Hintergrund.

Da geometrisch betrachtet eine Palette nur aus einer Ansammlung von Quadern besteht (in Wirklichkeit: Kartons auf der Palette), wird der Rendering-Prozess am Beispiel einer Box illustriert. Zuerst wollen wir hierbei auf die notwendigen mathematischen Grundlagen, spezifisch Vektoren, Matrizen und Transformationen, eingehen. Anschließend werden wir diese Konzepte verwenden, um sowohl die Geometrie der Box und ihre Projektion auf das Canvas zu modellieren. Am Ende skizzieren wir noch, welche Schritte zur Implementation mit WebGL nötig sind.

Mathematische Grundlagen: Vektoren

Viele haben vermutlich schon in Ihrer Schul- oder Studienzeit den Begriff eines Vektors im Kontext der Geometrie kennengelernt. Konzeptionell ist ein reeller n-dimensionaler Vektor $\overrightarrow{v}=(a_0,a_1,\dots ,a_n{)}^T\in {\mathbb{R}}^n$ nicht mehr als eine Liste von n-vielen reellen Zahlen $n$ vielen reellen Zahlen $a_0,a_1,\dots ,a_n\in \mathbb{R}$ (i.e. Zahlen mit beliebig vielen Nachkommastellen), denen wir eine Bedeutung zuweisen können. Bspw. kann der Vektor $(\mathrm{55,55},55{)}^T$ verwendet werden, um in einem RGB-System einen dunklen Grauton zu beschreiben, eine Zeitspanne von 55 Stunden, 55 Minuten, 55 Sekunden darzustellen oder die Zeichenfolge 777 im ASCII-Standard notieren.

Im Kontext der Geometrie arbeiten wir in der Regel mit zwei- und dreidimensionalen Vektoren. Die einzelnen Einträge beziehen sich hierbei auf eine gewisse Anzahl Schritte entlang der Achsen eines gegebenen Koordinatensystems. Konkret notiert im dreidimensionalen Fall der Vektor $(s_x,s_y,s_z{)}^T$ insgesamt $s_x$ entlang der x-Achse (rechts/links), $s_y$ entlang der y-Achse (unten/oben) und $s_z$ entlang der z-Achse (vorne/hinten).

Wie im obigen Beispiel kann hierbei der Vektor verwendet werden, um unterschiedliche Gegebenheiten zu beschreiben. Am Beispiel in Abbildung 2 kann man sehen, dass der Vektor $\overrightarrow{v}=(\mathrm{0,0},1{)}^T$ sowohl die Position des Punktes $p_0=\left(\mathrm{0,0},1\right)$ wiedergibt, eine Bewegung dieses Punktes nach $p_1=\left(\mathrm{0,0},2\right)$ notiert und die Ausrichtung des Quadrats Q beschreibt. Um diese verschiedenen Interpretationsmöglichkeiten gut unterscheiden zu können, werden wir im Nachfolgenden einheitlich Positionen im Raum mit $\overrightarrow{p}$ (für Punkt), Bewegungen mit $\overrightarrow{t}$ (für Translation) sowie RGB-Farben mit $\overrightarrow{c}$ (für Color) notieren. Zusätzlich wird $\overrightarrow{v}$ für Vektoren ohne zugewiesene Bedeutung verwendet. In jedem anderen Fall ( $\overrightarrow{n},\overrightarrow{r},\overrightarrow{u},\dots$ ) ist eine Richtung gemeint.

Wie in dem schon aus der Schule bekannten Zahlensystem können wir für Vektoren verschiedene Rechenoperationen definieren. Gegeben sind zwei Vektoren, $\overrightarrow{v_0}=(a_0,b_0,c_0{)}^T$ und $\overrightarrow{v_1}=(a_1,b_1,c_1{)}^T$ , bei denen die in Abbildung 3 dargestellten Verknüpfungen bekannt sind. Beachtet man Abbildung 3 genauer, erkennt man, dass Addition und Subtraktion typischerweise für Bewegungen verwendet werden. Als Beispiel ergibt sich der Ortsvektor $\overrightarrow{p_1}=(\mathrm{0,0},2{)}^T$ zum Punkt $p_1$ , der aus der Addition von $\overrightarrow{p_0}=\left(\mathrm{0,0},1\right)$ und $\overrightarrow{v}=\left(\mathrm{0,0},1\right)$ , also $\overrightarrow{p_0}+\overrightarrow{v}=\left(\mathrm{0,0},1\right)+\left(\mathrm{0,0},1\right)=\left(\mathrm{0,0},1+1\right)=\left(\mathrm{0,0},2\right)=\overrightarrow{p_1}$ sichtbar wird. Multiplikationen von Vektoren mit einer Zahl kommen unter anderem im Skalieren der Größe von geometrischen Objekten (bspw. Quadrat, Hexagon, Quader, …) und zur sogenannten Normierung eines Vektors $\overrightarrow{v}$ zum Einsatz.

Letzteres ist besonderes dann relevant, wenn eine Richtung beschrieben werden soll: Betrachten wir als Beispiel die beiden Richtungsvektoren $\overrightarrow{n}=\left(\mathrm{0,0},2\right)$ und ${\overrightarrow{n}}^{\text{'}}=\left(\mathrm{0,0},1\right)$ . In jedem Fall wird hier dieselbe Richtung beschrieben, nur die Länge der Vektoren ist unterschiedlich. Da wir im besten Fall mit einer eindeutigen Darstellung für Richtungen arbeiten wollen, einigen wir uns nun darauf, dass Richtungsvektoren grundsätzlich normiert sein müssen, sie haben genau Länge 1.

Um Vektoren, die keine Länge 1 haben, zu Vektoren mit Länge 1 umzubauen, kann man sie mit dem multiplikativen Inversen ihrer Norm ( $1÷\left|\overrightarrow{v}\right|$ ) multiplizieren. Stellt man sich hierbei den Vektor $\overrightarrow{v }$ als einen Pfeil im Raum vor, so entspricht die Norm von $\overrightarrow{v}$ der Länge dieses Pfeils, bestimmbar mittels des Satz des Pythagoras. Normieren wir obigen Beispielsvektor $\overrightarrow{n}$ , erhalten wir gesamt $\left(1÷\left|n\right|\right)\cdot \overrightarrow{n}=\left(1÷2\right)\cdot \left(\mathrm{0,0},2\right)=\left(\mathrm{0,0},1\right)={\overrightarrow{n}}^{\text{'}}$ . ${\overrightarrow{n}}^{\text{'}}$ ist also die normierte Variante von $\overrightarrow{n}$ .

Schließlich haben wir noch das Skalar- und Kreuzprodukt. Ersteres gibt uns Informationen darüber, wie zwei Vektoren zueinanderstehen: Berechnen wir das Skalarprodukt zweier normierter Richtungsvektoren $\overrightarrow{n_0}$ und $\overrightarrow{n_1}$ als $s=\overrightarrow{n_0}\cdot \overrightarrow{n_1}$ , so stehen diese

1. senkrecht aufeinander, wenn $s=0$ ist,

2. zeigen in dieselbe Richtung für $s=1$ und

3. sind zueinander entgegengesetzt bei $s=-1$ (wichtig: das gilt nur für normierte Vektoren).

Das Kreuzprodukt hingegen erlaubt uns für zwei gegebene Vektoren einen neuen Vektor, der genau senkrecht auf beiden steht, zu generieren. Das wird unter anderem später helfen, wenn wir die Ausrichtung der Kamera in der Szene modellieren wollen. Beachte: Das Kreuzprodukt ist nur für dreidimensionale Vektoren definiert, während alle anderen Verknüpfungen sich auf beliebig dimensionale Vektoren anwenden lassen.

Mathematische Grundlagen: Matrizen und Transformationen

Betrachtet man in Bezug auf Programmiersprachen einfache Arrays als Analogon zu Vektoren, so entsprechen Matrizen zweidimensionalen Arrays. Konkret ist eine $n\times m$ Matrix $M$ eine Tabelle von Zahlen $a_{i,j}\in \mathbb{R}$ mit $n$ Zeilen und $m$ Spalten, wobei $a_{i,j}$ den Eintrag für die $i$ -te Zeile und $j$ -te Spalte notiert. Zum Beispiel ist in der $2\times 3$ -Matrix E (Abb. 4) $a_{\mathrm{2,3}}=6$ , $a_{\mathrm{1,1}}=1$ und $a_{\mathrm{2,2}}=5$ . Eine wichtige Beobachtung: Für uns sind Vektoren nichts anderes als $1\times n$ -Matrizen, also Matrizen mit einer Zeile und n Spalten.

In Bezug auf Verknüpfungen kann man äquivalent wie für Vektoren Addition, Subtraktion und Multiplikation einer Zahl für Matrizen definieren. Für uns besonders relevant ist allerdings die sogenannte Matrixmultiplikation. Nehmen wir zwei Matrizen A und B. Ist A eine $n\times k$ Matrix und B eine $k\times m$ -Matrix (i. e., A hat genauso viele Spalten, wie B Zeilen hat), so lässt sich eine Produktmatrix $C=A\cdot B$ berechnen, wobei C eine $n\times m$ -Matrix ist. Betrachtet man hierbei $\overrightarrow{v_{A,i}}$ und $\overrightarrow{v_{B,j}}$ als die Vektoren der $i$ -ten Zeile in  $A$ und $j$ -ten Spalte in  $B$ , so ist der Eintrag $c_{i,j}$ von  $C$ gegeben durch $c_{i,j}=\overrightarrow{v_{A,i}}\cdot \overrightarrow{v_{B,j}}$ , also das Skalarprodukt dieser beiden Vektoren. Als Beispiel wollen wir die Multiplikation einer $2\times 2$ -Matrix A mit einem $2\times 1$ -Vektor ${\overrightarrow{v}}^T$ betrachten (Abb. 5).

Beachte: Das ${}^T$ , die sogenannte Transposition, vertauscht Zeilen und Spalten und wird hier verwendet, um aus dem $1\times 2$ -Vektor $\overrightarrow{v}$ einen $2\times 1$ -Vektor zu machen. Das Ergebnis ist ein $2\times 1$ -Vektor, wobei effektiv die zweite Spalte von  $A$ selektiert wurde.

Die Klasse von Matrizen, die für uns von besonderer Bedeutung ist, sind die Transformationen. Formal handelt es sich hierbei um genau die Matrizen, die einen sogenannten Basiswechsel beschreiben, näher erläutert in Abbildung 4. Hier beschreiben zwei verschiedene Personen die Position desselben Punktes P. So wird Person  $O_a$ den Punkt 2 Meter links und einen Meter vor sich beschreiben (also $P_a=\left(-\mathrm{2,2}\right)$ ), während Person  $O_b$ den gleichen Punkt 1 Meter rechts und 3 Meter vor sich beschreibt (also $P_b=\left(\mathrm{1,3}\right)$ ). Beide Beschreibungen sind valide, nur der Referenzrahmen (das genutzte Koordinatensystem) ist unterschiedlich. Eine Transformation kann hierbei den Übergang zwischen diesen beiden Referenzrahmen beschreiben. Sie beantwortet die Frage: „Wie sieht die Welt gesehen von Person $O_a$ aus Sicht von Person $O_b$ aus?“. In der Grafik ist dieses Konzept vor allem dann wichtig, wenn wir etwa wissen wollen, wie die Welt aus der Sicht der Kamera aufgebaut ist.

Transformationen lassen sich zudem nutzen, um Bewegungen sowie Deformationen im dreidimensionalen Raum zu modellieren. Betrachten wir als Beispiel die Rotation (beschrieben durch die Matrix $3\times 3$ $R$ ) eines Punktes $\overrightarrow{p}$ mit anschließender Verschiebung entlang des Vektors $\overrightarrow{t}$ (Abb. 7).

B beschreibt die vollständige Bewegung des Punktes $\overrightarrow{p}$ , die durch Multiplikation realisiert wird. Zu beachten ist hier, dass wir uns zur Implementation der Verschiebung eines Tricks bedienen: Anstatt rein mit dreidimensionalen Koordinaten zu rechnen, erweitern wir diese stattdessen zu sogenannten homogenen Koordinaten. Dabei fügen wir eine weitere Dimension hinzu, die mit dem Wert 1 gefüllt wird (entsprechend sind unsere Bewegungen dann auch mit $4\times 4$ Matrizen modelliert). Wie im obigen Beispiel zu sehen, wird diese neue Komponente nach der Definition der Matrixmultiplikation mit $\overrightarrow{t}$ malgenommen, was schlussendlich effektiv einer Addition von $\overrightarrow{t}$ zum Punkt gleichkommt.

Eine besonders kritische Eigenschaft dieser Art Matrizen ist, dass es sehr einfach ist, Transformationen...