Computergraphik II

Transcrição

Computergraphik II

Computergraphik II
Susanne Krömker
Sommersemester 2010
Skript zur Vorlesung, Stand 9. April 2010
Inhaltsverzeichnis
1
Einführung ins Rendering
1
1.1
OpenGL und was es sonst noch so alles gibt . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Blinn-Phong, ein lokales Lichtmodell . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.1
Gerichtete Lichtquellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Cook & Torrance Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3.1
Bidirektionale Reflexivität . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3.2
Distributionsfunktion des Mikrofacettenmodells . . . . . . . . . . . . . . . .
6
1.3.3
Geometrische Abschwächung durch Mikrofacetten . . . . . . . . . . . . . .
8
1.3.4
Fresnelterm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.3
1.4
2
Graphikkarten Programmierung
17
2.1
Shader Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2
Shade trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.2.1
Reyes-Pipeline und Renderman Interface . . . . . . . . . . . . . . . . . . .
21
2.2.2
Dicing oder Würfelalgorithmus . . . . . . . . . . . . . . . . . . . . . . . .
21
C for graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.3.1
24
2.3
Cg - Historische Entwicklung . . . . . . . . . . . . . . . . . . . . . . . . .
iii
iv
INHALTSVERZEICHNIS
2.4
3
Programmierbarer Vertex Prozessor . . . . . . . . . . . . . . . . . . . . . .
24
2.3.3
Programmierbarer Fragment Prozessor . . . . . . . . . . . . . . . . . . . .
25
2.3.4
CgFX Toolkit und Austauschformat . . . . . . . . . . . . . . . . . . . . . .
25
2.3.5
Compiler und Bibliotheken . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.3.6
Ähnlichkeit mit C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.3.7
Besonderheiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.3.8
Fehlerbehandlung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.3.9
Parameter, Texturen und mathematische Ausdrücke . . . . . . . . . . . . . .
37
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
Volume Rendering
45
3.1
Herleitung der Gleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.1.1
Energieerhaltungsgleichung . . . . . . . . . . . . . . . . . . . . . . . . . .
47
3.2
Vereinfachungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.3
Einfacher Ray Casting Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.3.1
Klassifizierung und Transferfunktion . . . . . . . . . . . . . . . . . . . . .
50
Beschleunigungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
3.4.1
Early Ray Termination – Abbruchkriterien . . . . . . . . . . . . . . . . . .
52
3.4.2
Ausnutzen kohärenter Strukturen . . . . . . . . . . . . . . . . . . . . . . .
52
3.4.3
Shear-Warp Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
3.4.4
Texturbasiertes Volume Rendering . . . . . . . . . . . . . . . . . . . . . . .
54
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.4
3.5
4
2.3.2
Radiosity
57
4.1
59
Herleitung des Verfahrens und Modellgleichung . . . . . . . . . . . . . . . . . . . .
INHALTSVERZEICHNIS
4.2
Diskrete Radiositygleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.3
Berechnung der Formfaktoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.3.1
Brute Force Ansatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.3.2
Methode nach Nusselt . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
4.3.3
Hemicube Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.3.4
Sillions Verbesserung und weitere Methoden . . . . . . . . . . . . . . . . .
67
Berechnung der Radiosity-Werte . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
4.4.1
Allgemeine Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.4.2
Jacobiverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.4.3
Gauß-Seidel Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.4.4
SOR-Verfahren (Successive Overrelaxation) bzw. Relaxationsverfahren . . .
72
4.4.5
Anwendbarkeit der Iterationsverfahren auf Radiosity . . . . . . . . . . . . .
73
4.4.6
Progressive Verfeinerungen . . . . . . . . . . . . . . . . . . . . . . . . . .
73
4.4.7
Gathering Verfahren (= Einsammeln) . . . . . . . . . . . . . . . . . . . . .
75
4.4.8
Shooting Verfahren (= Aussenden) . . . . . . . . . . . . . . . . . . . . . . .
76
Rendern mit Radiosity-Werten . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
4.5.1
Lichtlecks und Diskontinuitäten . . . . . . . . . . . . . . . . . . . . . . . .
79
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
4.4
4.5
4.6
5
v
Photon Mapping
81
5.1
Die Spur der Photonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
5.1.1
Photonemission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
5.1.2
Photonenverfolgung mit russischem Roulette . . . . . . . . . . . . . . . . .
85
5.1.3
Speichern von Photonen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
Photonen im Rendering Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.2
vi
INHALTSVERZEICHNIS
5.3
6
5.2.1
Abschätzung der Strahlung an einer Oberfläche . . . . . . . . . . . . . . . .
90
5.2.2
Filter für die Abschätzung . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
5.2.3
Strahlungsabschätzung im Volumenfall . . . . . . . . . . . . . . . . . . . .
94
5.2.4
Auffinden der n nächsten Photonen . . . . . . . . . . . . . . . . . . . . . .
95
5.2.5
Auswertung der Strahlungsabschätzung: Rendering . . . . . . . . . . . . . .
96
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
Nichtphotorealistisches Rendering
101
6.1
Zweidimensionale NPR-Techniken, Bildbearbeitung . . . . . . . . . . . . . . . . . 102
6.2
Dreidimensionale NPR-Techniken . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.3
Konturlinien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4
6.5
6.6
6.7
6.3.1
Silhouetten mit OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3.2
Exaktes Verfahren für Dreiecksgitter . . . . . . . . . . . . . . . . . . . . . . 104
6.3.3
Bildbasierter Konturalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . 106
Nichtphotorealistisches Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.4.1
Cel-Shading oder Toon-Shading . . . . . . . . . . . . . . . . . . . . . . . . 110
6.4.2
Gooch Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Line-Art Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5.1
Kreuzschraffur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.5.2
Krümmungsangepasste Schraffur . . . . . . . . . . . . . . . . . . . . . . . 113
Transformationen der Geometrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.1
Blickpunktsänderung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.2
Animationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
INHALTSVERZEICHNIS
7
Splines
7.1
7.2
7.4
121
Splinekurven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.1.1
Kubisch hermitesche Splines . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.1.2
Bézier-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.1.3
Konstruktionsalgorithmus nach Casteljau . . . . . . . . . . . . . . . . . . . 125
7.1.4
B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.1.5
Konstruktion der Basisfunktionen . . . . . . . . . . . . . . . . . . . . . . . 129
7.1.6
Verfeinerbarkeit von B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.1.7
Subdivision für Spline-Kurven . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.1.8
Nichtuniforme rationale B-Splines . . . . . . . . . . . . . . . . . . . . . . . 133
Flächen als bivariate Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.2.1
7.3
vii
NURBS-Flächen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Subdivisionflächen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.3.1
Subdivision Schemata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7.3.2
Catmull-Clark Subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.3.3
Subdivision nach Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.3.4
Weiche und scharfe Kanten . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Übungsaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Literaturverzeichnis
148
viii
INHALTSVERZEICHNIS
Kapitel 1
Einführung ins Rendering
Mit dem Begriff Echtzeit Rendering verbindet man immer noch geringere Qualität und schnelle, aber
nicht unbedingt realistische Spielegraphik. Inzwischen sind aber auch Verfahren wie Raytracing auf
gutem Wege, in Echtzeit darstellbare Bilder zu liefern. Hierfür ist noch immer speziell entwickelte
Hardware nötig, die die Parallelisierbarkeit des Algorithmus optimal ausnutzt (siehe beispielsweise
die Arbeiten von Philipp Slusallek, Universität Saarbrücken [SWW+ 04]). Eine weitere Entwicklung
setzt auf die Auslagerung vieler einfacher Operationen auf die Graphikprozessoren (GPU) und erzielt
damit einen großen Geschwindigkeitsvorteil im Renderprozess.
Diese Vorlesung wird sich mit den möglichen Qualitätssteigerungen im Rendering auseinandersetzen
und dabei den algorithmischen Teil und mathematische Verfahren betonen. Damit ein Quereinstieg
möglich ist, wiederholt dieses Eingangskapitel einige Themen aus dem ersten Teil der Vorlesung.
1.1
OpenGL und was es sonst noch so alles gibt
Die Open Graphics Library (OpenGL) ist eine architektur- und programmiersprachenunabhängige
Implementierung eines Application Programming Interface (API) zum Erzeugen von 3D-Computergraphik. Sie wird als Teil der Graphikkarten-Treiber ausgeliefert, wobei auf der Graphikkarte fehlende Funktionen von der CPU emuliert werden können. Die gängigste Open-Source-Implementierung
annähernd gleicher Mächtigkeit und nachprogrammierter Struktur ist die Mesa-Bibliothek.
Auf dieser Basis haben weitere Entwicklungen aufgesetzt, wie beispielsweise das Visualization Toolkit (VTK). Es wurde für spezielle Anforderungen im wissenschaftlichen Bereich entwickelt, hat daher
seine Stärken im Bereich der Darstellung von Messdaten und Simulationsdaten, Strömungs- und Vektorfeldern.
Die Virtual Reality Markup Language (VRML) ist ein Standard zur Beschreibung von 3D-Graphiken
mit einfachen geometrischen Objekten und Beleuchtungsmodellen. Erweitert um Interaktionen und
1
2
KAPITEL 1. EINFÜHRUNG INS RENDERING
mit der Möglichkeit, über Plugins im Browser darstellbar zu sein, ist diese 3D-Beschreibungssprache
von entprechenden z.B. auf Basis von OpenGL geschriebenen Viewern abhängig. Sie dient auch vielen Programmen als 3D-Austauschformat.
Java ist ebenfalls plattformunabhängig und eine Entwicklung von Sun Microsystems. Es lassen sich
damit 3D-Graphiken erstellen und animieren, und vor allem in Browsern interaktiv steuern. Java hat
dazu eine eigene Skriptsprache JavaScript, die von fast allen Browsern unterstützt wird.
DirectX ist eine Entwicklung von Microsoft speziell für multimediale Interaktion. Es bietet viele Vorteile beim Einbinden von Audiofunktionen in 3D-Graphiken, ist auf dem Spielesektor weit verbreitet,
aber von der Plattform auf Microsoft-Betriebssysteme eingeschränkt.
1.2
Blinn-Phong, ein lokales Lichtmodell
Die lokalen Lichtmodelle gehen einzig von einem Punkt auf der Oberfläche eines Objekts aus und
ermitteln die Lokalfarbe aus den an diesem Punkt bekannten Vektoren und den Eigenschaften dieser
Objekte und der Lichter. Sie lassen sich sehr gut mit dem z-Buffer Algorithmus kombinieren, denn
auch dieser Algorithmus arbeitet mit lokalen Werten: Über den z-Wert eines Punktes wird entschieden, ob dieser Punkt im Colorbuffer dargestellt wird. Für beide Algorihmen ist das Wissen um die
räumlichen Beziehungen zwischen Objekten nicht notwendig. Verdeckungen aus Betrachtersicht sind
effizient darstellbar, aber Verdeckungen aus Sicht einer Lichtquelle, die kein Headlight ist und daher
einen Schatten eines der Lichtquelle näheren Objekts auf andere Objekte wirft, benötigen weitere
Tricks. Man wird mit diesen eingeschränkten Verfahren keine photorealistischen Effekte erreichen
können. Um dennoch eine hohe reale Wirkung zu erzielen, setzt man auf den Oberflächen Texturen
ein, die mit lokalen Lichtmodellen überblendet werden, so dass auch bewegte Lichtquellen oder sich
im Lichtkegel bewegende Objekte realistisch wirken.
Zur Erinnerung: Lokale Lichtmodelle definieren an einem Punkt der Oberfläche Komponenten aus
Umgebungslicht, das mit Ambient bezeichnet wird, diffusem Streulicht und spiegelndem Spekularlicht.
I = Iambient + Idif f us + Ispecular
Das ambiente Licht stellt einen durch Streuung an allen Objekten im Raum vorhandenen Grundpegel
an diffusem Licht dar, das keiner speziellen Lichtquelle und damit keiner Richtung zugeordnet ist.
Der diffuse Anteil bezieht sich jetzt auf die Summe aller Lichtquellen, deren einstrahlende Intensität
mit der diffusen Oberflächeneigenschaft, einer Materialkonstante kd , gewichtet werden. Richtung der
Lichtquelle Li und die Normale N gehen in diesen Term ein. Das spiegelnde Licht ist außer von
der Materialkonstante ks noch vom Standpunkt des Betrachters abhängig. Hier unterscheidet man im
1.2. BLINN-PHONG, EIN LOKALES LICHTMODELL
3
Wesentlichen das Phong Modell von 1975
I = Ia ka + Ii [kd (L · N ) + ks (R · V )n ]
und die Weiterentwicklung zum Blinn-Phong Modell von 1977, dass mit dem Halfway Vektor H auf
Hälfte zwischen L und V arbeitet. Dieser Vektor lässt sich einfacher als die Reflexionsrichtung R
berechnen.
I = Ia ka + Ii [kd (L · N ) + ks (N · H)m ]
N H
6 R
L
(cosϕ)m
I
@
@
ϕ
(cosφ)n
@ I
φ
:
@θ V
@
Abbildung 1.1. Der diffuse Anteil des abstrahlenden Lichts (grüne Linie) geschieht gleichmäßig in alle Richtungen,
der dazu addierte spiegelnde Anteil berechnet sich aus der Betrachterposition V . Das Phong Modell (blaue Linie)
benutzt dazu den Reflexionsvektor R, das Blinn-Phong Modell (rote Linie) den Halfway Vektor H auf Hälfte
zwischen L und V .
1.2.1
Gerichtete Lichtquellen
Als sogenanntes Warn Modell (1983) bezeichnet man ein mit geringem Rechenaufwand erweitertes
Phong Modell, bei dem die Quellenintensität zusätzlich vom Winkel ϑ zwischen den Vektoren LN
und (−L) abhängt. Der cos ϑ kann wieder über ein Skalarprodukt ausgedrückt werden, mit dem die
Intensität gewichtet wird. Dabei sorgt der Exponent s für ein Fokussieren des Lichts: Je größer der
Exponent, desto konzentrierter fällt das Licht nur in die ausgezeichnete Richtung LN .
I = Ia ka + Ii (LN · (−L))s [kd (L · N ) + ks (N · H)n ]
4
Der konische Spot ist eine gerichtete Lichtquelle, bei der ein maximaler Winkel δ angegeben wird.
Außerhalb dieses Winkels wird diese Lichtquelle nicht berücksichtigt.
HH
H
@
N
6
ϑ@
@
LN I
@
@L
@
@θ
@
Abbildung 1.2. Quellenintensität hängt von der Richtung ab, in die die Lichtquelle strahlt.
1.3
Cook & Torrance Modell
Mit dem Phong-Modell lassen sich plastikartige Oberflächen gut modellieren, es zeigt aber deutliche
Mängel bei hochglänzenden, metallischen Oberflächen. Das von Cook und Torrance vorgeschlagene Beleuchtungsmodell von 1982 (siehe [CT82]) ist die physikalisch begründete Vereinfachung der
Auswirkungen von Mikrofacetten einer Oberfläche. Die Hauptunterschiede zum Phong-Modell bestehen in der Berücksichtigung der einfallenden Strahlungsenergie, dem Mikrofacetten-Modell für
das Spiegellicht, Farbabstufungen im Highlight und die Berücksichtigung des Fresnelschen Gesetzes.
Für dieses Modell typische Intensitätsverteilungen wirken sich insbesondere für nahezu tangentiale Einfalls- oder Betrachterwinkel aus. Das maximale Highlight ist dann nämlich NICHT identisch
mit der Reflexionsrichtung. Wie sich das an den Rändern einer spiegelnden Kugel auswirkt, wird in
Abb. 1.10 illustriert.
1.3.1
Bidirektionale Reflexivität
Die einfallende Beleuchtungsstärke Ei = Ii cosθi dωi = Ii (N ·L)dωi wird mit einem Faktor ρ gewichtet zur abstrahlenden Strahldichte Ir = ρIi (N · L)dωi . Dieser Faktor ρ = EIri wird als bidirektionale
Reflexivität bezeichnet. Dabei hat ρ = kd ρd + ks ρs mit kd + ks = 1 einen diffusen und einen spiegelnden Anteil. Das ambiente Umgebungslicht wird ebenfalls aus dem gesamten einfallenden Licht
berechnet. Daraus ergibt sich
1.3. COOK & TORRANCE MODELL
Ir = ρa Ia +
5
X
Iij (N · Lj )dωij [kd ρd + ks ρs ]
1≤j≤n
In diese von Cook und Torrance angegebene Formel geht der Einfallswinkel (φi , θi ) jeder Lichtquelle
Lj ein. Sofern in der bidirektionalen Reflexivität ρ anisotrope Oberflächen modelliert werden, trägt
auch der Ausfallswinkel (φr , θr ) zur Veränderung der abstrahlenden Strahldichte Ir bei. Daher ist
diese Gleichung eine vierdimensionale sogenannte BRDF.
Abbildung 1.3. Geometrie von einfallenden und reflektierten Elementarstrahlen auf der Oberflächeneinheit dA .
Mit der Bidirectional Reflectance Distribution Function (BRDF) bezeichnet man allgemein die Modellierung, bei der die einfallende Energiemenge und die abstrahlende Intensität in einen funktionalen
Zusammenhang gesetzt werden. Symbolisch notiert man die BRDF als fr
fr (θi , φi ; θr , φr ) ≡
dLr (θi , φi ; θr , φr ; Ei )
dEi (θi , φi )
6
wobei θ und φ zusammen eine Richtung, der tiefgestellte Index i die Größen für den einfallenden
Strahlungsfluss, der tiefgestellte Index r die Größen für den reflektierten Strahlungsfluss bezeichnen.
Ei ist die Bestrahlungsstärke (oder einfallende Strahlungsintensität), Lr ist die reflektierte Strahlung
(Remission). Mit d wird das Differential bezeichnet.
Damit ist eine BRDF eine Verteilungsfunktion, die die Bestrahlungsstärke aus einer bestimmten Richtung und ihren Anteil an der Remission in eine andere Richtung in Beziehung setzt. Diese Funktion
wird in der reziproken SI-Einheit Steradiant gemessen, [sr−1 ]. Zur Erinnerung: Mit Radiant [rad] bezeichnet man den ebenen Winkel, bei dem ein Vollkreis = 2π [rad] sind, mit Steradiant [sr] bezeichnet
man den Raumwinkel, bei dem eine volle Sphäre = 4π [sr] sind.
Für den ganz allgemeinen Fall betrachtet man auch die in das Material eindringende Strahlung und
modelliert das Streuen aus tieferen Schichten (subsurface scattering). Diese Funktion ist entsprechend
höherdimensional und wird mit BSSRDF bezeichnet. Für unsere Zwecke reicht aber zunächst ein
verbessertes Oberflächenmodell, um den spekularen Anteil ρs an der bidirektionalen Reflexivität zu
modellieren.
ρs =
F DG
π(N · V )(N · L)
(1.1)
Dieser Anteil setzt sich aus dem Fresnelterm F , einer Verteilungsfunktion D und einer geometrischen
Abschwächung G zusammen, wobei eine Wichtung mit den Proportionalitätsfaktoren (N · V ) (Was
sieht der Betrachter von der Oberfläche?) und (N · L) (Was sieht“ das Licht von der Oberfläche?)
”
sowie π (Maß für die Hemisphäre) vorgenommen wird.
1.3.2
Distributionsfunktion des Mikrofacettenmodells
Torrance and Sparrow haben 1967 ein verbessertes Oberflächenmodell, das sogenannte Mikrofacettenmodell vorgestellt, das von Cook und Torrance schließlich in das Lichtmodell integriert wurde.
Dabei wird angenommen, dass die Oberfläche eines glatt erscheinenden, matten Objekts aus perfekt
spiegelnden Mikrofacetten zusammengesetzt ist. Eine Verteilungsfunktion D gibt dabei an, wie groß
der Anteil der Facetten ist, deren Normale um den Winkel β von der mittleren Normale der Oberfläche
abweicht.
Torrance and Sparrow verwendeten eine einfache Gaußverteilung für den Anteil der in Betrachterrichtung reflektierenden Facetten:
D = k exp(−(β/m)2 )
Dabei ist β = arc cos (N · H) die mittlere Winkelabweichung von der mittleren Flächennormale
N bei einer mittleren Steigung von m. Hiermit wird also der Anteil der Mikrofacetten ermittelt,
7
Abbildung 1.4. Mikrofacettenmodell: Links auf Abstand betrachtet, in der Mitte ist die Spiegelung und damit
Streuung an den einzelnen Facetten skizziert, rechts die Verschattung durch V-förmige Kerben.
deren Normale genau in Betrachterrichtung V weist, also einer Normalen H entspricht. Die mittlere
Steigung m wird als root mean square (rms) bestimmt, d.h. als mittleres arithmetisches Mittel aller
quadrierten infinitesimal kleinen Steigungen, wobei aus diesem Term dann die Wurzel gezogen wird.
Somit ist m (ob gemessen oder abgeschätzt) ein Maß für die Rauigkeit der Oberfläche und m = 0
entspricht einem perfekt spiegelnden Objekt (wobei man dann keine Verteilungsfunktion braucht, da
hierfür die mittlere Normale gleich der eigentlichen Normalen ist. Zudem darf nicht durch 0 geteilt
werden!), m >> 0 einem matten Objekt. Eine geeignete Materialkonstante k kann experimentell
ermittelt und linear an das Modell angepasst werden.
Abbildung 1.5. Links Gaußverteilung und rechts Beckmannverteilung für oben m = 0.2 und unten m = 0.6
Beckmann schlägt dagegen eine verbesserte Modellierung vor, die im Cook-Torrance Modell benutzt
wird:
8
1
tan2 β
D=
exp − 2
.
4m2 cos4 β
m
Diese Beckmannverteilung kommt ohne eigene Materialkonstante aus, da ihr Vorfaktor bereits aus
den Parametern m und β berechnet wird, die die Oberflächenbeschaffenheit beschreiben.
Nicht jede Oberfläche hat Facetten von immer annähernd gleicher Größe, sondern zeigt auf jeder
Facette nochmal kleinskaligere Unterteilungen. Hierfür kann man ein sogenanntes Multiskalenmodell
anwenden:
D=
X
wj D(mj )
j
wobei mj die mittlere
P Steigung der j-ten Verteilung und wj eine Wichtung dieser j-ten Verteilung ist.
Es gilt natürlich wj = 1. Außerdem sollte eine isotrope Verteilung auf allen Skalen gelten. Wenn
verschiedene Skalen eine Vorzugsrichtung aufweisen, ist dieser Umstand von einer symmetrischen
Verteilungsfunktion nicht zu erfassen.
Abbildung 1.6. Mikrostrukturen können unterschiedliche Skalen aufweisen, die einander auch überlagern können.
1.3.3
Geometrische Abschwächung durch Mikrofacetten
Auch für die sogenannte geometrische Abschwächung ist die isotrope Verteilung der Mikrofacetten
vorausgesetzt. Unter der Annahme, dass diese Mikrofacetten V-förmige Kerben sind, die symmetrisch
zur mittleren Flächennormalen N verteilt sind, kann man sich drei Fälle vorstellen.
Abbildung 1.7.
a) Vollsicht
b) flacher Einblick
c) flacher Lichtwinkel
9
Im Fall a) hat der Betrachter V vollen Einblick auf alle Facetten und auch das Licht L scheint aus
einem Winkel auf die Fläche, der wenig von der mittleren Normalen N abweicht und erzeugt daher
keine Schatten. Meist ist das sogar für Betrachter- sowie Lichtwinkel von bis zu 70◦ der Fall. Sollte
aber der Betrachter wie in Fall b) sehr flach auf die Fläche blicken, kann ein Teil der Mikrofacetten
nicht eingesehen werden. Dieser Anteil b (blind) ist aus Symmetriegründen beim Vertauschen von V
und L auch genau der Bereich, der vom Licht nicht erreicht wird, wie in Fall c). Die geometrische
Abschwächung G wird also Werte zwischen G = 0 (totale Beschattung) und G = 1 (volle Einsicht)
annehmen müssen. Für die jeweiligen Fälle bedeutet das
Ga = 1
und
Gb = Gc = 1 −
l−b
b
=
,
l
l
wobei l die Länge der (eindimensionalen) Mikrofacette und b den aus Betrachter oder Lichtrichtung
verschatteten Bereich bezeichnet. Die geometrische Abschwächung ist dabei von der Größe und Steigung der Mikrofacetten unabhängig (ausführlich beschrieben von Blinn, 1977 [Bli77]). Diese Oberflächeneigenschaften sind bereits in die Verteilungsfunktion D eingegangen und auch vollständig
abgehandelt. Jetzt modelliert man
Gb =
2(N · H)(N · V )
(V · H)
Gc =
2(N · H)(N · L)
(L · H)
und entsprechend
und berücksichtigt, dass (L · H) = (V · H) per Definition des Halfway-Vektors H gilt. Dann lässt
sich für geometrische Abschwächung schließlich schreiben
2(N · H)(N · V ) 2(N · H)(N · L)
,
.
G = min 1,
(V · H)
(V · H)
1.3.4
Fresnelterm
Bisher wurde noch nicht modelliert, dass das Maximum des Highlights nicht mit der Reflektionsrichtung R übereinstimmt, dass also Intensität und auch Farbe des reflektierten Lichts von der Brechung
des Lichts an der Schichtgrenze abhängt. Ein Teil der Energie wird bei Lichtbrechung geschluckt, so
dass der reflektierte Teil mit geänderter Wellenlänge eine Intensitäts- und Farbverschiebung bedeutet.
Der französischen Physiker Auguste Jean Fresnel (1788 - 1827) entdeckte, dass die Brechung des
Lichts an Schichtgrenzen nur vom Einfallswinkel und nicht von der Dicke des Materials abhängt.
10
Abbildung 1.8. Profile mit gleicher Bündelung des Lichts: Fresnellinse (1) und glattes Profil (2). Rechts eine alte
Schiffslaterne mit Fresnel-Kugellinse.
Die Fresnellinse nutzt diese Tatsache und findet auch heute noch zur Bündelung von Licht ihre Verwendung beispielsweise in Leuchttürmen, Baulaternen oder als Folie auf Fensterscheiben, wobei eine
Lupenwirkung erzeugt wird.
6
N
@
I
@
@
@
L @
θi
@
optisch dünneres Medium
optisch dickeres Medium
@
@
A
A
A
θt AA
AAU
Abbildung 1.9. Lichtbrechung an einer Schichtgrenze
Das Brechungsgesetz an der Schichtgrenze zwischen Medium 1 und Medium 2 lautet:
η1 sin θ1 = η2 sin θ2
Der Fresnelterm F = F (θi , θt ) hängt nun vom Einfallswinkel des Lichts und vom Brechungswinkel
11
des Mediums ab. Damit ist dieser Term veranwortlich für das im Brechungswinkel geschluckte Licht
an einer spiegelnden Oberfläche.
1
F (θi , θt ) =
2
sin2 (θi − θt ) tan2 (θi − θt )
+
sin2 (θi + θt ) tan2 (θi + θt )
Durch Umformung des tan α = sin α/cos α ergibt sich
1 sin2 (θi − θt )
cos2 (θi + θt )
F (θi , θt ) =
1+
,
2 sin2 (θi + θt )
cos2 (θi − θt )
so dass dieser Ausdruck jetzt in üblicher Weise umgeschrieben werden kann. Fasst man nämlich F
θi cos θt
als
jetzt mit c = cos θi und g = sin sin
θ
t
1
F =
2
(g − c)2
(g + c)2
(c(g + c) − 1)2
1+
(c(g − c) + 1)2
(1.2)
auf, so ergibt sich g 2 = η 2 + cos2 θi − 1. Hierbei ist der Brechungsindex η zu bestimmen aus
ηt
sin θt = η sin θt = sin θi .
ηi
Das Medium Luft hat einen Wert ηi ≈ 1, so dass der Wert von
ηt
ηi
= η ≈ ηt ist.
Bemerkung 1.1 Für die Anwendung hier in der Computergraphik stellt sich der Winkel c = cos θi =
(L·H) dar, denn wir betrachten ideale Mikrofacetten, deren Spiegellicht ausschließlich in Betrachterrichtung reflektiert wird. Die Normale des Fresnelterms wird also durch die hypothetische Normale
H ersetzt.
Bemerkung 1.2 Der Fresnelterm bestimmt auch die Farbveränderung des Highlights als Funktion
dieser beiden Winkel, Einfallswinkel und Transmissionswinkel, und zwar über die Wellenlängenabhängigkeit des Brechungsindex η = ηλ .
Insgesamt erleichtert sich die Berechnung für extreme Einfallswinkel θi = 0 bzw. θi = π/2. Schreibt
man nämlich den Fresnelterm F = F (θi , ηλ ) wie in Gleichung (1.2) um, gilt für den normalen
Einfallswinkel θi = 0 (entlang der Normalen N , also für ein Headlight oder Kameralicht), dass
F = F (0, ηλ ) gerade
1
F (0, ηλ ) =
2
(ηλ − 1)2
(ηλ + 1)2
·2=
ηλ − 1
ηλ + 1
2
12
nämlich über c = 1 und g 2 = ηλ 2 + 1 − 1 , also g = ηλ ergibt. Achtung! Da bei normalem Einfallswinkel θi = θt = 0 ist, ergibt sich sin θi = sin θt = 0. Man darf g nicht direkt in Null auswerten, da
nicht nur der Zähler sondern auch der Nenner Null wird und man sonst durch Null teilt!
Jetzt kann man einen wellenlängenabhängigen Brechungsindex ηλ bestimmen und damit den Fresnelterm generell wellenlängenabhängig machen.
ηλ =
p
F0,λ
p
1 − F0,λ
1+
Damit ist die Abhängigkeit des Fresnelterms von der Wellenlänge Fλ = F (θi , ηλ ) aus der Gleichnug
für F bei θi = 0 bestimmbar.
Wenn das Licht die Oberfläche nur streift, also für den anderen Grenzfall θi = π/2, ergibt sich aus
Gleichung (1.2) mit c = 0, dass F (π/2, ηλ ) ≡ 1 gilt. Hier sieht man, dass der Fresnelterm für diesen
Winkel und sämtliche Materialien immer konstant 1 ist und sich damit neutral im spiegelnden Anteil
der bidirektionalen Reflexivität ρs verhält.
Abbildung 1.10. Links ohne, rechts mit Fresnelterm berechnete Reflexion (Quelle: Stephen H. Westin,
http://www.graphics.cornell.edu).
Die Vorgehensweise zur Bestimmung des Fresnelterms in Abhängigkeit von sämtlichen Wellenlängen
und allen möglichen Einfallswinkeln geschieht nun, indem man sich aus den Messgrößen für gegebene Materialien und einer für die RGB-Komponenten einzeln durchgeführten Interpolation die gesamte
Fläche berechnet.
Nun kann man den spiegelnden Anteil ρs an der Bidirektionalen Reflexivität ρ = EIri tatsächlich nicht
nur an einzelnen Punkten messen, was sehr diskontinuierliche Ergebnisse liefert, sondern mit der
Gleichung (1.1) modellieren.
13
Abbildung 1.11. Fresnelterm als Funktion von Einfallswinkel und Wellenlänge.
Bemerkung 1.3 Bei Streiflicht gilt F (π/2, ηλ ) ≡ 1. Damit wird die Farbe des Pixels genau die Farbe
der Lichtquelle erhalten.
Die Materialfarbe wird im RGB-System über die drei Farbkanäle angegeben. Ebenso verfährt man
mit der Farbe des Lichts. Nun machen wir die einzelnen Farbkanäle vom Einfallswinkel abhängig,
wobei wir die Werte bei 0 und π/2 bereits kennen oder messen können.
Red0
Redπ/2
für
für
θi = 0
θi = π/2
Rotkomponente des Materials
Rotkomponente des Lichts
Am Beispiel der Rotkomponente müssen wir also Red0 aus F0 , dem Spektrum des einfallenden Lichts
und den Farbfunktionen des CIE-Diagramms berechnen. Damit ergibt sich
Redθi = Red0 + (Redπ/2 − Red0 )
max(0, Fave,θi − Fave,0 )
Fave,π/2 − Fave,0
als eine lineare Interpolation zwischen dem Materialrot Red0 und dem Lichtrot Redπ/2 , bei der Fave,θi
einen über alle Wellenlängen gemittelten Fresnelterm meint.
Bemerkung 1.4 Ein spektralabhängiger Fresnelterm kann nicht als Summe dreier Farbkomponenten
wiedergegeben werden. Daher kommt es zu Ungenauigkeiten.
14
Abbildung 1.12. Kupferdarstellung im Comic: Asterix und der Kupferkessel.
Roy Hall dagegen schlägt vor, NICHT komponentenweise vorzugehen, sondern den Freselterm für
jede Wellenlänge zu bestimmen.
Fλ,θi = Fλ,0 + (1 − Fλ,0 )
max(0, Fave,θi − Fave,0 )
1 − Fave,0
Bemerkung 1.5 Bei anisotroper Oberfläche, z.B. gebürstete Metalloberflächen oder gekämmte Haare, liegen orientierte Mikrostrukturen vor, die nicht gleichmäßig zur Oberflächennormalen verteilt
sind. Hier kann man eine veränderte Normale benutzen, in die die Tangente an die Hauptstrukturrichtung eingeht.
Bemerkung 1.6 Der Fresnelterm gilt in dieser Form nur für unpolarisiertes Licht. Der Polarisationsgrad ändert sich, wenn Licht von einer Oberfläche mit Mikrostruktur reflektiert wird. Metalloberflächen polarisieren wellenlängenabhängig: Licht unterschiedlicher Wellenlänge wird unterschiedlich stark polarisiert.
1.4
Übungsaufgaben
Aufgabe 1.1 Transformationen über gluLookAt()
Schreiben Sie in OpenGL ein Programm, das ein Koordinatenkreuz mit Achsenbeschriftung und ein
beliebiges Objekt darstellt. Steuern Sie die Transformationen über Veränderungen des Befehls void
gluLookAt(GLdouble eyeX,.Y,.Z, GLdouble centerX,.Y,.Z, GLdouble upX,.Y,.Z). Machen Sie
diese Transformationen vom Drücken der linken Maustaste und dann der Bewegung der Maus in x-
1.4. ÜBUNGSAUFGABEN
15
oder y-Richtung abhängig. Legen Sie den Zoom auf die mittlere Maustaste, damit die rechte Maustaste
für eine Menüsteuerung mit einem Eintrag für Quit belegt werden kann.
Aufgabe 1.2 Gerichtete Lichtquelle
Stellen Sie in OpenGL eine gerichtete Lichtquelle als Objekt dar. Achten Sie dabei darauf, dass ein
konischer Lampenschirm sich entsprechend des eingestellten Winkels Ihres Lichts öffnet. Lassen Sie
dieses Licht auf ein möglichst fein unterteiltes Objekt scheinen, das eine metallische Materialeigenschaft trägt.
Abbildung 1.13. Schreibtischlampe mit Star-Charakter: Das Logo von Pixar.
Abbildung 1.14. Realer Nachbau des Logos für die Pixar Ausstellung in Melbourne, September 2007.
16
Aufgabe 1.3 Umformung des Fresnelterms
Der Fresnelterm F = F (θi , θt ) hängt vom Einfallswinkel des Lichts und vom Brechungswinkel des
Mediums ab.
1
F =
2
sin2 (θi − θt ) tan2 (θi − θt )
+
sin2 (θi + θt ) tan2 (θi + θt )
wird üblicherweise umgeschrieben zu
1 (g − c)2
F =
2 (g + c)2
(c(g + c) − 1)2
1+
(c(g − c) + 1)2
mit c = cos θi und g 2 = η 2 + cos2 θi − 1. Dadurch erleichtert sich die Berechnung für extreme
Einfallswinkel θi = 0 bzw. θi = π/2.
a) Führen Sie diese Umformung durch. Hinweis: Beachten Sie die Additionstheoreme für die Winkelfunktionen sowie den Zusammenhang zwischen dem Brechungsindex η und den entsprechenden
Winkeln, nämlich η sin θt = sin θi . Finden Sie einen wurzelfreien Ausdruck für g.
b) Zeigen Sie, wie sich F = F (0, θt ) und F = F (π/2, θt ) für alle Medien vereinfacht.
Kapitel 2
Graphikkarten Programmierung
Moderne Grafikkarten sind dafür ausgelegt, den Prozess des Renderings eines Bildes sehr schnell auszuführen, um in Echtzeit Animationen mit qualitativ möglichst hochwertigen Effekten zu berechnen.
Dabei resultiert der Geschwindigkeitsvorteil aus der einfach parallel zu bearbeitenden Bildberechnung, die auf die einzelnen Prozessoren einer GPU verteilt werden kann. Außerdem werden Vektoroperationen oder Matrix-Vektor-Produkte in einem einzigen Aufruf über sogenannte Packed arrays
berechnet. Diese Single Instruction Multiple Data (SIMD) Berechnungen sind eine Art Rückkehr des
Vektorrechners aus der Ecke der Hochleistungsrechner auf die Ebene der PC-Technologie. Früher
musste der Programmierer zu einer Assembler-Sprache greifen und den Code auf den eingesetzten
Grafikchip direkt anpassen, inzwischen gibt es dafür Hochsprachen (siehe [FK03]). Das macht es
wiederum interessant, auf der GPU auch Berechnungen vorzunehmen, die typischerweise parallelen Code auf der CPU erfordern, wie beispielsweise Filterverfahren der Bildverarbeitung, aber auch
einfache finite Differenzen für partielle Differentialgleichnungen, deren Ortsabhängigkeiten oder Geschwindigkeitsfelder in Texturen gespeichert und über Texturzugriffe neu berechnet werden können.
2.1
Shader Programmierung
Die Idee der Shader stammt aus den großen Studios für Animationsfilme. Ende der 80er Jahre wurde
bei Pixar für ihr Rendering-Interface Renderman eine eigene Shader-Sprache entwickelt. Die Anwendung beschränkte sich jedoch auf das relativ langsame Batch-Rendering einzelner Filmframes. Mit
einem Shader berechnen die Renderer für jeden Geometriepunkt respektive dargestellten Pixel das
Aussehen, statt nur statisch eine einzige Farbe oder Textur zu verwenden. Trotz einfacher Geometrie
erscheinen damit gerenderte Objekte mit komplexer Oberflächenstruktur. Diese Idee geht auf eine
frühe Arbeit von Robert Cook [Coo84] zurück, der den Ablauf des Shading in einer Baumstruktur
organisiert hat. In diese Bäume an unterschiedlichen Stufen eingreifen zu können, genügt ein rein
knotenbasierter Ansatz nicht. Auf der viel tiefer liegenden Ebene der Rasterung dagegen erzielt man
wie der Name schon sagt, das bessere Shading, die mit den Nachbarpunkten des Gitters abgestimm17
18
KAPITEL 2. GRAPHIKKARTEN PROGRAMMIERUNG
te Abstufung. Moderne Grafikkarten beherrschen diese Technologie in Echtzeit. Der Programmierer
lädt seinen Shader-Code in die GPU. Die Graphikkarte führt diesen Code während des Renderings
sehr schnell für jeden einzelnen Punkt aus. Dabei kann das Bild einfach parallel berechnet werden,
in dem es in Bereiche zerlegt und auf die einzelnen Prozessoren einer GPU verteilt wird. Im Renderprozess sind Vektoroperationen oder Matrix-Vektor-Produkte über Packed arrays auszuführen. Statt
in Assembler und für einen speziellen Grafikchipsatz kann die GPU heute in einer Hochsprache angesprochen werden. Die Besonderheit liegt darin, dass der Compiler den in einer solchen Sprache
abgefassten Shader in Code für die jeweilige GPU während der Ausführung übersetzt. Shader beschreiben keine Geometrien oder Objekte, das ist immer noch die Aufgabe von APIs wie OpenGL
oder Direct3D. Aber sie beeinflussen, wie die Grafikkarte Transformationen, Licht und Farben verarbeitet.
An dieser Stelle wird es nötig, den Begriff Fragment deutlich vom Pixel zu unterscheiden. Während
ein Pixel die kleinste Einheit auf dem Rasterschirm darstellt, umfasst das Fragment wesentlich mehr
Information und ist die abstraktere und von der anzusteuernden Hardware losgelöste Variante einer
kleinsten Rastereinheit. Mit an die Graphikprozessoren übergebenen Knoten (Vertices) und mit diesen
Fragmenten kann nun auf der Graphikkarte operiert werden, ohne dass die CPU in diesen Vorgang
eingreifen muss.
Zur Erinnerung: Buffer beinhalten gleichmäßig für alle Pixel des Graphikfensters (oder des Bildes
bei Offscreen-Rendering) gespeicherte Informationen. Sichtbar ist nur der (Front Left, Front Right)
Colorbuffer. Der Framebuffer ist die Vereinigung sämtlicher Buffer.
Definition 2.1 Ein Fragment ist in der Computergraphik der Begriff für sämtliche Daten, die benötigt
werden, um den Farbwert des Pixels im Colorbuffer zu erzeugen. Das beinhaltet (aber ist nicht beschränkt auf):
• Rasterposition
• z-Tiefe
• Interpolierte Attribute (Farbe, Texturkoordinaten , etc.)
• Einträge im Stencilbuffer
• Alphawerte
• Window ID
Man denke sich das Fragment als die Vereinigung alle Daten, die benötigt werden, um den Farbwert
des Pixels zu bestimmen, zusammen mit allen Daten, mit denen getestet wird, ob der Colorbuffer
überhaupt erreicht wird.
2.2. SHADE TREES
2.2
19
Shade trees
Um den Illuminationsprozess und Schattierungen zu modularisieren, hat man entsprechende Shader
implementiert. Der nächste Entwicklungsschritt betraf Entscheidungsbäume, um diese verschiedenen
Shader und Kombinationen in einem Programm benutzbar und zur Laufzeit entscheidbar einzusetzen.
Zum Beispiel stammt von Whitted (1982) die Idee eines Scanline Algorithmus, bei dem eine verkettete Liste einzelner Spans mit der Information (z-Werte, Normalen) an den jeweiligen Eckpunkten
assoziiert wird. Diese Idee konnte sich allerdings nicht gegen eine stärker objektorientierte Beschreibung durchsetzen, wie sie im Format des Renderman Interface Bytestream (RIB) festgehalten ist.
Definition 2.2 Ein Shade tree besitzt eine Baumstruktur, in deren Knoten Parameter der Kinderknoten eingehen und daraus Parameter für die darüberliegenden Elternknoten produzieren.
Die Parameter sind dabei Werte für einzelne Terme und Begriffe, die man aus Beleuchtungsmodellen kennt, z.B. der Spekularkoeffizient ks oder Oberflächennormalen. In den Knoten werden diese
Parameter aus darunterliegenden Halbbäumen gesammelt und weiter bearbeitet, um schließlich die
Farbgebung des Pixels zu erhalten. So werden z.B. Knoten als Spekularterm, Ambienter Term aber
auch Square root oder Mix-Knoten bezeichnet.
Abbildung 2.1. Shade tree für Kupfer, nach Robert L. Cook [Coo84].
Unterschiedliche Objekte können verschiedene Schattierungsbäume haben. Der Mix-Knoten erlaubt
das Mischen spezieller Shader für besondere Zwecke wie beispielsweise Holzmaserung.
Bemerkung 2.1 Außer Shade trees gibt es zur Modellierung von Licht sogenannte Light trees und
zur Modellierung von atmosphärischen Effekten entprechend Atmosphere trees.
20
Abbildung 2.2. Der mix-Knoten in einem Shade tree, nach Robert L. Cook [Coo84].
Lichter und ihre Parameter werden genau wie Objekte behandelt. Lichtberechnung und Streuung in
der Atmosphäre hängt vom Betrachterstandpunkt und der z-Tiefe ab.
Abbildung 2.3. Ein Light tree gibt die Lichtposition zurück, nach Robert L. Cook [Coo84].
Bemerkung 2.2 Häufig interessiert bei einem Highlight NICHT die Position der erzeugenden Lichtquelle sondern nur, WO es erscheint. Also möchte man ein Highlight positionieren und die Lichtrichtung als Ergebnis erhalten. Ein entsprechender Light tree ist in Abb. 2.3 gezeigt.
Beispiel 2.1 Ein benutzerseits definierter Shader kann die Welt aus der Sicht einer Biene (andere
Wahrnehmung der Spektralfarben) wiedergeben.
Beispiel 2.2 Relativitätsaspekte wie die spektrale Verzerrung bei Lichtgeschwindigkeit kann in einem
Shader implementiert werden. Dabei werden Projection trees nötig, die neben den Standardprojektionen wie paralleler und linear perspektivischer Projektion auch den gekrümmten Raum darstellen
können. Durch den Doppler Effekt entsteht eine Farbverschiebung, bei der sehr schnell unser übliches Farbspektrum rekalibriert werden muss, da ansonsten alle Farben, auf die man zufliegt, zu weiß
überstrahlen.
2.2. SHADE TREES
21
Abbildung 2.4. Tübingen, links: relativistisch verzerrt, rechts auch unter Berücksichtigung des Doppler Effekts
bei der Ausbreitung des Lichts. Bilder von Ute Kraus.
2.2.1
Reyes-Pipeline und Renderman Interface
Cook, Carpenter und Catmull gelten als die Urheber der sogenanten Reyes-Pipeline (siehe Abb. 2.5).
Die geographische Nähe der Lukasfilm Studios zu Point Reyes (siehe Abb. 2.6) hat dem Akronym aus
Renders everthing you ever saw sicherlich Vorschub geleistet.
Renderman greift diese Pipeline auf und speichert in sogenannten RIB-Files, dem Renderman Interface Bytestream die Punkte auf der Oberfläche eines Objekts, ihre Orientierung und die Lichtquellen
und übergibt diese einem Surface shader, der daraus Lichtfarbe und Lichtrichtung bestimmt. Wie
aus Abb. 2.5 hervorgeht, stellt das RIB-File die Eingabe für Programme wie beispielsweise 3Delight
dar, die Renderman Formate lesen und in Bilddaten ausgeben können. Renderman ist auf das (Nach-)
Bearbeiten einzelner Frames spezialisiert und beschränkt. Das Programm hat nicht den Anspruch,
Animationen zu erstellen, also zwischen einzelnen Bildern zu vermitteln.
2.2.2
Dicing oder Würfelalgorithmus
Ähnlich zu Catmulls Subdivision Algorithmus für Pixel werden beim Dicing alle Objekte in Mikropolygone zerlegt, deren Kantenlänge Subpixelgröße hat (Beispielsweise 1/2 Pixel).
(1) Dicing geschieht vor der perspektivischen Transformation, d.h. man schätzt die Größe der Mikropolygone aufgrund der anschließenden perspektivischen Transformation.
(2) Schattierung geschieht in Weltkoordinaten. Da alle quadrilateralen Polygone unter Pixelgröße
sind, kann mit einfachem Flatshading gearbeitet werden, das nur einen Farbwert für jedes Polygon
kennt.
(3) Das Bild wird in einzelne Rechtecke unterteilt, um nicht alle Gitter von Mikropolygonen und
Subpixelinformationen für das gesamte Bild sequenziell abarbeiten zu müssen. Auf diese Weise ist
22
Abbildung 2.5. Reyes-Pipeline.
der Algorithmus leicht parallelisierbar.
(4) Jedes Objekt wird mit der linken oberen Ecke seiner Bounding Box in das Rechteckgitter einsortiert. Die Bildbereiche werden nun von links nach rechts und von oben nach unten abgearbeitet.
Im Speicher muss nur die Information für einen Bildbereich gehalten werden, mit Ausnahme der
z-Werte, so dass die Speichertiefe des z-Buffers limitierend ist.
2.3
C for graphics
Mit der Programmbibliothek C for graphics (Cg) entstand 2002 ein verlässlicher Standard zur Ansteuerung der programmierbaren Teile eines Graphikprozessors. Bis dahin musste für jede Graphikkarte ein eigenes Interface zum Beispiel in Assembler geschrieben werden, was einerseits eine Hürde
für viele Programmierer darstellte und andererseits das Portieren der Anwenderprogramme extrem
schwierig machte.
2.3. C FOR GRAPHICS
23
Abbildung 2.6. Road to Point Reyes, eine Simulation aus Shade trees von Robert L. Cook [Coo84], und die Landkarte mit der entsprechenden Stelle.
Die Entwicklung von Cg wurde von Bill Mark bei NVIDIA in enger Kooperation mit Microsoft
betrieben, womit die beiden entscheidenden Plattformen für Graphikentwicklung, nämlich OpenGL
und Direct3D abgedeckt wurden. Über das Cg Tutorial von Fernando und Kilgard (siehe [FK03]),
das auf der SIGGRAPH 2003 zum Bestseller wurde, fand die Sprache rasche Verbreitung. Als rufende Programme sind Applikationen in beiden Graphikbibliotheken gleichermaßen möglich, und
Cg-Programme brauchen diesen APIs nicht angepasst werden. Dabei speist sich die Cg-Bibliothek
aus drei wesentlichen Quellen (siehe Abb. 2.7), nämlich der in der Graphikprogrammierung weit verbreiteten Programmiersprache C/C++, der aus der Reyes-Pipeline motivierten Shading Language und
den 3D APIs OpenGL und Direct3D.
Abbildung 2.7. Die Programmbibliothek C for graphics (Cg) speist sich aus drei Quellen.
24
Die folgende Skizze (Abb. 2.8) zeigt eine vereinfachte Graphikpipeline, über der man sich jede 3DApplikation oder ein Computerspiel denken kann, das mit OpenGL oder Direct3D Anweisungen auf
der CPU implementiert bleibt. Programmierbare Teile des Graphikprozessors sind der Vertex- (blau
hinterlegt) und der Fragmentprozessor (rot hinterlegt). Moderne Graphikkarten haben heute 16 bis 32
parallele Prozessoren in der Pixelpipeline, die das Rendering entsprechend beschleunigen.
OpenGL Anweisungen
?
Vertex-Verarbeitung
-
Rasterung
Transformationen
Licht- und Farbberechnung
-
Pixel-Verarbeitung
-
Framebuffer
Pixelbezogene
Farbberechnung
Abbildung 2.8. Vereinfachte OpenGL-Grafik-Pipeline. Die Teile, die sich bei neueren Grafikkarten frei programmieren lassen, sind farbig hinterlegt.
2.3.1
Cg - Historische Entwicklung
Die historische Entwicklung in der Zeitachse macht deutlich, wie sich seit den siebziger und speziell
in den achtziger Jahren parallele Stränge abzeichnen, die alle das gleiche Ziel hatten, nämlich ein
am Objekt orientiertes Bild schnell und in guter Qualität auf den Schirm bringen zu wollen (siehe
Abb. 2.9). Es wird ebenfalls deutlich, dass sich Standards nur dann durchsetzen, wenn sich eine kritische Firmenmasse auf diese Standards einlässt. Projekte wie NeXT sind über die Zeit eingestellt
worden.
2.3.2
Programmierbarer Vertex Prozessor
Untransformierte Knoten (Vertices) aus einem GPU-Frontend werden typischerweise als Vertex-IndexStream zu Graphikprimitiven zusammengestellt, um als Polygone, Linien und Punkte gerastert werden zu können. An dieser Stelle können die Knoten für eine optimale Darstellung transformiert
und neu geordnet werden. Dadurch ist dieser Teil grundsätzlich programmierbar geworden und lässt
natürlich auch eigene Programmierung zu, die vor allem zur Laufzeit interessant wird, wenn beispielsweise eine geänderte Transformation eine andere Dreieckszerlegung eines Polyeders erfordert.
2.3. C FOR GRAPHICS
25
Abbildung 2.9. Die historische Entwicklung im Überblick.
2.3.3
Programmierbarer Fragment Prozessor
Die schließlich gerasterten und für Interpolationen vortransformierten Fragmente sind über die Ortsangaben der Pixel (Pixel location stream) in der Pipeline auf dem Weg zum Colorbuffer. Im Fragmentprozessor erhalten sie ihre endgültige Schattierung häufig erst durch Texturen, die im Fall prozeduraler Texturen auch wieder notwendig während der Laufzeit anzupassen sind. Schon einfaches
Mipmapping setzt voraus, dass eine Entscheidung für die eine oder andere Textur von der Größe des
ankommenden Graphikprimitivs abhängt. Gerasterte vortransformierte Fragmente werden weiteren
Transformationen unterzogen: Bumpmapping und generelles Beeinflussen der Lichtmodelle ist auf
dieser Ebene leicht und vor allem schnell möglich.
2.3.4
CgFX Toolkit und Austauschformat
Ein standardisiertes Austauschformat zur Darstellung von Effekten setzt saubere Schnittstellen zu den
verschiedenen Graphikkarten voraus, die derzeit auf dem Markt erhältlich sind. Dann aber garantiert
26
Abbildung 2.10. Aufbau des programmierbaren Vertex Prozessors.
es auch die Verbreitung der nötigen Bibliotheken, die diesen Standard unterstützen. Je mehr große
Software-Pakete solche Austauschformate in ihren Code aufnehmen, um so stärker wird sich die
spezielle Implementierung verbreiten. Verlässlichkeit wird auf diese Weise propagiert.
Mit CgFX, einem Produkt von Microsoft und NVIDIA, wurde ein Austauschformat entwickelt, das
textbasiert, also lesbar und editierbar ist. Gebräuchliche Suffix ist *.fx.
CgFX geht in den folgenden Punkten über Cg hinaus:
1. Mechanismus für multiple Renderpfade
2. Beschreibung von nichtprogrammierbarem Renderstatus (Alpha-Test-Modus, Texturfilter)
3. Zusätzliche Annotation für Shaderparameter
Darüber hinaus wurde ein CgFX Toolkit zur Verfügung gestellt, das einen CgFX Compiler benötigt,
um zur Laufzeit ausführbare GPU Anweisungen zu erstellen. Auf dieser Basis sind Plugin-Module für
sogenanntes Digital Content Creation (DCC) möglich. Eine Beispieldatei ist am Ende dieses Kapi-
2.3. C FOR GRAPHICS
27
Abbildung 2.11. Aufbau des programmierbaren Fragment Prozessors.
tels in Abb. 2.14 dargestellt. Alle großen Animationsprogramme (Alias|Wavefront’s Maya, discreet’s
3dStudioMax und Softimage|XSI) unterstützen Cg über CgFX und DCC Applikationen.
2.3.5
Compiler und Bibliotheken
KEINE GPU kann ein Cg-Programm direkt ausführen. Es muss zunächst kompiliert werden. Dazu
wählt man ein 3D Programming Interface entweder in OpenGL (Prefix der Syntax: cgGL) oder
in Direct3D (Prefix der Syntax: cgD3D). Das dynamische Kompilieren (Kompilieren zur Laufzeit!)
wird über Cg-Bibliotheksaufrufe durchgeführt. Dazu besteht die Cg-Bibliothek aus (a) Cg-Runtime
instructions und (b) Cg-Compiler instructions.
Während ein C-Programm Dateien lesen und schreiben, über Standardschnittstellen mit dem Terminal
oder anderen Eingabeformen bedient werden, Graphiken anzeigen und über Netzwerk kommunizieren kann, geht das alles mit Cg nicht. Ein Cg-Programm kann NUR Positionen, Farben, Texturkoordinaten; Punktgrößen und uniforme Variablen entgegennehmen, Berechnungen durchführen und
Zahlenwerte zurückgeben.
Im Application Programming Interface (API) (siehe das OpenGL Beispiel 2.6) wird die nötige Headerdatei geladen.
28
Abbildung 2.12. Das CgFX-Austauschformat wird an den Cg-Kompiler übergeben.
#include <Cg/cg.h>
Diese Headerdatei wiederum lädt aus dem Standardpfad /usr/include/Cg die weiteren Header:
#include
#include
#include
#include
#include
<Cg/cg_bindlocations.h>
<Cg/cg_datatypes.h>
<Cg/cg_enums.h>
<Cg/cg_errors.h>
<Cg/cg_profiles.h>
Das Interface zu OpenGL wird mit
#include <Cg/cgGL.h>
geladen, indem bereits der Aufruf für cg.h enthalten ist. Also genügt der letzte Aufruf.
Die entsprechenden Bibliotheken stehen üblicherweise unter /usr/lib/libCg.so respektive
/usr/lib/libCgGL.so. Sie können mit den Kompilerflags -lCg beziehungsweise -lCgGL
geladen werden. Das Kompilieren der Shader zur Laufzeit geschieht über Bibliotheksaufrufe!
Eine Entry function definiert ein Cg-Vertex- oder Cg-Fragmentprogramm und ist ein Analogon zur
main function in C/C++. Da man aber viele solcher Entry functions in einem rufenden API haben
2.3. C FOR GRAPHICS
29
kann, sollte man sie nicht ebenfalls main nennen, um Verwirrungen vorzubeugen. Internal functions
sind Hilfsfunktionen, die von den Entry functions aufgerufen werden können. Das sind beispielsweise
von der Cg-Standardbibliothek zur Verfügung gestellte oder selbstgeschriebene Funktionen. Die Zeile
return OUT; gibt die initialsierte Output Struktur zurück (mit entsprechender Semantik, die den
einzelnen Komponenten zugeordnet ist).
Zum Kompilieren von Cg-Code muss zum einen der Name des Cg-Programms bekannt sein, zum
anderen muss der Profilname jeweils für Vertex- und Fragmentprofil gewählt werden. Da die Profile
abhängig von der Graphikkarte sind, sollte ein Profil gewählt werden, das nach Möglichkeit von allen
Graphikkarten unterstützt wird. Will man aber die Besonderheit eines speziellen Profils oder einfach
ein neueres Profil und seine Vorzüge ausnutzen, sollte eine Abfrage an die GPU geschehen, mit der
man das Vorhandensein entsprechender Möglichkeiten sicherstellt und wahlweise einfachen Cg-Code
für ältere Graphikkarten zur Verfügung stellt.
Cg-Vertexprofile:
arbvp1
vs 1 1
vs 2 x
OpenGL Basic multivendor programmibility ARB-vertex-profile
DirectX8 Vertex shader
DirectX9 Vertex shader
Cg-Fragmentprofile:
arbfp1
ps 1 1
ps 2 x
OpenGL Basic multivendor programmibility ARB-fragment-profile
DirectX8 Pixel shader
DirectX9 Pixel shader
2.3.6 Ähnlichkeit mit C
Cg liest sich einfach, wenn man mit C vertraut ist: Viele Keywords sind gleich oder erschließen sich
einfach aus ihrem Name (hier ein Auszug aus der alphabetischen Liste):
asm*, bool, break, · · · , pixelfragment*, · · · , while
!!!ACHTUNG: Sie sollten Keywords NIE als Identifier verwenden!!!
Auch Strukturen sind in gleicher Weise aufgebaut wie in C. Dem Keyword struct folgt ein Identifier mit dem Namen und in geschweiften Klammern die Liste der Variablen. Handelt es sich dabei
aber um eine IN- oder OUT-Struktur, wird jede Komponente um eine sogenannte Semantik erweitert.
30
2.3.7
Besonderheiten
Besonderheiten 1: Semantik Über die Semantik wird der Input oder das Ergebnis eines Cg-Programms an der richtigen Stelle in die Graphikpipeline eingegliedert. Die Semantik wird hinter einem
Doppelpunkt und in Großbuchstaben hinter einem Membernamen angefügt und mit einem Komma
vom nächsten Member getrennt. POSITION, COLOR, TEXCOORD0, PSIZE, NORMAL sind
mögliche Semantiken. Die Semantik POSITION hängt entscheidend davon ab, ob sie über ein Vertexoder ein Fragmentprofil in die Graphikpipeline eingefügt werden soll, denn eine Knotenposition
wird anders interpretiert, als eine Rasterposition. Texturkoordinaten werden mit angehängter Ziffer
einem Texturkoordinatensatz zugeordnet, da man häufig mehrere Texturzugriffe in einem Programm
ermöglichen möchte. Und schließlich will man mit PSIZE die sogenannten Partikelsysteme ebenfalls
hardwarenah steuern können.
Exkurs Partikelsysteme
Partikelsysteme stellen eine Möglichkeit dar, ein sprühendes oder fließendes Objekt und seine Materialeigenschaft über einzelne, nicht verbundene Punkte zu modellieren. Dabei berechnet man Trajektorien dieser Partikel nach (einfachen) physikalischen Gesetzen und modelliert graphisch die Darstellung dieser einzelnen Punkte, in dem man beispielsweise die Punktgröße mit der Zeit variiert. Bessere
Effekte erzielt man mit sogenannten Point sprites, kleinen meist quadratischen Texturen, die automatisch senkrecht zur Blickrichtung ausgerichtet werden und deren Mittelpunkt mit der Punktposition
übereinstimmt. Die üblichen Texturkoordinaten (typischerweise laufen uv-Koordinaten in den Intervallen [0,1]x[0,1]) werden ebenfalls automatisch an das entsprechende Quadrat mit der angegebenen
Punktgröße angepasst.
Mit Partikelsystemen kann man beispielsweise Feuerwerk, Spritzwasser, Springbrunnen, Wasserfälle,
aber auch semitransparente Objekte wie Flammen oder Rauch ansprechend und einfach darstellen.
Beispiel 2.3 Mit der einfachen Gleichung
1
Pfinal = Pinitial + vt + at2
2
wird eine Vorwärtsintegration eines Anfangswertproblems beschrieben. Wählt man für jedes Partikel eine zufällige Anfangsgeschwindigkeit v bei konstanter (Erd-)Beschleunigung a, kann man die
Punktgröße und Farbe mit der Zeit t variieren.
Besonderheiten 2: Vektoren Auf der Graphikhardware werden immer wieder Vektoroperationen
benötigt, die mit Rasterkoordinaten, Farben oder homogenen Raumkoordinaten umgehen und daher
typische Vektorlängen von zwei, drei oder vier haben. Daher liegt es nahe, diese Operationen in der
Hardware abzubilden und die Graphikleistung auf diese Weise zu beschleunigen. Will man diese
Graphikleistung optimal ansteuern, muss auch der Compiler entsprechende Datentypen kennen, was
2.3. C FOR GRAPHICS
31
Abbildung 2.13. Zwei Partikelsysteme mit Point sprites, die eine Flamme und einen Wasserstrahl mit entsprechend
unterschiedlichem Gravitationsverhalten darstellen. Bild von Daniel Jungblut.
in der Hochsprache C/C++ nicht der Fall ist. Cg dagegen kennt die Datentypen float2, float3,
float4 beziehungsweise entsprechende Vektoren, die mit den Standardnamen anderer Datentypen
und den Ziffern 2, 3 und 4 gebildet werden. Sie sind NICHT äquivalent mit einem Array derselben
Länge in C/C++, da die Vektoren als sogenannte Packed arrays gespeichert werden.
float x[4] 6= float4 x
Vektoren sind KEINE Keywords der Programmiersprache, könnten also als Identifier verwendet werden. Man sollte es aber vermeiden, um Verwirrungen vorzubeugen.
Bemerkung 2.3 Wenn zwei Input-Vektoren als packed arrays gespeichert sind, können typische vektorwertige Operationen (skalare Multiplikation, Addition, Negation, Skalarprodukt, Kreuzprodukt,
Vertauschen von Indizes) in einer einzigen Instruktion berechnet werden. Packed arrays helfen dem
Cg-Compiler, die schnellen Vektoroperationen der programmierbaren GPUs auszunutzen. Die GPU
ist ein Vektorrechner.
Außerdem sollte man beachten, dass man auf die einzelnen Einträge eines Vektors sehr effizient mit
der Ziffer des entsprechenden Index zugreift. Dagegen ist ein Zugriff über eine Referenz, die erst
ausgewertet werden muss, ineffizient oder sogar unmöglich.
float4 x = {1.0, 0.0, 1.0, 1.0};
// Initialisieren wie in C
32
int index = 3;
float scalar;
scalar = x[3];
// Effizienter Zugriff, scalar = 1.0;
scalar = x[index];
// Ineffizient oder unmoeglich!
Besonderheiten 3: Matrizen Da die GPU natürlich auch Matrix-Vektor-Operationen hardwarenah
unterstützen muss, liegt es nahe, dass es in Cg dafür entsprechende Matrizen gibt. Hier einige Beispiele:
float4x4
16 Elemente 32 bit
half3x2
6 Elemente 16 bit
Effizienter Datentyp für Fragmentoperationen
fixed2x4
8 Elemente 32 bit, [-2.0, 2.0 [ Effizient für exp2-Auswertung (Fog)
double4x4 16 Elemente 64 bit
Die sechs Elemente von half3x2 entsprechen einer Matrix mit drei Reihen und zwei Spalten. Matrizen sind für alle besonderen Datentypen der GPU verwendbar, die im nächsten Paragraphen kurz
vorgestellt werden.
Besonderheiten 4: Datentypen Neu hinzugekommene Datentypen auf der GPU sind half und
fixed. Mit half haben insbesondere alle Fragmentoperationen geringeren Speicherbedarf und laufen schneller ab, ohne dass man beispielsweise bei Farbinterpolationen einen sichtbaren Unterschied
zur vollen Darstellung in float oder gar double ausmachen kann. Der Datentyp fixed dagegen verfolgt als Festkommazahl eine andere Philosophie, nämlich mit dem gleichen Speicherbedarf
eines float eine größere Genauigkeit im Bereich von [-2.0, 2.0 [ zu garantieren, also in einem Intervall, das bei Operationen mit den Einträgen zweier Vektoren der Länge Eins maximal auftreten kann.
Dieser Datentyp ist sehr effizient für exp2-Auswertungen, die beispielsweise für atmosphärische Effekte wie Nebel (Fog) gebraucht werden (plötzliches Erscheinen von Objekten in Abhängigkeit ihrer
z-Tiefe).
Besonderheiten 5: Konstruktoren Man kann alle diese Datentypen samt angehängter Ziffern wie
Funktionen benutzen, also eine beliebige Zahlenfolge in einen Vektor oder eine Matrix packen. Sie
sind damit sogenannte Konstruktoren.
float4(1, 0, 1, 1); // erzeugt einen Vektor (Packed array)
Besonderheiten 6: Qualifier uniform Mit dem Qualifier uniform wird deutlich gemacht, dass
eine Variable aus einem externen Programm, also üblicherweise einem OpenGL oder Direct3D API,
2.3. C FOR GRAPHICS
33
an das Cg-Programm übergeben wird. Anders als in Renderman darf ein als uniform übergebener Parameter durchaus auf der GPU verändert werden. In Cg wird nicht zwischen uniform und
einem nur in Renderman bekannten Qualifier varying unterschieden. Ein mit uniform übergebener Parameter wird als Variable behandelt. Wenn eine Variable nicht initialisiert wurde, kann das in
der Entry function immer noch geschehen und dabei auch mit einer Semantik versehen werden, die
beispielsweise für die Ausgabe dieses Cg-Programms benötigt wird.
Besonderheiten 7: Swizzling Eine syntaktische Besonderheit stellt das Swizzling dar. Damit ist
der Zugriff auf die Komponenten von Vektoren oder Matrizen in beliebiger Reihenfolge möglich.
Zunächst können die Komponenten entsprechender Vektoren float4 position, color; über
die folgende Konvention aufgerufen und zugewiesen werden (wenn kein w angegeben wird, ist implizit w = 1):
float3 P = position.xyz;
float4 Q = position.xyzw;
float4 C = color.rgba;
Beide Suffix Zeichenketten sind gültig, können aber nicht gemischt werden. Sie bezeichnen in natürlicher Weise die erste (r oder x), zweite (g oder y), dritte (b oder z) und vierte (a oder w) Komponente.
Weder C noch C++ unterstützen das Swizzling, da keine der Sprachen Vektorrechnung unterstützt.
Beispiel 2.4 Dieses Beispiel zeigt, wie einfach mit der Syntax einzelne Komponenten eines Vektors
überschrieben werden können.
float4 vec1 = float4(4.0, -2.0, 5.0,
float2 vec2 = vec1.yx;
// vec2 =
float scalar = vec1.w;
// scalar
float3 vec3 = scalar.xxx; // vec3 =
vec1.xw = vec2;
// vec1 =
3.0); // float4 als Konstruktor
(-2.0, 4.0)
= 3.0
(3.0, 3.0, 3.0)
(-2.0,-2.0, 5.0, 4.0)
Beispiel 2.5 Gleiches gilt für Matrizen mit der Notation *. m<row><column>.
float4x4 myMatrix;
float
myScalar;
float4 myVec4;
myScalar = myMatrix._m32;
myVec4 = myMatrix._m00_m11_m22_m33
myVec4 = myMatrix[0]
// myMatrix[3][2]
// Diagonale
// erste Reihe der Matrix
34
2.3.8
Fehlerbehandlung
Bei den Cg-Compilerfehlern gibt es einerseits die konventionellen Fehler wie inkorrekte Syntax
(Tippfehler) oder inkorrekte Semantik (falsche Anzahl der Parameter). Derartige Fehler treten bereits beim Vorkompilieren zu Tage, man kennt diese Art Fehler aus C/C++. Es empfiehlt sich, eine
Fehlerfunktion im OpenGL oder Direct3D API zur Verfügung zustellen, wie in Beispiel 2.6 geschehen. Syntaktische Fehler werden mit der entsprechenden Stelle aus dem API sowie dem Kontext des
Cg-Programms an das Terminal ausgegeben.
Eine zweite Art der Fehler ist neu: der profilabhängige Fehler. Das ausgewählte Vertex- oder Fragmentprofil unterstützt die (an sich korrekten) Aufrufe nicht. Hierbei unterscheidet man nun drei verschiedene Arten solcher profilabhängiger ERROR:
(a) Capability. Ein Beispiel: Bisher (2003) wird vom Vertexprofil kein Texturzugriff erlaubt, in Zukunft wird sich das ändern. Cg kann das heute schon kompilieren, aber die Hardware oder das 3D
API kann es nicht umsetzen.
(b) Context. Ein Beispiel: Ein Vertexprogramm muss die Semantik POSITION zurückgeben, sonst
entsteht ein Fehler. Dagegen kann ein Fragmentprofil keine entsprechende Vertexposition zurückgeben, weil das in den Fluss der Graphikpipeline nicht passt.
(c) Capacity. Ein Beispiel: Einige GPUs erlauben nur vier Texturzugriffe in einem Renderpfad,
bei anderen ist der Zugriff unbeschränkt. Diese Art Fehler ist schwierig zu finden, da die Anzahl
der Zugriffe oft nicht klar ersichtlich ist (vergleichbar mit einem Segmentation Fault in der CPUProgrammierung).
Beispiel 2.6 Ein in OpenGL geschriebenes API stellt die auf der CPU zu kompilierenden Programmteile vor. Zum besseren Überblick sind die Teile des Codes blau gefärbt, die grundsätzlich nötig sind
oder sich auf den programmierbaren Vertexprozessor beziehen. Dagegen sind die Teile mit Bezug auf
den programmierbaren Fragmentprozessor in rot hervorgehoben. Die Übergabe von Parametern ist
grün dargestellt.
/*
Open-GL program using Cg for programming a simple vertex-shader
by Daniel Jungblut, IWR Heidelberg, February 2008
based on example code of Cg Tutorial (Addison-Wesley, ISBN 0321194969)
by Randima Fernando and Mark J. Kilgard.
*/
#include <cstdlib>
#include <stdio.h>
#include <GL/glut.h>
#include <Cg/cg.h>
#include <Cg/cgGL.h>
static CGcontext
static CGprofile
static CGprogram
cg_context;
cg_vertex_profile;
cg_vertex_program;
2.3. C FOR GRAPHICS
static CGprofile
static CGprogram
35
cg_fragment_profile;
cg_fragment_program;
static CGparameter cg_parameter_vertex_scale_factor;
static CGparameter cg_parameter_vertex_rotation;
static CGparameter cg_parameter_fragment_color;
// Error checking routine for Cg:
static void checkForCgError(const char *situation) {
CGerror error;
const char *string = cgGetLastErrorString(&error);
if (error != CG_NO_ERROR) {
printf("%s: %s\n", situation, string);
if (error == CG_COMPILER_ERROR) {
printf("%s\n", cgGetLastListing(cg_context));
}
exit(1);
}
}
// keyboard callback:
void keyboard(unsigned char key, int x, int y) {
switch (key) {
case 27: // Escape
case ’q’:
cgDestroyProgram(cg_vertex_program);
cgDestroyProgram(cg_fragment_program);
cgDestroyContext(cg_context);
exit(0);
break;
}
}
// display function:
void display() {
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
cgGLBindProgram(cg_vertex_program);
checkForCgError("binding vertex program");
cgGLEnableProfile(cg_vertex_profile);
checkForCgError("enabling vertex profile");
// Hier werden die Werte der einheitlichen Parameter "scale_factor", "vertex_rotation" festgesetzt:
cgGLSetParameter1f(cg_parameter_vertex_scale_factor, 0.7);
cgGLSetParameter1f(cg_parameter_vertex_rotation, 1.509);
cgGLBindProgram(cg_fragment_program);
checkForCgError("binding fragment program");
cgGLEnableProfile(cg_fragment_profile);
checkForCgError("enabling fragment profile");
GLfloat color[] = {0.2, 0.7, 0.3};
cgGLSetParameter3fv(cg_parameter_fragment_color, color);
// Rendern eines Dreiecks. Hierfuer wurde keine Farbe ausgewaehlt!
glBegin(GL_TRIANGLES);
glVertex2f(-0.8, 0.8);
glVertex2f(0.8, 0.8);
glVertex2f(0.0, -0.8);
glEnd();
cgGLDisableProfile(cg_vertex_profile);
checkForCgError("disabling vertex profile");
cgGLDisableProfile(cg_fragment_profile);
checkForCgError("disabling fragment profile");
36
glutSwapBuffers();
}
int main(int argc, char **argv) {
glutInitWindowSize(400, 400);
glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE);
glutInit(&argc, argv);
glutCreateWindow("Vertex and fragment shaders");
glutDisplayFunc(display);
glutKeyboardFunc(keyboard);
glClearColor(0.1, 0.2, 0.8, 1.0);
cg_context = cgCreateContext();
checkForCgError("creating context");
cg_vertex_profile = cgGLGetLatestProfile(CG_GL_VERTEX);
cgGLSetOptimalOptions(cg_vertex_profile);
checkForCgError("selecting vertex profile");
cg_vertex_program = cgCreateProgramFromFile(cg_context, CG_SOURCE,
"E6_vertex.cg", cg_vertex_profile, "more_complex_vertex_shader", NULL);
checkForCgError("creating vertex program from file");
cgGLLoadProgram(cg_vertex_program);
checkForCgError("loading vertex program");
// Verbinden der Variable "cg_parameter_vertex_scale_factor"
// mit der Variable "scale_factor" aus dem Vertex-Shader:
cg_parameter_vertex_scale_factor = cgGetNamedParameter(cg_vertex_program, "scale_factor");
checkForCgError("getting scale_factor parameter");
cg_parameter_vertex_rotation = cgGetNamedParameter(cg_vertex_program, "rotation");
cg_fragment_profile = cgGLGetLatestProfile(CG_GL_FRAGMENT);
checkForCgError("selecting fragment profile");
cg_fragment_program = cgCreateProgramFromFile(cg_context, CG_SOURCE,
"E6_fragment.cg", cg_fragment_profile, "simple_fragment_shader", NULL);
checkForCgError("creating fragment program from file");
cgGLLoadProgram(cg_fragment_program);
checkForCgError("loading fragment program");
cg_parameter_fragment_color = cgGetNamedParameter(cg_fragment_program, "color");
checkForCgError("getting fragment parameter color");
glutMainLoop();
return 0;
}
Beispiel 2.7 Passend zum vorhergehenden Beispiel ist hier ein Cg-Vertexprogramm aufgeführt.
/*
More complex vertex shader
by Daniel Jungblut, IWR Heidelberg, February 2008.
*/
void more_complex_vertex_shader(float4 position : POSITION,
out float4 out_position : POSITION,
uniform float scale_factor,
uniform float rotation) {
2.3. C FOR GRAPHICS
37
// Erzeugung der 2D-Skalierungsmatrix:
float2x2 scale_matrix = float2x2(scale_factor, 0.0, 0.0, scale_factor);
float sin_rot, cos_rot;
sincos(rotation, sin_rot, cos_rot);
float2x2 rotation_matrix = float2x2(cos_rot, -sin_rot, sin_rot, cos_rot);
// Transfomieren der Vertices mit Hilfe der Skalierungsmatrix:
out_position = float4(mul(scale_matrix, mul(rotation_matrix, position.xy)), 0, 1);
}
Beispiel 2.8 Ebenfalls zum vorhergehenden Beispiel passend ist hier ein ganz einfaches Cg-Fragmentprogramm aufgeführt.
/*
Simple fragment shader
by Daniel Jungblut, IWR Heidelberg, February 2008.
*/
void simple_fragment_shader(out float4 out_color : COLOR, uniform float3 color) {
out_color = float4(color, 1.0);
}
2.3.9
Parameter, Texturen und mathematische Ausdrücke
Mit dem Qualifier uniform werden Parameter eines externen Programms an das Cg-Programm
übergeben. Wenn eine Variable NICHT initialisiert wurde, kann das in der Entry function geschehen.
Hier können auch mit dem Qualifier const nicht veränderbare Konstanten gesetzt werden.
const float pi = 3.14159;
// NICHT veraenderbar!!!
pi = 4.0;
// NICHT erlaubt!
float a = pi++;
// NICHT erlaubt!
Texture sampler werden uniform übergeben, d.h. sie treten als Teil einer Eingabe an den Fragmentprozessor auf.
uniform sampler2D decal
// Teil einer IN-Struktur
Um auf eine Textur zuzugreifen, gibt es Standard Cg Funktionen, die den Namen der uniform übergebenen Textur mit den Texturkoordinaten versieht und als Farbe zurückgibt.
38
OUT.color = tex2d(decal, texCoord);
Folgende Texture sampler sind möglich:
Sampler Typ
Textur Typ
Anwendung
sampler1D
sampler2D
sampler3D
samplerCUBE
samplerRECT
Eindimensionale Textur
Zweidimensionale Textur
Dreidimensionale Textur
Cube Map Textur
Non-Power-of-Two
Non-Mipmapped 2D-Textur
1D Funktion
Abziehbilder (Decal), Normalenfelder
Volumendaten, Dämpfungsterme
Environment Maps, Skybox
Videofilme, Fotos
Tabelle 2.1. Mögliche Texturaufrufe
Mathematische Ausdrücke können einerseits Operatoren sein, die auf der Graphikkarte immer auch
für Vektoren gelten. Wenn skalare Operationen mit Vektoroperationen gemischt werden, wird der skalare Wert automatisch so häufig wiederholt, bis er die Länge des Vektors erreicht. Dieses Verschmieren eines Skalars auf einen Vektor wird Smearing genannt und garantiert wieder die Geschwindigkeitsvorteile eines Vektorrechners.
Operator Art
+
*
/
Auswertung
Negation
Links nach rechts
Addition
Subtraktion
Multiplikation
Division
Tabelle 2.2. Ausnahmen der Auswertung (Rechts nach links) bei: ++, +=, sizeof, (type)
Beispiel 2.9 Hier werden einige typische Vektoroperationen vorgestellt.
float3 modulatedColor = color * float3(0.2, 0.4, 0.5);
modulatedColor *= 0.5;
float3 specular = float3(0.1, 0.0, 0.2);
modulatedColor += specular;
negatedColor = -modulatedColor;
float3 direction = positionA - positionB;
Sehr effizient implementiert und daher eigenen Routinen gleicher Funktion vorzuziehen sind die in
der folgenden (überhaupt nicht vollständigen) Tabelle gelisteten Funktionsaufrufe. ACHTUNG: Es
gibt in Cg KEINE IO-Routinen, KEINE String-Manipulationen und KEINE Speicherallokationen.
Prototyp
abs(x)
cos(x)
cross(v1, v2)
ddx(a)
ddy(a)
dot(a,b)
reflect(v,n)
normalize(v)
determinant(M)
mul(M,N)
mul(M,v)
mul(v,M)
tex2D(sampler,x)
tex3Dproj(sampler,
texCUBE(sampler,x)
39
Profil
Beschreibung
alle
Vertex, Adv. Fragment
Advanced Fragment
Advanced Fragment
alle
Fragment
Fragment
Fragment
Absolutwert von Skalar oder Vektor
Kreuzprodukt zweier Vektoren
Richtungsableitung nach x im Fragment a
Richtungsableitung nach y im Fragment a
Skalarprodukt
Reflexion von Vektor v bei Normale n
Normalisieren des Vektors v
Determinante der Matrix M
Matrizenprodukt
Matrix-Vektorprodukt
Vektor-Matrixprodukt
2D-Texturaufruf
Projektiver 3D Texturaufruf
CubeMap Texturaufruf
Tabelle 2.3. Standardisierte Funktionsaufrufe, sehr effiziente Implementierung
Das Function overloading wird von allen diesen Funktionen ebenfalls sehr effizient unterstützt. Damit
ist gemeint, dass man sich nicht um den speziellen Datentyp kümmern muss, der in eine der Funktionen eingeht: die Cg-Bibliothek sucht für jeden Datentyp die richtige Funktion aus. Das gilt auch für
Vektoren, so dass es beispielsweise für die Funktion abs(x) egal ist, ob x ein Skalar oder ein Vektor
ist.
2.4
Übungsaufgaben
Aufgabe 2.1 Einfacher Vertex Shader
Ändern Sie den in der Übung vorgestellten einfachen Vertex-Shader wie folgt: Verschieben Sie das
Dreieck um einen beliebigen Offset. Verwenden Sie hierzu die in Cg vorgesehenen Vektorvariablen.
Das Dreieck soll anschließend noch voll sichtbar sein. Verändern Sie die Farbe des Dreiecks. Finden
Sie eine Möglichkeit jedem der drei Eckpunkte des Dreiecks eine andere Farbe zu geben?
Wichtig: Ändern Sie hierfür nur den Shader ”E3.cg”, nicht jedoch die C++-Datei ”main.cpp”!
Das in der Übung vorgestellte Beispielprogramm finden Sie auch im Netz unter
www.iwr.uni-heidelberg.de/groups/ngg/CG2008/lecture.php.
Beantworten Sie folgende Fragen durch Kommentare im von Ihnen geänderten Shader: Warum muss
40
das Programm nicht neu compiliert werden, wenn man nur den Shader verändert? Worin unterscheidet sich der Übergabeparameter der Shader-Funktion ”simple vertex shader” von den Übergabeparametern, die Sie aus C oder C++ kennen? Warum ist das so? Der hier vorgestellte einfache VertexShader verändert die Koordinaten und die Farbe der einzelnen Vertices. Welche Attribute eines Vertex
kann ein Vertex-Shader noch verändern?
Aufgabe 2.2 Listen aufrufen
Programmieren Sie ein Moebiusband als Trianglestrip. Zeichnen Sie mehrere dieser Bänder, wobei
Sie in Ihrer Display-Routine das Band direkt aufrufen oder ein mit void glNewList(GLuint list,
Glenum mode) vorkompiliertes Band zeichnen lassen. Lassen Sie sich die Framerate beim Drehen
nacheinander für beide Varianten auf dem Bildschirm ausgeben. Das Umschalten sollte über die
Taste l geschehen. Wie verhält sich die Framerate?
Aufgabe 2.3 Fragment-Shader
Der Ausgangscode für diese Aufgabe ist unter
www.iwr.uni-heidelberg.de/groups/ngg/CG2008/lecture.php zu finden. Erweitern Sie den Fragment-Shader, so dass die Farbe der Fragmente durch einen einheitlichen Parameter
über das Hauptprogramm festzulegen ist. Drehen Sie das Dreieck mit Hilfe des Vertex-Shaders um
einen Winkel, der durch das Hauptprogramm gesteuert werden kann. Erklären Sie den Unterschied
zwischen variierenden und einheitlichen Parametern. Erklären Sie den Begriff call-by-result. Warum
werden in Cg genau Vektoren bis zur Dimension 4 unterstützt? Schreiben Sie die Antworten zu den
Fragen als Kommentare in einen der beiden Shader.
Hinweis: Im Gegensatz zu Aufgabe E03 sind zur erfolgreichen Bearbeitung dieser Aufgabe auch
Änderungen im Hauptprogramm nötig.
Aufgabe 2.4 Heat Equation
Berechnen Sie eine numerische Lösung der linearen Wärmeleitungsgleichung
∂ut = ∆u auf R+ × Ω
u(x, 0) = u0 auf Ω̄
u = 0 auf R+ × ∂Ω
im Zweidimensionalen. Ein semiimplizites Diskretisierungsschema für den Zeitschritt führt zu dem
Gleichungssystem
(1 − τ ∆h )uτ = Auτ = u0
41
wobei u0 die Wärmeverteilung zu Beginn und uτ die Wärmeverteilung zum Zeitpunkt τ beschreibt.
Diskretisiert man den Laplace-Operator mittels finiter Differenzen, so ergeben sich die Gleichungen
i−1,j
(1 + 4τ )ui,j
+ ui+1,j
+ uτi,j−1 + ui,j+1
) = ui,j
∀ i, j
0
τ − τ (uτ
τ
τ
in denen die Indizes i und j die Raumkoordinaten der einzelnen Gitterpunkte angeben. Das Gleichungssystem soll mit Hilfe des Jacobi-Verfahrens gelöst werden für das sich folgende Iterationsvorschrift ergibt
ui,j
neu =
1
i,j
+ ui,j+1
+ ui,j−1
+ ui+1,j
(τ (ui−1,j
alt ) + u0 ).
alt
alt
alt
(1 + 4τ )
Implementieren Sie dieses numerische Lösungsverfahren, wobei die einzelnen Iterationsschritte des
Jacobi-Verfahrens in einem Fragment-Shader berechnet werden. Gehen Sie dabei wie folgt vor:
(a) Laden Sie von der Vorlesungswebseite die Datei waves.png herunter. Schreiben Sie zunächst
ein OpenGL Programm mit zweidimensionalem Weltkoordinatensystem, so dass jeder Texel dieser
Textur genau auf einen Pixel des Ausgabefensters abgebildet wird. Setzen Sie die Texturfilter auf
GL NEAREST um Interpolationsfehler zu vermeiden. Die vorgegebene Textur ist ein Graustufenbild.
Da später mehr als ein Farbkanal benötigt wird, übertragen Sie die Textur im RGB-Format an die
Graphikkarte, wobei die drei Kanäle R, G und B jeweils mit dem Grauwert des entsprechenden Texels
initialisiert werden.
(b) Erweitern Sie dieses Programm um einen Fragment-Shader, der die Auswertung der Textur übernimmt.
(c) Implementieren Sie eine idle-Funktion, die mit Hilfe des Befehls glCopyTexSubImage2D(...)
den Inhalt des aktuellen Color-Buffer in die Textur kopiert und anschließend das Bild neu zeichnet.
(d) Nach hinreichend vielen Jacobi-Iterationen ist das Gleichungssystem näherungsweise gelöst.
Speichern Sie nach 120τ Aufrufen der idle-Funktion den aktuellen Inhalt des Color-Buffers in eine
Datei und beenden Sie das Programm. Der Color-Buffer kann mit der Funktion glReadPixels(...)
ausgelesen werden.
(e) Implementieren Sie zum Abschluss das Jacobi-Verfahren in Ihrem Fragment-Shader. Verwenden
Sie den Rot-Kanal zur Speicherung des Iterationsfortschritts und den Grün-Kanal zur Speicherung
der rechten Seite u0 des Gleichungssystems. Um die Pixel am Rand des Bildes korrekt zu verarbeiten,
genügt es die Wrapping-Parameter für die Texturkoordinaten auf GL CLAMP zu setzen.
42
(f) Wenden Sie das Programm für τ = 1, 2, 4, 8 auf das Ausgangsbild an und speichern Sie die
Ergebnisbilder gut erkennbar ab. Beschreiben Sie das Ergebnis dieses Verfahrens als Kommentar
in Ihrem Shader.
Abbildung 2.14. Das CgFX-Austauschformat, eine Beispieldatei.
43
44
Kapitel 3
Volume Rendering
Das Problem der graphischen Darstellung von Volumendaten gilt als zentrales Forschungsgebiet
der wissenschaftlichen Visualisierung. Immer mehr dreidimensionale Skalarfelder und Vektorfelder
aus Messungen (bildgebende Verfahren der Medizin wie Computertomographie und Magnetresonanzspektrskopie, seismische Untersuchungen, Georadar, Sonar) oder aus Simulationsrechnungen
(Strömungsmechanik, Atomphysik) sollen möglichst plastisch dargestellt werden. Neben der Konturflächenbestimmung (Isoflächen = Oberflächen mit gleichen skalaren Werten) werden heute in zunehmendem Maße direkte Volume Rendering Verfahren eingesetzt.
Abbildung 3.1. 3D-Computertomogrammdaten bestehen aus einzelnen Schichten von Röntgenbildern. Das Volumen wird am Rechner zusammengesetzt und visualisiert.
45
46
KAPITEL 3. VOLUME RENDERING
Obwohl Raytracing in der Computergraphik eine schon lange bekannte Idee ist, wird sie für das
Volume Rendering wiederentdeckt und dabei allerdings entscheidend abgewandelt. Die Strahlen, die
durch das Volumen geschickt werden, treffen in jedem Volumenelement (Voxel) des regelmäßigen
Gitters auf unterschiedliche skalare Werte, die als optische Dichten interpretiert werden. Die Bestimmung der Schnittpunkte ist hier also nicht das Problem, sondern die große Menge an Voxeln und ihre
Zuordnung zu Farb- und Lichteffekten.
Jedes Voxel liefert einen Beitrag zum endgültigen Bild, so dass auch tiefer liegende Schichten durch
Transparenz sichtbar gemacht werden. Dabei können durch die flexible Abbildung der Datenwerte
auf Farbe und Opazität unterschiedliche Strukturen und Phänomene sehr effizient visualisiert werden.
Betrachter
@
xB
s
s
s
s
s
s
s
s
s
s@
@ @
@
@
Bildebene
s
Abbildung 3.2. Entlang des Sichtstrahl werden die als optische Dichten interpretierten skalaren Werte der einzelnen Voxeln auf dem Weg durch das Volumen summiert.
Volumenvisualisierungsverfahren basieren heute fast ausschließlich auf den Näherungen des Absorptions-Emissions-Modells, das Streuung und Frequenzabhängigkeiten als unerwünschte Effekte in der
Strahlungstransportgleichung nicht berücksichtigt. Beim Rendering von Szenen mit volumetrischen
Objekten (z.B. Nebel, Wolken, etc.) sind diese Phänomene für eine realistische Darstellung jedoch
unverzichtbar.
Ziel des Verfahrens ist insbesondere bei medizinischen Daten wie 3D-Computertomogrammdaten
(CT-Daten, Intensitäten im voxelbasierten Raum), dass sie
• möglichst plastisch dargestellt
• in Echtzeit transformierbar
• animierbar
3.1. HERLEITUNG DER GLEICHUNG
47
sind. Erst dann können sie über die reine Operationsplanung hinaus auch in der minimalinvasiven
Chirurgie zur visuellen Unterstützung während des Eingriffs eingesetzt werden.
3.1
Herleitung der Gleichung
Die physikalische Modellvorstellung rührt von einem Lichstrahl her, der an einem semitransparenten
Medium in einem beschränkten Volumen streut. Der Photonenfluss erreicht dabei sofort ein Gleichgewicht, d. h. für ein beschränktes Volumen werden für die vorher bestimmten Richtungen zeitlich
konstante Bilder erzeugt.
L(r, ω)
Strahlungsdichte, Radiance
beschreibt die Energiedichte an einem bestimmten Punkt r pro Flächenelement in Flussrichtung [m2 ],
die in Richtung des Betrachters ω pro Winkeleinheit [sr] in MKS-Einheit [W/m2 sr].
3.1.1
Energieerhaltungsgleichung
Die Energieerhaltungsgleichung oder Transfergleichung in ihrer differentiellen Form lautet
Z
k(r, ω 0 → ω)L(r, ω 0 )dω 0
ω · ∇L(r, ω) = −φt (r)L(r, ω) + (r, ω) +
S2
und Anfangsbedingungen und Randbedingungen.
Die integrale Form
−τ (r,rB )
L(r, ω) = e
Z
LB (rB , ω) +
0
e−τ (r,r ) Q(r0 , ω)dr0
Γ(r,rB )
mit einem Auslöschungsterm entlang des Strahls von r bis s
Z
τ (r, s) ≡
φt (r0 )dr0 ,
Γ(r,rB )
der Strahlungsdichte am Rand LB und einem aus Emissions- und einem Streuanteil gewonnenen Term
Z
Q(r, ω) = (r, ω) +
k(r, ω 0 → ω)L(r, ω 0 )dω 0
S2
erhält man durch Umformung aus der differentiellen Form.
48
Bemerkung 3.1 e−τ (r,s) ist der integrierende Faktor, um die Differentialgleichung in die Integralgleichung umzuwandeln.
3.2
Vereinfachungen
Die folgenden Vereinfachungen führen zu einem schnellen Algorithmus, der allerdings nicht jeder
Anforderung genügen kann. Beispielsweise lässt sich keine Schattenwirkung erzeugen.
1. Einfache Streutiefe: Photonen werden nur einmal am Volumenelement gestreut, gehen in keine
Iteration ein.
2. Keine Absorption zwischen Lichtquelle und Streuereignis.
3. Isotrope Absorption
4. Einfache Randbedingungen: Endliche Zahl punktförmiger Lichtquellen im Inneren
Wegen der 1. und 2. Vereinfachung ist der Streukern k = 0. Somit besteht Q nur aus einem Emissionsterm, der integrale Anteil entfällt.
Hier ergibt sich die Frage, wie der Emissionsteil modelliert wird. In jedem Voxel wird ein lokales Illuminationsmodell verwendet, das eine Funktion des skalaren Werts (optische Dichte) und der Position
der Lichtquelle ist. Schattenwurf ist nicht in diesem Modell enthalten, denn dazu müßte Absorption
des Lichts beim Streuvorgang auf die nachfolgenden Voxel berücksichtigt werden (siehe 2. Vereinfachung).
Mit diesen Vereinfachungen kommt man zur Volume Rendering Gleichung
Z
L(x) =
xB
R x0
e
x
φt (x00 )dx00
(x0 )dx0
x
wobei x den Abstand auf dem Betrachterstrahl markiert und xB den Randpunkt beim Verlassen des
Volumens. Die Isotropieanahme sorgt für die einfachen Integrationsgrenzen, wegen der Lichtquellenannahme entfällt der Randoperator.
3.3
Einfacher Ray Casting Algorithmus
Parallel zum Volumen werden Strahlen in das Volumen hineinverfolgt und werten die Integralgleichung im Innern numerisch aus. Mit der Rechteckregel erhält man folgende Summe:
3.3. EINFACHER RAY CASTING ALGORITHMUS
L(x) =
=
n−1
X
i=0
n−1
X
i=0
e−
49
Pi−1
j=0
i ∆x
φt ∆x
i−1
Y
i ∆x
e−φj ∆x
j=0
mit
i ≡ (x + i∆x)
φi ≡ φt (x + i∆x)
wobei ∆x das Inkrement entlang des Strahls bezeichnet.
Definiere
αi ≡ 1 − e−φi ∆x
Ci ≡ (i /αi )∆x
ci ≡ Ci αi
als Durchsichtigkeit, Farbe und mit der Durchsichtigkeit gewichtete Farbe an der i-ten Position auf
dem Strahl.
L(x) =
n−1
X
i=0
ci
i−1
Y
αj
j=0
= c0 + c1 (1 − α0 ) + c2 (1 − α0 )(1 − α1 ) + · · · + cn−1 (1 − α0 ) · · · (1 − αn−2 )
= c0 over c1 over · · · over cn−1
Bemerkung 3.2 Der Operator over bezieht sich auf den Digital composing operator, wodurch sich
die Gleichung kompakter schreiben lässt.
Damit ergibt sich der folgende Algorithmus:
1. Für jeden Bildpunkt wird ein Strahl durch das Volumen verfolgt.
2. Farbwerte Ci und Dichtewerte αi werden in regelmäßigen (äquidistanten) Abständen entlang
des Strahls aufgrund der Probepunkte ermittelt.
50
3. Die Produkte werden zur Strahlungsdichte L(x) summiert.
Für ein kubisches Volumen mit Kantenlänge n werden n2 Strahlen mit n Probepunkten pro Strahl zu
O(n3 ) Operationen führen.
3.3.1
Klassifizierung und Transferfunktion
Der Ablauf der Visualisierung vom skalaren Feld geschieht über die Klassifizierung der Daten, die
Farbgebung und schließlich die Bildgenerierung. Eine gute Interaktion erlaubt dem Benutzer, auf
diese Schritte interaktiv Einfluss zu nehmen.
Abbildung 3.3. User Interface zur Segmentierung auf Basis der Dichtewerte und Gradientenlängen.
Klassifizierung heißt, jedem Voxel aufgrund des skalaren Feldes von 3D-Daten Transparenzen ai und
Farbwerte Ci zuzuordnen. Dies geschieht mittels einer Transferfunktion, die die Intensitäten, also
skalare Werte, in Farb- und Transparenzwerte umsetzt. Zusätzlich will man häufig mittels Segmentierung größere Bereiche zusammenfassen, die dann einen gleichmäßigen Farbwert bekommen. Eine
Segmentierung lässt zu, dass nur ein (oder zwei) dieser Segmente gezeigt werden, während man die
anderen völlig transparent darstellt und somit ausblendet. Diese Segmentierung nimmt man anhand
3.3. EINFACHER RAY CASTING ALGORITHMUS
51
Abbildung 3.4. Ergebnis der Segmentierung und anschließender Glättung der Oberfläche.
des Histogramms des skalaren Feldes vor, das heißt anhand der Verteilung der Häufigkeit einzelner Intensitäten in den Volumendaten. Segmentgrenzen wird man typischerweise in den Tälern des
Histogramms platzieren.
Ein anderes wichtiges Merkmal ist die Länge der Grauwert- oder Dichtegradienten. Hierüber erfährt
man, an welchen Stellen der steilste Abfall zu benachbarten Voxeln vorhanden ist. Auch hier ist eine
Segmentgrenze sinnvoll gesetzt. Zudem zeigt der Gradient bereits in die Richtung einer Normalen
an der Oberfläche dieses Segments. Möchte man später diese Konturfläche mit einem Lichtmodell
versehen, kann man auf diese vorberechneten Normalen zurückgreifen.
Bemerkung 3.3 Eine wesentliche Verkürzung der Volume-Rendering-Zeiten kann für Röntgenbildartige Darstellungen unter Ausnützung des Fourier-Projection-Slice-Theorems im Frequenzraum erzielt werden. Zur genauen Rekonstruktion benötigte Filter können mit biorthogonalen Wavelets realisiert werden. Das reduziert den Aufwand auf O(n2 logn) Operationen.
Bemerkung 3.4 Wenn Daten auf gekrümmten oder unstrukturierten Gittern vorliegen, wie es bei Simulationsrechnungen häufig der Fall ist, muss man sie auf reguläre (nicht notwendig äquidistante
Gitter) zurückführen, bevor man den Weg der Strahlen durch das Volumen berechnet. Es lohnt, diese
Interpolation permanent zu speichern, auch wenn dadurch viele Daten, die auf Rechengittern ausgegeben wurden, doppelt auf der Festplatte vorliegen.
52
Abbildung 3.5. Volumenbasierte Darstellung eines Schädels, links angeschnitten, rechts als vollständiger Datensatz
mit Transparenzen.
Beispiel 3.1 Die CT-Daten eines menschlichen Schädels können aufgrund charakteristischer Intensitäten und unter Ausnutzung von Kontinuitätseigenschaften auf Zusammenhangskomponenten in die
Segmente Haut, Knochen, Hirnmasse und Tumormasse segmentiert werden. In der Operationsplanungsphase können diese Segmente stark kontrastierend im selben Bild dargestellt werden bzw. ein
oder mehrere Segmente ausgeblendet sein. Mit entsprechenden Werkzeugen kann nun auch der Datensatz manipuliert, d.h. eine virtuelle Operation vorgenommen werden.
3.4
Beschleunigungen
3.4.1 Early Ray Termination – Abbruchkriterien
Durch frühzeitiges Abbrechen der Summation bei Erreichen eines Schwellwerts, der nahezu Undurchsichtigkeit garantiert, kann der Algorithmus, abhängig von den Materialeigenschaften, erheblich
beschleunigt werden. Dieses Vorgehen wird Early Ray Termination genannt und lässt sich einfach implementieren.
3.4.2
Ausnutzen kohärenter Strukturen
Meagher [Mea82] hat 1982 einen Algorithmus vorgeschlagen, der einen Octree-Suchalgorithmus
durch einen 2D-Quadtree ersetzt. Bei der Segmentierung kann dieser nutzbringend in die Strahlverfolgung eingebracht werden, um bei Eintritt eines Strahls in ein Segment die erforderlichen Summatio-
3.4. BESCHLEUNIGUNGEN
53
nen abzuschätzen (Greene 1993, [GKM93]). Allerdings führt die Wandlung von einem zum anderen
Suchalgorithmus zu einem erheblichen Overhead, der die gewonnene Beschleunigung innerhalb von
virtueller Realität nahezu kompensiert. Bessere Ergebnisse verspricht man sich durch das dauerhafte
Filtern entlang dreidimensionaler Strukturen. Damit ist das Glätten verrauschter Daten gemeint, die
dann den Segmentieralgorithmen zugänglicher sind.
3.4.3 Shear-Warp Faktorisierung
Der Scher-Verwerfungsalgorithmus wurde in Stanford von Lacroute [Lac95] entwickelt und beinhaltet drei nacheinander ausgeführte Schritte, das Scheren, Projizieren und anschließende Neigen des
Bildes auf die für den Betrachter wesentliche Bildebene (siehe Abbildung 3.6). Statt Sichtstrahlen
schräg durch das Volumen zu schicken, werden die an den Koordinatenachsen ausgerichteten Schichten der Volumendaten um einen entsprechenden Offset gegeneinander verschoben, also geschert. Nun
können die Strahlen die im Speicher benachbarten Werte sehr viel schneller addieren. Das anschließende Projizieren resultiert in einem verzerrten Zwischenbild, das auf die tatsächliche Bildebene geneigt werden muss.
Bei orthographischen Projektionsverfahren funktioniert dieser Algorithmus über einfaches Abbilden
der entsprechend verzerrten Zwischenbilder auf die drei dem Betrachter zugewandten Seitenflächen
eines achsenparallelen Quaders in den Proportionen der Volumendaten.
scheren
Sichtstrahlen
I
@
@
I
@
I
@
@
@ @
@
@ @
@ Geschichtete
@
@
@ Volumendaten
@ @
@
@
@
@
@
@
@
@
@
@
@
@
Bildebene
6
6
6
projizieren
?
@
@
@
R
@ @
@
@ @
@
@ @
@
@
@
neigen
Bildebene
Abbildung 3.6. Scherverwerfung nach Lacroute.
Will man Objekte in perspektivischer Projektion darstellen, muss die Verkürzung weiter entfernter
Schichtbilder schon beim Scheren berücksichtigt werden. Die nun aufsummierten Farbwerte ergeben
so geartete Projektionen (Zwischenbilder), dass sie beim Texture Mapping auf einen perspektivisch
erscheinenden Kubus wieder geeignet entzerrt werden. Für den Betrachter erscheint das im Kubus
verborgene Volumen jetzt unverzerrt.
54
xz-Ebene
Bild auf dem Schirm
xy-Ebene
yz-Ebene
Abbildung 3.7. Die einzelnen verzerrt berechneten Zwischenbilder werden auf die Außenflächen des kubischen
Volumens projiziert. Vor einem schwarzen Hintergrund erscheint das 3D-Objekt.
3.4.4
Texturbasiertes Volume Rendering
Ein gänzlich anderer Ansatz der Volumenvisualisierung besteht in der Berechnung vieler einzelner
Schichtbilder auf Basis einer Transferfunktion, die wie oben beschrieben Intensitäten, also skalare
Werte, in Farb- und Transparenzwerte umsetzt. Diese Bilder werden als Texturen einander überblendet und erzeugen dadurch ebenfalls einen halbtransparenten farbigen Eindruck eines Volumens, der
sehr schnell gerendert werden kann. Schaut man allerdings nahezu parallel zu den Schichten auf das
Volumen, sieht man kaum noch Farbwerte des Datensatzes sondern zwischen den Schichten hindurch
die Hintergrundfarbe. Abhilfe schafft hier ein Wechsel zu einem ebenfalls vorab berechneten Stapel
othogonaler Schichten. Beim Ändern der Blickrichtung wird dabei immer wieder nötig, zwischen
den verschiedenen Texturen zu wechseln bzw. zu überblenden. Dabei treten allerdings unerwünschte Diskontinuitäten auf. Auch ist mit diesem Ansatz nicht möglich, Konturflächen von Segmenten
darzustellen, da auf jegliche Verbindung zwischen den Schichtbildern verzichtet wird. Oberflächennormalen, die für lokale Lichtmodelle benötigt werden, lassen sich daher nicht berechnen.
3.5
Übungsaufgaben
Aufgabe 3.1 Volumenvisualisierunssoftware Vrend Auf der Homepage zur Vorlesung liegt das File
Vrend2.1 dummy.tar.gz, das Sie auf Ihrem Account mit tar -xvzf Vrend2.1 dummy.tar.gz entpacken. Starten Sie das Programm Vrend2.1/bin/vrend und laden Sie die Beispiele. Unter dem
Menüpunkt Segments finden Sie vorbereitete Materialklassen <filename.scl>. Mit dem Segments
editor lassen sie sich weiter bearbeiten. Die Apply Taste sorgt für eine neue Berechnung der Normalen an den Segmentgrenzen.
Das Beispiel Dummy enthält noch keine Segmentierung. Was verbirgt sich hinter dummy.dat? Weisen Sie den von Ihnen erzeugten Segmenten unterschiedliche Materialeigenschaften und Transparenzen zu. Sichern Sie Ihre Segmentierung in einer Datei, die Sie sinnvoll benennen. Machen Sie einen
55
Abbildung 3.8. Hans Holbein der Jüngere, Die Gesandten, 1533. Schaut man durch einen Schlitz im Rahmen an
der rechten Seite auf halber Höhe, erkennt man in dem Objekt im Vordergrund einen Schädel, das Symbol für
Vergänglichkeit. Solche perspektivischen Verzerrungen werden Anamorphismen genannt.
Screenshot von Ihrem segmentierten, farbigen Ergebnis (z.B. mit gimp > File> Acquire).
Alternativ finden Sie das Programm unter:
http://www.iwr.uni-heidelberg.de/groups/ngg/Vrend/
56
Kapitel 4
Radiosity
Anders als bei den lokalen Beleuchtungsverfahren, die jeweils immer nur einen Vertex betrachten wie
z.B. das Blinn-Phong Modell, wird beim Radiosity-Verfahren der ganze Objektraum berücksichtigt.
Dadurch lassen sich realistischere Bilder einer Szene erstellen.
Abbildung 4.1. Die Lösung des Bildes Steel mill der Cornell University benötigte 1988 für die Berechnung der
Radiosity fünf Stunden bei 30000 Flächenstücken und 2000 Iterationsschritten eines Shooting Verfahrens, dann
nochmal 190 Stunden für das Rendern auf einer VAX8700 (siehe [CCWG88]).
Mit dem Begriff Radiosity (Strahlung) wird die gesamte von einer Fläche abgegebene Energie bezeichnet. Bei dem Verfahren handelt es sich um ein Strahlungstransportmodell für diffuse Beleuchtung, das auf Methoden zurückgeht, die von Siegel und Howell 1984 für den Strahlungstransport von
57
58
KAPITEL 4. RADIOSITY
Hitze in Schmelzöfen oder Raketentriebwerken entwickelt wurden. Im gleichen Jahr wurde das Verfahren von Goral, Torrance, Greenberg und Bataille in die Computergraphik eingeführt [GTGB84].
Die Idee des Verfahrens beruht auf der Berücksichtigung des Strahlungsaustausches zwischen Oberflächen und dem Energieerhaltungssatz (Energiesumme in einem abgeschlossenem System ist konstant). Da Licht eine Form von Energie ist, können Sätze der Thermodynamik verwendet werden, um
die Radiosity zu berechnen. Zur Vereinfachung der Szene gelten folgende Annahmen:
1. Die Szene wird in endliche zusammenhängende Teilflächen (Patches) unterteilt, die so gewählt
werden, dass jede Fläche homogen in Bezug auf ihre Strahlungsemissions- und Reflexionseigenschaften (konstante Radiosity) ist.
2. Alle Teilflächen sind Lambert-Strahler bzw. Reflektoren, d.h. die Lichtquellen zeigen ideal diffuse Emissionseigenschaften und alle Oberflächen haben ideal diffuse Reflexionseigenschaften. Ideal diffus bedeutet, dass Licht in alle Richtungen gleichmäßig abgestrahlt bzw. reflektiert
wird.
3. Die Szene ist abgeschlossen bezüglich ihrer Strahlungsenergiebilanz, d.h. es wird weder Energie zugeführt noch abgegeben.
Das Radiosity-Verfahren berechnet unabhängig vom Blickpunkt alle Lichtintensitäten einer Szene. Es
benutzt den Energieerhaltungssatz in abgeschlossenen Systemen. Damit ist es ähnlich wie das Volume Rendering oder das Photonmapping beobachterunabhängig, d.h. die Berechnung wird einmal für
alle Objekte durchgeführt und die vollständige Lösung des 3D-Objektraums wird dann einem Darstellungsprogramm übergeben, das das gewünschte Bild in 2D rendert, also die aus einer bestimmten
Richtung sichtbaren Flächen ermittelt, projiziert und durch Interpolation schattiert (mittels Flatshading oder Gouraud Shading).
Vorteil des Verfahrens ist ein überzeugender Realismus und die gute Eignung für matte Objekte,
Nachteile sind ein noch höherer Rechenaufwand als beim Raytracing und ein hoher Speicherbedarf.
Zudem muss die spiegelnde Reflexion gesondert behandelt werden (beispielsweise mit pixelbasiertem Raytracing). Außerdem ist das Verfahren gitterbasiert, lässt also keine einfache Behandlung analytisch definierter Primitive (Kugel, Konus, etc.) zu, sondern muss diese triangulieren und die Einzelflächen behandeln.
Indirekte Beleuchtung und Lichtführung sind besonders in Museen gefragt, wo die Exponate gleichmäßig ausgeleuchtet sein sollen. Derartige Ansprüche an realistische Simulationen von Streulicht
können nur mit dem Radiosity-Verfahren erreicht werden. Ein sehr bekanntes Beispiel findet sich
auf der Webseite der Graphikgruppe an der Cornell University (siehe Abb. 4.2). Hauptsächlich findet
Radiosity in speziellen Programmen für Innenarchitektur Verwendung, um einem Kunden ein geplantes Gebäude möglichst realistisch vorzuführen. Statische Gebäude eignen sich außerdem besser
für die aufwändige Berechnung der Radiosity-Werte als dynamische Objekte und Animationen, da
die Werte nur einmal für jede Szene berechnet werden müssen. Die folgende Abb. 4.3 stammt von
3d-architectural-rendering (www.archiform3d.com).
4.1. HERLEITUNG DES VERFAHRENS UND MODELLGLEICHUNG
59
Abbildung 4.2. Darstellung einer Museumsbeleuchtung (Cornell University).
In Abb. 4.4 ist die so genannte Cornell Box dargestellt, die als Benchmark für das Lösen der RadiosityGleichung dient. Um realistische Bilder zu erzeugen, wird die Strahlungstransportgleichung für jeden
einzelnen Farbkanal berechnet. Dadurch wird der als Colorbleeding bekannte Effekt erzielt: Farbige
Wände strahlen ihre Farbe auf hellere Objekte ab.
Bemerkung 4.1 Während Raytracing mit globaler Spiegelung arbeitet, aber kein Streulicht kennt,
versucht das Radiosity-Modell global diffuse Reflexion zu behandeln. Der Nachteil besteht in einem
nochmals höheren Aufwand als beim Raytracing. Zudem muss Spiegellicht gesondert behandelt werden. Daher eignet es sich eher für matte Objekte. Vorteile sind der überzeugende Realismus und die
betrachterunabhängige Berechnung.
4.1
Herleitung des Verfahrens und Modellgleichung
Radiosity wird betrachterunabhängig einmal für alle Objekte durchgeführt. Die vollständige Lösung
in 3D wird in einem zweiten Schritt an ein Darstellungsprogramm übergeben, das ein projiziertes und
mit Radiosity-Werten schattiertes Bild in 2D liefert.
60
Abbildung 4.3. Mit Radiosity-Verfahren gerenderter Wohnbereich eines Appartments.
Definition 4.1 Als Radiosity definiert man die Energie pro Flächeneinheit, die ein Element je Zeiteinheit als Summe aus emittierter und reflektierter Energie verlässt.
Der Formel für die Radiosity liegt das Strahlungsgleichgewicht in einem abgeschlossenen System
zugrunde. Auf den Seiten 23 bis 26 in [SP94] findet sich eine genaue Herleitung der Radiosity B aus
der Strahlung (Radiance) L über
Z
B(x) =
L(x, θ, φ) cos θ dω.
Ω
Das führt schließlich zu der Formel für Radiosity, die als Integral dargestellt anschließend diskretisiert
werden kann.
Z
B(x) = E(x) + R(x)
B(x0 ) cos φx cos φx0 V (x, x0 ) dA0
ZS
= E(x) + R(x)
B(x0 )
x0 ∈S
1
cos φx cos φx0 V (x, x0 ) dx0
πr2
B(x) Gesamte vom Punkt x abgestrahlte Energie (Radiosity), eine Summe aus Eigenstrahlung und
Reflexion als Leistung pro Flächeneinheit
(Einheit [W/m2 ])
A0 Fläche um den Punkt x0
(Einheit [m2 ])
4.2. DISKRETE RADIOSITYGLEICHUNG
61
Abbildung 4.4. Diese Cornell Box zeigt Colorbleeding. Es wurden 2370 einzelne Patches mittels Gouraud Shading
gerendert.
E(x) Emittierte Energie oder Eigenstrahlung in x ohne Fremdeinwirkung
(Einheit [W/m2 ])
R(x) Reflexionsfaktor, der angibt, welcher Teil des einfallenden Lichtes wieder abgestrahlt wird
(dimensionslos)
S Alle Oberflächen der Szene
(Einheit [m2 ])
V (x, x0 ) Verdeckungsfunktion, die die Sichtbarkeit von x zu x0 mit 1 bewertet, falls kein Objekt den
Sichtstrahl blockiert. Sonst ist V = 0.
(
1 falls x von x0 aus sichtbar
V (x, x0 ) =
0 sonst
Die Verdeckungsfunktion ist eine Heavyside-Funktion.
4.2
Diskrete Radiositygleichung
In einem ersten Schritt muss eine Aufteilung der Geometrie in Teilflächen (Dreiecke oder Quadrate)
geschehen. Je feinmaschiger dabei das Gitter gewählt wird, desto genauer wird das Ergebnis, aber
um so aufwändiger ist das Verfahren. Die Unterteilung der Szene bestimmt also den Aufwand des
Algorithmus. Anders als beim Raytracing kann man keinen Vorteil aus der Darstellung einer Szene
mit analytischen Primitiven wie z.B. Kugeln, Kegeln und Zylindern ziehen. Auch Flächen, die eine
analytische Beschreibung haben, müssen unterteilt werden, wobei eine sehr feine Unterteilung für
einen gleichmäßigen Verlauf der Schattierung auf der gekrümmten Fläche nötig ist. Wo die Feinheit
der Unterteilung nicht durch die Krümmung vorgegeben ist, unterteilt man nur dort, wo es aus anderen
Gründen erforderlich ist, also z.B. entlang der Begrenzung von Schatten auf einer an sich ebenen
62
Wand (siehe Abb. 4.7). Gleichmäßiges Verfeinern führt natürlich zu viel zu komplexen Strukturen
und ist bei geringfügigen Änderungen der Radiosity nicht nötig. Daher wird meist adaptiv verfeinert,
und zwar abhängig von
• der Größe des Radiosity-Gradienten benachbarter Flächenstücke,
• Diskontinuitäten im Lichtverlauf und bei
• ungünstigen Netzen (z.B. T-Junctions).
Abbildung 4.5. Zentralperspektivische Szene.
Abbildung 4.6. Zerlegung der Szene.
Abbildung 4.7. Eine adaptive Verfeinerung der Szene erhöht den Realismus bei begrenztem zusätzlichen Rechenaufwand, links: 145, mitte: 1021, rechts: 1306 Einzelflächen.
In einem zweiten Schritt werden zur Lösung der Radiosity-Gleichung finite Elementverfahren angewendet. Meist wählt man konstante Basisfunktionen auf den einzelnen Flächenstücken, aber es sind
auch lineare oder quadratische Funktionen denkbar.
4.3. BERECHNUNG DER FORMFAKTOREN
63
Unterteilt man die gesamte Szene in einzelne Flächenelemente Ai , so ergibt sich bezogen auf das i-te
Flächenstück die Formel:
Z
Bi dAi = Ei dAi + Ri
Bj Fji dAj
j
Darin bezeichnet Ei die von Ai emittierte Energie, der zweite Term die reflektierte Energie oder
Reflektivität von Ai , die sich aus dem Reflexionsfaktor der Fläche Ai und der Radiosity aller übrigen
Flächen Aj zusammensetzt, die gemäß ihrer geometrischen Lage über sogenannte Formfaktoren F
gewichtet werden. In diesen Formfaktoren sind die Neigungswinkel sowie die Verdeckungsfunktionen
der Flächen Ai und Aj zueinander zusammengefasst.
Fläche Ai
P
Bj Aj Fji
HH
H
H
H
j
@
@
@
R
@
Ai Ei
Ri Ai
P
Bj Fij
Abbildung 4.8. Berechnung der Radiosity für die Fläche Ai .
Zur Berechnung der Radiosity-Werte Bi sind häufig gemachte Annahmen, dass jedes Ai planar ist
und Bi sowie Ri über Ai konstant sind. Außerdem besteht die folgende reziproke Relation, bei der
man sich leicht merken kann, dass der Formfaktor immer mit der Größe der abstrahlenden Fläche
gewichtet wird.
Ai Fij = Aj Fji
Mit dieser reziproken Relation wird man die Abhängigkeit von der jeweiligen Größe der Flächen Aj
los und kann das Ganze einzig aus der Sicht der aussendenden Fläche Ai beschreiben. Das Maß der
Fläche Ai kürzt sich nun aus der Gleichung heraus und als diskrete Implementierung für insgesamt n
Flächenstücke in der Szene ergibt sich die Formel (siehe [SP94], Seite 30)
Bi = Ei + Ri
n
X
Bj Fij .
j=1
4.3
Berechnung der Formfaktoren
Der Hauptanteil der Arbeit beim Lösen der obigen Gleichung besteht in der Berechnung der sogenannten Formfaktoren Fij . Diese Faktoren sind rein geometrisch motiviert, dimensionslos und be-
64
schreiben den Anteil der Energie, der vom i-ten Flächenstück abgestrahlt auf dem j-ten Flächenstück
eintrifft. Diese Formfaktoren werden auch Gestalt- oder Winkelfaktoren genannt.
Abbildung 4.9. Berechnung der Formfaktoren aus der Lage der Flächen.
Definition 4.2 (Formfaktor oder Gestaltfaktor oder Winkelfaktor) Sei Ai ein Lambertscher Emitter, der eine bestimmte Menge eines Strahlungsflusses Φi emittiert. Sei Aj das Flächenelement, das
einen Anteil Φij von Ai erhält. Der dimensionslose Quotient
Fij :=
Φij
Φi
wird Formfaktor genannt.
Eine generelle Lösung für die Formfaktoren wurde mithilfe analytischer Geometrie von Schröder und
Hanrahan erst 1993 gefunden.
FAi →Aj
1
= Fij =
Ai
Z
Ai
Z
Aj
1
cos φi cos φj V (i, j) dAj dAi
2
πrij
Darin ist rij der Abstand von dAi und dAj , φi der Winkel zwischen der Normalen Ni und dem Vektor
in Richtung dAj . Der Winkel φj ist analog definiert. Der beim Formfaktor erstgenannte Index ist
immer der Sender, der zweite der Empfänger.
Bemerkung 4.2 Wenn man in planare Teilflächen unterteilt hat, sind alle Fii = 0, (i = 1, . . . , n)
also alle Diagonalelemente = 1, da eine planare Fläche sich nicht selbst beleuchten kann.
4.3. BERECHNUNG DER FORMFAKTOREN
65
Bemerkung 4.3 Aufgrund der Definition der Formfaktoren und aufgrund der Energieerhaltung gilt
folgende wichtige Eigenschaft
n
X
Fij = 1
(1 ≤ i ≤ n).
j=1
Die Berechnung der Formfaktoren ist der weitaus aufwändigste Teil des Radiosity-Verfahrens. Beschreibt man die Formfaktoren für beschränkte Flächen i und j in einer konvexen Umgebung, bei der
sich keine Objekte gegenseitig verdecken, entfällt die Verdeckungsfunktion Vij .
Die exakte Berechnung der Integrale erweist sich als ziemlich schwierig. Deswegen sucht man nach
alternativen Berechnungsmethoden, um die Formfaktoren ausreichend gut annähern zu können.
4.3.1
Brute Force Ansatz
Das simpelste Verfahren ist nur für Flächen korrekt, die relativ klein und relativ weit entfernt sind.
Partielle Verdeckung wird ausgeschlossen, Winkel und Entfernungen werden nur zwischen zwei repräsentativen Punkten (z.B. den Mittelpunkten) beider Flächen ermittelt.
Fij ≈ Aj
4.3.2
cos φi cos φj V (i, j)
2
π rij
Methode nach Nusselt
Eine weitere, genauere Möglichkeit, die Formfaktoren zu berechnen, beruht auf folgender geometrischer Beobachtung:
Abbildung 4.10. Skizze zum Analogon von Nusselt, Fij ≈ FdAi Aj
66
Satz 4.1 (Analogon von Nusselt) Der Formfaktor von einer infinitesimal kleinen Fläche dAi zu einer Fläche Aj wird durch die Formel
Z
FdAi ,Aj =
Aj
cos φi cos φj
V (i, j) dAj
2
πrij
beschrieben. Dieser Wert ist äquivalent zu einem Flächenverhältnis, das sich wie folgt berechnet.
Zunächst projiziert man diejenigen Teile der Fläche Aj , die von dAi aus sichtbar sind, auf eine Einheitshalbkugel, deren Zentrum sich im Mittelpunkt von dAi befindet. Diese Projektion wird nochmals
senkrecht auf die Grundfläche der Halbkugel projiziert und die entstehende Fläche durch die Grundfläche der Halbkugel dividiert.
4.3.3
Hemicube Verfahren
Das Nusselt Verfahren ist analytisch schwer zu beschreiben und umständlich zu implementieren.
In einer weiteren Vereinfachung approximiert man daher die Halbkugel durch einen Halbwürfel
(Hemicube-Verfahren). Die Außenflächen des Halbwürfels sind uniform in Zellen pi eingeteilt. Jede Zelle speichert einen Delta-Formfaktor, also den Anteil, der von der Fläche Aj auf das Zentrum dAi projiziert wird. Der endgültige Formfaktor errechnet sich somit aus der Summe der DeltaFormfaktoren all dieser betroffenen Zellen.
FdAi ,Aj ≈
X
∆Fpi
i
Abbildung 4.11. Simulation der Halbkugel durch einen Halbwürfel
4.4. BERECHNUNG DER RADIOSITY-WERTE
4.3.4
67
Sillions Verbesserung und weitere Methoden
Eine zusätzliche, von François Sillion gemachte Vereinfachung lässt sich erzielen, wenn man nur den
Deckel des Würfels, also nur eine Ebene betrachtet. Dadurch verliert man einen Teil der Szeneninformation, aber der Rechenaufwand vermindert sich erheblich.
In der Abb. 4.12 sind noch diverse andere Methoden aufgezeigt, wie man Formfaktoren berechnen
kann. Dabei überwiegen die verschiedenen numerischen Verfahren, die zunächst grob in differentielle und totale Verfahren eingeteilt werden können. Die differenziellen Verfahren werden schließlich
danach eingeteilt, ob sie die über dem Flächenstück Ai befindliche Hemisphäre abtasten oder die
gesamte Fläche über einem differentiellen Flächenstück dAi .
Abbildung 4.12. Berechnung der Formfaktoren, nach Cohen/Wallace: Radiosity and Realistic Image Synthesis
[CW93].
4.4
Berechnung der Radiosity-Werte
Zur numerischen Berechnung der Radiosity-Werte Bi betrachten wir wieder die Gleichung
Bi = Ei + Ri
n
X
Bj Fij .
j=1
Die Gleichung lässt sich umformen zu
Bi − Ri
n
X
j=0
Bj Fij = Ei
(1 ≤ i ≤ n).
68
In Matrixschreibweise löst man dazu ein Gleichungssystem

1 − R1 F11

 −R2 F21


..

.

−Rn Fn1
−R1 F12
···
−R1 F1n

B1


E1

1 − R2 F22
..
.
···
−R2 F2n
..
.






B2
..
.
 
 
 
=
 
 
E2
..
.






−Rn Fn2
···
..
.
1 − Rn Fnn
Bn
En
Gesucht werden Radiosity-Werte Bi für n Flächenstücke i ∈ {1, . . . , n}. Dabei sind die Emissionswerte Ei nur für Lichtquellen von Null verschieden. Der Formfaktor eines Flächenstücks muss nur
einmal berechnet werden, es sei denn, dass sich die Geometrie der Szene ändert. Da der Reflexionsfaktor Ri und der Emissionswert Ei wellenlängenabhängig sind, muss das Gleichungssystem für
jeden Wellenlängenbereich ausgewertet werden, der im Beleuchtungsmodell vorkommt. Dabei kann
man sich auf die drei üblichen Primärfarben Rot, Grün und Blau beschränken, da sie für die Wahrnehmung und Darstellung ausreichen. Somit muss das Gleichungssystem nur drei Mal ausgewertet
werden.
Bemerkung 4.4 Die Formfaktoren Fij werden allein von der Geometrie einer Szene bestimmt. Sie
müssen nicht neu berechnet werden, wenn sich nur die Beleuchtung ändert. Für ebene oder konvexe
Flächenstücke gilt Fii = 0, d.h. Strahlung, die ein Flächenstück verlässt, trifft nicht wieder auf dieses
Flächenstück zurück.
Bemerkung 4.5 Der Reflexionsfaktor Ri und der Emissionsfaktor Ei sind grundsätzlich von der Wellenlänge abhängig. Dazu werden die einzelnen Farbkanäle gesondert behandelt. Ri wird vereinfacht
monochromatisch betrachtet1 .
Die Radiosity einer Fläche setzt sich somit aus der eigenen Energie (falls sie eine Lichtquelle ist)
und der gewichteten Summe aller auf diese Fläche auftreffenden Energiewerte von anderen Flächen
zusammen.
Ein mögliches Lösungsverfahren für ein Gleichungssystem der Form (I − T ) · B = E ist das
Gauß’sche Eliminationsverfahren. Die Variable (Unbekannte) ist hier die Radiosity B, die rechte
Seite ist die Emission E, die lineare Matrix lautet (I − T ). Damit ist die Gleichung von der Form
A · x = b und A bezeichne im Folgenden eine lineare Matrix. Gaußelimination ist jedoch nur bei vollbesetzten n × n Matrizen sinnvoll, da es bei dünnbesetzten Matrizen (also Matrizen, deren Anzahl
der Nicht-Null-Einträge von O(n) ist) zu sogenannten “Fill-Ins“ kommt. Außerdem spricht auch der
hohe Rechenaufwand von O(n3 ) gegen diese Methode.
Die Invertierung der Matrix A löst ebenfalls das Gleichungssystem x = A−1 b. Jedoch ist dies bei
zu großen Matrizen (also 1000 × 1000) unpraktisch, da der Aufwand auch bei O(n3 ) liegt. Eine
1
Für genauere Berechnungen muss wellenlängenabhängig vorgegangen werden.
69
bessere Möglichkeit zur Lösung sind Iterationsverfahren. Dazu zählen das Jacobi- und das GaußSeidel Verfahren.
4.4.1
Allgemeine Iterationsverfahren
Gegeben sei eine nichtsinguläre n × n-Matrix A und ein lineares Gleichungssystem
Ax = b
mit der exakten Lösung x = A−1 b. Ausgehend von einem Startvektor x(0) wird eine Folge von Vektoren x(0) → x(1) → x(2) → . . . erzeugt, die gegen die gesuchte Lösung x konvergiert, d.h. es werden
Fixpunktverfahren der Form
x(i+1) = Φ(x(i) )
(i = 0, 1, . . .)
betrachtet, wobei eine Iterationsfunktion Φ so konstruiert wird, dass sie genau einen Fixpunkt besitzt
und dieser gerade die gesuchte Lösung x = A−1 b ist.
Durch Hinzunahme einer beliebigen nichtsingulären n × n-Matrix M erhält man eine solche Iterationsvorschrift aus der Gleichung
M x + (A − M )x = b,
(4.1)
M x(i+1) + (A − M )x(i) = b
(4.2)
indem man
setzt und nach x(i+1) auflöst
⇔
x(i+1) = x(i) − M −1 (Ax(i) − b) = (I − M −1 A)x(i) + M −1 b
x(i+1) = S x(i) + M −1 b,
wobei zur Vereinfachung die Matrix S := (I − M −1 A) eingeführt wird.
Definition 4.3 Ein Iterationsverfahren zur Lösung von Ax = b heißt konsistent genau dann wenn x
ein Fixpunkt der Iteration ist.
Um die Konsistenz des Verfahrens oder anders ausgedrückt die Konvergenz der Iteration gegen die
Lösung anhand der Matrix S erkennen zu können, werden Spektralradius und Matrixnorm definiert.
70
Definition 4.4 (Spektralradius) Sei A ∈ Cn×n eine beliebige Matrix. Der Spektralradius ρ einer
Matrix A ist das Maximum über sämtliche Eigenwerte λi von A
ρ(A) := max |λi |.
1≤i≤n
Definition 4.5 (Matrixnorm) Sei A ∈ Cn×n eine beliebige Matrix. Für x ∈ Cn und einer gegebenen
.
Vektornorm kxk wird die Matrixnorm definiert durch k|A|k := sup kAxk
kxk
x6=0
Jetzt kann man das Konvergenzkriterium in einem Satz formulieren.
Satz 4.2
1. Das Verfahren x(i+1) = S x(i) + M −1 b ist genau dann konvergent, wenn
ρ(S) < 1.
2. Hinreichend für die Konvergenz des Verfahrens ist die Bedingung
k|S|k < 1
für beliebige Matrizen M .
Zum Beweis dieses Satzes benötigt man nun folgende zwei Sätze:
Satz 4.3 (Hirsch) Für alle Eigenwerte λ von A gilt
|λ| ≤ k|A|k .
Satz 4.4
1. Zu jeder Matrix A und jedem > 0 existiert eine Vektornorm mit
k|A|k ≤ ρ(A) + .
2. Hat jeder Eigenwert λ von A mit der Eigenschaft |λ| = ρ(A) nur lineare Elementarteiler, so
existiert sogar eine Vektornorm mit
k|A|k = ρ(A).
Beweis von Satz 4.2:
Für den Fehler fi := x(i) − x folgt durch Subtraktion der Gleichung (4.1) von der Gleichung (4.2)
fi+1 = Sfi
71
bzw. durch wiederholtes Anwenden der Matrix S auf den anfänglichen Fehler
fi = S i f0
i = 0, 1, . . .
Sei nun x(i+1) = S x(i) + M −1 b konvergent. Dann ist lim fi = 0 für alle f0 . Wählt man f0 als
i→∞
Eigenvektor zum Eigenwert λ von S, dann folgt daraus
fi = λi f0 .
Da lim fi = 0, muss |λ| < 1, und daraus folgt schließlich ρ(S) < 1.
i→∞
Sei umgekehrt ρ(S) < 1, so folgt aus Satz 4.4 sofort lim S i = 0 und so lim fi = 0 für alle f0 . Die
i→∞
i→∞
hinreichende Bedingung für die Konvergenz des Verfahrens k|S|k < 1 folgt unmittelbar aus Satz 4.3.
Es werden nun spezielle Verfahren erläutert, die von der Wahl der Matrix M abhängen. Dabei wird die
Matrix A = L + D + R in eine linke untere Matrix L, eine Diagonalmatrix D = diag(a11 , . . . , ann )
und eine rechte obere Matrix R, in Matrixschreibweise






0 a12 . . . a1n
a11 0 . . . 0
0 ...
0
0
..
.. 
..
.. 
..
.
.




.
.
. 
.
. 
 0 0

 0 a22 . .
 a21 . .
L= . .

, R =  .
, D =  . .
.
.
.
..
. . an−1,n 
.. .. 0 
..
 ..
 ..
 ..
0
0 
0 0 ...
0
an1 . . . an,n−1 0
0 . . . 0 ann
zerlegt. Die Matrix M sollte nun eine leicht zu invertierende Matrix sein und es sollte gelten M ≈ A,
denn dann würde das Verfahren die exakte Lösung liefern.
4.4.2
Jacobiverfahren
Wählt man nun für M = D, so resultiert daraus das Jacobiverfahren mit der Vorschrift
x(i+1) = (I − D−1 A)x(i) + D−1 b
= −D−1 (L + R)x(i) + D−1 b.
Das Jacobiverfahren wird synonym auch als Gesamtschrittverfahren bezeichnet. Erst wenn alle
vorherigen Werte x der i-ten Iteration bekannt sind, wird der neue Wert x(i+1) in einem Gesamtschritt
ermittelt.
72
Definition 4.6 (Diagonaldominanz) Eine Matrix A ∈ KI×I heißt stark diagonaldominant, wenn
X
|aii | >
|aij |
∀i ∈ I
j∈I,i6=j
Eine Matrix A ∈ KI×I heißt schwach diagonaldominant, wenn
X
|aii | ≥
|aij |
∀i ∈ I
j∈I,i6=j
Für das Jacobiverfahren gilt der Konvergenzsatz:
Satz 4.5 Das Jacobiverfahren konvergiert für alle stark diagonaldominanten Matrizen A.
4.4.3
Gauß-Seidel Verfahren
Für das Gauß-Seidel-Verfahren wählt man M = L + D und die dazugehörige Iterationsvorschrift
x(i+1) = (I − (D + L)−1 A)x(i) + (D + L)−1 b
= −(D + L)−1 Rx(i) + (D + L)−1 b.
Damit ist das Gauß-Seidel Verfahren ein Einzelschrittverfahren, denn aufgrund der speziellen Struktur können bereits ermittelte Werte der (i + 1)-ten Iteration in die Berechnung der noch fehlenden
Werte dieser Iteration eingehen. Für das Gauß-Seidel Verfahren gilt:
Satz 4.6 Das Gauß-Seidel Verfahren konvergiert für alle stark diagonaldominanten Matrizen A und
es gilt
k|SG |k∞ ≤ k|SJ |k∞ < 1.
4.4.4
SOR-Verfahren (Successive Overrelaxation) bzw. Relaxationsverfahren
Eine weitere Möglichkeit, bessere Konvergenzbedingungen, als mit dem Gauß-Seidel-Verfahren zu
erzielen, ist eine ganze Klasse von Matrizen M (ω) in Abhängigkeit eines Parameters ω zu betrachten.
Die Kunst liegt nun darin, ω so zu wählen, dass R(I − M (ω)−1 A) möglichst klein wird. Man wählt
M (ω) folgendermaßen:
1
M (ω) = D(I + ωL)
ω
Man kann jedoch beweisen, dass das Verfahren nur für 0 < ω < 2 konvergiert und R(I − M (ω)−1 A)
minimal wird, wenn
2
ω=
2 − λmin − λmax
73
gewählt wird. Für ω < 1 spricht man von Unterrelaxation und für ω > 1 von Überrelaxation. Jedoch
gelten diese Sätze nur, falls A positiv definit ist.
4.4.5
Anwendbarkeit der Iterationsverfahren auf Radiosity
Um das Jacobi- oder das Gauß-Seidel Verfahren auf die Berechnung der Radiosity-Werte anwenden
zu können, muss noch gezeigt werden, dass die Radiosity-Matrix A wirklich stark diagonaldominant
ist. Sei aij ∈ A (1 ≤ i, j ≤ n). Man betrachtet dazu die Diagonalelemente der Matrix A.
aii = 1 − Ri Fii =
n
X
Fij − Ri Fii >
j=1
da
n
X
Ri Fij − Ri Fii =
j=1
n
X
n
X
Ri Fij ,
j=1,j6=i
Fij = 1 und Fij > Ri Fij (Ri < 1)
j=1
⇒ |aii | >
n
X
|aij |
j=1,j6=i
Also sind beide Verfahren auf die Radiosity-Matrix anwendbar.
Das Jacobiverfahren benötigt in jeder Iteration zwei Vektoren, da der neue immer aus dem alten
berechnet wird. Das Gauß-Seidel Verfahren braucht dagegen nur einen Vektor, da es in jedem Iterationsschritt sofort die bis dahin errechneten Werte für die weitere Berechnung benutzt. D.h. das
Jacobiverfahren errechnet immer nur eine Reflexion pro Iteration, während das Gauß-Seidel Verfahren mehrere Reflexionen pro Iteration berechnet. Das ist auch der Grund, warum das Gauß-Seidel
Verfahren im Allgemeinen fast doppelt so schnell konvergiert wie das Jacobiverfahren. Dafür ist das
Jacobiverfahren sehr leicht parallelisierbar.
4.4.6
Progressive Verfeinerungen
Die hohen Kosten der Radiosity-Methode liegen in der Berechnung der Formfaktoren. Daher werden sie einmal berechnet und danach gespeichert. Auch wenn viele Formfaktoren aus Sichtbarkeitsgründen Null gesetzt werden können, ist der potenzielle Speicherbedarf das Quadrat aus der Anzahl
der Patches. In konventionellen Algorithmen werden alle Formfaktoren im Voraus berechnet. Eine
Abschätzung der Radiosity-Werte ist daher erst nach der ersten vollständigen Iteration des GaußSeidel Verfahren möglich. Um schnell eine Szene mit Radiosity rendern zu können, kann man die
Formfaktoren on-the-fly berechnen lassen, wobei der Halbwürfel über einem Flächenstück Ai nach
und nach verfeinert wird. In den Abbildungen 4.13 bis 4.18 werden Bildbeispiele aus der Veröffentlichung von Cohen et al. über Progressive Refinement [CCWG88] gezeigt, in denen jeweils für 1, 2,
24 und 100 Halbwürfel Aufnahmen der Szene gemacht worden sind.
74
Die Radiosity Berechnung mit Progressive Refinement macht es nötig, zwischen zwei Typen von
Oberflächen (Faces) zu unterschieden:
Definition 4.7 (Patch) Ein Patch ist ein Drei- oder Viereck, das in der Lage ist Energie auszusenden.
Die Energie des Patches wird nur vom Zentrum des Patches emittiert.
Um eine schnelle Lösung berechnen zu können, sollte man die Szene in so wenig Patches wie möglich
unterteilen. Das Patch muss klein genug sein, eine Energieverteilung auf seine gesamte Fläche realistisch erscheinen zu lassen. Wenn beispielsweise ein kleines Objekt über dem Zentrum des Patches
die Abstrahlung vollständig blockiert, muss das Patch unterteilt werden.
Definition 4.8 (Element) Elemente sind Drei- oder Vierecke welche Energie erhalten. Jedes Element
ist einem Patch zugeordnet, Patches sind in mehrere kleine Elemente aufgeteilt.
Wenn ein Element Energie empfängt, wird ein Teil davon absorbiert. Die restliche Energie wird dem
Patch zugeführt, und von dort wieder abgestrahlt. Mit der für die Elemente berechneten Radiosity
werden die Oberflächen dargestellt, daher ist es wichtig, dass diese so klein wie möglich sind. Nur so
können fein abgestufte Schattengrenzen und Lichtverläufe errechnet werden.
Bei der Methode des Progressive Refinement werden zunächst alle verfügbaren Patches untersucht.
Das am stärksten aufgeladene Patch schießt nun seine Energie in die Umgebung. Die vom Patch
aus sichtbaren Elemente erhalten diese Energie und fügen sie ihrer eigenen Energie hinzu. Dieser
Prozess wird itteriert, bis die unverbrauchte Energie einen bestimmten Wert unterschritten hat. Mit
Hilfe von Halbwürfeln wird berechnet, wieviel Energie jedes Patch an ein Element abstrahlt. Jeder
Halbwürfel besteht aus fünf kleinen Bildern der Umgebung, die vom Zentrum des Patches aus durch
diese Würfelfläche zu sehen ist. Für jedes Pixel dieser Bilder wird ein bestimmtes Element farbkodiert und die transmittierte Energie berechnet. Diese Methode ist eine Vereinfachung der richtigen
Radiosity Formel (der Form-Faktor Berechnung). Deshalb ist die Auflösung des Halbwürfels, also
die Anzahl an Pixeln in seinen Bildern, immer nur eine Annäherung. Die Größe der Patches und Elemente bestimmen die Qualität der Radiosity Lösung. Deshalb wurden Methoden zur automatischen
Unterteilung entwickelt.
Einerseits kann man die emittierenden Patches unterteilen. Dazu wird Lichtenergie in die Umgebung
geschossen, und der über den Halbwürfel berechnete Wert mit den Werten eines nächst feiner unterteilten Patches verglichen. Wird eine Fehlerschranke unterschritten, kann man die Verfeinerung
beenden. Andererseits kann es nötig sein, die empfangenden Elemente zu verfeinern. Wenn innerhalb eines Patches sehr starke Energieunterschiede (Gradienten) zwischen den Elementen gefunden
werden, werden die Elemente dieses Patches unterteilt. Das führt zu kleineren Elementen und einer
längeren Lösungszeit, aber einer größeren Detailliertheit.
75
Abbildung 4.13. Gauß-Seidel nur mit Gathering-Verfahren, für 1, 2, 24 und 100 Hemikuben.
4.4.7
Gathering Verfahren (= Einsammeln)
Jacobi- und Gauß-Seidel Verfahren sind so genannte Gathering-Methoden (siehe [CCWG88]). Damit
ist gemeint, dass ein Patch die Radiosity der übrigen Patches in der Szene einsammelt. Die Lösung
einer Zeile des Gleichungssystems beim Gauß-Seidel Verfahren liefert den Radiosity-Wert eines Patches. Genauer: Gathering über einen Hemi-Cube erlaubt es die Radiosity über einen Patch zu aktualisieren.
 
 
  x

 

 
 x

 x
 

 
 

 
 

 
  =  +
 

 
 

 
 

 
 

 
x
x
x
x
x
x
x
x
  x
  x
 
  x
  x
 
  x
 
  x
 
x
x
Abbildung 4.14. Links
Pn die Skizze des Gathering Verfahrens und rechts die Matrizenbelegung im Fall des Gathering, Bi = Ei + Ri j=1 Fij Bj .
Der Pseudo-Code für das Gathering sieht wie folgt aus:
for (i = 0, i < n; i++)
B[i] = E[i];
while (no convergence)
{
for (i = 0; i < n; i++)
76
{
B_sum = 0;
for (j = 0; j < n; j++)
B_sum += F[i][j] * B[j];
B[i] = E[i] + R[i] * B_sum;
}
render(B);
}
4.4.8
Shooting Verfahren (= Aussenden)
Abbildung 4.15. Gauß-Seidel nur mit Shooting Verfahren, für 1, 2, 24 und 100 Hemikuben.
Beim Shooting wird jeweils das Licht des Patches mit der höchsten Energie in die Umgebung verschossen. Genauer: Shooting über einen Hemi-Cube erlaubt es, die Radiosity mehrerer Patches zu
aktualisieren.
 x
 x

x
 x
 x

 x
 x

 

 
 x
 x

 x
 x

  =  +
 x
 x

 
 


 x
 x
 
 

x
x
x
x
x
x
x
x
x
x
x
x
 
 
  x
 
 
 
 
 
 
 
 
Abbildung 4.16. Links die Skizze des Shooting Verfahrens und rechts die Matrizenbelegung im Fall des Shooting,
Bj = Bj + (Rj Fji )Bi .
Wie auch im Gathering-Verfahren wird der Wert für die Radiosity der Fläche Ai mit dem Emissionsterm initialisiert. Darüberhinaus wird auch die von dieser Fläche nicht über dieses Element verschos-
77
sene Energie mit dem Emissionsterm initialisiert. Der Pseudo-Code für das Shooting sieht wie folgt
aus:
for (i = 0, i < n; i++)
B[i] = dB[i] = E[i];
// dB[i]: unshot radiosity
while (no convergence)
{
set i as dB[i] is the largest
{
for (j = 0; j < n; j++)
{
db = R[j] * F[j][i] * dB[i];
dB[j] += db; // update change since last time patch j shot
// light
B[j] += db; // update total radiosity of patch j
}
dB[i] = 0;
// reset unshot radiosity for patch i to zero
}
render(B);
}
Bei der Benutzung von einfachem Gauß-Seidel Verfahren bleibt die Szene auch mit 100 Halbwürfeln
relativ dunkel (siehe Abb. 4.13). Wenn man das Shooting ohne die Sortierung nach dem größten Energiewert verwendet, wird kein allzu großer Unterschied zum Gathering sichtbar (siehe Abb. 4.15).
Aber wenn man beim Shooting-Verfahren zusätzlich nach der Helligkeit der auftretenden Patches
sortiert, erhellt sich auch die Szene schneller. Man erkennt deutlich den Unterschied zum reinen
Shooting-Verfahren (siehe Abb. 4.17). In Abb. 4.18 wurde auch noch ein konstanter ambienter Anteil
von Anfang an aus Sichtbarkeitsgründen in die Szene eingerechnet. Er hängt in jedem Verfeinerungsschritt von den jeweils bis dahin berechneten Radiosity-Werten aller Patches und der Reflektivität der
Umgebung ab. Er geht aber nicht in die Lösung des Gleichungssystems ein und wird nur in jedem
Iterationsschritt in geringerem Maß in der Rendergleichung verwertet.
Abbildung 4.17. Kombination aus Shooting mit Sortierverfahren, für 1, 2, 24 und 100 Hemikuben.
78
Abbildung 4.18. Hier wurde Shooting und Sorting kombiniert und mit einem ambienten Anteil bei der Darstellung
verrechnet, ebenfalls für 1, 2, 24 und 100 Hemikuben.
4.5
Rendern mit Radiosity-Werten
Da der Radiosity-Wert pro Flächenstück konstant ist, kann er auf Vertices abgebildet und dann dem
Renderer übergeben werden. Die Berechnung der Vertex-Radiosities erfolgt beispielsweise nach einem Ansatz von Cohen und Greenberg [CG88]. Dabei wird unterschieden, ob der Vertex im Inneren
einer zusammenhängenden Fläche oder am Rand oder in einer Ecke liegt.
• Die Radiosity für einen Vertex BM im Inneren einer Fläche wird über die angrenzenden Flächenstücke gemittelt.
• Der Mittelwert der Vertex-Radiosity eines Randpunktes und des nächstliegenden inneren Punktes entsprechen dem Mittelwert der Radiosity aller an diesem Randpunkt angrenzenden Flächen.
Abbildung 4.19. Berechnung der Vertex-Radiosity.
Zu dieser Berechnung sei hier das Beispiel aus der Abb. 4.19 in Formeln dargestellt. Die Indizes M ,
und N O bezeichnen die Vertex-Radiosity in den Knoten Mitte, Nord und Nord Ost, während die
Ziffern die Radiosity auf den jeweiligen Flächenstücken bezeichnen.
N
1
BM = (B1 + B2 + B3 + B4 )
4
1
1
(BN + BM ) = (B1 + B2 ) ⇒ BN = B1 + B2 − BM
2
2
1
(BN O + BM ) = B2 ⇒ BN O = 2B2 − BM
2
4.5.1
79
Lichtlecks und Diskontinuitäten
Typische Fehler, die beim Rendern auftreten können, betreffen die Art wie die Gitter die Geometrie widerspiegeln. Sogenannte Lichtlecks entstehen, wenn ein Gitterpunkt die gemittelte VertexRadiosity von Flächen bekommt, die beispielsweise durch eine Wand getrennt jeweils ganz unterschiedlichen Beleuchtungen ausgesetzt sind (siehe Abb. 4.20 links). Abhilfe schafft hier die Modellierung geschlossener Räume bzw. eine Wandstärke, die so groß wie die Maschenweite der angrenzenden Wände ist.
Ein anderer schwerer zu entdeckender und zu behebender Fehler betrifft die Unterteilung aneinander
angrenzender Flächen (siehe Abb. 4.20 rechts). Ein Sprung oder Versatz von Gitterpunkten wird bei
anschließender linearer Interpolation der Farbwerte diskontinuierliche Verläufe zeigen.
Abbildung 4.20. Links Lichtlecks, rechts Diskontinuitäten, die als Fehler beim Rendern mit Radiosity-Werten
auftreten können (aus Cohen/Wallace: Radiosity and Realistic Image Synthesis [CW93]).
4.6
Übungsaufgaben
Aufgabe 4.1 Formfaktoren
Für Radiosity spielen die sogenannten Formfaktoren Fij eine wichtige Rolle. Für eine Szene, die aus
n Flächenstücken besteht, definiert man
Z Z
1
cos θi cos θj
Fij =
dAj dAi
(1 ≤ i, j ≤ n).
2
Ai Ai Aj
πrij
Dabei wird volle Sichtbarkeit des Flächenstücks Ai von Aj vorausgesetzt. Der Abstand zwischen den
Flächenstücken i und j ist rij und der Winkel θi befindet sich zwischen der Normalen der Fläche Ai
80
und dem Richtungsvektor auf die Fläche Aj .
(a) Leiten Sie eine Beziehung zwischen Fij und Fji her.
(b) Um die Sichtbarkeit zu garantieren, wird eine Verdeckungsfunktion Vij unter dem Integral eingeführt.
(
1 falls Flächenstück i von j aus voll sichtbar
Vij =
0 sonst
Schreiben Sie jetzt die vollständige Definition hin. Wie groß ist Fii für ebene oder konvexe Flächen?
(c) Die Formel für Radiosity Bi der Teilfläche i lautet
Bi Ai = Ei Ai + Ri
n
X
Bj Aj Fji
(1 ≤ i ≤ n)
j=0
mit einer emittierten Energie Ei und dem Reflexionsfaktor Ri . Aus der Definition der Formfaktoren
und der Energieerhaltung im System leiten Sie die folgende Beziehung her:
n
X
j=1
Fij = 1
(1 ≤ i ≤ n)
Kapitel 5
Photon Mapping
Die größten Schwächen des Raytracing bestehen darin, dass es KEINE diffusen Abstrahlungen und
KEINE Kaustik wiedergeben kann. Während man für die diffusen Abstrahlungen, dem sogenannten
Color bleeding oder Ausbluten von Farbe auf benachbarte Flächen, mit Radiosity Abhilfe schaffen
kann, indem man mit finite Elementmethoden Strahlungsgleichgewichte zwischen einzelnen Flächenstücken berechnet, hatte man für die Kaustik, also das Bündeln oder Fokussieren von Lichtstrahlen
keine wirklich gute Methode. Lichtreflexe auf dem Boden eines Schwimmbeckens oder am Fuß eines
Cognacglases, eine Lupe, die als Brennglas dient, konnten nicht wirklich wiedergegeben werden.
Das Photon Mapping ist eine Methode, die als Ergänzung zum Raytracing zu sehen ist. Sie wurde in
den Jahren 1993/94 in der Dissertation von Henrik Wann Jensen entwickelt und 1995 veröffentlicht.
Beide oben genannten Probleme, das Ausbluten und die Kaustik, können mit Photon Mapping gelöst
werden: es sind indirekte Beleuchtungen diffuser Oberflächen. Außerdem können auch Streuungen an
Volumen in ähnlicher Weise in diese Technik einbezogen werden und so Nebel und Rauch realistisch
erscheinen lassen (Participating Media). Zudem ist sie einfach parallelisierbar. Dieses Skript lehnt
sich eng an die Ausführungen im SIGGRAPH Course 38 von 2001 an (siehe [JCS01]).
Die Idee ist denkbar einfach: man stelle sich Licht in Form von Teilchen vor, die von der Lichtquelle
in zufällige Richtungen emittiert werden und dabei Energie nach Farbkanälen aufgespalten transportieren. In einem ersten Schritt wird eine Photon Map erstellt, die alle Ereignisse des Aufpralls eines
zufällig gestreuten Photons auf ein nichtreflektierendes Objekt registriert. Der zweite Schritt besteht
im Rendering Pass, der mit statistischen Techniken die Informationen über hereinkommenden Fluss
und reflektierte Strahlung an jedem Punkt berechnet.
Die Photon Map ist von der geometrischen Repräsentation entkoppelt. Dadurch ist sie bei komplexen
Szenen der Methode des Radiosity klar überlegen, denn Photon Mapping benötigt kein Gitter und
skaliert daher besser, wenn die Anzahl der Objekte groß ist. Außerdem ist noch anzumerken, dass das
Verfahren nicht patentiert ist und daher bereits in viele gängige Raytracingalgorithmen übernommen
wurde (beispielsweise in Povray und Renderpark).
81
82
KAPITEL 5. PHOTON MAPPING
Abbildung 5.1. Henrik Wann Jensen
5.1
Die Spur der Photonen
Ziel des Photonenverfolgens ist die Berechnung von indirekter Beleuchtung auf diffusen Oberflächen,
die beispielsweise auch durch die Bündelung von Licht an spiegelnden oder transparent fokussierenden Objekten entsteht.
5.1.1
Photonemission
Photonen werden von einer Lichtquelle über eine Verteilungsfunktion emittiert, die von der emissiven
Lichtstärke bestimmt wird. Hier muss zwischen der Lichtstärke und dem Photonenfluss vermittelt
werden.
Man unterscheidet (a) punktförmige und (b) gerichtete Lichtquellen, (c) Schlaglichter oder (d) generelle Lichtobjekte (für die man über goniometrische Diagramme die Emission bestimmt). Während
man für die Photonen bei (a) gleichmäßig verteilte zufällige Richtungen von einem Punkt aus wählt,
haben die Photonen im Fall (b) alle dieselbe Richtung, nämlich die aus der das Licht einstrahlt (mit
vierten Koordinate w = 0, also unendlich weit entfernt). Im Fall (c) eines Schlaglichts (z.B. ein
rechteckiges Fenster), nimmt man zufällig verteilte Positionen innerhalb der ausgedehnten Fläche des
Schlaglichts an und ermittelt zufällige Richtungen mit einer über den Kosinus verteilten Wahrschein-
5.1. DIE SPUR DER PHOTONEN
83
lichkeit (die Null ist, für parallel zur Fläche emittierte Photonen und höchste Wahrscheinlichkeit für
senkrecht abgestrahlte Photonen hat). Im allgemeinen Fall (d) variiert man die Wahrscheinlichkeit der
Position auf der Lichtquelle und die Richtung des Photons.
Die Stärke des Lichts (in Watt, [w]) muss von den emittierten Photonen reproduziert werden. In einer
Formel ausgedrückt muss gelten
Pphoton =
Plight
ne
(5.1)
mit der Lichtstärke Pphoton für ein einzelnes Photon, während Plight die gesamte Lichtstärke der Quelle
und ne die Anzahl der emittierten Photonen ist.
Abbildung 5.2. Mögliche Lichtquellen von links nach rechts: (a) Punktförmige Lichtquelle, (b) gerichtete Lichtquelle, (c) Schlaglicht, (d) generelles Lichtobjekt
Pseudocode für das Aussenden von Photonen:
emit_photons_from_diffuse_point_light(){
ne = 0;
// number of emitted photons
while (not enough photons) {
do {
x = random number between -1 and 1;
y = random number between -1 and 1;
z = random number between -1 and 1;
}
d = <x,y,z>;
p = light source position;
trace_photon_from_p_in_direction_d();
ne= ne + 1;
}
scale power of stored photons with 1/ne
}
84
Bemerkung 5.1 Szenen mit vielen Lichtquellen benötigen nicht mehr Photonen als Szenen mit nur
einer Lichtquelle, da jede Lichtquelle zur gesamten Beleuchtung weniger beiträgt. Wenn nur wenige
Lichtquellen für die gesamte Beleuchtung von Bedeutung sind, kann man die Bedeutung in einer
Abbildung festhalten (Importance sampling map), um danach die Photonen zu konzentrieren.
Bemerkung 5.2 Statt Photonen unterschiedlicher Energieniveaus für schwächere und stärkere Lichtquellen zu speichern, kann man auch einfach die Anzahl der emittierten Photonen bei schwächeren
Quellen reduzieren. Tausend Photonen mit halber Energie entsprechen fünfhundert Photonen mit voller Energie.
In Szenen mit wenigen Objekten treffen viele der emittierten Photonen auf gar kein Objekt. Um
diese Verschwendung von Rechenleistung zu reduzieren, optimiert man die Emission über sogenannte
Projection maps.
Definition 5.1 Eine Projection map ist eine Abbildung der Geometrie aus Sicht einer Lichtquelle.
Sie besteht aus vielen einzelnen Zellen, die angeschaltet sind, falls geometrische Objekte in dieser
Richtung liegen, und ausgeschaltet sind, falls das nicht der Fall ist.
In der Praxis hat sich das Clustern von Objekten und ein Arbeiten mit Bounding spheres oder Bounding boxes als nützlich erwiesen.
Mit der Projection map erhält man eine konservative Abschätzung für die Richtung, in der es nötig
ist, Photonen zu emittieren. Das generelle Vorgehen sieht bei dünn besetzten Szenen eine Schleife über alle angeschalteten Zellen vor. Es werden zufällig Photonen in den Bereich dieser Zellen
emittiert. Das kann allerdings zu verzerrten Ergebnissen führen, wenn die Anzahl angestrebter Photonenereignisse bereits erreicht ist, bevor alle Zellrichtungen abgearbeitet sind. Daher wird man bei
dicht besetzten Szenen zunächst eine zufällige Richtung generieren, dann testen, ob die Zelle in dieser
Richtung angeschaltet ist. Andernfalls generiert man eine neue Richtung. Dieses Testen ist für dünn
besetzte Szenen zu kostspielig und bringt im dicht besetzten Fall nur dann einen Vorteil gegenüber
dem Arbeiten ohne Projection map, wenn man die Objekte in Clustern und begrenzenden Volumina
organisiert.
Jedenfalls aber muss man die Gleichung 5.1 mit dem Verhältnis aus angeschalteten Zellen zur Gesamtzahl der Zellen wichten.
Pphoton =
Plight # of cells with objects
ne
total # of cells
(5.2)
Ein weiterer Vorteil von Projection maps besteht darin, dass man Objekte mit spiegelnden Eigenschaften leicht identifizieren kann. Diese meist wenigen Objekte sind wichtig für das Erzeugen von
Kaustiken.
5.1.2
85
Photonenverfolgung mit russischem Roulette
Die Photonenverfolgung basiert auf dem Raytracing ganz ähnlichen Verfahren, mit dem Unterschied,
dass hier die emittierten Photonen in die Szene verfolgt werden. Dieses Verfahren wird von den verschiedenen Autoren meist als Light ray tracing oder Forward ray tracing manchmal auch Backward
path tracing bezeichnet. Beim Verfolgen des Strahls müssen im Wesentlichen Schnittpunkte mit Objekten berechnet werden, an denen ein Richtungswechsel des Strahls geschieht. Dabei transportieren
Photonen Energie in Form eines Energieflusses, während Sichtstrahlen, die durch jeweils alle Pixel in
eine Szene verfolgt werden, eine Strahlungsdichte an den jeweiligen Schnittpunkten einsammeln.
Beispiel 5.1 Die Wechselwirkung eines Photons mit einem Material ist anders als bei einem Sichtstrahl:
Für den Strahl existiert ein Brechungsindex, für das Photonenteilchen nicht.
Wenn ein Photon auf ein Objekt trifft, wird es entweder
(a) diffus oder spiegelnd reflektiert,
(b) diffus oder spiegelnd transmittiert oder
(c) absorbiert (ausgelöscht).
Die Wahrscheinlichkeit für die drei Fälle hängt von den jeweiligen Materialeigenschaften ab. Wenn
wir zunächst den monochromatischen reflektierenden Fall betrachten, so gilt
kd + ks ≤ 1.
Dabei ist kd der diffuse und ks der spiegelnde Reflexionskoeffizient. Sei nun ξ ∈ [0, 1] eine gleichmäßig
verteilte Zufallsvariable (die man z.B. mit drand48() berechnet). Man unterscheidet
ξ ∈ [0, kd ]
ξ ∈ [kd , kd + ks ]
ξ ∈ [kd + ks , 1]
→
→
→
diffuse Reflexion
spiegelnde Reflexion
Absorption.
Diese Methode ist bekannt als Russisches Roulette. Die Energie eines Photons muss dabei nicht modifiziert werden!
Beispiel 5.2 Ein Material, dessen Oberfläche 50 % des eingestrahlten Lichts reflektiert, wird auch
nur die Hälfte der ankommenden Photonen reflektieren (mit voller Energie). Die restlichen 50 %
werden absorbiert.
86
Im chromatischen Fall (z.B. mit drei Farbkanälen RGB) bestimmt man jeweils eine Wahrscheinlichkeit für diffuse und spiegelnde Reflexion, statt einfach kd und ks einzusetzen. Daher erhält man für
den
diffusen Fall:
Pd =
max(kdr Pr , kdg Pg , kdb Pb )
max(Pr , Pg , Pb )
spiegelnden Fall:
Ps =
max(ksr Pr , ksg Pg , ksb Pb )
,
max(Pr , Pg , Pb )
und den
wobei (kdr , kdg , kdb ) die diffusen, (ksr , ksg , ksb ) die spiegelnden Reflexionskoeffizienten sind und das
Tupel (Pr , Pg , Pb ) die Energie des einfallenden Photons nach Farbkanälen aufgespalten darstellt. Die
Wahrscheinlichkeit der Absorption bei reflektierenden (nicht transmittierenden) Oberflächen beträgt
P a = 1 − Pd − Ps
mit einer Zufallsvariablen ξ ∈ [0, 1] und
ξ ∈ [0, Pd ]
ξ ∈ [Pd , Pd + Ps ]
ξ ∈ [Pd + Ps , 1]
→
→
→
diffuse Reflexion
spiegelnde Reflexion
Absorption.
Jetzt muss allerdings die Energie des reflektierten Photons angepasst werden, denn entweder wird
das Photon mit voller Energie gespiegelt oder mit voller Energie diffus gestreut. Sollte spiegelnde
Reflexion ausgewählt worden sein, ergibt sich:
Prefl,r = Pin,r /Ps
Prefl,g = Pin,g /Ps
Prefl,b = Pin,b /Ps
Diese Vorgehensweise ist natürlich auf transmittierte Strahlung erweiterbar. Auch das Aufspalten in
nur drei Farbkanäle kann auf generelle Wellenlängenabhängigkeit erweitert werden. Für spezielle
Reflexionseigenschaften wie glänzende oder richtungsabhängige diffuse Reflexion wurden ebenfalls
geeignete Modelle auf Basis von Wahrscheinlichkeiten entwickelt.
Vorteil von Russischem Roulette: Die gespeicherten Photonenereignisse haben immer vergleichbare Energie. Damit wird die Abschätzung der Strahldichte einfacher und selbst bei wenigen Photonen
erzielt man eine bessere Qualität, als würde man auch die Energie der Photonen je Ereignis abnehmen
87
lassen und schließlich viel Rechenleistung in das Verfolgen von energetisch geringwertigen Photonen
verschwenden. Würde man nämlich ein Photon beim Auftreffen auf eine Fläche beispielsweise in ein
diffuses und ein spekulares Photon aufspalten, wobei die Energie jeweils in gleicher Weise aufgespalten wird, würde man für jedes Photon einen binären Baum erzeugen, dessen Einzelereignisse in jeder
Stufe entsprechende Anteile der Energie verlieren würden.
Nachteil von Russischem Roulette: Allerdings wird über den Wahrscheinlichkeitsansatz eine Varianz in die Lösung eingebracht, da zur Skalierung der Photonenenergie anstelle von exakten Werten
für Reflexion und Transmission eine Wahrscheinlichkeit eingesetzt wird, die erst bei großer Anzahl
von Ereignissen gegen den korrekten Wert konvergiert.
5.1.3
Speichern von Photonen
Das Auftreffen eines Photons auf eine diffuse Oberfläche wird als Photonenereignis oder als Spur des
Photons bezeichnet. Diese Photonen, oder besser: Photonenereignisse, werden in einer sogenannten
Photon Map gespeichert. Photon Maps zeichnen sich also NUR an DIFFUSEN Oberflächen ab, nicht
aber an spiegelnden Flächen, denn die Wahrscheinlichkeit dafür, dass ein Photon von einer spiegelnden Fläche direkt durch ein Pixel den Betrachter erreicht, ist identisch null.
Bemerkung 5.3 Um korrekte spiegelnde Reflexion zu erzielen, verfolgt man einen Strahl vom Pixel
in die Spiegelrichtung (Backward Raytracing). Photon Mapping spielt hier praktisch keine Rolle.
Die Wechselwirkung eines Photons mit einer diffusen Oberfläche wird in einer globalen Datenstruktur, der Photon Map gespeichert. Für das emittierte Photon können mehrfache Ereignisse entlang eines
Pfades gespeichert werden. Auch Absorption an einer diffusen Oberfläche wird aufgezeichnet. Die
Anzahl der Photonen in einer Photon Map bezieht sich auf die Anzahl sämtlicher solcher Ereignisse.
Definition 5.2 Eine Photon Map ist eine globale Datenstruktur, die die Position, die eingestrahlte
Photonenenergie und die einfallende Richtung einer Wechselwirkung mit einer diffusen Oberfläche
speichert. Zudem ergänzt man häufig eine Flag zum Sortieren innerhalb eines kd-trees.
Die Struktur einer Photon Map hat folgende Gestalt:
struct photon{
float x, y, z;
// Position
char p[4];
// Power packed in Ward’s RGB-format
char phi, theta;
// compressend incident direction
short flag;
// used in kd-tree
}
88
Abbildung 5.3. Photonenpfade: (a) LDDD mit anschließender Absorption, (b) LSR DR DR und Verlassen der Box,
(c) LST ST D mit anschließender Absorption.
Dabei sind die Raumwinkel φ und θ jeweils in die Länge eines char gepackt.
phi = 255 * (atan2(dx, dy) + PI) / 2 * PI;
theta = 255 * acos(dx) / PI;
Man unterscheidet aus Effizienzgründen drei verschiedene Photon Maps, die in abkürzender Schreibweise die folgenden Ereignisse verzeichnen:
• Kaustische Photon Map: LS + D
• Globale Photon Map: L{S|D|V }∗ D
• Volumenbezogene Photon Map: L{S|D|V }+ V
Die Schreibweise zählt dabei jeweils die Art und Häufigkeit des Ereignisses auf, das in der jeweiligen
Photon Map gespeichert ist. Dabei ist
L = Emission von einer Lichtquelle
S = Spiegelnde Reflexion oder Transmission
D = Diffuse Reflexion oder Transmission
V = Streuung an einem Volumenelement
5.2. PHOTONEN IM RENDERING PASS
89
{x|y|z} eines der Ereignisse
x+ mindestens ein x oder mehrfache Wiederholung von x
x∗ kein x oder mehrfache Wiederholung von x.
In der kaustischen Photon Map sind gezielt Photonen in die Richtung von spiegelnden Objekten verfolgt worden, um das Phänomen der Lichtbündelung möglichst präzise wiederzugeben. Die globale
Photon Map streut die Photonen völlig zufällig in alle Raumrichtungen und würde die Lichtbündelung
nur unzureichend oder erst bei sehr hoher Anzahl von Photonen abbilden können. Streuung an Volumenelementen ist sehr aufwändig und wird nur in den wenigsten Fällen in die Strahlungsabschätzung
im Rendering Pass eingehen.
Abbildung 5.4. Links: Darstellung des Raums mit farbigen Wänden und einer Kugel aus Chrom, einer aus Glas
mit Raytracing ohne Auswertung der Photon Map, rechts: Darstellung der Photonenereignisse als entsprechende
farbige Punkte. Man erkennt in der Photon Map sehr gut die Kaustik als Bündelung weißer Photonenereignise
unter der Glaskugel. Außerdem sind die Ereignisse an der Decke und in den Schatten der Kugeln je nach Nähe
zu einer der farbigen Wände unterschiedlich gefärbt. Spiegelnde Objekte verzeichnen keine Photonenereignisse,
daher wurden sie hier schwarz dargestellt. Wie sich die Photon Map beim Rendern auswirkt, zeigt Abb. 5.5.
Hiermit ist der Photon Tracing Pass abgeschlossen, die Photon Maps sind vorbereitet und der zweite
Schritt, das Rendern mithilfe der Photon Maps beginnt.
5.2
Photonen im Rendering Pass
Die Idee im Rendering Pass besteht darin, die Strahlung unter Berücksichtigung von jeweils n nächsten
Photonen zum Punkt x abzuschätzen.
90
Abbildung 5.5. Bezieht man die globale Photon Map und die kaustische Photon Map in die Berechnungen des
Raytracing ein, ist sowohl die Decke beleuchtet, die Schatten unterschiedlich farbig als auch ein durch Kaustik
hervorgerufenes Glanzlicht unter der Glaskugel zu sehen. Der helle Punkt an der blauen Wand resultiert aus
der Spiegelung der Kaustik an der Glaskugel und dem Transport dieses Lichtpunktes durch die Photonen der
kaustischen Photon Map durch die Glaskugel auf die Wand.
5.2.1
Abschätzung der Strahlung an einer Oberfläche
Die Photon Map stellt eine Repräsentation des eingestrahlten Energieflusses dar. Die Formel für reflektierte Strahlung
Z
Lr (x, ω) =
fr (x, ω 0 , ω)Li (x, ω 0 )|Nx · ω 0 |dω 0
Ωx
berechnet die Abstrahlung in einem Punkt x und in eine Raumrichtung ω aus dem Integral über die
Hemisphäre Ωx aller einstrahlenden Raumrichtungen um x. Der Ausdruck unter dem Integral ergibt
sich aus der einstrahlenden Energie Li je festem Raumwinkel ω 0 , die von der BRDF fr umgelenkt
und mit dem Einstrahlwinkel |Nx · ω 0 | gewichtet wird.
Mit der Beziehung zwischen der Einstrahlung Li und dem hereinkommenden Photonenfluss
Li (x, ω 0 ) =
erhält man
d2 Φi (x, ω 0 )
cos θi dωi0 dAi
91
Z
fr (x, ω 0 , ω)
Lr (x, ω) =
Ωx
d2 Φi (x, ω 0 )
dAi
und daraus schätzt man jetzt die reflektierte Strahlung mit den n nächsten Photonen zum Punkt x ab.
Jedes dieser Photonen hat dabei die Energie ∆Φp (ωp ) und es wird angenommen, dass es die Fläche
in x trifft. Dazu dehnt man eine Kugel um x solange aus, bis sie n Photonen enthält.
Lr (x, ω) ≈
n
X
fr (x, ωp , ω)
p=1
∆Φp (x, ωp )
∆A
Abbildung 5.6. Die nächsten n Photonenereignisse in der Nähe des Punktes x gehen in die Abschätzung ein.
Bemerkung 5.4 Unter der Annahme, dass Oberflächen lokal eben sind, kann man sich auf die Projektion der Kugel in die Ebene, also einen Kreis beschränken. Damit ist
∆A = πr2
und r der Radius der Kugel. Daher gilt verkürzt:
n
1 X
fr (x, ωp , ω)∆Φp (x, ωp )
Lr (x, ω) ≈ 2
πr p=1
Mögliche Fehlerquellen oder die Beeinträchtigung der Genauigkeit hängen von
(a) der Gesamtanzahl der Photonen in der Photon Map oder von
(b) der Anzahl n der Photonen ab, die in die Abschätzung einbezogen werden.
92
Zudem ist die Annahme, dass Oberflächen lokal eben sind, in Ecken und an scharfen Kanten einfach
falsch. Hier werden Photonenereignisse an Wänden für die Berechnung des Bodens einbezogen und
umgekehrt, was zu fehlerhaft weichen Kanten und Farbverläufen führt. Eine Abhilfe für all diese Fehlerquellen besteht über das Gesetz der großen Zahl: Je mehr Photonen in die Abschätzung einbezogen
werden und je mehr Photonen in der Photon Map vorhanden sind, um so genauer ist das Ergebnis der
Näherungsformel.
Im Limes gilt sogar
α
bN c
1 X
fr (x, ωp , ω)∆Φp (x, ωp ) = Lr (x, ω),
lim
N →∞ πr 2
p=1
α ∈]0, 1[
mit der Gesamtanzahl N Photonen in der Photon Map. Im Beweis geht ein, dass x lokal eine zweidimensionale Umgebung hat und die BRDF keine Diracsche Deltafunktion ist (das schließt den perfekten Spiegel aus). Die verschiedenen Grade von unendlich werden über N α kontrolliert, womit garantiert wird, dass die Gesamtanzahl der Photonen der Photon Map schneller gegen unendlich geht, als
die Anzahl der in die Abschätzung einbezogenen. Insgesamt folgert man, dass man hinreichend gute
Ergebnisse erzielen kann, wenn man nur genügend Photonen benutzt.
Bemerkung 5.5 Vergleicht man die Fehlerquellen mit denen aus der Radiosityberechnung (siehe voriges Kapitel), so fällt auf, dass es in finite Elementmethoden komplizierter ist, hinreichende Genauigkeit zu erzielen. Der Fehler hängt dann nämlich (1) von der Auflösung des Gitters, (2) von der
Auflösung der gerichteten Strahlungsenergie und (3) von der Genauigkeit der Simulationsgleichungen ab.
Bemerkung 5.6 Anstelle einer Kugel um x kann man auch ein Ellipsoid oder eine Box oder eine
Scheibe nehmen, um die Photonen für die Abschätzung zu finden. Dadurch kann man zum einen den
Suchalgorithmus beschleunigen, zum anderen erzielt man bessere Ergebnisse in Ecken und Kanten.
Allerdings muss ∆A an die neue Geometrie angepasst werden und man verliert die Vorteile der
Kugelgeometrie, nämlich die einfache Distanzbestimmung und die einfache Projektion.
5.2.2
Filter für die Abschätzung
Wenn die Anzahl der Photonen in der Photon Map zu niedrig ist, wird die Abschätzung an den Kanten
verschwommen. Das ist durchaus manchmal wünschenswert, da es weniger sterile Computerbilder
generiert, aber bei Kaustiken mit scharfen Abgrenzungen ist es unerwünscht. Eine Abhilfe besteht
im Einsatz von Filtern, um näher am Auswertungspunkt x liegende Photonen stärker zu wichten. Da
Photonen auf Oberflächen registriert werden, benötigt man 2D-Filter, wie sie aus der Bildverarbeitung
bekannt sind.
93
Beim Cone-Filter wird jedes Photon in der Abschätzung mit einem Gewicht
wpc = 1 −
dp
kr
multipliziert, wobei dp die Distanz zwischen dem Punkt x und dem Photonenereignis p ist. Der Parameter k ≥ 1 stellt eine charakteristische Filterkonstante und r eine maximale Entfernung dar. Aus
2
im Nenner der Abschätzung:
der 2D-Verteilung ergibt sich ein Normalisierungsfaktor 1 − 3k
Pn
Lr (x, ω) ≈
p=1
fr (x, ωp , ω)∆Φp (x, ωp )wpc
(1 −
2
)πr2
3k
Die Wichtungsfunktion wpg des Gauß-Filters schreibt sich mit den gleichen Termen aber etwas komplizierter, nämlich

wpg = α 1 −
−β
d2
p
2r 2

1−e
,
1 − e−β
wobei die Parameter α, β beispielsweise die Werte α = 0.918 und β = 1.953 annehmen können.
Dieser Filter ist bereits normalisiert und ergibt die Abschätzung
Lr (x, ω) ≈
n
X
fr (x, ωp , ω)∆Φp (x, ωp )wpg .
p=1
Der Variationsansatz (Differential checking) hat sich speziell bei Kaustiken bewährt. Er beruht auf der
Beobachtung, dass sich das Monotonieverhalten der Helligkeit je nach Ort x nahe einer Kante (der
Kaustik) ändert, wenn man den Radius vergrößert und damit die Anzahl der Photonen erhöht, die in
die Abschätzung einbezogen werden:
x außerhalb der Kaustik →
x innerhalb der Kaustik →
monoton wachsend
monoton fallend
Der Grund liegt für einen Punkt außerhalb der Kaustik in einer unproportional erhöhten Anzahl Photonen beim Eintritt des Radius in den Bereich der Kaustik. Umgekehrt wird für einen Punkt innerhalb
der Kaustik die Anzahl der Photonen bei einem Austritt des Radius aus dem Bereich der Kaustik
unproportional erniedrigt.
94
Abbildung 5.7. Das bekannte Cognacglas von Henrik Wann Jensen besteht aus 12000 Dreiecken, die kaustische
Photon Map besteht aus 200000 Photonen und 40 Photonen wurden in der Abschätzung verwendet.
Auf Basis dieser Beobachtung bricht man das Vergrößern des Radius (= Einbeziehung weiterer Photonen in die Abschätzung) ab und nimmt lieber erhöhtes Rauschen im Grenzbereich der Kanten/Kaustik
in Kauf.
5.2.3
Strahlungsabschätzung im Volumenfall
Nebel oder Rauch brechen das Licht je nach Dichte in ganz unterschiedlicher Weise. Hierdurch wird
erst der Lichtkegel auch im Raum sichtbar, der sich sonst nur an einer 2D-Oberfläche zeigt. Der
Qualm einer Zigarette in einem Spotlight oder Bodennebel im Autoscheinwerfer benötigen daher
3D Berechnungen mit sogenannten Participating media. Dazu muss zunächst die Gleichung für die
Strahlungsabschätzung abgeändert werden.
95
Abbildung 5.8. Diese Berechnung der Cornell Box mit Nebel benötigte 100000 Photonen in der globalen Photon
Map, 150000 Photonen in der Volumenmap und 44 Minuten für den Renderprozess.
Z
Lins (x, ω) =
f (x, ω 0 , ω)L(x, ω 0 )dω 0
ZΩ
d2 Φ(x, ω 0 )
dω 0
f (x, ω 0 , ω)
0 dV
σ
(x)
dω
s
Ω
Z
d2 Φ(x, ω 0 )
1
f (x, ω 0 , ω)
=
σs (x) Ω
dV
n
∆Φp (x, ωp0 )
1 X
≈
f (x, ωp0 , ω)
4
σs (x) p=1
πr3
3
=
Dabei bezeichnet Lins (x, ω) die in die Umgebung gestreute (in-scattered) Abstrahlung und σs (x)
den Streukoeffizienten, der anstelle des Produkts aus Einfallswinkels und abstrahlender Fläche im
2D-Oberflächenfall in die Gleichung eingeht.
Der Rechenaufwand, der beim Rendern mit einer solchen Volumenabschätzung nötig wird, ist extrem
groß. Daher versucht man ihn nach Möglichkeit zu vermeiden und nur für spezielle Effekte einzusetzen.
5.2.4
Auffinden der n nächsten Photonen
Um eine Photon Map effizient auszuwerten, sind effektive Strategien nötig:
96
• Durchsuchen von kd-trees (k-dimensionale Bäume)
• Balancieren von kd-trees über Median (= Zentralwert) Ansatz
• max-heap (oder priority queue) Ansatz: Das am weitesten entfernte Photon wird am ehesten
wieder herausgeschmissen, wenn der max-heap erreicht ist.
Bemerkung 5.7 Es empfiehlt sich hierbei immer mit quadrierten Distanzen zu rechnen, das erspart
teures Wurzelziehen. Außerdem kann man den maximal nötigen Suchradius nach oben abschätzen.
Wenn man sich einen Schwellwert Lt für die Abstrahlung vorgibt, erhält man
1
rm =
π
r
n Pmax
Lt
für den ebenen Fall und
r
rm =
3
3 n Pmax
.
16 π 2 σ Lt
im Fall isotrop streuender Volumenelemente.
5.2.5
Auswertung der Strahlungsabschätzung: Rendering
Das Photon Mapping ist eine Erweiterung des Raytracing. Daher wird für das eigentliche Rendern
ein verteiltes Raytracing (Distributed Raytracing) vorgenommen. Die Pixelstrahlung ist dabei das
arithmetische Mittel über verschiedene Einzelabschätzungen.
Bemerkung 5.8 Die Photon Map ist unabhängig von der Betrachterposition! Eine einmal berechnete
Photon Map kann für das Rendern einer Szene aus (a) jeder möglichen Blickrichtung hergenommen
werden und kann (b) für verschiedenste Rendertechniken benutzt werden, z.B. für die Berechnung von
Radiositywerten in Gitterpunkten.
Allgemein gilt, dass für jedes Pixel vom Auge des Betrachters ein Strahl durch das Pixel in die Szene
verfolgt wird (sogenanntes backward raytracing). Die abstrahlende Energie wird hier mit dem Index
o für outgoing bezeichnet. Dann ergibt sich
Lo (x, ω) = Le (x, ω) + Lr (x, ω)
97
die von einem Pixel ausgehende Strahlung als Summe der emittierten Le (x, ω) und der reflektierten
Lr (x, ω) Strahlung. Die reflektierte Strahlung kann jetzt nach der bewährten Formel als Integral aus
der einstrahlenden Energie berechnet werden:
Z
Lr (x, ω) =
fr (x, ω 0 , ω)Li (x, ω 0 )|Nx · ω 0 |dω 0
Ωx
Die BRDF fr wird dabei in einen spekularen und einen diffusen Anteil zerlegt.
fr (x, ω 0 , ω) = fr,s (x, ω 0 , ω) + fr,d (x, ω 0 , ω)
Auch die Einstrahlung Li = Li,l +Li,c +Li,d wird in drei Terme aufgespalten, die direkte Beleuchtung
Li,l (x, ω) durch eine Lichtquelle, die kaustische Beleuchtung Li,c (x, ω), also indirekte Beleuchtung
durch spiegelnde Reflexion, und die indirekte Beleuchtung Li,d (x, ω), bei der wenigstens einmal diffus reflektierte Photonenereignisse berücksichtigt werden.
In der Kombination ergeben sich vier Terme:
Z
fr (x, ω 0 , ω)Li (x, ω 0 )cos θi dω 0
Lr (x, ω) =
Ωx
Z
fr (x, ω 0 , ω)Li,l (x, ω 0 )cos θi dω 0
=
(I)
Ωx
Z
+ fr,s (x, ω 0 , ω)(Li,c (x, ω 0 ) + Li,d (x, ω 0 ))cos θi dω 0
(II)
Ωx
Z
+ fr,d (x, ω 0 , ω)Li,c (x, ω 0 )cos θi dω 0
(III)
Ωx
Z
+ fr,d (x, ω 0 , ω)Li,d (x, ω 0 )cos θi dω 0
(IV)
Ωx
Der erste Term (I) besteht aus der direkten Illumination. Hier geht der direkte Anteil der Lichtquelle
ein. Das sogenannte Raycasting, das nur einen einfachen Strahl von der Lichtquelle auf den betrachteten Punkt wirft, bestimmt die Lokalfarbe an dieser Stelle. Verdeckt ein anderes Objekt diese Lichtquelle aus Sicht dieses Punktes, wird dieser Punkt nicht direkt von dieser Lichtquelle erreicht und der
Term entfällt. Das motiviert das Aussenden sogenannter Schattenstrahlen Shadowcasting von einem
Punkt in Richtung sämtlicher Lichtquellen. Treffen sie auf ein Objekt, das nicht die Lichtquelle ist,
erhalten diese Punkte kein Licht von dieser Quelle. Diesen Ansatz kann man weiter verfolgen und
Shadowphotons berechnen.
Der zweite Term (II) stellt das spekulare oder Glanzlicht dar. Hier wird das Photon Mapping NICHT
eingesetzt!!! Dieses Integral wird mit den Standard Monte Carlo Methoden des Raytracing berechnet.
98
Abbildung 5.9. Skizzen zu den Strahlen des Raytracing und der Auswertung der Photon Map an diesen Stellen,
links die direkte Beleuchtung/Verdeckung (I), rechts die spiegelnde Reflexion OHNE Photon Mapping (II).
Die Funktion fr,s erzeugt dabei einen engen Peak in Spiegelrichtung.
Der dritte Term (III) betrifft das kaustische Integral. Wenn die Anzahl der Photonen in der Caustic
map hoch ist, erzielt man hiermit eine gute Qualität der Abschätzung.
Der vierte Term (IV) berechnet sich aus der vielfach diffusen Reflexion. Eine ungefähre Abschätzung
erfolgt mit der globalen Photon Map, eine genauere Abschätzung bezieht Monte Carlo Methoden des
Raytracing ein.
Abbildung 5.10. Links die Skizze für das kaustische Integral (III), rechts das globale diffuse Photon Mapping (IV).
5.3
Übungsaufgaben
Aufgabe 5.1 Russisches Roulette
Berechnen Sie für eine einfache Szene mit einer Glaskugel und einer Lichtquelle in einer Raumecke
(z.B. die Cornell Box) eine (globale) Photon Map, wobei Sie einzig die einzelnen Photonenereignisse
mit ihren Farbwerten als Punkte in einem OpenGL Programm darstellen.
99
Aufgabe 5.2 BRDF
Eine Bidirectional Reflectance Distribution Function (BRDF) ist die Funktion fr (θi , φi ; θr , φr ), die
sich aus dem Quotienten der reflektierten differentiellen Strahldichte dLr in Betrachterrichtung und
der differentiellen Bestrahlungsstärke dEi aus der Lichtrichtung ergibt. Sie kann mit Gonioreflektometern gemessen oder aufgrund ideller Annahmen für ein Material modelliert werden.
(a) Ein Lambert-Strahler ist das Modell für einen diffus reflektierenden Körper und zeichnet sich
durch folgende Eigenschaften aus:
1. Der Körper absorbiert kein Licht. Das auf den Körper einfallende Licht wird komplett reflektiert.
2. Der Körper erscheint von allen Betrachtungsrichtungen aus gleich hell.
Leiten Sie daraus die BRDF eines Lambert-Strahlers her.
(b) Das Ward Modell von 1992 sieht für isotrope spiegelnde Reflexion die BRDF
tan2 δ
−
e α2
1
fiso (θi , φi ; θr , φr ) = √
cosθi cosθr 4πα2
vor. Anders als das Phong-Modell ist es physikalisch gültig aber trotzdem einfach. Dabei ist α der
Rauhigkeitskoeffizient der isotropen Fläche, δ der Winkel zwischen der Normale N und dem HalfwayVektor H. Leiten Sie daraus eine Formel für faniso (θi , φi ; θr , φr ) mit Rauhigkeitskoeffizienten αx und
αy ab.
(c) Die Faktorisierung einer BRDF lautet
fiso (θi , φi ; θr , φr ) =
n
X
pj (θi , φi )qj (θr , φr )
j=1
Welche Vorteile kann man daraus ziehen? Hinweis: Denken Sie an GPU-Programmierung und Environment-Mapping.
100
Aufgabe 5.3 Maximalradius
Bestimmen Sie für die Rendergleichung mit Photon Mapping einen maximalen Radius rm . Schätzen
Sie dazu die Formel für Lr (x, ω) mit der BRDF eines perfekt diffusen Strahlers und bekannten Maximalwerten (wie maximaler Photonenenergie) sowie einem vorgegebenen Schwellwert von Lt (x, ω)
ab.
(a) Wie lautet die Formel für rm ?
(b) Es sei σ(x) das Streuereignis in einem beteiligten Medium (participating medium). Wie lautet eine
entsprechende Formel für rm bei Streuung an einem Volumen?
Kapitel 6
Nichtphotorealistisches Rendering
Nichtphotorealistisches Rendern (NPR) ist inspiriert durch Stilrichtungen der bildenden Kunst, der
technischen Zeichnung und dem Comic und Zeichentrickfilm. Begonnen hat diese Entwicklung Ende
der achtziger Jahre, als Photorealismus immer mehr ausgereizt war. Ein bekannter erster Kurzfilm
ist Technological Threat von 1988, die erster Veröffentlichung zum Thema war Paint by Numbers:
Abstract Image Representation, SIGGRAPH 90. Langfilme griffen die Technik erst kürzlich auf, so
in Sin City, einer Comic-Verfilmung des Autors Frank Miller (Regie: Robert Rodriguez, 2005) und in
A Scanner Darkly von Richard Linklater (2006) nach dem gleichnamigen Roman von Philip K. Dick.
Der Begriff Nichtphotorealismus ist einer Veröffentlichung von Salesin, Winkenbach, 1994, entnommen.
Abbildung 6.1. Phong Shading versus Toon Shading verdeutlicht die unterschiedliche Zielsetzung.
101
102
6.1
KAPITEL 6. NICHTPHOTOREALISTISCHES RENDERING
Zweidimensionale NPR-Techniken, Bildbearbeitung
Input ist ein Bild oder eine Sequenz von Bildern, Output ist ein stilisiertes Bild oder ein Film. Filterverfahren auf der Basis von Rasterinformation werden in Bildbearbeitungsprogrammen wie gimp oder
Photoshop geführt. Diese sogenannten Artistic Filter versuchen Farbstiftzeichnungen, Frescotechnik,
Pastellbilder oder Wasserfarben zu imitieren. Andere Bildbearbeitungsprogamme wie Impressionist
versuchen den Entstehungsprozess eines Bildes zu imitieren, indem sie zunächst den Bildträger (Untergrund) simulieren und ein mit der Maus (oder anderen Eingabegeräten) zu führendes Werkzeug zur
Auswahl stellen. Nass-in-Nass Techniken bei Aquarellzeichnungen benötigen jetzt Simulationen des
Trocknungsverhaltens und der Diffusion von Farbpigmenten in verschiedenen Schichten (im feuchten
Papier oder im Wasserfilm oder an der Wasseroberfläche; zur korrekten Behandlung muss sogar die
Oberflächenspannung berücksichtigt werden).
Variablen für die Bildbearbeitung sind Strichstärke, -länge und -richtung (Brush strokes), die Anzahl
der Farbtöne, die Größe und Gestalt einzelner Flächenelemente sowie die Art der Begrenzung der
Flächen.
Abbildung 6.2. Die goldene Kugel des NGG-Logos links im Original, dann als Papierschnitt, Untermalung auf
Leinwand, Pastell auf Sandstein und Aquarell auf rauhem Papier.
6.2
Dreidimensionale NPR-Techniken
Der Input hier ist ein 3D-Modell, das computergeneriert, aber auch aus vermaschten Laserscans oder
stereographisch erfassten Bilddaten erzeugt sein kann. Als mögliches Zwischenergebnis wird ein in
seiner 3D-Geometrie verändertes Modell gespeichert. Diese Veränderungen sind entweder
• betrachterabhängig und durch die Projektionen bedingte Deformationen,
• überdimensionierte Detaildarstellungen oder
• angeschnittene Objekte.
Sie richten sich nach der Sichtbarkeit wichtiger Details oder dem Wiedererkennungseffekt einer Abstraktion. Auf dieses Zwischenergebnis wirken nun veränderte Lichtmodelle, die mit den Informationen aus dem Tiefenspeicher oder dem Normalenfeld Silhouetten und Krümmungen der Oberfläche
interpretieren können. Der Output ist wieder ein stilisiertes Bild oder ein Film.
6.3. KONTURLINIEN
103
Anwendungen finden diese Techniken in Konzeptzeichnungen, z.B. für architektonische Entwürfe,
in Bedienungsanleitungen und technischen Zeichnungen, medizinischen Handbüchern oder in Zeichentrickfilmen und Computerspielen.
Häufig wird das 3D-Modell unverändert übernommen und nur beim Rendern auf verfremdende Verfahren zurückgegriffen.
6.3
Konturlinien
Die Umrisslinie ist die einfachste Form der Zeichnung. Diese kann man aus der einfachen Umrandung gewinnen, die als Schattenriss wirklich nur eine geschlossene Linie ergibt. Wie aber kann man
mathematisch eine Silhouette definieren, der ein 3D-Modell zugrunde liegt?
Definition 6.1 Die Silhouette S eines 3D-Objekts ist die Vereinigung aller Punkte xi auf der Oberfläche O, deren Normale ni senkrecht zum Sichtstrahl liegt und deren Krümmung echt positiv (konvex)
ist.
S = {xi ∈ O | Ni · (xi − V ) = 0}
Abbildung 6.3. Eine Silhouette wird von Punkten xi gebildet, die auf der Oberfläche eines Objekts tangential zur
Blickrichtung liegen.
Bemerkung 6.1 In dieser Definition werden Falten nur erfasst, wenn sie lokal echt konvex sind.
Die Definition gilt nur für glatte, unberandete Objekte. Ränder von zweidimensionalen, endlichen
Mannigfaltigkeiten werden nicht erfasst, z.B. eine Kreisscheibe hätte keinen Rand.
6.3.1
Silhouetten mit OpenGL
Die Idee hinter diesem einfachen Algorithmus besteht darin, alle blickabgewandten Polygone als
dickes Drahtgittermodell, alle zugewandten Polygone ausgefüllt mit beliebigen Shadern zu zeichnen.
104
Dieses Verfahren eignet sich gut für sogenannte Polygonsuppe, da es recht robust mit einer großen
Anzahl von Dreiecken zurechtkommt.
glEnable(GL_CULL_FACE);
glCullFace(GL_BACK);
glPolygonMode(GL_FRONT, GL_FILL);
glDepthFunc(GL_LESS);
cgGLBindProgram(cg_vertex_program);
//
cgGLEnableProfile(cg_vertex_profile); //
cgGLBindProgram(cg_fragment_program); //
cgGLEnableProfile(cg_fragment_profile);//
{Zeichne 3D-Objekt}
cgGLDisableProfile(cg_fragment_profile);
cgGLDisableProfile(cg_vertex_profile);
Einbinden
eines Vertexshaders
Einbinden
eines Fragmentshaders
glLineWidth(5.0);
glPolygonMode(GL_BACK, GL_LINE);
glDepthFunc(GL_LEQUAL);
glCullFace(GL_FRONT);
glColor3f(0.0, 0.0, 0.0);
{Zeichne 3D-Objekt}
glPointSize(5.0);
glPolygonMode(GL_BACK, GL_POINT);
{Zeichne 3D-Objekt}
Bemerkung 6.2 (Linienstärke) Die Linienstärke wird bei einer Rastersteigung von −1 < m ≤ 1
senkrecht zum linienrelevanten Pixel bemessen, für die restlichen Steigungen wird sie waagerecht bestimmt. Daher variiert die Stärke der Silhouette mit der Steigung. Das Einfügen von Punkten in gleicher Punktgröße vermeidet hässliche einspringende Ecken beim Zusammentreffen von Linien größerer Stärke. Wenn die Punkte und Linien antialiased gezeichnet werden, wird ebenfalls der störende
Effekt beim Abknicken der Linien vermieden.
6.3.2
Exaktes Verfahren für Dreiecksgitter
Ein exaktes Verfahren für Dreiecksgitter ermittelt für jeden Knoten den Wert
di (xi ) =
ni · (xi − V )
kni k kxi − V k
6.3. KONTURLINIEN
105
und betrachtet dann das Vorzeichen


 1
sgn (di ) =
0


−1
falls di > 0
falls di = 0 .
falls di < 0
Der Fall di = 0 kommt
dabei generisch nicht vor. Aber unabhängig davon genügt es, die Dreiecke
P
zu finden, für die | i sgn (di )| ≤ 2 ist. Das sind genau die Dreiecke mit einem Vorzeichenwechsel.
Abbildung 6.4. Rechts ein Dreiecksgitter. Die darin verlaufende Silhouette führt durch solche Dreiecke, deren
Eckpunkte einen Vorzeichenwechsel für d aufweisen.
Für reguläre Dreiecksgitter, deren Eckpunkte also immer mit den Eckpunkten anderer Dreiecke zusammen treffen, ergibt sich eine Bandstruktur in Form eines Trianglestrips. Für alle Kanten mit einen
Vorzeichenwechsel findet man den Knoten x̃ auf der Silhouette durch lineare Interpolation mit den
Werten d(xj ) = dj und d(xk ) = dk der Eckpunkte. Dann ist d(x̃) = 0.
x̃1 =
|dj |
|dk |
xj +
xk
|dj | + |dk |
|dj | + |dk |
x̃2 =
|dk |
|di |
xi +
xk
|di | + |dk |
|di | + |dk |
Die Silhouette ist jetzt die Verbindungslinie zwischen x̃1 und x̃2 . Da benachbarte Dreiecke gemeinsame Kanten haben, setzt sich die Silhouette durch alle Dreiecke des Strips fort.
106
6.3.3
Bildbasierter Konturalgorithmus
Die Idee eines bildbasierten Konturalgorithmus ist eine Kantendetektion an Rasterbildern. Die relevanten Informationen für Konturen sind (a) im Tiefenspeicher und (b) im Normalenfeld enthalten.
Abbildung 6.5. Kantenextraktion aus einem Tiefenbild und einem Bild mit in Farbwerte umgesetzten Normalenfeld.
Algorithmus
1. Schritt: Erzeuge ein Schwarz-Weißbild des Tiefenspeichers wie in Abb. 6.5 oben links (z.B. mit
glReadPixels(GL DEPTH COMPONENT);)
2. Schritt: Erzeuge ein Bild des Normalenfelds als Farbbild wie in Abb. 6.5 unten links, bei dem die
(x, y, z)-Werte betragsmäßig in (R, G, B)-Werte übersetzt werden.
3. Schritt: Bestimme die Kanten in beiden Bildern.
4. Schritt: Vereinige beide Kantenbilder.
Im ersten Schritt wird die Silhouette komplett erfasst, wenn sich das Objekt von seinem Hintergrund
genügend weit abhebt. Das gilt allerdings nicht für z.B. einen Bilderrahmen an einer Wand. Hierfür
braucht man den Richtungswechsel im Normalenfeld.
Bemerkung 6.3 Dieser Algorithmus zeichnet mehr als nur die reine Silhouette, da auch Sprünge
im Normalenfeld registriert werden. Sie sind hilfreich für die Interpretation eines 3D-Objekts. Da
sie betrachterunabhängig sind, kann man sie auch direkt dem Objekt zuordnen, statt sie aus der
Kantendetektion eines Bildes zu gewinnen.
6.3. KONTURLINIEN
107
Abbildung 6.6. Das vollständige Kantenbild entsteht aus einer Kombination der Kantenbilder aus Tiefenwert und
Normalenfeld, Bilder aus der Dissertation von Aaron Hertzmann.
Bemerkung 6.4 Durch die Kombination beider Kantenbilder werden die jeweiligen Schwächen ausgeglichen.
Bemerkung 6.5 Im allgemeinen Fall ist eine Kante eine hinreichend starke Schwankung der Intensität benachbarter Pixel, die NICHT notwendig mit den geometrischen Eigenschaften der dargestellten Objekte korreliert, sondern eine
• Textur,
• Schattenkante oder
• scharfe Begrenzung von Highlights (bei stark spiegelnden Objekten)
sein kann. Abhilfe kann in der reinen Bildverarbeitung nur durch weitere Bildinformation (z.B. Stereobilder und daraus geschätzte Tiefen oder Normaleninformation) gewonnen werden.
Ein eindimensionales Bild f (x) mit exakt einer Kante bei x = 0 wird mit der Errorfunktion modelliert:
Z
erf(x) =
0
Damit ist
x
2
e−t dt
108
Ir − Il
f (x) =
2
x
+ 1 + Il
erf √
2σ
mit Intensität Ir am rechten und Il am linken Rand. Parameter σ ist der Unschärfeparameter der
Kante.
Mit diesem Idealfall werden nun einzelne Bildzeilen (oder -spalten) verglichen. Dabei wählt man
einen Schwellwert und einen Unschärfebereich, um die tatsächliche Kante auszuzeichnen. Um Rauschen zu entfernen, werden Bilder vorgeglättet.
Bemerkung 6.6 Tatsächlich vorhandene geometrische Kanten können unscharf oder gar nicht erscheinen, wenn sie
• außerhalb des Tiefenschärfebereichs liegen,
• von anderen Objekten verschattet werden oder
• überstrahlt mit einem anderen hellen Objekt oder dem Hintergrund verschmelzen.
Abbildung 6.7. Kantenextraktion mit dem Sobel-Filter, links das Original, rechts das gefaltete Bild.
Ein bis heute gebräuchliches und sehr elaboriertes Verfahren ist die Canny Edge Detection von Canny, Deriche, 1987. Es sucht nach optimalen Glättern und bestimmt Kanten als lokale Maxima im
Gradientenfeld. Damit fällt es in die Klasse der differentiellen Kantendetektoren und ist hier ein Verfahren erster Ordnung, da es auf zentralen Differenzen beruht, die letztlich lokale erste Ableitungen
darstellen.
1
1
Ix (x, y) = − I(x − 1, y) + 0 · I(x, y) + I(x + 1, y)
2
2
1
1
Iy (x, y) = − I(x, y − 1) + 0 · I(x, y) + I(x, y + 1)
2
2
6.4. NICHTPHOTOREALISTISCHES SHADING
109
Mit entsprechenden Filtermasken schreibt man nun
1
2

Ix = − 12 0
1
2
∗ I,


0 ∗I

Iy = 
− 12
Andere Filtermasken sind die sogenannten Sobel Kernel.

−1

Sx =  −2
−1
0
0
0

1

2 ,
1


1
2
1


0
0 
Sy =  0
−1 −2 −1
Die Terme Ix (x, y) und Iy (x, y) sind dann die Faltung mit den Filtermasken und entsprechen ebenfalls
einer Diskretisierung des Grauwertgradienten in Richtung von x bzw. y.
Ix (x, y) = I(x, y) ∗ Sx ,
Iy (x, y) = I(x, y) ∗ Sy
q
|∇I| = Ix 2 (x, y) + Iy 2 (x, y)
Stellt man sich die Faltung als Überlappung zweier Funktionen vor, so erzeugt das Vorzeichen in den
Filtermasken ein Über- oder Unterbewerten des linken (unteren) Pixels. Somit wird eine Kante auf
Pixellevel entweder früher oder später angeschaltet.
(
Edge (x, y) =
1 falls |∇I| ≥ T
0 falls |∇I| < T
Eine Kante liegt vor, wenn ein Schwellwert T (Threshold) überschritten wurde. Auch
die Richtung
des Gradienten θ kann aus diesen Werten abgelesen werden, nämlich θ = arctan IIxy . Für θ = 0
besteht eine senkrechte Kante, die links dunkel, rechts hell begrenzt ist.
6.4
Nichtphotorealistisches Shading
Die Vorteile nichtphotorealistischer Darstellungen bestehen in der Einflussnahme auf das resultierende Bild. Damit sind sie in der Lage, Abstraktionen vom realen Detail zu leisten. Das angestrebte
110
Shading sollte plakativ sein, also nur wenige Abstufungen zulassen. Außerdem empfiehlt sich eine
klare Abgrenzung von der meist schwarz gezeichneten Kontur.
6.4.1
Cel-Shading oder Toon-Shading
Klare Konturen erfordern eine Abgrenzung des Shading, das man daher Cel-Shading nennt (Cel steht
dabei für Contour Enhancing Lines). Seit ungefähr 1999 wird ein an Cartoons (daher Toon-Shading)
erprobtes Shading in Animationsfilmen eingesetzt, seit dem Jahr 2000 fand es auch in Computerspielen Verbreitung.
Abbildung 6.8. Toon Shading verwendet nur wenige Graustufen, die der Objektfarbe überlagert werden.
Ausgangspunkt ist ein konturiertes 3D-Modell. Dann legt man drei bis vier Helligkeitsstufen fest,
z.B. weiß, hellgrau und dunkelgrau. Dabei sollte die dunkelste Stufe deutlich von schwarz entfernt
bleiben, um sich auch in verschatteten Bereichen immer noch deutlich von der Kontur abzuheben.
Die Graustufen werden nun in einer eindimensionalen Textur gespeichert, die dazu dient, den Grauwerten eine (eindimensionale) Ausdehnung zu geben. Über den Winkel (N · L) wird die Schattierung
dem Objekt zugeordnet und mit einer Objektfarbe verrechnet. Highlights werden üblicherweise über
(H · N )n berechnet und weiß dargestellt, ohne Material- oder Lichtfarbe zu berücksichtigen. Dieses
Verfahren ist leicht auf Graphikkarten implementierbar.
6.4.2
Gooch Shading
Das nach den Autoren benannte Gooch Shading verwendet einen der Objektfarbe überlagerten kaltzu-warm Farbgradienten, um die Krümmung wiederzugeben (siehe [GGSC98]).
Wie für das Toon Shading gilt auch hier, dass der Spekularterm aus dem Blinn-Phong Modell übernommen und aus (H·N )n berechnet wird. Die resultierenden Highlights bekommen eine weiße Farbe,
die sich gegen die üblicherweise schwarzen Konturen auch dann gut abhebt, wenn das Highlight an
den Rand einer Fläche stößt.
6.4. NICHTPHOTOREALISTISCHES SHADING
111
Abbildung 6.9. Der unvermeidliche Teapot in Gooch Shading.
Abbildung 6.10. Ein komplizierteres technisches Objekt links in Phong, rechts in Gooch Shading, Bilder von Amy
und Bruce Gooch.
Ein begrenzter Luminanzwert wird jetzt zur Darstellung der Krümmung der Oberfläche genutzt. Dazu
verfährt man wie folgt:
1. Schritt: Wähle eine Objektfarbe, die wenige weiß/schwarz-Anteile hat. In Formelschreibweise
heißt das: Der Schwarzanteil K = min(C, M, Y ) = min(1 − R, 1 − G, 1 − B) = 1 −
max(R, G, B) soll minimal sein, aber auch der Weißanteil W = min(R, G, B).
2. Schritt: Lege einen kalt-zu-warm Farbgradienten fest, beispielsweise von Blau zu Gelb.
3. Schritt: Die kalt-zu-warm Rampe wird zur diffusen Farbkomponente addiert. Dabei wird für jede
Farbe eine Wichtung vorgenommen, damit die resultierende warme und kalte Objektfarbe
nicht ins Weiße überstrahlt.
4. Schritt: Highlights werden über (H · N )n berechnet und weiß eingefärbt.
112
Abbildung 6.11. Verschieden farbige Kugeln, oben in Phong, unten in Gooch Shading. Man erkennt deutlich sowohl
die Objektfarbe als auch die schwarze Silhouette. Bilder von Amy und Bruce Gooch.
Damit ergeben sich die folgenden Formeln für das Gooch Shading:
kfinal
kcool = kblue + α kdiffuse
kwarm = kyellow + β kdiffuse
1 + (N · L)
1 + (N · L)
= 1−
kcool +
kwarm
2
2
Darin ist kcool die Objektfarbe im unbeleuchteten Teil, wobei die gewählte Objektfarbe kdiffuse mit
α gewichtet und zur kalten Farbe der Rampe addiert wird. Genauso ist kwarm die Objektfarbe im
beleuchteten Teil, die aus der Summe einer warmen Farbe und der mit β gewichteten gewählten
1 + (N · L)
∈ [0, 1]. Damit ist kfinal die
Objektfarbe kdiffuse entsteht. Da (N · L) ∈ [−1, 1] liegt
2
lineare Interpolation zwischen beiden Extremen der Objektfarbe und wird im diffusen Farbanteil des
Beleuchtungsmodells eingesetzt. (Anmerkung: Obige Formel ist die korrigierte lineare Interpolation,
die von der (fehlerhaften) Originalveröffentlichung abweicht: dort sind kcool und kwarm vertauscht.)
Eine weitere Möglichkeit ist der Einsatz von einer warmen und einer kalten Lichtquelle, die das in
Grundfarbe gehaltene Objekt aus zwei verschiedenen Richtungen beleuchtet.
Ifinal = ka Ibasic + (N · L1 )(I warm − k1 Ibasic )k2 + (N · L2 )(I cool − k3 Ibasic )k4
Auch hier wird zur Vermeidung von Übersättigung mit geeigneten Parametern k1 , k3 gewichtet.
6.5
Line-Art Rendering
Um Handzeichnungen zu imitieren, wird neben der Konturlinie auch die Schattierung aus Linien,
Schraffuren erzeugt. Die einfachste Art ist die Texturierung einer Fläche mit einer Schraffur von
geeigneter Helligkeit.
6.5. LINE-ART RENDERING
6.5.1
113
Kreuzschraffur
Eine bekannte Zeichentechnik des 19. Jahrhunderts, die aus dem Stahlstich herrührt, ist die Kreuzschraffur. Anders als die in der Kaltnadelradierung eingesetzten Kupferplatten ist Stahl ein härteres
Material, das viel mehr Abzüge des einzelnen Druckstocks als das weiche Kupfer zulässt. Dafür ist
es in der Bearbeitung entsprechend schwieriger, geschwungene Linien entlang einer Krümmung einzusetzen. Man beschränkte sich daher auf Helligkeitsabstufungen aus parallelen Linien in gleichen
Abständen, die einander überlagert wurden. Meist sind es fünf Hellligkeitsstufen, nämlich gar keine
Schraffur (weiß), eine horizontale, darüber eine vertikale und dann zwei diagonale Schraffuren (siehe Abb. 6.12). Traditionell wird die diagonale Schraffur zunächst von links unten nach rechts oben
geführt, gemäß dem Lichteinfall in barocken Handzeichnungen. Die von links oben nach rechts unten
geführte Schraffur blockiert das Licht und wird für die dunkelsten Schatten benutzt. Hier sei auf wahrnehmungspsychologische und kulturell bedingte Unterschiede verwiesen, die sich in starkem Maß in
der Handzeichnung niederschlagen.
Abbildung 6.12. Mit der Kreuzschraffur lassen sich fünf Helligkeitsstufen erstellen. Ganz rechts ist ein Grauwertgradient in Kreuzschraffur dargestellt.
Die Kreuzschraffur ist computertechnisch recht einfach umzusetzen, in dem man die vier nötigen
Texturen periodisch anlegt und die Objekte (z.B. im Fragmentshader) entsprechend der Intensitäten
auf Pixelbasis texturiert.
6.5.2
Krümmungsangepasste Schraffur
Die Federzeichnung ist eine der frühesten Handzeichnungen und lässt durch den weichen Federkiel
das An- und Abschwellen der Linie in natürlicher Weise zu. Seit der Frührenaissance ist die Zeichnung perfektioniert worden. Martin Schongauer (Oberdeutsche Schule), Albrecht Dürer, Leonardo da
Vinci sind die bekanntesten Vertreter, wobei Rembrandt im Barock und Van Gogh für die klassische
Moderne nochmal neue Impulse gesetzt haben.
Mit dem An- und Abschwellen einer gekrümmten Linie kann zugleich Helligkeitsintensität und
Krümmung der Objekte wiedergegeben werden. Um das auch computertechnisch umzusetzen, wird
114
3D-Information benötigt, die man aus Stereoaufnahmen, vermaschten Laserscandaten oder computergenerierten Modellen bezieht.
Die folgende Technik und die Bilder sind dem Artikel Line-Art Rendering von Rössel und Kobbelt
[RK00] entnommen. Die Geometrie wird zunächst mit einem tangentialen Vektorfeld überzogen.
Daraus gewinnt man in jedem Punkt die Hauptkrümmungsrichtungen. Die betragsmäßig kleinere
Krümmung bestimmt das Rückgrat (backbone) eines Objekts. In Richtung der betragsmäßig größeren
Krümmung können nun beliebig viele Linien als Rippen angesetzt werden, um die Gestalt des Objekts
wiederzugeben (siehe Abb. 6.13 links). Dadurch werden aber meist zu dichte Schraffuren erzeugt, die
hellere Bereiche der Objekte nicht adäquat wiedergeben.
Abbildung 6.13. Rückgrat (blau) und Rippen (rot) orientieren sich an den Hauptkrümmungsrichtungen. Für die
zweidimensionale Projektion werden nur wenige charakteristische Referenzlinien benötigt. Rechts ist die Interpolation in der 2D-Projektion dargestellt.
Es empfielt sich daher, die in einer bestimmten 2D-Projektion relevanten Rippen z.B. aufgrund einer
in dieser Projektion deutlichen Krümmungsänderung auszuwählen und die dazwischen zu platzierende Anzahl von Linien abhängig vom zu erzielenden Grauwert zu machen.
Die charakteristische Form einer ausgezeichneten (roten) Rippe wird über einen Punkt auf dem Rückgrat b(0), eine Orientierung E0 und eine Folge von Winkeln αi gegeben. Sei eine zweite, benachbarte
Rippe an dem Punkt b(1) mit Orientierung F0 und eine Folge von Winkeln βi bekannt. Die dazwischen zu zeichnenden Rippen werden gemäß eines Parameters t ∈ [0, 1] interpoliert, wobei p0 = b(t)
ist. Den Punkt p1 findet man nun, indem man die Orienierung G0 linear zwischen E0 und F0 interpoliert. Die Winkel γi sind einfach das arithmetische Mittel aus den Winkeln (1 − t)αi und tβi . Damit
ist

pk (l) = p0 + G0 ± h
P
i
j=1

k−1
cos
γj
X




Pi
sin
i=1
j=1 γj
bei konstanter Schrittweite h der k-te Punkt auf der l-ten Linie. Wenn man jetzt die Anzahl der Rip-
6.5. LINE-ART RENDERING
115
pen entsprechend der gewünschten Intensität bestimmt, kann man mit obiger Formel alle Punkte der
einzufügenden Rippen berechnen. Der Vorzeichenwechsel beruht auf der Annahme von zum Rückgrat symmetrischer Rippen. Dabei entsteht das Problem, dass das Rückgrat selbst gekrümmt ist und
unerwünschte Intensitätsschwankungen auftreten, wenn sich bedingt durch die 2D-Projektion die Rippen einseitig (oder beidseitig) stärker häufen (siehe Abb. 6.15, ganz links). Eine Abhilfe schafft die
Verwendung von Texturen, die aus einem zentralen schwarzen Band und weißen Rändern besteht
(siehe Abb. 6.14). Die Weite w0 der schwarzen Linie wird über den lokalen Grauwert c und eine
maximale Breite w gesteuert.
w0 = (1 − c)w
Damit wird einerseits das An- und Abschwellen der Linie bewirkt, andererseits überlagern die weißen Bänder in Regionen dichter Linien zum Teil andere Linien und erhellen dadurch den Grauwert.
Schwierigkeiten entstehen bei zu starkem Überlapp bei ungünstiger Reihenfolge des Zeichnens (siehe
Abb. 6.15, zweites Bild von links).
Abbildung 6.14. Linientextur mit Schwarz-Weiß-Bändern.
Um hier erneut Abhilfe zu schaffen, wird in jedem Helligkeitslevel zunächst mit dem hellsten, weit
auseinanderliegenden Linienmuster begonnen, um dann je nach Intensität weitere Linien einzufügen.
So entsteht nach und nach eine gleichmäßige Intensität des Grauwerts bei gekrümmter Obefläche
(siehe die drei rechten Bilder in Abb, 6.15).
Abbildung 6.15. Verschiedene Graustufen mit Überlagerungen von Schwarz-Weiß-Bändern.
116
Abbildung 6.16. Endergebnis der krümmungsangepassten Schraffur für einen Motorblock.
6.6
Transformationen der Geometrie
Um Okklusionen zu vermeiden oder künstliche 2D-Übertreibungen zu ermöglichen, muss die 3DGeometrie eines Objekts verändert werden. Die folgenden Bilder zur blickrichtungsabhängigen Geometrieveränderung sind dem Artikel View-Dependent Geometry von Paul Rademacher [Rad99] entnommen.
6.6.1
Blickpunktsänderung
In Comiczeichnungen oder Zeichentrickfilmen ist es zum einfachen Wiedererkennen der Charaktere
nötig, dass wesentliche Merkmale prompt erkannt werden. Ein typisches Beispiel sind die Ohren
einer Micky Maus. Diese flachen, annähernd kreisrunden Gebilde würden in der Seitenansicht zu
antennenartigen Strichen reduziert erscheinen, im Halbprofil würden sie sich teilweise überdecken.
Beides beeinträchtigt das schnelle Erkennen der Figur. Computergenerierte 3D-Modelle werden daher
für verschiedene Blickrichtungen aus einem Basismodell abgeleitet. Dazu geht man wie folgt vor:
6.6. TRANSFORMATIONEN DER GEOMETRIE
117
1. Schritt: Erstelle Referenzzeichnungen für verschiedene Ansichten.
2. Schritt: Transformiere das Basismodell manuell in diese verschiedenen Ansichten und überlagere
es mit den Referenzzeichnungen.
3. Schritt: Deformiere das Basismodell in diese Key Deformationen. Dazu wähle entsprechende
Knoten mit einem Skalierungsfaktor (1 − d/r)2 um einen zentralen Knoten aus.
Abbildung 6.17. Das 3D-Basismodell der Comicfigur wird manuell den Referenzzeichnungen aus verschiedenen
Blickrichtungen angepasst, Bilder von Paul Rademacher.
Dabei ist d die Distanz zum Zentralknoten und r der maximale Radius der Einflussnahme. Dadurch
wird garantiert, dass beim Deformieren der Ohren des Hasen aus Abb. 6.17 alle Nachbarknoten zur
Spitze des Ohrs mitgeführt werden, bis sie aus dem Einflussbereich der Ohrspitze austreten und an
das undeformierte Basismodell harmonisch anschließen können.
Man benötigt ungefähr acht Key Deformationen pro Basismodell, um dazwischen sinnvoll weitere
Blickrichtungen und resultierende Projektionen interpolieren zu können. Die Zahl acht ergibt sich
relativ natürlich, wenn man eine begrenzende Box um das Basismodell legt und durch alle acht Ecken
auf das Zentrum der Figur schaut. Bei der Interpolation geht man dann in folgender Weise vor:
1. Schritt: Finde die drei Punkte i, j, k aus den vorgegebenen Key Viewpoints, die das Dreieck aufspannen, dessen Normale die geringste Abweichung von der aktuellen Blickrichtung hat.
2. Schritt: Gehe zu baryzentrischen Koordinaten (t1 , t2 , t3 ) dieses Dreiecks über.
3. Schritt: Für ein gewichtetes schnelles (α > 1) oder langsames (α < 1) Überblenden werden diese
Koordinaten exponentiell skaliert.
t̃i = ti α /(t1 α + t2 α + t3 α )
118
4. Schritt: Jeder Knoten wird durch eine Menge von N Key Deformationen {ν 1 , ν 2 , . . . , ν N } beschrieben. Der aktuelle Knoten ν errechnet sich nun aus
ν = ν i t̃1 + ν j t̃2 + ν k t̃3 .
.
Abbildung 6.18. Aus acht verschiedenen Ansichten werden drei ausgewählt, deren Dreiecksfläche möglichst orthogonal zur Blickrichtung liegt.
Die baryzentrischen Koordinaten sind dabei als Verhältnisse von Teildreiecksflächen definiert. Seien
A1 , A2 , A3 die Massen in den Eckpunkten des Dreiecks und P das geometrische Zentrum, dann wird
die dem Punkt A1 gegenüberliegende Kante im Verhältnis t3 : t2 geteilt. Entsprechend wird die dem
Punkt A2 gegenüberliegende Kante im Verhältnis t1 : t3 und die dem Punkt A3 gegenüberliegende
Kante im Verhältnis t2 : t1 geteilt. Die entsprechenden Teilungsstrecken durch Punkte und Kanten
schneiden sich in P . Lässt man sie von jedem Eckpunkt aus in P enden, entstehen drei Teildreiecke,
deren Flächenverhältnisse zueinander gerade t1 : t2 : t3 beträgt. Die Eckpunkte des Dreiecks lauten
in baryzentriscen Koordinaten A1 = (1, 0, 0), A2 = (0, 1, 0) und A3 = (0, 0, 1). Damit sind diese
Koordinaten in natürlichr Weise gegeinet, um gewichtete Interpolationen im Dreieck vorzunehmen.
6.6.2
Animationen
In Animationen ist es häufig nötig, einen Bewegungsablauf übertrieben darzustellen, um alle abgewinkelten Gliedmaßen aus entsprechenden Blickrichtungen vollständig sehen zu können. Dazu müssen
für einen gesamten Bewegungszyklus Key Deformationen aus den verschiedenen Blickrichtungen
angefertigt werden. Die Zeitinterpolationen können dabei schon vorberechnet sein. Dreht sich jetzt
während des Bewegungsszyklus die Kamera, so werden zusätzlich betrachterabhängige Interpolationen zur Laufzeit benötigt.
119
Abbildung 6.19. Oben: Blickpunktsänderung und optimale Verzerrung aus Kamerasicht, unten: das 3D-Modell
aus immer der gleichen Perspektive.
6.7
Übungsaufgaben
Aufgabe 6.1 Gooch Shading
Implementieren Sie einen Silhouettenalgorithmus für einfache Objekte, indem Sie abwechselnd mit
Backface und Frontface Culling arbeiten und dabei entsprechend den Polygonmodus von gefüllten
Vordergrundpolygonen zu Linienobjekten (mit Linienstärke 5) wechseln. Ändern Sie außerdem die
Testfunktion für den Tiefenspeicher von glDepthFunc(GL LESS) zu glDepthFunc(GL LEQUAL). Stellen Sie nun drei verschiedene und verschieden farbige, von einer bewegten Lichtquelle beleuchtete
Objekte mit schwarzer Silhouette dar. Durch Drücken der Taste g wird die gleiche Szene in Gooch
Shading, also einer Kalt-Warm Schattierung dargestellt, erneutes Drücken von g stellt das ursprüngliche Phong Modell wieder her.
Aufgabe 6.2 Cross Hatching
Verschaffen Sie sich vier periodische Texturen in der Manier der Kreuzschraffur. Stellen Sie nun drei
verschiedene, von einer zentralen Lichtquelle beleuchtete Objekte mit schwarzer Silhouette und in
Plastik Shading mit grauer (default) Objektfarbe dar. Durch Drücken der Taste c wird die gleiche
Szene mit der Kreuzschraffur texturiert, erneutes Drücken von c stellt das ursprüngliche Phong Modell wieder her. Gehen Sie dabei ähnlich wie beim Toon Shading mit einer Lookup-Table für die fünf
Intensitätsstufen vor.
120
Abbildung 6.20. Blickpunktsänderung bei einer einzelnen Aufnahme eines Bewegungszyklus, oben die optimale
Verzerrung aus Kamerasicht, unten das 3D-Modell aus immer der gleichen Perspektive.
Kapitel 7
Splines
In den 50er Jahren des 20. Jahrhunderts wurde besonders im Automobilbau und im Schiffbau eine exakte Beschreibung von Freiformflächen benötigt. Eng mit der Entwicklung verbunden sind die Namen
Bézier und de Casteljau. Pierre Étienne Bézier, der bei Renault in Frankreich beschäftigt war, wurde
zum Namensgeber des Bézier-Spline. Ebenfalls im französischen Automobilbau bei Citroën hat Paul
de Casteljau über Splines gearbeitet und wurde Namensgeber für einen Konstruktionsalgorithmus.
Abbildung 7.1. Dachflächen eines BMW werden mit dem Programm CATIA (Computer Aided Three-Dimensional
Interactive Application) der französischen Firma Dassault Systèmes entwickelt.
Der Begriff Spline stammt ursprünglich aus dem Schiffbau und ist die englische Bezeichnung für
eine Straklatte, eine lange dünne Latte, die an mehreren Punkten eingespannt wird und sich zwischen
diesen ihren freien Kräften überlassen ausformt. Eingang in die mathematische Wissenschaft und
121
122
KAPITEL 7. SPLINES
erste Erwähnung in einer Veröffentlichung fand der Begriff 1946 durch Isaac Jacob Schoenberg. Das
praktische Vorgehen im Schiff- und Karosseriebau ist geprägt durch die Kontrolle des Prototypen
unter Streifenlicht: Man dreht das Objekt in einer Halle, deren Decke mit Neonröhren dicht besetzt ist.
Hier wird auch der enge Zusammenhang zur Computergraphik deutlich. Eine glatte Freiformfläche
wird über den Grad der Differenzierbarkeit in jedem Punkt und damit über die Eigenschaften des
Tangentialfelds erreicht. Das Tangentialfeld an eine Fläche ist über das orthogonale Normalenfeld
leicht sichtbar zu machen, denn der Term (L · N ) gibt das diffuse, der Term (H · N )n gibt das
Highlight wieder. Sprünge im Tangentialfeld stellen auch Sprünge im Normalenfeld dar. Notwendig
für eine auch an Wendepunkten (von positiver zu negativer Krümmung) glatte Fläche ist zweifach
stetige Differenzierbarkeit (oder C 2 Stetigkeit) und damit ein kubischer Spline.
Definition 7.1 Ein Spline n-ten Grades ist die Parametrisierung einer Mannigfaltigkeit (Kurve, Fläche), deren Koordinatenfunktionen stückweise aus Polynomen mit maximalem Grad n zusammengesetzt sind. Die Gestalt der Polynome wird von Kontrollpunkten bestimmt.
7.1
Splinekurven
Zunächst beschränken wir uns auf ebene Splines, wobei sich der Ansatz auf den Rn einfach übertragen
lässt, da jede Koordinatenfunktion mit dem gleichen Parameter t parametrisiert werden kann.
Betrachtet man nun eine Folge von Kontrollpunkten Pi ∈ R2 , so besteht das Ziel darin, diese Kontrollpunkte durch eine Funktion S : R → R2 zu interpolieren (d.h. die von der Funktion beschriebene
Kurve läuft durch die Punkte) oder zu approximieren (die Funktion nähert die Folge der Kontrollpunkte). Ein interpolierender oder approximierender Spline ist stückweise aus Polynomen zusammengesetzt und wird so konstruiert, dass er die geforderten Eigenschaften erfüllt.
Bemerkung 7.1 Viele Versuche im CAD sind motiviert durch die an S gestellten gewünschten Eigenschaften, interpolierend, approximierend, hinreichend glatt oder uniform (gleiche Abstände der
Kontrollpunkte zueinander) zu sein.
Sei f (t) = (x(t), y(t)). Dann kann man die Koordinatenfunktionen x und y mit den Kontrollpunkten
Pi = (xi , yi ) komponentenweise darstellen als
X
x(t) =
bi (t)xi
i
y(t) =
X
bi (t)yi
i
Werden die Basisfunktionen bi so gewählt, dass sie lokalen Träger haben (d.h. nur lokal von Null
verschieden sind), beschränkt sich der Einfluss, den ein Kontrollpunkt Pi auf die Kurve hat, auf eine
kleine Umgebung dieses Kontrollpunkts. Die Stetigkeit von f ergibt sich aus der Stetigkeit der bi .
Einen weichen Kurvenverlauf erhält man, wenn die bi hinreichend glatt sind.
7.1. SPLINEKURVEN
7.1.1
123
Kubisch hermitesche Splines
Eine wichtige Rolle spielen kubisch hermitesche Splines, wobei jedes Polynom auf dem Intervall
t ∈ [0, 1] von zwei Kontrollpunkten P0 , P1 und zwei Kontrolltangenten mit Steigung m0 , m1 bestimmt
wird. Diese interpolierenden Splines sind von der Form
f (t) = (2t3 − 3t2 + 1)P0 + (t3 − 2t2 + t)m0 + (−2t3 + 3t2 )P1 + (t3 − t2 )m1
= h00 (t)P0 + h10 (t)m0 + h01 (t)P1 + h11 (t)m1
mit den vier in obiger Gleichung aufgeführten hermiteschen Basisfunktionen {hij , i, j ∈ {0, 1}}.
Abbildung 7.2. Die vier hermiteschen Polynome vom Grad 3 auf dem Intervall [0, 1].
Hat man nun eine beliebige Menge von Kontrollpunkten {Pk , k = 1, . . . , n}, ordnet man dieser einen
Knotenvektor (xk ) zu, der die Reihenfolge und die parametrisierten Abstände der Punkte zueinander
festlegt. Die Interpolation dieses Datensatzes (xk , Pk ) für k = 1, . . . , n geschieht zwischen je zwei
Punkten Pk , Pk+1 , indem man die räumliche Schrittweite h = xk+1 − xk auf dem Knotenvektor und
den Parameter t = (x − xk )/h dem Intervall anpasst. Ein Punkt f (t) ergibt sich jetzt aus
f (t) = h00 (t)Pk + h10 (t)h mk + h01 (t)Pk+1 + h11 (t)h mk+1 ,
wobei die Steigung jeweils mit der Schrittweite h multipliziert werden muss. Stimmen nun die Tangenten in den jeweiligen End- und Anfangspunkten überein, erhält man einen interpolierenden Spline
dritten Grades für eine beliebige Anzahl von Kontrollpunkten. Einfachste Bedingung an die Tangente,
die auch für nicht uniforme Knotenvektoren stimmt, ist die finite Differenz mit
124
KAPITEL 7. SPLINES
mk =
Pk − Pk−1
Pk+1 − Pk
+
.
2(xk+1 − xk ) 2(xk − xk−1 )
Zu den kubisch hermiteschen interpolierenden Splines zählen aber auch die Kardinalsplines mit
mk = (1 − c)
Pk+1 − Pk−1
2
mit c ∈ [0, 1[ und als einfachster Spezialfall die Catmull-Rom Splines mit c = 0.
Bemerkung 7.2 Die Tangentialbedingung bedeutet beispielsweise für den Kardinalspline, dass er
Rundungen nur mit einer großen Anzahl von Punkten gut nähern kann, da er bei starkem Richtungswechsel zum Überschießen neigt.
7.1.2
Bézier-Splines
Bézier-Splines sind approximierende Splines, die allerdings ihren Anfangs- und Endpunkt interpolieren. Sie setzen die Bernsteinpolynome als Basis ein. Diese Polynome wurden 1911 von Sergei
Natanowitsch Bernstein für den konstruktiven Beweis des Weierstraß’schen Approximationssatzes
entwickelt.
Definition 7.2 Bernsteinpolynome Bi,n sind für alle 0 ≤ i ≤ n definiert als
Bi,n : R → R
n i
t 7→
t (1 − t)n−i
i
und werden üblicherweise auf dem Intervall [0, 1] betrachtet. Für ein beliebiges Intervall [a, b] verallgemeinert sich die Formel zu
[a,b]
Bi,n : R → R
1
t →
7
(b − a)n
n
(t − a)i (b − t)n−i .
i
Wichtige Eigenschaften, die man zum Teil direkt aus Abb. 7.3 ablesen kann, sind die Basiseigenschaft, die Positivität, die Partition der Eins und die Symmetrie.
Basis:
Die Bernsteinpolynome {Bi,n : 0 ≤ i ≤ n} sind linear unabhängig und bilden eine
Basis vom Raum Πn der Polynome vom Grad kleiner gleich n.
7.1. SPLINEKURVEN
125
Abbildung 7.3. Die sechs Bernsteinpolynome vom Grad 5 auf dem Intervall [0, 1].
Positivität: Alle Bi,n sind auf dem Einheitsintervall positiv, Bi,n (t) > 0 ∀ t ∈ ]0, 1[.
Partition der Eins: Sie bilden eine Zerlegung der Eins, also
n
n X
X
n i
Bi,n (t) =
t (1 − t)n−i = 1.
i
i=0
i=0
Symmetrie: Zu jedem Basispolynom gibt es ein an der Achse t = 0.5 gespiegeltes Basispolynom
Bi,n (t) = Bn−i,n (1 − t).
Es gibt zahlreiche Java-Applets, um sich die verschiedenen Splines und die Manipulationsmöglichkeiten anzeigen zu lassen. Eine empfehlenswerte Webseite für Bézier-Splines befindet sich unter
http://www.gris.uni-tuebingen/edu/projects/grdef/applets/bezier/html/index.html.
7.1.3
Konstruktionsalgorithmus nach Casteljau
Der Bézier-Spline geht durch den Anfangs- und Endpunkt A und B und approximiert die dazwischen
liegenden Kontrollpunkte. Ein Punkt C auf der Kurve ist dabei eine affine Kombination aus den
Kontrollpunkten.
C = tA + (1 − t)B
t ∈ [0, 1[
Werden nur zwei Punkte angegeben, ist die Kurve die (lineare) Verbindung und der Spline hat den
Grad eins. Der Konstruktionsalgorithmus von Casteljau sieht nun vor, dass beim Einfügen eines weiteren Kontrollpunkts der Linienzug jeweils bis zum Parameter t durchlaufen wird, um eine neue
126
KAPITEL 7. SPLINES
Strecke zwischen den Geraden einzufügen, die den Punkt auf der Kurve ebenfalls bei t bezeichnet.
Dabei erhöht sich der Grad jeweils um eins.
Bemerkung 7.3 Ein Bézier-Spline vom Grad n benötigt n+1 Kontrollpunkte, geht durch den Anfangsund Endpunkt und approximiert die dazwischenliegenden n − 1 Punkte.
Abbildung 7.4. Casteljau Algorithmus mit zugehörigen Bernsteinpolynomen links für drei und rechts für vier
Kontrollpunkte.
Es wird deutlich, dass beim Einfügen eines neuen Punktes der Grad des Splines automatisch zunimmt.
Die Koordinaten des Punktes wirken sich auf die gesamte Kurve aus. Will man einen festen Grad n
und beliebig viele Punkte vorgeben, müsste man die stückweise konstruierten Bézier-Kurven in ihren
Endpunkten hinreichend glatt, nämlich C n−1 , verkleben, was mit dem Ansatz der Bernsteinpolynome
als Basis unnötig kompliziert ist.
7.1.4
B-Splines
Will man den Grad des Splines beschränken und dennoch eine glatte Kurve durch beliebig viele
Kontrollpunkte bestimmen, muss man die Auswirkung der einzelnen Basisfunktionen in natürlicher
Weise begrenzen. Isaac Jacob Schoenberg hat den Begriff B-Spline (für Basis-Spline) geprägt und
über das Faltungsintegral motiviert, Carl de Boor hat 1978 die algorithmische und numerisch stabile
Konstruktion der Basis geliefert. Die in besonderer Weise konstruierte Basis hat einige Eigenschaften,
die man auch bei subdivision surfaces benötigt.
Definition 7.3 Für einen gegebenen Knotenvektor aus m + 1 aufsteigend sortierten Werten ti ∈ [0, 1]
des Einheitsintervalls
0 ≤ t0 ≤ t1 ≤ · · · ≤ tm ≤ 1
7.1. SPLINEKURVEN
127
Abbildung 7.5. Maßgeblich an der Entwicklung von Splines beteiligt waren links: Pierre Étienne Bézier (1910–
1999), mitte: Isaac (Iso) Schoenberg (1903–1990) und rechts: Carl de Boor (* 1937).
ist ein B-Spline vom Grad n eine parametrisierte Kurve
f : [tn , tm−n [ →
t
7→
R2
m−n−1
X
bi,n (t) Pi
i=0
mit m − n Kontrollpunkten {P0 , . . . , Pm−n−1 } und rekursiv definierten Basispolynomen
(
1 für tj ≤ t < tj+1
bj,0 (t) :=
0 sonst
bj,n (t) :=
t − tj
tj+n+1 − t
bj,n−1 (t) +
bj+1,n−1 (t).
tj+n − tj
tj+n+1 − tj+1
Für identische Knoten tj ≡ tj+1 wird bj,0 (t) ≡ 0 und es reduziert sich bj,1 zu
bj,1 (t) :=
tj+2 − t
bj+1,0 (t).
tj+2 − tj+1
Was an dieser Definition gegenüber der Bézierkurve auffällt, ist dass man den Grad vorschreiben und
beliebig viele Kontrollpunkte entlang des Splines positionieren kann, solange man einen Kontrollvektor zur Verfügung stellt, der die Summe aus der Anzahl der Kontrollpunkte und dem geforderten
Grad um mindestens eins übersteigt. Es fällt weiter auf, dass der B-Spline nicht auf dem gesamten
Intervall [t0 , tm [ definiert ist, sondern nur auf [tn , tm−n [.
Definition 7.4 Wenn die Knoten das Intervall zur Parametrisierung der Kurve äquidistant unterteilen, heißt der B-Spline uniform, sonst wird er nichtuniform genannt.
Ein offen uniformer B-Spline wiederholt den ersten und letzten Knoten entsprechend der Gradzahl,
also (n + 1)mal, um den Spline bis an diese Punkte heranzuführen. Dieser offen uniforme B-Spline,
128
KAPITEL 7. SPLINES
bei dem die Anzahl der Kontrollpunkte den Grad um genau eins übersteigt, degeneriert zu einem
Bézier-Spline.
Abbildung 7.6. Die Veränderung des Knotenvektors bei vier identischen Kontrollpunkten zeigt sich in der Ausdehnung des Trägers und der Basisfunktionen: Links ein kubischer B-Spline mit äquidistantem Knotenvektor, rechts
ein zum Bézier-Spline degenerierter B-Spline mit (0, 0, 0, 0, 1, 1, 1, 1) als Knotenvektor.
Beispiel 7.1 Für einen kubischen Spline vom Grad n = 3 benötigt ein Bézier-Spline vier Kontrollpunkte. Daher muss der Knotenvektor für einen B-Spline wegen m−3 = 4 ⇒ m = 7, also m+1 = 8
die Länge acht haben. Der dazugehörige offen uniforme Knotenvektor auf dem Einheitsintervall ist
(0, 0, 0, 0, 1, 1, 1, 1).
Bemerkung 7.4 Die Länge des Knotenvektors ergibt sich aus dem gewünschten Grad n des B-Splines
und der Anzahl der Kontrollpunkte k = m − n ⇔ m + 1 = k + n + 1. Da die Anzahl der Kontrollpunkte den Grad um mindestens eins übersteigen muss, ist die Länge des Knotenvektors mindestens
2n + 2.
Wie man im linken Teil der Abb. 7.6 sieht, besteht die Basis eines uniformen B-Spline für einen
gegebenen Grad n aus m − n (= Anzahl der Kontrollpunkte) identischen, verschobenen Kopien. Alle
diese Kopien haben lokalen Träger, der sich über ]tj , tj+n+1 [ erstreckt. Dadurch bleibt der Einfluss
jedes Kontrollpunkts Pi lokal begrenzt und richtet sich nur nach dem Grad des gewünschten Splines.
Die sogenannten Blendfunktionen sind auf jedem Intervall zwischen zwei Knoten gleich (siehe den
rechteckig hervorgehobenen Bereich zwischen i3 und i4 im linken Teil von Abb. 7.6). Es sind n + 1
disjunkte Abschnitte einer Kopie dieser Basisfunktion. Mit ihnen lässt sich der i-te Abschnitt des
kubisch uniformen Splines in Matrixform schreiben als

fi (t) = [t3 t2

−1 3 −3 1
Pi−1



1
3 −6 3 0   Pi
t 1] 

3 0   Pi+1
6 −3 0
1
4
1 0
Pi+2




für t ∈ [0, 1[,
wobei der allen gemeinsame Träger ]tj+n , tj+n+1 [ der Einfachheit halber mit dem Einheitsintervall
identifiziert wird. Es wirken sich hier die zentral um den Punkt Pi (für n gerade) oder die Punkte
7.1. SPLINEKURVEN
129
Pi , Pi+1 angeordneten n + 1 Punkte aus. Hier wird nochmal deutlich, dass der Knotenvektor keinen direkten Zusamenhang mit den Kontrollpunkten sondern eher mit den Basisfunktionen hat. Ein
nichtuniformer Spline kann sukzessiv kleiner werdende Intervalle nutzen, um Kontrollpunkte zu interpolieren.
Allgemein kann man die uniformen bj,n auch schreiben als
bj,n (t) = bn (t − tj ),
j = 0, . . . , m − n − 1
und nicht rekursiv sondern direkt ermitteln als
n+1
n+1X
bn (t) :=
ai,n (t − ti )n+
n i=0
mit
ai,n =
n+1
Y
1
.
t
l − ti
l=0,l6=i
Dabei bezeichnet (t − ti )n+ die positive Potenzfunktion (negative Teile werden abgeschnitten).
Definition 7.5 Ein Polygonzug durch die Kontrollpunkte oder de Boor Punkte wird de Boor Polygon
genannt.
7.1.5
Konstruktion der Basisfunktionen
Um die Basisfunktionen Bi der B-Splines zu konstruieren, bedient man sich der Faltung, da durch die
Integration die gewünschten Eigenschaften ganz unterschiedlicher Funktionen auf das Faltungsprodukt übertragen werden. Das Faltungsprodukt zweier Funktionen f und g ist definiert als
Z
f ∗ g (t) := f (s)g(t − s)ds.
Sei nun B0 : R → R die charakteristische Funktion auf [− 21 , 12 [
(
1 für −
B0 (t) :=
0 sonst
1
2
≤t<
1
2
mit lokalem Träger, nämlich genau dem Einheitsintervall. Nun erhält man B1 durch Faltung von B0
mit sich selbst.
Z
B1 (t) := B0 ∗ B0 (t) = B0 (s)B0 (t − s)ds
War B0 noch unstetig an den Stellen − 21 und 12 , so ist B1 stetig und ist eine sogenannte Hutfunktion mit
einem Maximum bei B1 (0) = 1 und einem Träger, der aus dem Intervall ] − 1, 1[ besteht. Faltet man
130
KAPITEL 7. SPLINES
nun B1 mit B0 so erhält man eine einmal stetig differenzierbare Funktion B2 mit einem Maximum
bei b2 (0) < 1 und einem Träger ] − 32 , 32 [. Allgemein gilt
Z
Bl (t) := Bl−1 ∗ B0 (t) =
Bl−1 (s)B0 (t − s)ds,
, l+1
[
wobei die Funktionen Bl alle gerade Funktionen sind und der Träger aus dem Intervall ] − l+1
2
2
besteht. Eine wichtige Eigenschaft dieser Konstruktionsmethode ist, dass man mit jeder Faltung einen
zusätzlichen Grad in der Differenzierbarkeit gewinnt. Wenn eine Funktion f k-mal stetig differenzierbar ist, also f (t) ∈ C k , dann ist f ∗ B0 (t) ∈ C k+1 . War die Funktion B1 (t) ∈ C 0 , also stetig, so ist
B2 (t) ∈ C 1 , also stetig differenzierbar. Für die Funktion Bn gilt damit Bn (t) ∈ C n−1 .
Die Basisfunktionen Bl werden zentrierte Kardinal B-Splines genannt, ein Ausdruck, der auf Schoenberg zurückgeht. Die Funktionen bn erhalten wir nun aus einem der Bn durch Verschieben und Stauchen
bj,n (t) = bn (t − tj ) = Bn (m(t − tj+ n+1 )).
2
7.1.6
Verfeinerbarkeit von B-Splines
Eine wichtige Eigenschaft der B-Splines ist ihre Verfeinerbarkeit. Diese Eigenschaft ist es, die BSplines mit Subdivisionsalgorithmen eng verbindet. Man versteht darunter, dass man neue Kontrollpunkte so einfügen kann, dass sich die durch den B-Spline beschriebene Kurve nicht ändert. Die oben
konstruierten Basisfunktionen erfüllen die Verfeinerungsgleichung
n+1 1 X n+1
Bn (2t − k).
Bn (t) = n
2 k=0
k
Eine B-Spline Basisfunktion kann also als Summe über gestauchte und verschobene Kopien von sich
selbst geschrieben werden. Eine Anleitung zum Beweis dieser wichtigen Eigenschaft wird in Aufgabe
7.2 gegeben.
Abbildung 7.7. Die (blaue) Hutfunktion B1 (t) kann als Linearkombination aus gestauchten und verschobenen (rot
gestrichelten) Hutfunktionen 12 B1 (2t) + B1 (2t − 1) + 12 B1 (2t − 2) dargestellt werden.
7.1. SPLINEKURVEN
7.1.7
131
Subdivision für Spline-Kurven
Betrachtet man einen (uniformen) B-Spline in der Darstellung
X
f (t) :=
Bn (t − i) Pi
i
und es sei P der Vektor aus Kontrollpunkten um einen zentralen Punkt P0
 . 
..


 P−1 




P
P= 0


 P1 


..
.
und Bn (t) der Vektor aus Basisfunktionen
Bn (t) = [. . . , Bn (t + 2), Bn (t + 1), Bn (t), Bn (t − 1), Bn (t − 2), . . .] ,
so kann man die Kurve f auch schreiben als
f (t) = Bn (t)P.
Der neue Vektor Bn (2t) ist durch die Verfeinerungsgleichung motiviert
Bn (2t) = [. . . , Bn (2t + 2), Bn (2t + 1), Bn (2t), Bn (2t − 1), Bn (2t − 2), . . .]
und fasst doppelt so viele Elemente wie Bn (t). Jetzt stellt man über eine Matrix S den Zusammenhang
Bn (t) = Bn (2t)S
her. Die Einträge der Matrix S sind durch die Verfeinerungsgleichung
!
1 n+1
S2i+k,i = sk = n
2
k
gegeben, wobei n den Grad der Basisfunktionen bezeichnet. Die Kurve f lässt sich nun schreiben als
f (t) = Bn (t)P = Bn (2t)SP.
Wie man sieht, geht man mit der neuen Basis von den alten Kontrollpunkten P auf die neuen Kontrollpunkte SP über, verändert aber die beschriebene Kurve nicht. Sie wird nur mit doppelt so vielen
Basisfunktionen beschrieben, deren Träger jeweils halb so groß sind und die doppelt so schnell durchlaufen werden.
132
KAPITEL 7. SPLINES
Diesen Schritt kann man beliebig oft wiederholen.
f (t) =
=
..
.
Bn (t)P0
Bn (2t)P1
Bn (2t)SP0
=
= Bn (2j t)Pj = Bn (2j t)S j P0
Dabei gibt der hochgestellte Index j an dem Kontrollpunktevektor Pj das Level der Verfeinerung an.
Für die Beziehung zwischen zwei aufeinanderfolgenden Subdivisionslevel ergibt sich
Pj+1 = SPj .
Betrachtet man nun gesondert die Punkte mit geradem Index (die den alten Kontrollpunkten aus
Pj entsprechen) und die Punkte mit ungeradem Index (Punkte, die in Pj+1 durch Verfeinerung neu
hinzugekommen sind), so erhält man
X
X
P2ij+1 =
S2i,l Plj =
s2(i−l) Plj
l
l
für die geraden und
j+1
=
P2i+1
X
l
S2i+1,l Plj =
X
s2(i−l)+1 Plj
l
für die ungeraden Knoten. Für lineare Splines sind die Punkte mit geradem Index identisch mit den
Punkten des vorhergehenden Levels und die neuen Punkte liegen immer mittig zwischen den alten
Punkten. Für interpolierende Splines gilt ebenfalls, dass einmal auf dem Spline befindliche Punkte
identisch bleiben. Im approximierenden Fall (also für alle B-Splinebasen vom Grad n ≥ 2 sind alle
Punkte des Levels j + 1 eine Linearkombination aus den Punkten des Levels j, also auch die mit
geradem Index, und also gilt P2ij+1 6= Pij .
Abbildung 7.8. Ein Linienzug mit anschließenden Verfeinerungsstufen für eine kubische (approximierende) BSplinebasis.
Bemerkung 7.5 Wenn der Prozess der Verfeinerung wiederholt wird, erhält man eine immer dichter
werdende Folge von Kontrollpunkten, die gegen die Spline-Kurve konvergiert. Der Abstand der Kontrollpunkte zur Kurve nimmt dabei um einen konstanten Faktor pro Verfeinerungsschritt ab. Schon
nach wenigen Schritten wird es schwer, die Kontrollpunkte von der Kurve zu unterscheiden. Darin besteht auch der Sinn der Verfeinerung: Statt die Punkte auf der Kurve mit den entsprechenden
Splinebasen höheren Grades aus wenigen Kontrollpunkten zu berechnen, verfeinert man hinreichend
häufig und interpoliert die Punkte linear.
7.1. SPLINEKURVEN
133
Beispiel 7.2 Bei kubischen Splines (Grad 3) ergibt sich für die Einträge der Subdivision Matrix
1
s0 = ,
8
4
s1 = ,
8
6
s2 = ,
8
4
s3 = ,
8
1
s4 = .
8
Für die geraden Knoten ergibt sich so
6
1 j
1 j
+ Pij + Pi+1
.
P2ij+1 = Pi−1
8
8
8
Für die ungeraden ergibt sich
1
1 j
j+1
P2i+1
= Pij + Pi+1
.
2
2
Mit zentralen fünf Kontrollpunkten des Levels j kann man fünf neue Punkte des nächsten Levels j + 1
ganz einfach über Matrixmultiplikation gewinnen.
 j+1 

 j 
1 6 1 0 0
P−2
P−2
 j+1 

 j 
 P−1 
 0 4 4 0 0   P−1 




1
 j+1 

 j 
 P0  =  0 1 6 1 0   P0 




8
 P j+1 
 0 0 4 4 0  Pj 
1
1





j+1
j
P2
P2
0 0 1 6 1
7.1.8
Nichtuniforme rationale B-Splines
Nichtuniforme rationale B-Splines (NURBS) werden aus den einfacheren uniformen nichtrationalen
B-Splines abgeleitet, die wir im vorigen Abschnitt ausführlich behandelt haben. Wenn man zusätzlich
Gewichte wi einfügt, kann man den Spline für wi > 1 stärker an einen Punkt Pi heranführen (oder für
0 > wi > 1 den Einfluss mindern) als im ungewichteten Fall. Weniger intuitiv (aber genauso richtig)
kann man die Gewichte auch den Basisfunktionen zuordnen, da es genauso viele Basisfunktionen
wie Kontrollpunkte gibt. Lokal allerdings ist die Anzahl der von null verschiedenen Basisfunktionen
immer um eins größer als der Grad des Splines. Letztlich erzeugt man diese Wichtung auch durch ein
nicht uniformes Unterteilen des Knotenvektors. Dadurch werden ebenfalls einzelne Basisfunktionen
gegenüber den benachbarten Basisfunktionen stärker oder schwächer bewertet. Erstaunlicherweise
2
2
aber können Kreise oder Ellipsen (in Koordinaten xa2 + yb2 = 1) und Hyperbeln (in Koordinaten
2
x2
− yb2 = 1) nur schlecht von Splines approximiert werden. Ihre Koordinatendarstellungen legen
a2
nahe, sie als rationale Splines darzustellen, also Nennerpolynome aus gewichteten Basisfunktionen
zuzulassen.
Definition 7.6 Die rationalen B-Spline Basisfunktionen Ri,n errechnen sich aus den B-Spline Basisfunktionen bi,n über
wi bi,n (t)
Ri,n (t) = Pk−1
.
j=0 wj bj,n (t)
134
KAPITEL 7. SPLINES
Eine NURBS-Kurve ist die Summe der mit rationalen B-Spline Basisfunktionen Ri,n gewichteten k
Kontrollpunkte {P0 , . . . , Pk−1 }
k−1
X
f (t) =
Ri,n (t)Pi ,
i=0
wobei der Parameter t ∈ [a, b[ einen monoton steigenden Knotenvektor
T = { a, . . . , a , tn+1 , . . . , tm−n−1 , b, . . . , b }
| {z }
| {z }
n+1
n+1
der Länge m + 1 = k + n + 1 durchläuft.
Bemerkung 7.6 Gewichte an den einzelnen Knoten verändern bereits den Einfluss der Punkte. Dennoch können NICHTrationale Splines nur schlecht Kreise und Kegelschnitte approximieren. Eine Abhilfe schaffen rationale B-Splines mit Zähler- und Nennerpolynom von der Form
k−1
X
f (t) =
wi bi,n (t) Pi
i=0
k−1
X
=
p(t)
.
q(t)
wi bi,n (t)
i=0
Wenn die gewichteten Basisfunktionen wieder eine Partition der Eins darstellen, entspricht der rationale wieder dem einfachen B-Spline.
7.2
Flächen als bivariate Splines
Die an Kurven dargestellte Theorie lässt sich natürlich auch auf Flächen ausdehnen, wobei die Parametrisierung über einem Rechteck statt einem Intervall geschieht, um den zwei linear unabhängigen
Raumrichtungen auch (bivariate) unabhängige Krümmungen zuordnen zu können.
Steven Anson Coons war einer der Pioniere der Computergraphik und Lehrer von Ivan Sutherland
(dessen Dissertation als Beginn der interaktiven Computergraphik gilt). Mit seiner analytischen Metode zur Berechnung der Ränder einer doppelt gekrümmten Oberfläche ist er vom Einheitsquadrat
ausgegangen und hat mit den Monomen bis Grad sieben jede beliebige Fläche approximieren können.
Die sogenannten Coons Pflaster stellen die grundlegende Formulierung zur Oberflächenbeschreibung
interpolierender oder approximierender Flächen dar. Es wundert daher nicht, dass der Steven A. Coons Award die höchste Auszeichnung auf dem Gebiet der Computergraphik ist, die alle zwei Jahre
auf der ACM SIGGRAPH vergeben wird, Preisträger waren u.a. Sutherland, Bézier, Evans, van Dam,
Catmull, Foley, Blinn, Hanrahan.
7.2. FLÄCHEN ALS BIVARIATE SPLINES
7.2.1
135
NURBS-Flächen
In vielen CAD-Werkzeugen speziell im Karosseriebau werden bevorzugt NURBS-Flächen zur Modellierung eingesetzt, so z.B. in dem Programm CATIA der französischen Firma Dassault Systèmes.
Eine NURBS-Fläche ist ein bivariater Spline, der in zwei Richtungen mit den Parametern u und v
aufgespannt wird.
f (u, v) =
k−1 X
r−1
X
Ri,n;j,t (u, v) Pi,j
i=0 j=0
Dabei liegen die k mal r Punkte Pi,j auf einem Kontrollgitter, das sich durchaus selbst durchdringen,
berandet oder unberandet sein kann. Die rationalen Basisfunktionen sind durch
wi,j bi,n (u) bj,t (v)
Ri,n;j,t (u, v) = Pk−1 Pr−1
i=0
j=0 wi,j bi,n (u) bj,t (v)
gegeben. Die Gewichtematrix ist ebenfalls zweidimensional. Die Länge der Knotenvektoren U und
V sind vom Grad n oder vom Grad t abhängig, wobei natürlich auch beide Richtungen vom gleichen
Grad sein können. Sie besitzen jeweils m + 1 = k + n + 1 oder s + 1 = r + t + 1 monoton wachsende
Einträge.
U = { a, . . . , a , un+1 , . . . , um−n−1 , b, . . . , b }
| {z }
| {z }
n+1
V
n+1
= { c, . . . , c , vt+1 , . . . , vs−t−1 , d, . . . , d }
| {z }
| {z }
t+1
t+1
Die in dieser Weise formulierten Knotenvektoren interpolieren jeweils die Randpunkte des Gitters
und approximieren die inneren Gitterpunkte.
In OpenGL Implementierungen sind Evaluatoren für Splinekurven und -flächen enthalten, die auf
Bernsteinpolynomen aufbauen. Nachdem die Theorie hier behandelt wurde, sollte es leicht möglich
sein, die entsprechenden Kontrollpunkte und Parameter für die Bibliotheksfunktionen glMap1*()
und glMap2*() bereitzustellen. Die GLU Bibliothek stellt ein Interface für NURBS bereit, das auf
diesen Evaluatoren aufbaut. Die Parameter werden mit gluNurbsProperty() eingestellt, die eigentlichen Flächenspezifischen Kontrollpunkte und -parameter zwischen gluBeginSurface() und
gluEndSurface() über gluNurbsSurface() bereitgestellt. Man kann auch beliebige Kurven zwischen gluBeginTrim() und gluEndTrim() mit gluPwlCurve() oder gluNurbsCurve() aus einer
Fläche herausschneiden (die Fläche trimmen).
136
KAPITEL 7. SPLINES
Abbildung 7.9. Die mit OpenGL dargestellte grüne NURBS-Fläche vom Grad 4 approximiert 36 Kontrollpunkten
über einem zweidimensionalen Gitter.
7.3
Subdivisionflächen
Subdivision surfaces (Unterteilungsflächen) dienen der Beschreibung von glatten Oberflächen beliebiger Topologie. Mittels eines so genannten Kontrollgitters oder control mesh lässt sich die Topologie
sowie die ungefähre Form der Flächen vorgeben. Indem man von dem Kontrollgitter ausgehend wiederholt verfeinert und nach jeder Verfeinerung die Punkte des neuen Gitters nach gewissen Regeln
verschiebt, erhält man - bei passender Wahl des Regelwerks - eine glatte, das Kontrollgitter approximierende oder auch interpolierende Oberfläche.
Das erste Mal wurden subdivision surfaces 1978 in Arbeiten von Doo und Sabin [DS78] sowie Catmull und Clark [CC78] beschrieben. Aber erst 1995 gelang es Ulrich Reif, grundlegende Fragen über
das Verhalten von subdivision surfaces in der Umgebung außerordentlicher Knoten zu beantworten.
Seither wurden viele neue Schemata entwickelt sowie die Glattheit der meisten Verfahren untersucht.
Abbildung 7.10. Ein Tetraeder aus Vierkantengestänge mit anschließenden Verfeinerungsstufen.
Auch für die Filmindustrie sind subdivision surfaces interessant. In Subdivision Surfaces in Character
Animation [DKT98] (auch zu finden in [ZSD+ 00]) werden Vorteile von subdivision surfaces über
traditionelle Oberflächenbeschreibungen (wie z.B. NURBS) bezüglich Animation und Editierbarkeit
herausgestellt.
7.3. SUBDIVISIONFLÄCHEN
137
Definition 7.7 (Mesh) Ein Mesh beschreibt eine stückweise lineare Oberfläche. Er besteht aus Knoten (Vertices), Kanten (Edges) und Flächenstücken (Faces). Jede Kante eines Meshes hat höchstens
zwei, mindestens aber ein benachbartes Flächenstück.
Definition 7.8 (Glattheit) Eine Oberfläche O ⊂ R3 wird als glatt bezeichnet, wenn zu jedem Punkt
P ∈ O eine offene Umgebung U ⊂ R3 und eine offene Nullumgebung V ⊂ R2 existieren, so dass
eine stetig differenzierbare C 1 Abbildung ϕ : R2 → R3 existiert mit ϕ(V ) = U ∩ O.
Bemerkung 7.7 In der Computergraphik ist man häufig eher an Gn statt C n -Stetigkeit interessiert.
Für die Analyse der Flächen ist aber die C n -Stetigkeit einfacher handhabbar. Der Unterschied besteht
in der Definition: die mathematische C n -Stetigkeit wird über die n-ten Ableitungen definiert, die stetig
sein müssen. Darin sind solche Spezialfälle möglich, bei denen ein Tangentialvektor in einem Punkt
gegen die Länge Null konvergiert und optisch eine Ecke entstehen kann. G1 -Stetigkeit besagt, dass
in jedem Punkt eine eindeutige Tangente positiver Länge existiert. Die entsprechend höheren Gn Stetigkeiten sind wieder über n-te Ableitungen definiert.
Das Ziel ist eine stückweise lineare Oberfläche so fein zu unterteilen, dass sie den Eindruck einer
glatten Oberfläche erzeugt, also lokal wie ein Stück der Ebene aussieht, bei der es keine Knicke an
Kanten gibt. Der wichtigste Unterschied von Subdivisionsalgorithmen zu NURBS-Flächen besteht in
der allgemeineren Beschreibung einer zweidimensionalen Mannigfaltigkeit. Wird die Fläche aus einzelnen NURBS-Flächen zusammengestückelt, muss man sich beim Verkleben der einzelnen Patches
immer genau über den Glattheitsgrad am Rand von einer zur nächsten Fläche kümmern. Bei Subdivisionsalgorithmen gibt man ein Regelwerk vor, mit dem die Unterteilung gegen eine Fläche beliebiger
Glattheit konvergiert. Um sinnvoll angewendet werden zu können, sollten subdivision surfaces einigen Anforderungen genügen.
Einfachheit: Das Regelwerk sollte möglichst klein sein.
Effizienz des Regelwerks: Die Berechnung der neuen Positionen der Knoten nach einem Verfeinerungsschritt sollte wenige Operationen benötigen.
Kompakter Träger: Die Umgebung, in der ein Knoten die Form der resultierenden Oberfläche beeinflusst, sollte möglichst klein, in jedem Fall endlich sein.
Lokale Definition: Die Regeln für die Positionierung neuer Knoten sollte nicht auf weit entfernten
Knoten beruhen. Entfernung meint hier die Anzahl der Kanten auf dem Mesh.
Affine Invarianz: Wird das Kontrollgitter M einer affinen Transformation (z.B. Translation, Skalierung, Rotation) unterzogen, so sollte sich auch die subdivision surface durch die selbe Transformation in die aus dem transformierten Kontrollgitter resultierende subdivision surface transformieren lassen.
Stetigkeit: Aussagen über den Grad der Stetigkeit (Glattheit) der resultierenden subdivision surface
sollten (fast überall) möglich sein.
138
7.3.1
KAPITEL 7. SPLINES
Subdivision Schemata
Hat im eindimensionalen Fall (also bei Unterteilungskurven) noch jeder Knoten genau zwei Nachbarn
(insofern es sich nicht um einen Randknoten handelt) kann es im zweidimensionalen Fall zu einem
Knoten beliebig viele Nachbarn geben.
Im Folgenden werden Merkmale und Eigenschaften unterschiedlicher Subdivision Schemata aufgeführt, mit deren Hilfe eine grobe Klassifizierung der verschiedenen Verfahren vorgenommen werden kann. Zunächst benötigen wir weitere Begriffe:
Dreiecks-Mesh: Alle Faces des Meshes sind Dreiecke.
Vierecks-Mesh: Alle Faces des Meshes sind Vierecke.
Face Split: Bei Verfeinerung werden Faces in mehrere kleinere Faces zerlegt. Alte Knoten bleiben
bei Verfeinerung erhalten.
Vertex Split: Bei Verfeinerung werden pro Face vier neue Knoten eingefügt (bei Vierecks-Mesh).
Neue Faces werden erstellt, indem die neuen Knoten verbunden werden. Alte Knoten kommen
im verfeinerten Mesh nicht mehr vor.
Abbildung 7.11. Flächenbezogenes Aufspalten der Unterteilungsalgorithmen, links für reguläres Dreiecksgitter,
rechts für Rechtecksgitter.
Abbildung 7.12. Beim knotenbezogenen Aufspalten werden die Knoten des vorigen Levels durch neue Knoten
ersetzt.
Definition 7.9 (Reguläre Knoten) Ein Knoten heißt regulär, wenn sechs Kanten in einem DreiecksMesh bzw. vier Kanten in einem Vierecks-Mesh von ihm ausgehen (siehe Abb. 7.11).
139
Für die irregulären Fälle müssen gesonderte Regeln in die Schemata eingeführt werden. Da für jede
Zielsetzung unterschiedliche Subdivision Schemata entwickelt wurden, ist es sinnvoll, eine grobe
Typisierung anhand der folgenden Merkmale vorzunehmen:
• Art der Verfeinerungsregel (Face Split oder Vertex Split)
• Typ des zugrunde liegenden Meshes (Dreiecks- oder Vierecks-Mesh)
• Approximierende oder interpolierende Schemata
• Glattheit der Grenzfläche bei regulären Meshes
Die große Anzahl verschiedener Schemata lassen sich mit dieser Klassifizierung grob einordnen.
Face split
Dreiecksgitter
Vierecksgitter
2
Approximierend
Loop (C )
Catmull-Clark (C 2 )
Interpolierend
Modified Butterfly (C 1 )
Kobbelt (C 1 )
Vertex split
Doo-Sabin, Midedge (C 1 )
Biquartic (C 2 )
7.3.2
Catmull-Clark Subdivision
Abbildung 7.13. Zwei Stadien beim Modellieren eines Fischmauls mit zbrush, die unterschiedlich feine Unterteilungen zeigen.
140
KAPITEL 7. SPLINES
Modellierungssoftware wie beispielsweise zbrush benutzt Catmull-Clark Unterteilungsflächen. Der
Nutzer kann zwischen den einzelnen Level der Verfeinerung leicht hin- und herspringen. Während das
Modell zur Visualisierung in vielen Bereichen grob vorgehalten und schnell gerendert wird, können
in interessierenden Bereichen viele Details modelliert und gespeichert werden. Dabei erscheint das
ganze Objekt als stetige glatte Fläche.
Das Catmull-Clark Schema ist ein approximierendes Verfahren, das auf dem Tensorprodukt von bikubischen box splines basiert. Damit ist die Fläche C 2 -stetig bis auf die irregulären Punkte, an denen
man nur C 1 -Stetigkeit erhält. In Matrixform kann ein bikubischer B-Spline Patch ausgedrückt werden
als
f (u, v) = U M GM t V t ,
wobei M die Koeffizienten der kubischen Basis enthält und die Vektoren U = (u3 , u2 , u, 1) und
V = (v 3 , v 2 , v, 1) aus den Monomen bis zum Grad n = 3 bestehen.


−1
3 −3
1


3 −6
3
0 
1


M = 
6  −3
0
3
0 

1
4
1
0
Abbildung 7.14. Das Kontrollmesh dieser Unterteilung ist ein Würfel, der nach wenigen Schritten gegen eine allerdings viel kleinere Kugel konvergiert.
Das Gitter G aus Kontrollpunkten


P11
P12
P13
P14

 P21
G = 
 P
 31
P22
P23
P32
P33

P24 

P34 

P41
P42
P43
P44
wird nun im Bereich 0 < u, v < 12 in der Hälfte verfeinert (die anderen Gitter ergeben sich aus
Symmetriegründen in gleicher Weise, da die Basisfunktionen aufgrund der Verfeinerungsgleichung
verschobene Kopien sind). Setzt man u1 = u2 und v1 = v2 , so erhält man in Matrixschreibweise jetzt
f (u1 , v1 ) = U SM GM t S t V t ,
141
wobei
1
8
0
0
0

 0
S = 
 0

1
4
0
0
1
2

0 
.
0 

0
0
1

0

Dieser Patch muss wieder ein bikubischer B-Spline mit eigenem Kontrollgitter G1 sein, also der
Gleichung f (u, v) = U M G1 M t V t genügen. Daraus ergibt sich
M G1 M t = SM GM t S t .
Da M invertierbar ist, berechnet man
G1 = M −1 SM GM t S t M −t = H1 GH1t
mit

M
−1

4
4
0
0

 1
SM = H1 = 
 0

6
1
4
4

0 
.
0 

0
1
6
1
Dadurch ergeben sich für das neue Gitter G1 zwei neue Flächenpunkte
Q11 =
P11 + P12 + P21 + P22
4
und
Q13 =
P11 + P13 + P23 + P23
,
4
ein neuer Kantenpunkt
Q12
Der neue Knoten Q22 =
Q
4
+
R
2
+
1
=
2
P22
4
1
R=
4
Q11 + Q13 P12 + P22
+
2
2
.
wird mit
Q=
und
Q11 + Q13 + Q31 + Q33
4
P22 + P12 P22 + P21 P22 + P32 P22 + P23
+
+
+
2
2
2
2
gebildet. Man kann leicht nachvollziehen, dass jeder neue Knoten eines Verfeinerungsgitters G1 in
einer dieser Arten interpoliert werden kann. Daraus ergeben sich jetzt die Regeln für die Verfeinerung
eines beliebigen Gitters und auch entsprechende Ausnahmeregeln, wenn die Kantenzahl an einem
Knoten im irregulären Fall nicht vier ist.
142
7.3.3
KAPITEL 7. SPLINES
Subdivision nach Loop
Charles Loop hat 1987 ein einfaches Verfahren für Dreiecks-Meshes eingeführt, das Loop Schema.
Mittels eines Face-Splits wird in einem Verfeinerungsschritt jedes Dreieck des alten Meshes in vier
neue unterteilt.
Abbildung 7.15. Nach dem Loop Schema verfeinerte Fläche.
Das Loop Schema ist ein approximierendes Verfahren, das auf dem three-directional quartic box
spline basiert.
Die generierende Funktion der zugehörigen Verfeinerungsgleichung lautet
S(z1 , z2 ) =
1
(1 + z1 )2 (1 + z2 )2 (1 + z1 z2 )2 ,
16
wobei generierende Funktionen mit zwei Variablen allgemein als
A(x, y) =
X
an,m xn y m
n,m=0
definiert sind. Im regulären Fall ergeben sich die in Abb. 7.16 angegebenen Gewichte.
Definition 7.10 Ein Schema heißt stationär, wenn unabhängig vom Level für jeden Verfeinerungsschritt der gleiche Algorithmus verwendet wird.
Bemerkung 7.8 Stationäre Schemata haben den Vorteil, dass sie Aussagen über die Qualität (Glätte,
Differenzierbarkeit) einer Fläche bei beliebigem Verfeinerungsgrad für reguläre Bereiche treffen können. Für irreguläre Knoten müssen meist gesonderte Betrachtungen gemacht werden.
143
Abbildung 7.16. Wichtung der Knoten im regulären Fall.
Abbildung 7.17. Vorschlag für die Wichtung der Knoten im irregulären Fall.
Loop schlug für die Wahl von β den Koeffizienten β =
Fall ergibt sich daraus wieder β =
Grenzfläche.
1
.
16
1
k
5
8
−
3
8
+ 14 cos 2π
k
2 vor. Im regulären
Für irreguläre Knoten garantiert diese Modellierung eine glatte
Bemerkung 7.9 Wenn man ein Dreiecks- oder Vierecksgitter regulär verfeinert, fügt man überall nur
reguläre Knoten ein. Die Anzahl der irregulären Knoten wird gegenüber dem Ausgangsgitter also
nicht vergrößert, sondern bleibt gleich.
7.3.4
Weiche und scharfe Kanten
Durch das Verständnis der zu Grunde liegenden mathematischen Theorie erkennt man in den Subdivisionsalgorithmen ein Verfahren, mit dem es möglich ist, glatte Oberflächen beliebiger Topologie
nicht nur zu beschreiben, sondern mittels einfacher Algorithmen effizient zu approximieren. Um subdivision surfaces allgemeiner einsetzen zu können, muss man das Regelwerk erweitern. Hier wurde
Subdivision ausschließlich für Meshes ohne Rand betrachtet. Auch fehlt eine Möglichkeit, scharfe
Kanten auf der Oberfläche zu beschreiben.
144
KAPITEL 7. SPLINES
Abbildung 7.18. Verfeinerung eines Kopfes mit einzelnen Gitterpunkten, bei denen mehr als sechs Nachbarn vorkommen (siehe Schläfenregion).
Weiterführende Arbeiten zu diesem Thema sowie eine einfache und effiziente Lösung lassen sich
beispielsweise in der Arbeit von Hoppe [HDD+ 94] über Piecewise Smooth Surface Reconstruction
finden. Hier werden Verfahren vorgestellt, bei denen einzelne Punkte auf den Flächen zu Kurven
zusammengefasst und diese Kurven nun weiter verfeinert werden. Dadurch werden sie nicht bivariat
verfeinert, also nicht als zur angrenzenden Fläche gehörig aufgefasst. So kann eine Fläche beliebiger
Topologie mit einem einzigen Kontrollgitter auskommen und trotzdem in einzelnen Bereichen Knicke
und Kanten aufweisen, ohne den Grad des Splines zu ändern oder die Kontrollpunkte zu häufen (siehe
Abb. 7.19).
7.4
Übungsaufgaben
Aufgabe 7.1 Uniforme und nichtuniforme quadratische B-Spline Basisfunktionen
(a) Ermitteln Sie die quadratischen Blendfunktionen eines uniformen B-Spline und notieren Sie den
i-ten Abschnitt eines Splines, also den Bereich um den i-ten Kontrollpunkt in Matrixschreibweise.
(b) Die Basisfunktionen ändern ihre Gestalt, wenn man zu nichtuniformen Knotenvektoren übergeht.
Schreiben Sie für den Knotenvektor (0, 0.5, 0.5, 0.75, 1) die quadratischen Basisfunktionen eines BSpline auf.
Aufgabe 7.2 Verfeinerungseigenschaft
Beweisen Sie die Verfeinerungseigenschaft für Basisfunktionen der B-Splines, wobei Sie die Distributivität, den Time shift und die Skalierbarkeit
145
Abbildung 7.19. Oben ist eine Fläche mit dem Subdivisionverfahren nach Loop dargestellt, unten im Vergleich
dazu die Erweiterungen mit den Arbeiten von Hoppe et al. [HDD+ 94].
f ∗ (g + h) (t) = f ∗ g (t) + f ∗ h (t)
f (t − i) ∗ g(t − k) = f ∗ g (t − i − k)
1
(f ∗ g) (2t)
f (2t) ∗ g(2t) =
2
Distributiviität
Time shift
Skalierbarkeit
des Faltungsprodukts ausnutzen. Benutzen Sie dazu, dass sich die charakteristische Funktion einfach
aus zwei skalierten und verschobenen Kopien erzeugen lässt
B0 (t) = B0 (2t) + B0 (2t − 1)
und zeigen Sie zunächst
2 1 X 2
B1 (t) = B0 ∗ B0 (t) = 1
B1 (2t − k).
2 k=0 k
Zeigen Sie jetzt, dass die allgemeine Verfeinerungsgleichung
n+1 1 X n+1
Bn (t) = n
Bn (2t − k)
2 k=0
k
aus
(x + y)
n+1
n+1 X
n + 1 n+1−k k
=
x
y
k
k=0
146
KAPITEL 7. SPLINES
mit x = B0 (2t) und y = B0 (2t − 1) folgt, da Bn die (n + 1)fach wiederholte Faltung von B0 (mit
sich selbst) ist.
Aufgabe 7.3 NURBS in OpenGL
Stellen Sie eine NURBS Fläche wie in Abb. 7.9 in OpenGL dar, wobei Sie das Kontrollgitter aus 36
Punkten ebenfalls als durchsichtige Zellen zeichnen.
(a) Verändern Sie den Knotenvektor so, dass die Randpunkte alle interpoliert werden.
(b) Schneiden Sie ein dreieckiges und ein herzförmiges Loch in diese Fläche.
(c) Zeichnen Sie eine zu dieser Fläche verschobene Fläche, bei der Sie die Kontrollpunkte so verändert
haben, dass eine unberandete (d.h. geschlossene) Fläche, beispielsweise ein Torus entsteht.
(d) Bei einem Torus durchläuft man die Kontrollpunkte der gegenüberliegenden Ränder eines quadratischen Gitters in gleicher Orientierung. Für die Darstellung einer Kleinschen Flasche wird die
Orientierung einer Kante gerade umgedreht. Im dreidimensionalen Raum kann diese zweidimensionale Fläche nicht ohne Selbsdurchdringung eingebettet werden. Verändern Sie die Kontrollpunkte
entsprechend, um eine Kleinsche Flasche darzustellen.
Abbildung 7.20. Links ist ein Einheitsquadrat und die Orientierung der Kanten gezeichnet, wodurch sich bei
entsprechender Deformation rechts die Kleinsche Flasche ergibt.
Literaturverzeichnis
[Bli77]
B LINN , JAMES F.: Models of Light Reflection for Computer Synthesized Pictures. Computer Graphics, 11, 1977.
[CC78]
C ATMULL , E. und J. C LARK: Recursively generated B-Spline surfaces on arbitrary
topological meshes. Computer Aided Design, 10:350–355, 1978.
[CCWG88] C OHEN , M. F., S. E. C HEN, J. R. WALLACE und D. P. G REENBERG: A Progressive
Refinement Approach to Fast Radiosity Image Generation. Proceedings of SIGGRAPH
88, Seiten 75–84, 1988.
[CG88]
C OHEN , M. F. und D. P. G REENBERG: The Hemi-Cube: A Radiosity Solution for Complex Environments. Proceedings of SIGGRAPH 85, Seiten 31–40, 1988.
[Coo84]
C OOK , ROBERT L.: Shade Trees. Computer Graphics, 18:223–231, 1984.
[CT82]
C OOK , ROBERT L. und K ENNETH E. T ORRANCE: A reflectance model for computer
graphics. ACM Transaction on Graphics, 1:7–24, 1982.
[CW93]
C OHEN , M. F. und J. R. WALLACE: Radiosity and realistic image synthesis. Morgan
Kaufmann, San Francisco, 1993.
[DKT98]
D E ROSE , T., M. K ASS und T. T RUONG: Subdivision Surfaces in Character Animation. Proceedings of the 25th annual conference on Computer graphics and interactive
techniques, Seiten 85–94, 1998.
[DS78]
D OO , D. und M. S ABIN: Analysis of the behaviour of recursive division surfaces. Computer Aided Design, 10:356–360, 1978.
[FK03]
F ERNANDO , R ANDIMA und M ARK J. K ILGARD: The Cg Tutorial. Addison-Wesley,
2003.
[GGSC98] G OOCH , A MY, B RUCE G OOCH, P ETER S HIRLEY und E LAINE C OHEN: A NonPhotorealistic Lighting Model For Automatic Technical Illustration. SIGGRAPH, 1998.
[GKM93]
G REENE , N., M. K ASS und G. M ILLER: Hierarchical Z-buffer visibility. Computer
Graphics (SIGGRAPH ’93 Proceedings), 27:231–238, 1993.
147
148
LITERATURVERZEICHNIS
[GTGB84] G ORAL , C. M., K. E. T ORRANCE, D. P. G REENBERG und G. BATTAILE: Modeling the
Interaction of Light Between Diffuse Surfaces. Proceedings of SIGGRAPH 84, Seiten
213–222, 1984.
[HDD+ 94] H OPPE , H., T. D E ROSE, T. D UCHAMP, M. H ALSTEAD, H. J IN, J. M C D ONALD,
J. S CHWEITZER und W. S TUETZLE: Piecewise Smooth Surface Reconstruction. SIGGRAPH, Seiten 295–302, 1994.
[JCS01]
J ENSEN , H. W., P. H. C HRISTENSEN und F. S UYKENS: A Practical Guide to Global
Illumination using Photon Mapping. SIGGRAPH 2001 Course 38, 2001.
[Lac95]
L ACROUTE , P H . G.: Fast Volume Rendering Using a Shear-Warp Factorization of the
Viewing Transformation. Stanford University, CA, Technical Report: CSL-TR-95-678,
1995.
[Mea82]
M EAGHER , D. J.: Efficient synthetc image generation of arbitrary 3-D objects. Proceeding of the IEEE Conference on Pattern Recognition and Image Processing, Seiten
473–478, 1982.
[Rad99]
R ADEMACHER , PAUL: View-Dependent Geometry. Computer Graphics Proceedings,
Annual Conference Series, 1999.
[RK00]
R ÖSSEL , C HRISTIAN und L EIF KOBBELT: Line-art Rendering of 3D-Models. Computer Graphics and Applications, Seiten 87 – 96, 2000.
[SP94]
S ILLION , F RANÇOIS X. und C LAUDE P UECH: Radiosty and Global Illumination. Morgan Kaufmann Publishers, 1994.
[SWW+ 04] S CHMITTLER , J ÖRG, S VEN W OOP, DANIEL WAGNER, W OLFGANG J. PAUL und
P HILIPP S LUSALLEK: Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip.
Proceedings of Graphics Hardware 2004, August 28th-29th, 2004.
[ZSD+ 00]
Z ORIN , D., P. S CHR ÖDER, T. D E ROSE, L. KOBBELT, A. L EVIN und W. S WELDENS:
Subdivision for Modeling and Animation. SIGGRAPH 2000 Course Notes, 2000.

Computergraphik II

Transcrição

Documentos relacionados

PDF / 33 kB - Forschungszentrum Jülich

PG-Antrag - Lehrstuhl 5 für Programmiersysteme

Kapitel 7: Parameterinvariante Integrale und Differentialformen

Marketing Guide

Eklat im Leinwiger Rat - Leuphana Universität Lüneburg

Flächen, Volumen und Integral - Mathematik in Bonn

Merci Cherie

Lowe Vertex 200 AW

Die drei Blockaden - Saskia Anders

Die schlesischen Weber