2.4 Isolinien

Abbildung 2.13: IsoLine Klasse

Abbildung 2.14: Isolinien Funktionsauswertung

Neben der Darstellung durch Farben bzw. als Gitter oder Fläche über der Fläche können wir G-Spline-Funktionen auch durch Isolinien oder Niveaulinien darstellen. Dazu zeichnen wir auf der Fläche eine Linie, entlang der die Funktion den gleichen Wert hat. Die Werte, für die wir solche Linien zeichnen, können entweder äquidistant sein, oder wir können eine Liste spezieller Werte angeben.

Im Prinzip ist der Algorithmus für diese Darstellung ein verallgemeinerter Plotter für Contourlinien einer Funktion . Für die Isolinien leiten wir von Object eine neue Klasse IsoLine ab, die Zeiger auf die Fläche und die Funktion besitzt und die Darstellung der Isolinien genauer beschreibt, wie in Abbildung 2.13 dargestellt. Wir gehen davon aus, daß die Fläche und die Funktion bereits durch biquadratische Bézierkontrollnetze beschrieben werden. Wieder bearbeiten wir jedes Bézierkontrollnetz einzeln. Der Algorithmus isolines zeichnet die Isolinien für das Bézierkontrollnetz fb der Funktion, auf der durch das Bézierkontrollnetz b gegebenen Fläche, für den Parameterbereich u0u1v0v1. isolines wird rekursiv aufgerufen, um Unterschiede in der Dichte der Linien auszugleichen. Dabei sollte aber die maximale Rekursionstiefe möglichst klein gewählt werden. Der erste Aufruf erfolgt natürlich für den Parameterbereich .

Algorithmus 2.2  

1.

Falls die Funktion schon wenigstens einmal rekursiv aufgerufen wurde, d.h. falls die Rekursionstiefe level größer als 0 ist, dann überprüfe, ob in dem ausgewählten Quadrat im Parameterbereich Linien gezeichnet werden können:

(a)

Berechne die Funktionswerte f[0:3] an den vier Ecken des Parameterbereiches (siehe Abbildung 2.14).

(b)

Überprüfe, ob durch jede Seite des Quadrats maximal eine Isolinie geht, dann zeichne die Linien für das Quadrat mittels handle_quad:

i.

Falls äquidistante Isolinien gezeichnet werden sollen, verschiebe und skaliere zunächst die Funktionswerte: f[0:3] = (f[0:3] - base) / step. Dabei ist base ein Funktionswert, für den Isolinien gezeichnet werden sollen und step der Abstand zwischen den Funktionswerten der Isolinien. Damit wird das Problem auf das von Isolinien für ganzzahlige Funktionswerte reduziert.

ii.

Berechne die Differenz zwischen den Funktionswerten an den Ecken des Quadrats.

iii.

Sind alle Differenzen 0, dann nimm an, die Funktion ist konstant und kehre vom rekursiven Funktionsaufruf zurück. Wenn die Unterteilung am Anfang nicht fein genug gewählt wurde, können hierbei allerdings Details verloren gehen.

iv.

Sind alle Beträge der Differenzen kleiner als mindist, dann geht durch jede Seite des Quadrats maximal eine Isolinie. Rufe für dieses Quadrat handle_quad zum Zeichnen der Isolinien auf und kehre dann vom rekursiven Funktionsaufruf zurück. Für äquidistante Isolinien ist mindist gleich , für eine Liste von Werten ist mindist die kleinste Differenz zweier direkt aufeinanderfolgender Werte. Dieser Wert muß vor dem Aufruf von isolines bestimmt werden.

(c)

Falls die maximale Rekursionstiefe maxlevel erreicht wurde, unterteile das verbleibende Quadrat im Parameterbereich mittels bilinearer Interpolation in Teilquadrate:

i.

Berechne folgende ganzzahlige Werte für die Iteration über die Teilquadrate:
    uimax = abs(max(f[1] - f[0], f[2] - f[3]) / mindist) + 1
    vimax = abs(max(f[3] - f[0], f[2] - f[1]) / mindist) + 1
    uskip = (uimax / maxlines) + 1
    vskip = (vimax / maxlines) + 1
wobei maxlines die maximal erlaubte Anzahl von Isolinien pro Quadrat festlegt.

ii.

Zerlege den Parameterbereich in Teilquadrate über eine durch obige Werte bestimmte Iteration und rufe für jedes Teilquadrat handle_quad auf.
uimax und vimax geben die maximale Anzahl der Teilintervalle in - bzw. -Richtung an. uksip und vksip geben an, wieviele der Teilintervalle pro Iterationsschritt in - bzw. -Richtung übersprungen werden.

iii.

Kehre vom rekursiven Funktionsaufruf zurück.

2.

Zerlege den quadratischen Parameterbereich u0u1v0v1 in resolution gleichgroße Teilquadrate und rufe isolines rekursiv für jedes dieser Quadrate mit einer um erhöhten Rekursionstiefe auf.

Abbildung 2.15: isolines Algorithmus

Wie in Abbildung 2.15 gezeigt, unterteilen wir den Parameterbereich in Quadrate solange, bis nur noch maximal eine Linie durch jede Seite des Quadrats geht. Haben wir vorher die maximale Rekursionstiefe erreicht, dann legen wir über das Quadrat im Parameterbereich noch einmal ein Gitter, damit wir wieder Quadrate erhalten, durch deren Seiten maximal eine Linie geht. Das Gitter wird durch die Variablen aus Schritt refit:KuF:bilinf bestimmt. Es gibt zusätzlich den Parameter maxlines zur Begrenzung der Anzahl der Linien, die pro Quadrat des letzten Rekursionsschritts gezeichnet werden. Damit wird verhindert, daß hier ein zu feines Gitter erzeugt wird. Die Funktionswerte auf diesem Gitter werden durch bilineare Interpolation approximiert. Vor allem bei äquidistanten Isolinien für Funktionen, bei denen die Werte in einzelnen Bereichen stark ansteigen oder abfallen, aber sich sonst eher gering verändern, verbessert dies das Verhalten des Algorithmus'.

Die Interpolationsformel für die bilineare Interpolation von auf dem Quadrat bei Schritt I-C im Algorithmus lautet

Die Linien für ein einzelnes Quadrat werden schließlich durch den Algorithmus handle_quad gezeichnet. Hier wird einfach überprüft, von welcher Seite des Quadrats zu welcher Seite wir eine Linie zeichnen müssen. Dazu wird das Quadrat zusätzlich in zwei Dreiecke aufgeteilt und der Schnittpunkt mit der Diagonalen berücksichtigt. Optional kann die Linie auch noch in der Farbe für den für sie vorgesehenen Funktionswert gezeichnet werden. Außerdem kann man die Linien längs der Einheitsnormalen der Fläche um einen festen Wert verschieben, um sicherzustellen, daß sie nicht von der Fläche überdeckt werden.

Abbildung 2.16: handle_quad Algorithmus

Algorithmus 2.3  

1.

Zeichne die Linie für das Dreieck (u0,v0), (u1,v0), (u0,v1):

(a)

Überprüfe, ob eine Isolinie durch die Strecke von (u0,v0) nach (u1,v0) geht. Wenn ja, dann unterscheide folgende zwei Fälle:

i.

Geht eine Isolinie zum gleichen Funktionswert durch die Strecke von (u0,v0) nach (u0,v1), dann zeichne die Verbindungsstrecke.

ii.

Geht eine Isolinie zum gleichen Funktionswert durch die Strecke von (u1,v0) nach (u0,v1), dann zeichne die Verbindungsstrecke.

(b)

Überprüfe, ob eine Isolinie durch die Strecke von (u0,v0) nach (u0,v1) geht. Geht eine Isolinie zum gleichen Funktionswert auch durch die Strecke von (u1,v0) nach (u0,v1), dann zeichne die Verbindungsstrecke.

2.

Zeichne die Linie für das Dreieck (u1,v0), (u1,v1), (u0,v1):

(a)

Überprüfe, ob eine Isolinie durch die Strecke von (u1,v1) nach (u0,v1) geht. Wenn ja, dann unterscheide folgende zwei Fälle:

i.

Geht eine Isolinie zum gleichen Funktionswert durch die Strecke von (u1,v0) nach (u1,v1), dann zeichne die Verbindungsstrecke.

ii.

Geht eine Isolinie zum gleichen Funktionswert durch die Strecke von (u1,v0) nach (u0,v1), dann zeichne die Verbindungsstrecke.

(b)

Überprüfe, ob eine Isolinie durch die Strecke von (u1,v0) nach (u1,v1) geht. Geht eine Isolinie zum gleichen Funktionswert auch durch die Strecke von (u1,v0) nach (u0,v1), dann zeichne die Verbindungsstrecke.

Wir zerlegen zunächst das Quadrat in zwei Dreiecke über die Diagonale von (u1,v0) nach (u0,v1). In beiden Dreiecken überprüfen wir dann, von welcher Seite zu welcher Seite wir eventuell eine Linie ziehen müssen. Diese Linie wird auf dem Bézierflächenstück der Fläche, welches zum Bézierkontrollnetz der Funktion gehört, zu den entsprechenden Parameterwerten gezeichnet. Falls eine Isolinie durch eine der Seiten im Parameterbereich geht, wird der genaue Parameterwert durch lineare Interpolation auf der Seite berechnet. In Abbildung 2.16 sind die drei Fälle für das Dreieck (u0,v0), (u1,v0), (u0,v1) dargestellt.

Der Test, ob durch eine Seite eine Isolinie geht, hängt von der Weise ab, wie die Funktionswerte für die Isolinien gegeben wurden. Verwenden wir äquidistante Linien, wird handle_quad bereits mit den auf ganzzahlige Werte verschobenen und skalierten Funktionswerten aufgerufen. Wir müssen dann nur noch überprüfen, ob zwischen zwei Funktionswerten eine ganze Zahl liegt. Für eine Liste von Funktionswerten ist dies nicht ganz so einfach. Hierfür müssen wir für jedes Element dieser Liste überprüfen, ob es zwischen den zwei Funktionswerten an den Ecken liegt. Wenn wir die Liste der Funktionswerte sortieren, können wir dabei ein paar Vergleiche einsparen.

Abbildung 2.17: Contourplot des Affensattels

Mit Hilfe des Isolinien-Algorithmus' können wir auch Contourplots erstellen. Dazu verwenden wir für die Kontrollpunkte der Fläche ein ebenes Gitter. Auf diesem Gitter geben wir die Funktionskontrollpunkte für den Contourplot an. Zeichnen wir die Isolinien für diese Funktion, erhalten wir einen Contourplot. So können wir die Funktionskontrollpunkte z.B. über die Parametrisierung des Affensattels

mit , festlegen. Daraus ergibt sich der Contourplot aus Abbildung 2.17. In dieser Abbildung haben wir zusätzlich die Funktion über Farbwerte auf der Ebene dargestellt. Wir können auch die Höhenfunktion als Isolinien auf dem Affensattel darstellen. In Abbildung 2.18 haben wir die Isolinien etwas oberhalb und unterhalb der Fläche gezeichnet.

Abbildung 2.18: Höhenlinien des Affensattels

Abbildung 2.19: Isolinien auf der verdrehten Acht

In Abbildung 2.19 stellen wir die Funktion auf der in Abbildung 1.22 vorgestellten verdrehten Acht dar. Der Ursprung liegt dabei “links hinten” in der Ecke des entsprechenden erzeugenden Würfels. Ein Contourplot auf einer Ebene ist für diese Funktion nicht mehr möglich.

Abbildung 2.20: Isolinien des Kreuzes

Abbildung 2.21: Reflektionslinien

Neben den Isolinien für Funktionen können wir sie auch für die Fläche selbst zeichnen, d.h. wir verwenden die Flächenfunktion selbst für Isolinien. In diesem Fall markieren die Isolinien die Kurven auf der Fläche mit konstantem Abstand vom Ursprung. Abbildung 2.20 zeigt dies für das in Abbildung 1.23 vorgestellte Kreuz. Der Ursprung wurde dabei in den Mittelpunkt des Kreuzes gelegt.

Interessanter sind aber Reflektionslinien. Dazu definieren wir zunächst eine Ebene im Raum über einen Punkt und zwei linear unabhängige Vektoren und . Auf dieser Ebene seien nun parallele Lichtquellen im gleichen Abstand angebracht. In unserem einfachen Modell sind die Lichtquellen unendlich lang und besitzen keine Breite. Weiter nehmen wir an, daß die Intensität der Lichtstrahlen unabhängig von der Entfernung immer gleich groß sei. gebe die Richtung der Lichtquellen an und sei der Abstand zwischen den parallelen Lichtquellen. Das Licht von diesen Lichtquellen reflektieren wir an der Fläche für einen vorgegebenen Beobachtungspunkt . Diese Situation ist schematisch in Abbildung 2.21 dargestellt.

Sei ein beliebiger Punkt auf . Die Strecke legt den Ausfallswinkel für einen Reflektionsstrahl fest. Da der Einfallswinkel genauso groß wie der Ausfallswinkel sein muß, erhalten wir die Richtung des Reflektionsstrahls aus

wobei der Normalenvektor von bei ist. Für den Schnittpunkt des Reflektionsstrahls mit der Ebene erhalten wir die lineare Gleichung

mit den Unbekannten . In Matrixform ergibt dies

Numerisch können wir dieses System über einen Lösungsalgorithmus für lineare Gleichungssysteme lösen. Uns interessiert allerdings nicht der Schnittpunkt mit der Ebene, sondern ob der Reflektionsstrahl eine Lichtquelle auf der Ebene trifft. Dies ist der Fall, wenn ganzzahlig ist. Ist negativ, dann findet die Reflektion “hinter” der Ebene statt. Um diesen Fall auszuschließen, setzen wir die Reflektionsfunktion auf 0, wenn negativ ist.

Die Reflektionslinien können wir über den Isolinien-Algorithmus zeichnen, indem wir in Abhängigkeit von als Funktionswert verwenden. Auch wenn es kein realistisches Reflektionsmodell ist, kann man über diese Reflektionslinien sehr schön kleine Unebenheiten, etc. in der Fläche erkennen. Wichtig ist allerdings dabei eine sinnvolle Wahl der Ebene und des Beobachtungspunktes. Es genügt auch meistens nicht, die Fläche nur mit einer Einstellung zu untersuchen.

Abbildung 2.22: Reflektionslinien auf einem hyperbolischen Paraboloid

Abbildung 2.22 zeigt die Reflektionslinien für ein Fläche, deren Kontrollpunkte über das hyperbolische Paraboloid

bestimmt wurden. Die Reflektionsebene wurde dabei parallel zur --Ebene über der Fläche gewählt. Nachdem die Reflektionsebene unendlich groß ist, erhalten wir am Rand sehr viele Reflektionslinien. Um den Aufwand für das Zeichnen dieser Linien über den Algorithmus isolines zu verkleinern, sollte sowohl resolution, als auch maxlevel und maxlines möglichst klein gewählt werden. Für das hyperbolische Paraboloid wurde resolution auf , maxlevel auf und maxlines auf gesetzt.

Abbildung 2.23 zeigt die Reflektionslinien für Irregularitäten der Ordnung , und . Die Irregularitäten liegen alle um den Punkt und die Reflektionsebene ist durch den Punkt , den Lichtquellenrichtungsvektor und den Abstandsvektor gegeben. Für die Irregularitäten der Ordnung und wurde resolution auf , maxlevel auf undmaxlines auf gesetzt. Für die Irregularität der Ordnung war resolution, maxlevel und maxlines.

Abbildung 2.23: Reflektionslinien für Irregularitäten der Ordnung , und

Abbildung 2.24: Reflektionslinien auf der Acht

Für die in Abbildung 1.21 vorgestellte Acht zeigt Abbildung 2.24 die Reflektionslinien für eine zur --Ebene parallelen Ebene über der Acht. Aufgrund der Irregularitäten sind diese sehr unregelmäßig. Auch ist es notwendig maxlines und maxlevel des Isolinien-Algorithmus' stark zu beschränken, um unnötigen Rechenaufwand am Rand des Reflektionsgebietes zu vermeiden. maxlevel wurde für diese Abbildung auf , maxlines auf 6 und resolution auf gesetzt.