1.8 Algorithmen f�r biquadratische G-Splines

Wir werden nun die Algorithmen zur Berechnung und Darstellung der biquadratischen G-Spline-Fl�chen vorstellen. Dazu f�hren wir zun�chst eine Datenstruktur ein, mit der wir allgemein die geometrischen Objekte f�r eine Szene beschreiben k�nnen. Wir beschr�nken uns momentan darauf, nur die grobe Struktur anzugeben. Die vollst�ndige Dokumentation der Klassenstruktur in C++ ist im Anhang A zur Programm-Dokumentation beschrieben.

Eine einzelne Szene fassen wir zu einer World Klasse zusammen. Diese Klasse enth�lt zun�chst die generellen Eigenschaften der Szene, Informationen zur Projektionsmethode, zum Betrachter und �ber das Fenster, in dem die Szene angezeigt werden soll. Weiter enth�lt sie eine Liste von grafischen Objekten, die zu der Szene geh�ren, eine Liste der Lichtquellen und schlie�lich eine Liste der Objekte, die angezeigt werden sollen. Die Objekte in der letzten Liste m�ssen auch in der Liste aller grafischen Objekte vorhanden sein. Es k�nnen durchaus Objekte zur Szene geh�ren, die nicht angezeigt, aber zu deren Aufbau ben�tigt werden. Dies k�nnen z.B. Teile eines Kontrollnetzes sein. Die Klasse stellt auch Methoden zur Darstellung und Bearbeitung der Objekte zur Verf�gung. Dabei mu� zun�chst die Methode zur Bearbeitung der Objekte aufgerufen werden, die z.B. die G-Spline-Kontrollnetze in Bézierkontrollnetze umwandelt. Die Methode zur Darstellung zeichnet die vorher bearbeiteten, darzustellenden Objekte direkt. Abbildung 1.13 zeigt den groben Aufbau dieser Klasse.

Die grafischen Objekte k�nnen Punkte, Polygone, G-Splines, etc. sein, aber auch Lichtquellen k�nnen so beschrieben werden. Die Lichtquellen werden in der World Klasse aus Effizienzgr�nden in einer speziellen Liste eingetragen. Die Klassen f�r diese Objekte werden alle von der Klasse Object abgeleitet. Dabei enth�lt Object die allgemeinen Eigenschaften eines solchen grafischen Objekts. Dies sind z.B. ein Bezeichner f�r das Objekt, die Materialeigenschaften und Methoden zum Darstellen, Bearbeiten, etc. des Objekts. F�r die speziellen Typen der Objekte kommen dann weitere spezielle Eigenschaften hinzu. Teilweise werden auch spezielle Methoden zum Darstellen und Bearbeiten des Objekts zur Verf�gung gestellt. F�r ein Polygon speichern wir z.B. als zus�tzliche Eigenschaft eine Liste von Punkt-Objekten, die die Kanten des Polygons beschreiben. Ein G-Spline-Objekt enth�lt dann eine Liste von Polygon-Objekten, aus denen das G-Spline-Kontrollnetz aufgebaut ist. Weiter enth�lt es eine Liste von Bézierkontrollnetzen f�r biquadratische Bézierfl�chen, die aus dem Kontrollnetz erzeugt wurden. Wir werden sp�ter weitere Eigenschaften und Objekte hinzuf�gen. Die grobe Struktur der Object Klassen wird in Abbildung 1.14 dargestellt.

Ein Kontrollnetz einer G-Spline-Fl�che wird durch Punkte dargestellt, die durch Polygone zu einem Netz verbunden sind. Soweit die Fl�che selbst orientierbar ist, sollte jedes dieser Polygone die gleiche Orientierung besitzen. F�r einen einfachen G-Spline-Algorithmus ben�tigen wir die Orientierung allerdings nicht. Sie wird aber f�r bestimmte Darstellungen von Funktionen auf den Fl�chen notwendig. Auch k�nnen wir die Orientierung bei der Berechnung des G-Splines ausnutzen. Wir setzen aber nicht voraus, da� die Polygone gleich mit der richtigen Orientierung vorgegeben wurden. Der Algorithmus gspline_orientation orientiert die Polygone eines G-Spline-Kontrollnetzes.

Algorithmus 1.1

gspline_orientation

G-Spline-Kontrollnetz orientieren

1.

Falls das Kontrollnetz der G-Spline-Fl�che schon als orientiert markiert ist, ist nichts zu tun.

2.

Erzeuge eine Liste pfl, die zu jedem Kontrollpunkt die Polygone angibt, die diesen Punkt enthalten. Dazu bearbeite jedes Polygon facet des G-Spline-Kontrollnetzes einzeln:

(a)

F�r jeden Punkt eines solchen Polygons unterscheide die beiden F�lle:

i.: Wenn der Punkt noch nicht in der Liste pfl vorhanden ist, f�ge ein neues Element f�r diesen Punkt mit dem Polygon facet hinzu.
ii.: Wenn der Punkt schon in der Liste vorhanden ist, f�ge das Polygon facet zu dem Element hinzu.

3.

Markiere alle Polygone als nicht orientiert.

4.

Orientiere jedes Polygon allpolygon des G-Spline-Kontrollnetzes. Dazu f�hre Folgendes f�r jedes allpolygon aus:

(a)

Falls das Polygon allpolygon nicht orientiert ist, verwende die Orientierung des Polygons allpolygon um alle Polygone zu orientieren, die in dem zusammenh�ngenden Teilnetz von allpolygon liegen:

i.

Markiere allpolygon als orientiert.

ii.

Falls vom Benutzer gefordert wird die Orientierung der Fl�che zu �ndern, drehe die Reihenfolge der Punkte in allpolygon um.

iii.

F�ge allpolygon in die leere Polygonliste poly_list ein.

iv.

Nun orientiere alle Polygone, die zum zusammenh�ngenden Teilnetz von allpolygon geh�ren. Dazu wiederhole Folgendes, solange poly_list nicht leer ist:

a.

Entferne das erste Element polygon aus poly_list.

b.

Finde f�r jede Kante von polygon die anderen Polygone, die diese Kante enthalten. Benutze dazu die am Anfang erzeugte Liste pfl.

c.

Jedes dieser anderen Polygone polygon2 mu� die entsprechende Kante in die entgegengesetzte Richtung durchlaufen, damit die Orientierung korrekt ist. Unterscheide hierf�r folgende F�lle:

a.: Wenn die Kante in polygon2 entgegengesetzt durchlaufen wird und polygon2 noch nicht als orientiert markiert ist, dann markiere es als orientiert und f�ge es zur Liste poly_list hinzu.
b.: Wenn die Kante in polygon2 entgegengesetzt durchlaufen wird und polygon2 als orientiert markiert ist, ignoriere es.
c.: Wenn die Kante in polygon2 in der gleichen Richtung durchlaufen wird und polygon2 als nicht orientiert markiert ist, dann drehe die Reihenfolge der Punkte in polygon2 um, markiere es als orientiert und f�ge es zur Liste poly_list hinzu.
d.: Wenn die Kante in polygon2 in der gleichen Richtung durchlaufen wird und polygon2 als orientiert markiert ist, dann ist die Fl�che nicht orientierbar. Gib eine entsprechende Warnung aus.

Damit obiger Algorithmus funktioniert, mu� die Fl�che orientierbar sein. Bei nicht orientierbaren Fl�chen wird lediglich die Anzahl der Kanten, an denen das Kontrollnetz nicht orientiert ist, reduziert. Es bleiben die Kanten �brig, f�r die der Fall d. von IV-A-4 zutrifft. Dies kann an beliebigen Stellen im Kontrollnetz erfolgen, ohne da� diese Kanten miteinander verbunden sind und h�ngt von der Reihenfolge ab, in der die Polygone bearbeitet werden.

Normalerweise nehmen wir auch an, da� nur maximal zwei Polygone eine gemeinsame Kante haben. Der Algorithmus funktioniert aber auch, wenn es mehr Polygone sind, allerdings kann man dann genau genommen nicht mehr von einer Orientierung sprechen. Sp�testens bei der Umwandlung des Kontrollnetzes in Bézierpunkte werden an solchen Stellen nur noch zwei Polygone ber�cksichtigt. Welche dies sind, ist dabei nicht festgelegt und h�ngt wieder von der Reihenfolge ab, in der die Polygone bearbeitet werden.

Es bietet sich auch an, die Liste pfl durch eine weiteres Objekt zu repr�sentieren, da wir solche und �hnliche Listen h�ufiger ben�tigen. Wir werden sie also durch eine Klasse implementieren, die Methoden zur Umwandlung des Kontrollnetzes in eine solche Liste enth�lt.

Unser n�chstes Ziel ist die Entwicklung eines Algorithmus, der die Kontrollpunkte f�r die G-Spline-Fl�che in Bézierpunkte f�r biquadratische Bézierfl�chen nach Theorem 1.8 umwandelt. Hier ist das Hauptproblem, die entsprechenden Punkte in dem �ber Polygone definierten semi-regul�ren Kontrollnetz zu finden. Dazu behandeln wir zun�chst alle irregul�ren Stellen des Netzes. Jedes Polygon

des Kontrollnetzes mit mehr oder weniger als vier Punkten beschreibt eine Irregularit�t. Die Punkte in der Umgebung dieses Polygons werden unter Ber�cksichtigung der Orientierung durch folgenden Algorithmus bestimmt und �ber Theorem 1.8 werden die Bézierpunkte berechnet. Dabei werden zun�chst nur die Fl�chenst�cke f�r die Punkte des Polygons

berechnet und die Quasikontrollpunkte gespeichert. Denn die Gleichungen f�r den �u�eren Ring um

stimmen mit dem regul�ren Fall �berein, falls die Quasikontrollpunkte verwendet werden. Nachdem alle Irregularit�ten behandelt wurden, werden die restlichen Bézierpunkte f�r den regul�ren Fall berechnet, wobei die entsprechenden Quasikontrollpunkte und die schon berechneten Bézierpunkte ber�cksichtigt werden.

Algorithmus 1.2

process_gspline_object

G-Spline-Kontrollnetz in Bézierkontrollnetze umwandeln

1.

Orientiere das G-Spline-Kontrollnetz mit gspline_orientation.

2.

Erzeuge eine Liste pfl, die zu jedem Kontrollpunkt die Ordnung und die Polygone angibt, die diesen Punkt enthalten. Bearbeite dazu jedes Polygon facet des G-Spline-Kontrollnetzes einzeln:

(a)

Bestimme zun�chst die Anzahl n der Punkte des Polygons.

(b)

F�r jeden Punkt des Polygons unterscheide die beiden F�lle:

i.

Wenn der Punkt schon in der Liste vorhanden ist, f�ge das Polygon facet zu dem Element hinzu:

a.: Falls n nicht 4 ist, setze die Ordnung des Punktes in der Liste auf n. Sollte die Ordnung des Punktes in der Liste vorher schon von 4 verschieden sein, dann liegen zwei irregul�re Teile des Netzes nebeneinander. Beende in diesem Fall den Algorithmus mit einer entsprechenden Fehlermeldung.
b.: Falls das Element f�r den Punkt in pfl wenigstens 4 Polygone auflistet, die diesen Punkt enthalten, dann beende den Algorithmus ebenfalls mit einer entsprechenden Fehlermeldung.
c.: F�ge facet dem Element f�r den Punkt in pfl hinzu.

ii.

Wenn der Punkt noch nicht in der Liste vorhanden ist, erzeuge ein neues Element in der Liste f�r diesen Punkt mit dem Polygon facet und der Ordnung n.

3.

Berechne die Bézierkontrollnetze f�r die irregul�ren Teile des G-Spline-Kontrollnetzes. Betrachte dazu jeden Punkt p aus der Liste pfl mit der Ordnung n ungleich 4 der in 4 Polygone des Kontrollnetzes enthalten ist und noch nicht bearbeitet wurde. Die Bézierkontrollnetze f�r diese Irregularit�t werden wie folgt erzeugt:

(a)

Finde das Polygon fi, das genau n Punkte enth�lt, von denen einer p ist. Dies ist das Polygon welches die Irregularit�t im Netz erzeugt.

(b)

Bestimme die Punkte D (vgl. Abbildung 1.15) als Punkte von fi. Die Numerierung sei durch die Reihenfolge der Punkte in fi beginnend mit p festgelegt.

(c)

Markiere alle Punkte D als bearbeitet.

(d)

Wenn einer der Punkte D nicht genau in 4 Polygonen enthalten ist, fahre mit dem n�chsten Punkt fort, da die Irregularit�t nicht vollst�ndig ist.

(e)

Finde das Polygon D[0], J[0], L[0], F[0] (vgl. Abbildung 1.15). Dies ist das einzige Polygon, das D[0] enth�lt, aber nicht D[1] und D[n-1]. Nehme zun�chst an, da� die Punkte J[0], L[0], F[0] dem Punkt D[0] in dieser Reihenfolge im Polygon folgen.

(f)

Finde den Punkt J[1]. Suche dazu das Polygon, welches D[1], D[0] und F[0] in dieser Reihenfolge enth�lt. Existiert dieses Polygon nicht, dann stimmt die vorher gew�hlte Orientierung an dieser Stelle nicht. Suche in diesem Fall das Polygon mit der Kante von D[1] nach D[0] und vertausche J[0] und F[0]. In beiden F�llen ist J[1] der fehlende Punkt des Polygons.

(g)

Bestimme die restlichen Punkte F[k], L[k], J[k+1] f�r

(vgl. Abbildung 1.15):

i.: Finde das Polygon D[k], J[k], L[k], F[k]. Dazu suche zun�chst das Polygon, das die Kante D[k], J[k] enth�lt. Folgt diesen Punkten im Polygon nicht F[k-1], dann sind die n�chsten beiden Punkte des Polygons L[k] und F[k]. Wird dieses Polygon nicht gefunden, dann stimmt die Orientierung an dieser Stelle nicht. Suche in diesem Fall das Polygon mit der Kante von J[k] nach D[k]. Folgt auf diese Kante im Polygon nicht D[k-1], dann sind die n�chsten beiden Punkte des Polygon F[k] und L[k].
ii.: Ist k kleiner als , dann bestimme J[k+1]. Dazu suche zun�chst das Polygon mit der Kante von D[k] nach F[k]. Ist der n�chste Punkt in diesem Polygon nicht der Punkt D[k+1], dann ist dieser J[k+1]. Existiert ein solches Polygon nicht, dann stimmt die Orientierung an dieser Stelle nicht. In diesem Fall suche das Polygon mit der Kante von D[k] nach D[k+1]. Folgt hier nicht der Punkt F[k], dann ist dies der Punkt J[k+1].

(h)

Berechne die Quasikontrollpunkte Dv, Fv, Jv, Lv aus D, F, J, L �ber (1.48).

(i)

Berechne die Bézierpunkte A, B, C, E, G, H, I, K, M aus den Quasikontrollpunkten �ber die Gleichungen (1.45).

(j)

Erzeuge f�r jeden Kontrollpunkt das entsprechende Bézierkontrollnetz aus den bisher berechneten Punkten und f�ge es zur Liste der Bézierkontrollnetze des G-Splines mit einer Referenz auf den Kontrollpunkt hinzu.

(k)

Speichere f�r jeden Kontrollpunkt D, F, J, L zus�tzlich die Position des zugeh�rigen Quasikontrollpunktes. Diese wird dazu verwendet den �u�eren Ring der Bézierpunkte im n�chsten Teil des Algorithmus' zu berechnen.

4.

Berechne die Bézierkontrollnetze f�r die regul�ren (noch nicht bearbeiteten) Teile des G-Spline-Kontrollnetzes. Hierzu wird ein Bézierkontrollnetz f�r jeden Punkt m aus der Liste pfl der Ordnung 4 erzeugt, der in 4 Polygonen des G-Spline-Kontrollnetzes enthalten ist und noch nicht bearbeitet wurde (vgl. Abbildung 1.17):

(a): W�hle ein beliebiges Polygon f0 aus, das m enth�lt und markiere dieses Polygon als benutzt.
(b): W�hle Punkte n0, nn0, n1 als die Punkte, die m in der Punktliste des Polygons in dieser Reihenfolge folgen.
(c): Finde das Polygon f1. Dazu suche in allen nicht als benutzt markierten Polygonen, die m enthalten, die Kante von m nach n1. Nach diesen beiden Punkten folgen die Punkte nn1 und n2. Wird die Kante in die entgegengesetzte Richtung durchlaufen, stimmt die Orientierung an dieser Stelle nicht. In diesem Fall folgen auf die Kante von n1 nach m die Punkte n2, nn1. Markiere schlie�lich das Polygon f1 als benutzt.
(d): Finde das Polygon f2 analog zu f1, wobei die gesuchte Kante nun m, n2 ist. nn2, n3 folgen entsprechend der Orientierung.
(e): Finde nn3 in dem noch nicht als benutzt markierten Polygon, das m enth�lt. Unabh�ngig von der Orientierung ist nn3 in diesem Polygon der zweite Punkt nach m.
(f): Erzeuge das Bézierkontrollnetz f�r m nach (1.38) f�r den regul�ren Fall. Dazu werden im wesentlichen die Mittel der f�r die Bézierpunkte zust�ndigen Kontrollpunkte berechnet. Falls allerdings Quasikontrollpunkte f�r die Kontrollpunkte im irregul�ren Fall berechnet wurden oder schon Bézierkontrollnetze f�r die angrenzenden Fl�chenst�cke existieren, verwende die Koordinaten dieser Punkte. Sollten f�r die vorher bestimmten Punkte schon Bézierkontrollnetze berechnet worden sein, dann verwende die Koordinaten des mittleren Bézierpunktes. Falls ein Quasikontrollpunkt f�r diese Punkte berechnet wurde, verwende die Koordinaten des Quasikontrollpunktes. Sonst verwende die Koordinaten des Kontrollpunktes.

In Schritt III-H wird zur Berechnung der Quasikontrollpunkte die Matrix

f�r die Gleichung (1.48) ben�tigt. Da diese Matrix nur von der Ordnung der Irregularit�t abh�ngt, gen�gt es aber, sie pro ben�tigter Ordnung nur einmal zu berechnen und sie f�r weitere Berechnungen zu speichern.

Abbildung 1.16 zeigt ein M�biusband, das durch ein regul�res Kontrollnetz beschrieben wird. Dieses Netz wurde allerdings schon mit dem im n�chsten Abschnitt beschriebenen Doo-Sabin-Subdivision-Algorithmus aus einem vereinfachten Kontrollnetz erzeugt.