– Diplomarbeit –

Transcrição

– Diplomarbeit –

GPU- BASIERTE
E CHTZEIT-S IMULATION UND V ISUALISIERUNG
VON
S HALLOW WATER E QUATIONS
– Diplomarbeit –
dem Fachbereich Informatik
der Universität Dortmund vorgelegt von
Hendrik Becker
Universität Dortmund
Hiermit versichere ich, daß ich die vorliegende Arbeit selbständig
und nur unter Verwendung der angegebenen Quellen und Hilfsmittel verfaßt habe.
Dortmund, den 8. Mai 2006
iv
Inhaltsverzeichnis
1
Einleitung
1.1 Einführung und Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Übersicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
Mathematische Grundlagen der Arbeit
2.1 Physikalisch basierte Modellierung . . . . . . . . . . . . . . . .
2.1.1 Differentialgleichungen . . . . . . . . . . . . . . . . .
2.1.2 Erhaltungsgleichungen . . . . . . . . . . . . . . . . . .
2.1.3 Navier-Stokes-Gleichungen . . . . . . . . . . . . . . .
2.2 Shallow Water Equations . . . . . . . . . . . . . . . . . . . . .
2.3 Numerische Verfahren zur Lösung der Shallow Water Equations
2.3.1 Räumliche Diskretisierung . . . . . . . . . . . . . . . .
2.3.2 Die Methode der Finiten Differenzen . . . . . . . . . .
2.3.3 Zeitliche Diskretisierung . . . . . . . . . . . . . . . . .
2.3.4 Die semi-lagrange’sche Integrationsmethode . . . . . .
2.3.5 Die diskretisierten Shallow Water Equations . . . . . . .
2.3.6 Das Jacobi-Verfahren . . . . . . . . . . . . . . . . . . .
2.4 Volumenbestimmung . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
3
4
7
7
9
10
12
13
15
17
18
20
Grafikkarten-Programmierung
3.1 Die programmierbare Grafik-Pipeline . . . . . . . . . . .
3.2 General-Purpose Computing on Graphics Processing Units
3.3 Optimierung von GPU Programmen . . . . . . . . . . . .
3.3.1 Bustransfer . . . . . . . . . . . . . . . . . . . . .
3.3.2 Speicher-Zugriff . . . . . . . . . . . . . . . . . .
3.3.3 Arithmetische Intensität . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
23
25
27
27
28
29
Implementierung
4.1 Werkzeuge und Bibliotheken . . . . . . .
4.2 Das Rahmenprogramm . . . . . . . . . .
4.2.1 Initialisierung . . . . . . . . . . .
4.2.2 Textur-Datenstrukturen . . . . . .
4.2.3 Das Framebuffer-Objekt . . . . .
4.3 Fragment-Shader-Programme . . . . . . .
4.3.1 Berechnung der Departure Points
4.3.2 Jacobi-Iteration . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
32
33
33
33
36
38
38
3
4
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
vi
INHALTSVERZEICHNIS
4.4
4.5
5
4.3.3 Aktualisierung des Geschwindigkeitsfeldes
Visualisierung . . . . . . . . . . . . . . . . . . . .
4.4.1 VBOs/PBOs . . . . . . . . . . . . . . . .
4.4.2 Vertex Texture Fetch . . . . . . . . . . . .
4.4.3 Reflektion . . . . . . . . . . . . . . . . . .
4.4.4 Refraktion . . . . . . . . . . . . . . . . .
Bedienung . . . . . . . . . . . . . . . . . . . . . .
Ergebnisse
5.1 Visuelles Ergebnis . . . . . . . .
5.2 Geschwindigkeit . . . . . . . .
5.3 Genauigkeit . . . . . . . . . . .
5.4 Zusammenfassung und Ausblick
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
40
41
43
43
45
47
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
49
49
58
64
A Code-Auszüge
A.1 Shader-Programme . . . . . . . . . . . . . . .
A.1.1 Berechnung der Departure Points . . .
A.1.2 Jacobi . . . . . . . . . . . . . . . . . .
A.1.3 Aktualisierung der Geschwindigkeiten .
A.1.4 Koordinaten-Erzeugung . . . . . . . .
A.1.5 Normalen-Erzeugung . . . . . . . . . .
A.1.6 Reflektion, Brechung und Fresnel-Term
A.1.7 Environment-Mapping . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
71
71
71
73
75
76
77
78
80
Literaturverzeichnis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
80
Kapitel 1
Einleitung
1.1
Einführung und Motivation
Schon von Kindheit an ist das Spielen eine der liebsten Beschäftigungen des Menschen. Wen
wundert es also, dass auch - und in den letzten Jahren gerade! - Computer zum Spielen verwendet werden. Der Softwaremarkt wird klar dominiert vom Verkauf von PC- und KonsolenSpielen, während klassische Rechneranwendungen wie Textverarbeitung und Tabellenkalkulation zumindest im privaten Bereich nur noch ein Nischendasein fristen.
Die Spieleentwicklung begann vor einigen Jahren mit wenigen, bewegten ASCII- Zeichen auf
den zu Monitoren umfunktionierten Fernseh-Bildschirmen, und lebte mehr von den Spiel-Ideen
als von der mageren grafischen Darstellung. Leistungsfähigere Rechner ließen diese Anfangszeiten jedoch rasch vergessen, und schon bald tummelten sich animierte Sprites in zweidimensionalen Pixelwelten. Die Grafik-Erzeugung bekam eine eigene Hardware-Industrie, und mit
den Ergebnissen der neuen informatischen Disziplin der Computergrafik schafften die Spiele
auch den Sprung ins Dreidimensionale.
Diese neuen Spiele glänzten durch immer spektakulärere 3D-Effekte, die die vorhandenen
Graffikkarten bis an die Grenzen ihrer Leistungsfähigkeit ausreizten. Beflügelt von den hohen
Verkaufszahlen legten die Grafikkarten-Hersteller nach, und stellten immer stärkere Grafikchips zur Verfügung, die von den Spieleentwicklern genutzt werden konnten.
Heute hat die Komplexität der Schaltkreise in den Grafik-Chips die der CPUs schon lange
überholt. In einigen Jahren werden die erzeugten virtuellen Welten ein Ausmaß an Realismus
in der grafischen Darstellung erreicht haben, in dem sie von der Wirklichkeit kaum noch zu
unterscheiden sind.
Neben der realistischen Visualisierung der dargestellten Objekte tritt in vor allem auch ihr naturgetreues Verhalten in den Vordergrund. Auf der Basis von physikalischen Gesetzen werden
dafür Modelle entworfen, die vielleicht nicht in allen Bereichen ganz exakt sind, aber dennoch
dem Betrachter das Gefühl einer realistischen Interaktion mit der Szenerie vermitteln.
Die realitätsnahe Darstellung von bewegtem Wasser ist dabei schon immer eine besondere Herausforderung gewesen. Was vor einigen Jahren im Raytracing-Bereich begann, gewinnt nun
auch für virtuelle Welten und moderne Computerspiele an Bedeutung. Interaktive Raten in der
1
2
KAPITEL 1. EINLEITUNG
Berechnung der Bewegung und deren ansprechende Darstellung sind dafür jedoch zwingend
notwendig.
An diesem Punkt setzt diese Arbeit an. Die großen Parallelvearbeitungs-Kapazitäten moderner
Grafikkarten mit hohen Speicherbandbreiten und Taktraten, und vor allem der freien Programmierbarkeit bestimmter Teile der Hardware ermöglichen es, die GPU nicht nur für die Darstellung, sondern auch für die Simulation physikalisch korrekten Wasserverhaltens einzusetzen,
mit dem Ziel, die für eine Berechnung und Visualisierung in Echtzeit notwendige Rechenleistung zu erbringen.
1.2
Übersicht
Die vorliegende Arbeit ist wie folgt gegliedert:
• Kapitel 2 befasst sich mit den für die Umsetzung notwendigen mathematischen Grundlagen. Ausgehend von den für physikalisch basierte Modellierung ganz allgemein benötigten Begriffen wird das für die Implementierung verwendete Modell der sogenannten
Shallow Water Equations hergeleitet. Ein für die spätere Untersuchung der erzielten Ergebnisse verwendetes Verfahren zur Volumenbestimmung wird vorgestellt.
• Kapitel 3 geht auf den Aufbau der eingesetzen Grafikkarten ein, und hält wichtige Aspekte für deren effiziente Programmierung fest, die auch für die Implementierung in dieser
Arbeit von Bedeutung sind.
• Kapitel 4 beschreibt im Detail das Vorgehen bei der Umsetzung des vorgestellten Verfahrens in eine GPU-Implementierung. Dabei spielen neben dem Verfahren zur Lösung
des zugrundeliegenden mathematischen Problems auch die für die Visualisierung eingesetzten Techniken eine Rolle.
• Kapitel 5 dient der Vorstellung der erzielten Ergebnisse und deren Analyse in Bezug auf
Geschwindigkeit und Genauigkeit der Simulation.
Diese Reihenfolge beschreibt auch den chronologischen Ablauf in der Entstehung dieser Arbeit. Nach dem Verständnis der grundlegenden mathematischen Verfahren und der Besonderheiten der modernen Grafikkarten-Programmierung wurde die Implementierung vorgenommen, und abschließend analysiert.
Teile des Programmcodes von zentraler Bedeutung für die Implementierung sind auszugsweise
in Anhang A zu finden. Der Code liegt der Arbeit auch in Gänze auf einer CD bei.
Kapitel 2
Mathematische Grundlagen der
Arbeit
2.1
Physikalisch basierte Modellierung
Der Ursprung dieser Arbeit findet sich im Feld der physikalisch basierten Modellierung, oder
kurz PBM. Das Ziel dieser Form der Modellierung ist es, natürliche Phänomene - wie in diesem
Fall das Verhalten von Wasser - auf eine Computeranwendung abzubilden, ohne die Veränderungen der beobachteten Objekte schrittweise von Hand zu animieren [28].
Anwendungen für PBM finden sich in vielen Bereichen: die Zeitersparnis bei der Animation kommt der Trickfilmindustrie zu Gute, der höhere Realismus beflügelt die Spieleindustrie
z.B. bei der Entwicklung von Simulatoren, etc., aber auch im wissenschaftlichen Bereich wird
PBM eingesetzt, um das qualitative Verhalten eines Systems zu bestimmen [20]. Beispiele
für Einsatzgebiete der physikalisch basierten Modellierung sind Masse-Feder-Systeme, wie sie
zur Simulation von verformbaren Materialien wie Stoff oder in der Animation von Muskeln
und Gewebe verwendet werden [33, 40], oder Partikel-Systeme zur Modellierung von natürlichen Phänomenen wie Feuer, Regen, Schnee, Rauch, oder dem Schwarmverhalten von Tieren
etc. [34].
Die physikalischen Gesetze, die ein solches System bestimmen, werden dabei meist in partiellen Differentialgleichungen ausgedrückt. Dabei wird versucht, die Eigenschaften des betrachteten Systems möglichst vollständig zu erfassen, um auf dieser Basis den zeitlichen Ablauf
vorherzusagen [42]. Kapitel 2.1 fasst sehr kurz benötigte Verfahren der Modellierung zusammen, während in Abschnitt 2.2 ausführlich das verwendete Lösungschema für die Shallow
Water Equations hergeleitet wird.
2.1.1
Differentialgleichungen
Gewöhnliche Differentialgleichungen sind Gleichungen, in denen eine Funktion und ihre Ableitungen nach einer Variablen auftreten [48]. Wird die Funktion dabei nach mehr als einer
Variable abgeleitet, so spricht man von partiellen Differentialgleichungen.
3
4
KAPITEL 2. MATHEMATISCHE GRUNDLAGEN DER ARBEIT
Als einfaches Beispiel betrachte man eine Funktion u : R × R → R, die z.B. von der Ortsvariablen x und der Zeit t abhängt. Die partielle Ableitung
∂u(x, t)
∂t
beschreibt dann die Änderung der Funktion mit der Zeit, und analog
∂u(x, t)
∂x
die Änderung der Funktionswerte mit der Ortsvariablen. Sind die Änderungen gleich ergibt
sich folgende partielle Differentialgleichung
∂u
∂u
=
,
∂t
∂x
wobei der einfacheren Lesbarkeit halber ∂u(x, t) durch ∂u ersetzt wurde. Durch erneutes Ableiten nach den Variablen t und u erhält man die sogenannte Wellengleichung
∂2u
∂2u
=
,
∂t2
∂x2
in der ∂ 2 die zweite Ableitung bezeichnet.
Ein wichtiges Beispiel für partielle Differentialgleichungen sind die sogenannten Erhaltungsgleichungen, die die Basis der Kontinuumsmechanik bilden. Das Grundprinzip der Erhaltung
besagt, dass sich die Integrale der in Dichtefunktionen dargestellten Zustandsgrößen wie Massedichte, Temperatur, Impuls oder innere Energie in einem bewegten Volumen nicht ändern,
solange sie frei von äusseren Einflüssen bleiben. Sie spielen eine wichtige Rolle im in dieser
Arbeit vorstellten Modell, und werden daher im folgenden kurz erläutert. Für weitere Informationen wird auf Lehrbücher zum Thema verwiesen (z.B. [23, 43] oder Vorlesungsskripte
wie [41]).
2.1.2
Erhaltungsgleichungen
Die im Folgenden vorgestelle allgemeine Erhaltungsgleichung lässt sich später auf die Spezialfälle für die drei für diese Arbeit wichtigen physikalischen Größen Masse, Impuls und Energie
anwenden.
Man kann sich ein gas- oder flüssigkeitsgefülltes Volumen als Kontinuum (aus dem Lateinischen, continuum:„Das Zusammenhängende“) vorstellen, also als ein Objekt welches keine
Risse, Brüche, Löcher, Hohlräume oder ähnliches innerhalb seiner Grenzen besitzt.
Diese Vorstellung ist wegen der großen Anzahl der in diesem Volumen vorhandenen Moleküle
gerechtfertigt, und erlaubt die Untersuchung der beschreibenden Funktionen auf kleinsten Intervallen.
Man betrachtet nun einen beliebig geformten, stückweise stetig differenzierbaren dreidimensionalen Bereich Ω mit Volumen V , dessen Rand ∂Ω mit der Oberfläche S, und eine Funktion
F (t). Diese gibt zu jedem Zeitpunkt t eine physikalische Größe für den gesamten Bereich Ω
an (z.B. die Gesamtmasse, den Gesamtimpuls, etc.).
2.1. PHYSIKALISCH BASIERTE MODELLIERUNG
5
Diese Funktion kann mit Hilfe der ihr zugehörigen Dichten f (r, t) beschreiben werden, indem
über den Bereich Ω integriert wird:
Z
F (t) = f (r, t)dV
Ω
r bezeichnet dabei einen Ortsvektor. Die Änderung der Größe F mit der Zeit t wird beschrieben durch
Z
∂F
∂f (r, t)
=
dV
∂t
∂t
Ω
und kann folgende Ursachen haben:
1. Die betrachtete Größe F gelangt durch die Oberfläche in das Volumen hinein oder aus
ihm heraus.
2. Im Inneren des Gebietes Ω liegt eine Quelle (bzw. Senke) von F .
3. Fernwirkungen wie z.B. Gravitation oder Wärmestrahlung beeinflussen das Innere von
Ω von ausserhalb.
Der mit φf bezeichnete, und Stromdichte genannte Vektor gibt die ein- oder ausfließende Größe pro Zeit- und Oberflächeneinheit an. Da nur der senkrecht zur Oberfläche fließende Anteil
relevant ist, wird das Skalarprodukt n · φf gebildet, welches negativ wird, wenn φf auf die
Oberfläche gerichtet ist.
Der Term qf beschreibt die pro Zeit t und Volumeneinheit gebildete Menge an F im Inneren
von , und sf die pro Zeit- und Volumeneinheit gebildete Menge an F steht.
Die gesamte Änderung von F lässt sich also durch Summation der einzelnen ÄnderungsIntegrale ausdrücken:
Z
Z
Z
Z
∂F
∂f (r, t)
=
dV = − φf · ndS + qf dV + sf dV
∂t
∂t
Ω
∂Ω
Ω
Ω
Drückt man nun den Fluss von φf über dem Rand ∂Ω durch das Volumenintegral der Divergenz
der Dichtefunktion div(φf ) über dem gesamten Gebiet Ω aus, und berücksichtigt, dass die
Gleichung nur möglich ist, wenn bereits die Integranden gleich sind, erhält man die allgemeine
Erhaltungsgleichung:
∂f
+ div(φf ) = qf + sf .
∂t
Erhaltung der Gesamtmasse
Wählt man für F nun die Gesamtmasse des Systems m, so entspricht die Dichte fm der Massendichte ρ, und die Massenstromdichte φm ergibt sich aus dem Produkt der Geschwindigkeit
6
v und der Dichte ρ. Die Terme qm und sm sind beide 0. Durch Einsetzen in die allgemeine
Erhaltungsgleichung erhält man die Massenerhaltungsgleichung:
∂ρ
+ div(vρ) = 0.
∂t
Erhaltung des Impulses
Die Größe F ist in diesem Fall durch den Gesamtimpuls des Systems gegeben, wodurch fmv
der Impulsdichte pv entspricht, und die Impulsstromdichte φmv sich zu φmv = vp · v + p̃ ergibt.
p̃ bezeichnet dabei die Impulsänderung durch Druck- und Reibungskräfte.
qmv ist 0, da im Inneren keine Kräfte entstehen, die eine Impulsänderung nach sich ziehen.
Jedoch wird der Impuls durch eine Fernwirkung smv beeinflusst, nämlich der Gravitationskraft
pro Volumen, gegeben durch pg . Für eine genaue Herleitung verweise ich auf [27].
Einsetzen in die allgemeine Erhaltungsgleichung führt zur Impulserhaltungsgleichung:
∂pv
+ div(vp · v) + div(p̃) = pg .
∂t
Erhaltung der Energie
Betrachtet man für die Größe F die Gesamtenergie des Systems, also die Summe der potentiellen Energie (pG , das Maß an Energie, das nötig ist, um einen Körper ausgehend von einem
Bezugsniveau in seine aktuelle Lage zu versetzen), der kinetischen Energie (pv , die Schwerpunktsbewegung der Moleküle) und der inneren Energie (pu , die Schwingung und Rotation
der einzelnen Moleküle), so ist die entsprechende Dichte fe die sogenannte Energiedichte pe .
Diese setzt sich wie folgt zusammen:
1
pe = pu + p2v + pG .
2
Im folgenden wird mit p̃v die Reibungsarbeit bezeichnet, die aufgrund der Viskosität (die ”Zähigkeit” einer Flüssigkeit oder eines Gases, die umso höher wird, je dickflüssiger das Medium
ist) verrichtet wird.
Die Energiestromdichte φe (ein Vektor) ergibt sich zu φe = pev + p̃v +iq , mit der Wärmestromdichte iq = −γgradT , wobei γ den Wärmeleitkoeffizienten ausdrückt, T für die Temperatur und
gradT für den Vektor (den sogenannten Gradienten) steht, der in die Richtung zeigt, in der die
Temperatur am stärksten ansteigt.
Der Quellterm qe ist 0, da im Inneren keine Energie entsteht oder vernichtet wird, wohl aber
durch eine Fernwirkung se , mit Ursache in der Wärmestrahlung, gegeben durch qr . Auf eine
detaillierte Ausarbeitung verweise ich an dieser Stelle wieder auf [27].
Erneutes Einsetzen in die allgemeine Erhaltungsgleichung führt zur Energieerhaltungsgleichung:
∂pe
+ div(pev + p̃v − γgradT ) = qr
∂t
2.2. SHALLOW WATER EQUATIONS
2.1.3
7
Navier-Stokes-Gleichungen
Mit den im vorigen Abschnitt vorgestellten Erhaltungsgleichungen lässt sich zusammenfassend
ein Gleichungssystem aufstellen, das wie folgt aussieht:



 

p
pv
0
∂ 
 =  pg 
pv  + div 
p ⊗ v + p̃
∂t
pe
pev + p̃ − γgradT
qr
Dieses Gleichungssystem ist benannt nach dem Franzosen Claude-Louis Navier und dem Briten George Gabriel Stokes, die unabhängig von einander in der Mitte des 19. Jahrhunderts den
Impulssatz für Newtonsche Fluide in differentieller Form gefunden, also die Abhängigkeit von
Druck und Geschwindigkeit als Funktion von Ort und Zeit.
Eine Variation dieser Gleichungen bezieht sich auf inkompressible Fluide, also Medien, in denen sich die Dichte ρ im Verlauf der Zeit und zwischen den betrachteten Punkten nicht ändert.
Es gilt also
∂ρ
∂ρ
∂ρ
∂ρ
=
=
=
= 0,
∂t
∂x
∂y
∂z
wobei t für die Zeit und x, y und z für die drei räumlichen Richtungen stehen. Eine derartige
Inkompressibilität vorausgesetzt, lässt sich die Massenerhaltungsgleichung vereinfachen( [29])
zu
∂u ∂v ∂w
+
+
= 0,
∂x ∂y
∂z
und die Navier-Stokes-Gleichungen lassen sich unter dieser Nebenbedingung darstellen als
∂u
∂u
∂u
∂u
1 ∂p
∂2u ∂2u ∂2u
+u
+v
+w
= gx −
+ v( 2 + 2 + 2 ),
∂t
∂x
∂y
∂z
ρ ∂x
∂x
∂y
∂z
∂v
∂v
∂v
∂v
1 ∂p
∂2v
∂2v ∂2v
+u
+v
+w
= gy −
+ v( 2 + 2 + 2 ),
∂t
∂x
∂y
∂z
ρ ∂y
∂x
∂y
∂z
∂w
∂w
∂w
∂w
1 ∂p
∂2w ∂2w ∂2w
+u
+v
+w
= gz −
+ v( 2 +
+
).
∂t
∂x
∂z
∂z
ρ ∂z
∂x
∂y 2
∂z 2
Dabei bezeichnen u, v und w die Geschwindigkeiten in x-, y- und z-Richtung, p den Druck, v
die Viskosität der Flüssigkeit, gx , gy und gz die Gravitations-Konstanten für die drei räumlichen
Richtungen und t für die Zeit.
2.2
Shallow Water Equations
Auf Navier Stokes Gleichungen basierende Simulationen erreichen einen hohen Grad an Realismus. Für das in dieser Arbeit angestrebte Ziel sind sie allerdings zu komplex. Es wird also
eine Vereinfachung dieses Systems benötigt, die sich effizient lösen lässt, und trotzdem ein
ausreichendes Maß an Genauigkeit liefert, um als Grundlage für ein physikalisch basiertes
Wasser-Modell zu dienen.
8
Ein erster Schritt besteht darin, den Koeffizienten für die Viskosität der Flüssigkeit v auf Null
zu setzen:
∂u
∂u
∂u
∂u
1 ∂p
+u
+v
+w
= gx −
,
∂t
∂x
∂y
∂z
p ∂x
∂v
∂v
∂v
∂v
1 ∂p
+u
+v
+w
= gy −
,
∂t
∂x
∂y
∂z
p ∂y
∂w
∂w
∂w
1 ∂p
∂w
+u
+v
+w
= gz −
.
∂t
∂x
∂y
∂z
p ∂y
Das entstandene Modell entspricht nun physikalisch betrachtet nicht exakt dem von Wasser,
das z.B. abhängig vom seiner Temperatur oder den in ihm gelösten Stoffen eine Viskosität aufweist, die erheblich von Null verschieden ist. Gleiches gilt aber bereits für die Annahme der
Inkompressibilität, wie die in Tabelle 2.1 empirisch ermittelten Werte für die Eigenschaften
von Wasser zeigen [17]:
Temperatur T
(◦C)
0
5
10
15
20
25
30
50
100
Dynamische Viskosität ν
(10−3 Psa )
1,78
1,52
1,31
1,40
1,00
0,89
0,80
0,55
0,28
Kompressibilität κ
(10−9 hP a−1 )
51,0
49,6
45,9
44,2
44,5
46,1
48,9
44,0
47,7
Tabelle 2.1: Viskosität und Kompressibilität von Wasser
Reduziert man das entstandene Gleichungssystem noch weiter und betrachtet nur noch die Geschwindigkeiten u und v in x- resp. y-Richtung, erhält man ein noch einfacheres Gleichungssystem, die sog. Shallow Water Equations (SWEs):
∂u
∂u
∂u
∂h
+u
+v
+g
=0
∂t
∂x
∂y
∂x
∂v
∂v
∂h
∂v
+u
+v
+g
=0
∂t
∂x
∂y
∂y
∂h ∂[u(h − b)] ∂[v(h − b)]
+
+
=0
∂x
∂x
∂y
Wie in Abbildung 2.2 gezeigt, stehen u und v weiterhin für die Geschwindigkeiten in x-und
y-Richtung, g für die Gravitationskonstante (nur z-Richtung) und t für die Zeit. h bezeichnet
2.3. NUMERISCHE VERFAHREN ZUR LÖSUNG DER SHALLOW WATER EQUATIONS9
Abbildung 2.1: Die im Modell verwendeten Bezeichnungen
das Höhenfeld des Wassers und b das Bodenprofil. Allgemein ausgedrückt beschreiben SWEs
also den Fluss von dünnen Flüssigkeitsschichten über einer beliebigen Bodentopographie. Sie
werden gelegentlich auch als Saint-Venant-Gleichungen bezeichnet, benannt nach dem französischen Ingenieur Adhémar Jean Claude Barré de Saint-Venant (1797-1886), der während
seiner Zeit im „Corps des Ponts-et-Chaussées“ die Grundlagen dafür legte.
Praktische Anwendungsgebiete der SWEs finden sich in Dammbruch- und Tsunami-Simulationen und in der Küstenmodellierung, und wird sowohl in wissenschaftlichen als auch kommerziellen Programmen eingesetzt (siehe z.B. [12]).
Die oben dargestellte Form ist nur eine Spielart der SWEs. Weite Verbreitung finden sie in
ozeanographischen oder atmosphärischen Anwendungen, wo zusätzlich die Corioliskraft mit
erfasst wird, die die Ablenkung bewegter Körper in einem rotierenden Bezugssystem aus Sicht
eines sich mitbewegenden Beobachters wiedergibt. Da wir in dieser Arbeit relativ kleine Gebiete betrachten werden, ist für die realistische Darstellung die Corioliskraft aber vernachlässigbar.
2.3
Numerische Verfahren zur Lösung der Shallow Water Equations
Eine Aufgabe der numerischen Mathematik besteht in der Entwicklung von Methoden, mit
denen mathematische Probleme effektiv und meißt unter Angabe des dabei gemachten Fehlers
(der Abweichung der gefundenen, approximativen Lösung von der exakten) gelöst werden können. Das Hauptanwendungsgebiet liegt demnach in der Simulation von komplexen Vorgängen
- wie sie z.B. in der Natur vorkommen - auf schnellen Rechenanlagen, um teure Experimente
durch beliebig oft wiederholbare Modellrechnungen zu ersetzen.
Um die SWEs und Differentialgleichungen im allgemeinen zu lösen, muss eine Funktion gefunden werden, die mit ihren Ableitungen der Gleichung genügt. Eine analytische Lösung - das
„Finden“ einer Funktion mit den gesuchten Eigenschaften für den ganzen betrachteten Bereich
- ist aufgrund der Komplexität der Gleichungen nicht möglich. Daher bedient man sich einer
geeigneten Diskretisierung, was bedeutet, dass man aus der vorliegenden, kontinuierlichen In-
10
formation endlich viele (diskrete) Werte gewinnt - im konkreten Fall ein Netz oder Gitter von
Stützstellen - um sie in endlicher Zeit und mit endlichem Speicherplatz bearbeiten zu können.
Die diskretisierten Differentialgleichungen enthalten dann keine kontinuierlichen Ableitungen
mehr, sondern nur noch diskrete, also rein algebraische Ausdrücke. Da die SWEs sowohl von
zeitlichen als auch von räumlichen Variablen abhängen, muss auch eine zeitliche und räumliche
Diskretisierung erfolgen. Oft ist die gewählte Diskretisierung bereits eng mit dem eigentlichen
Lösungsverfahren (s.u.) verknüpft.
2.3.1
Räumliche Diskretisierung
Eine Hauptunterscheidung bei der räumlichen Diskretisierung bildet dabei die Unterteilung in
strukturierte und unstrukturierte Netze oder Gitter. In Abbildung 2.2 ist ein Beispiel für ein
unstrukturiertes Gitter zu sehen.
Unstrukturierte Netze weisen die höchste Flexibilität auf. Man könnte sie zum Beispiel ver-
Abbildung 2.2: Ein unstrukturiertes Gitter
wenden, um einen realistischen Küstenstreifen mit vorgelagerten Inseln, Felsen oder Wellenbrechern zu modellieren. Sie sind allerdings auch am schwersten zu generieren. Ein Knoten
(Gitterpunkt) oder eine Zelle (das Innere eines durch zusammenhängende Kanten (Knotenverbindungen) beschränkten Bereiches) kann nicht einfach anhand zweier bzw. dreier (2D bzw.
3D) Koordinaten identifiziert werden.
Obschon in der Informatik effiziente Datenstrukturen für unstrukturierte Gitter bekannt sind
(zum Beispiel die sog. Winged Edge-Datenstruktur, [16]), lassen sich diese nur sehr schlecht für
eine GPU-Implementierung benutzen. Wie Kapitel 2.3 genauer erläutert, erreicht eine Anwendung auf der GPU für größere Probleme nur dann einen Geschwindigkeitsvorteil gegenüber
der CPU, wenn auf den Grafikkarten Speicher sequentiell zugegriffen wird. Oben genannte
Datenstruktur lebt aber von der Verwendung von Zeigern auf die Zellen, Kanten und Knoten
des Gitters, deren Verfolgung letztendlich zu einem zufälligen Speicherzugriffsmuster führt.
Wie im Implementierungs-Teil dieser Arbeit noch genauer beschrieben, liegt daher die Ver-
wendung eines regulären Gitters näher. Abbildung 2.3 zeigt einige Spielarten strukturierter
Netze [26].
Abbildung 2.3: Verschieden Arten strukturierter Netze: Reguläre, orthogonale Gitter
(A und B), krummliniges Gitter (C) und orthogonal, krummliniges Gitter (D).
Strukturierte Gitter zeichnen sich dadurch aus, dass die Anzahl der Gitterpunkte in einer Raumdimension konstant ist. Ein Gitter besitzt also eine feste Anzahl nx Knoten in x-Richtung und
ny in y-Richtung (im zweidimensionalen Fall, analog besitzt ein strukturiertes 3D-Gitter zusätzlich nz Punkte in z- Richtung). Werden die Punkte der Reihe nach in der jeweiligen Dimension durchnummeriert, kann ein Punkt eindeutig anhand des Zwei- bzw. Drei-Tupels aus
x-, y- und z-Index identifiziert werden.
Sind die Zellenlängen eines strukturierten Netzes in den einzelnen Raumdimensionen konstant,
spricht man von einem regulären Gitter. Stehen die Kanten senkrecht aufeinander, bezeichnet
man das Gitter als orthogonal.
Generell gilt dabei: Je feiner die Unterteilung des Berechnungsgebietes ist, desto geringer fallen die Näherungen auf den Untergebieten ins Gewicht. Dies gilt sowohl für die zeitliche, wie
auch für die räumliche Diskretisierung. Der Nachteil einer sehr feinen Unterteilung liegt dabei
auf der Hand: Je mehr Stützstellen ausgewertet werden müssen, um so höher liegt auch der
benötigte Rechenaufwand und Speicherplatzbedarf.
Ein in der Praxis häufig verwendeter Ansatz zur Minimierung des Fehlers, bei dem gleichzeitigen Versuch, den Gesamt-Rechenaufwand so gering wie möglich zu halten, liegt darin, die
Zellen des Gitters weiter zu verfeinern, in denen der Fehler groß wird. Man spricht dann von
einem adaptiven Gitter (siehe Abbildung 2.4).
. Um die Verfeinerung des Gittes vorzunehmen, müssen also die stark fehlerbehafteten Zellen
identifiziert, und anschließend verfeinert werden. Für das angestrebte Ergebnis ist diese Verfeinerung aber nicht nötig, wie in Kapitel 5 gezeigt wird.
12
Abbildung 2.4: Ein adaptives Gitter
Die Implementierung dieser Arbeit basiert auf der räumlichen Aufteilung des Rechengebietes
in ein nicht-adaptives, strukturiertes, reguläres, orthogonales Gitter. Da die Funktionswerte an
den Stützstellen wie später ausführlich erklärt in einer Textur gespeichert werden, können die
einzelnen Gitterpunkte intuitiv anhand ihrer Textur-Koordinaten identifiziert werden. Ausserdem eignet sich ein derart strukturiertes Gitter gut für die sog. Methode der Finiten Differenzen.
2.3.2
Die Methode der Finiten Differenzen
Ausgangspunkt der Finiten Differenzen (FD) Methode ist eine Gleichung in Differentialform.
Zur Veranschaulichung betrachte man eine Funktion u : R × R → R, deren Ableitung nach
der x-Koordinate man als ∂u
∂x schreibt. Um auf einem regulären Gitter mit den Punkten (xi , yj ),
1 ≤ i ≤ nx und 1 ≤ j ≤ ny einen Differenzenquotienten für die erste Ableitung in x-Richtung
zu erhalten, entwickeln wir die Funktion u am Punkt (i + 1, j) in eine Taylorreihe (siehe dazu
z.B. [21, 42]).
ui+1,j = ui,j + (xi+1 − xi )
∂ui,j
∂ui,j 2
1
+ (xi+1 − xi )2
+ ...
∂x
2
∂x2
Für den Entwicklungsknoten (i − 1, j) erhalten wir
ui−1,j = ui,j − (xi − xi−1 )
∂ui,j
∂ui,j 2
1
− (xi − xi−1 )2
− ...
∂x
2
∂x2
Löst man nun die erste Taylorreihe nach
ent als Approximation der Ableitung:
∂ui,j
∂x
auf, so ergibt sich der vordere Differenzenquoti-
∂ui,j
ui+1,j − ui,j
≈
∂x
4x
Eine Fehlerabschätzung für Taylorreihen besagt, dass die Terme höherer Ableitungen mit O(4x)
abgeschätzt werden können (siehe z.B. [42] , [21]). Für 4x → 0 gehen auch sie gegen Null.
∂u
Aus der zweiten Taylorreihe erhalten wir nach Auflösen nach ∂xi,j den sog. rückwärtige Differenzenquotienten:
∂ui,j
ui,j − ui−1,j
≈
∂x
4x
Durch Subtraktion der zweiten Reihe von der ersten ergibt sich der zentrale Differenzenquotient:
∂ui,j
ui+1,j − ui−1,j
≈
∂x
24x
Die Differenzenformeln für die zweiten Ableitungen lassen sich analog herleiten, und man
erhält
∂ 2 ui,j
ui−1,j − 2ui,j + ui+1,j
≈
.
2
∂x
∆x2
Ersetzt man nun in der ursprünglichen Gleichung alle partiellen Ableitungen durch die so gebildeten Differenzenquotienten, tauchen in der Gleichung nur noch arithmetische Operationen
auf. Das hier vorgestellte finite Differenzenverfahren wird in Abschnitt 2.3.1 zur räumlichen
Diskretisierung der SWEs verwendet.
Da die Taylorreihen nur bis zu den quadratischen Termen entwickelt wurden, spricht man von
einem Fehler in der Ortsdiskretisierung von der Grössenordnung O(4x2 ), bzw. von Genauigkeit zweiter Ordnung für die zentralen Differenzenquotienten.
2.3.3
Zeitliche Diskretisierung
Da in den SWEs zeitliche Ableitungen enthalten sind, beschreiben sie also wie sich die entsprechenden Größen mit der Zeit entwickeln. Um dieses Geschehen numerisch zu behandeln, wird
ein Anfangszeitpunkt t0 festgelegt, und durch das fortwährende Hinzufügen von Zeitschritten
4t eine Folge von Zeitpunkten „erzeugt“:
tn = t0 + n 4 t
Dies nennt man zeitliche Diskretisierung.
Unter der Bedingung, dass alle betrachteten physikalischen Größen für den Zeitpunkt t0 als
Startwerte vorliegen, werden nun Rechenvorschriften gesucht, anhand derer die Lösungswerte
für den Zeitpunkt t1 , und dann sukzessive für alle weiteren Zeitpunkte t2 , t3 , ... bis zum Abbruch der Simulation ermittelt werden können.
Im allgemeinen unterscheidet man zwei Ansätze zur Diskretisierung partieller Differentialgleichungen in der Zeit: Den expliziten und den impliziten Ansatz.
Explizit bedeutet dabei, dass auf einer Seite der Gleichung nur bekannte Größen vorhanden
sind, und man daher explizit nach den gesuchten Unbekannten auflösen kann. Auf konkreten
14
Fall der SWEs zum Beispiel bezogen bedeutet das, dass die Lösung für den nächsten Zeitschritt
ausschließlich anhand geeigneter Koeffizienten aus der Lösung des letzten Zeitschritts gewonnen werden kann.
Explizite Verfahren haben also den Vorteil, dass sie mit vergleichbar wenig Rechenaufwand
zwischen pro Zeitschritt auskommen. Es ist allerdings bekannt, dass explizite Verfahren Probleme mit der Stabilität haben, wenn die Zeitschritte zu groß gewählt werden. Unter Stabilität
eines numerischen Verfahrens versteht man die Robustheit des Algorithmus gegenüber Störungen in den Eingabedaten und Rundungsfehlern, also die Tatsache, dass sich diese Einflüsse
während der Berechnung nicht aufsummieren und zur Divergenz des Verfahrens oder einer
grob falschen Lösungen führen.
Sei f (x) ein mathematisches Problem mit Eingabe x und f˜(x̃) der numerische Algorithmus
für dieses Problem mit gestörter Eingabe x̃, so bezeichnet
kf (x) − f˜(x̃)k
den Fehler der numerischen Lösung. Die Stabilität wird ausgedrückt durch
kf (x̃) − f˜(x̃)k.
Eine Quantifizierung hängt vom konkreten Problem und der verwendeten Norm ab, und soll
hier nicht weiter erörtert werden.
Damit ein explizites Verfahren stabil bleibt, muss die Zeitschritt-Größe geeignet klein gewählt
werden. Ausschlaggebend für die Wahl des Zeitschritts ist dabei die Maschenweite des Gitters
4x. Als Maß für die Anzahl der Zellen, die sich ein Partikel pro Zeitschritt maximal bewegt,
dient dient sogenannte Courant-Friedrichs-Lewy-Zahl c (auch CFL- oder Courant-Zahl genannt):
u · 4t
c=
.
4x
Bewegt sich ein Partikel des Fluids in einem Zeitschritt um mehr als eine Zellen-Länge 4x
(c > 1) wird das Verfahren instabil. Die Zeitschritt-Größe muss also für jeden Zeitschritt überprüft, und abhängig von den maximal auftretenden Geschwindigkeiten u angepasst werden.
Diese sogenannte Zeitschritt-Kontrolle lässt sich allein auf der GPU nicht effizient realisieren.
Ein weiterer Nachteil liegt darin, dass die zulässige Zeitschritt-Größe für ”höhere” Geschwindigkeiten so gering wird, dass sehr viele - für eine Echtzeitsimulation zu viele - Zeitschritte
nötig werden um eine stabile Lösung zu gewährleisten.
Implizite Verfahren ziehen zur Berechnung der Lösung eines Zeitschritts für einen Gitterpunkt
zwar ebenfalls die Lösung des letzten Zeitschritts (evtl. auch mehrerer vorheriger Zeitschritte) heran, sind aber zusätzlich an die benachbarten Gitterpunkte gekoppelt. Anders ausgedrückt
bedeutet das, dass sich die Lösung nicht mehr einfach aus der des letzten Zeitschritts berechnen
lässt, sondern für jeden Zeitschritt ein neues Gleichungssystem, das diese Kopplung beschreibt,
aufgestellt und gelöst werden muss.
Der Vorteil impliziter Verfahren liegt in deren größerer Robustheit gegenüber größeren Zeitschritten, allerdings sind sie rechenintensiver in den Zeitschritten.
Für die Implementierung dieser Arbeit wurde ein impliziter Ansatz verwendet, mit der Absicht, dass auch Zeitschrittgrößen gewählt werden können, die von der CFL-Zahl nicht so stark
abhängig sind, dass die Echzeitberechnung der Ergebnisse unmöglich wird.
2.3.4
Die semi-lagrange’sche Integrationsmethode
In Strömungssimulationen gebräuchlich sind zwei Methoden zur Integration in der Zeit: Das
Euler’sche Strömungsschema, bei dem der Beobachter sich an einem fixen Punkt befindet, und
der Lagrange’sche Ansatz, bei dem der Beobachter sich mit einem Partikel bewegt.
Der erste Ansatz bewahrt die Regelmäßigkeit des Gitters, benötigt aber kleine Zeitschritte um
stabil zu bleiben. Der zweite Ansatz erlaubt auch größere Zeitschritte, allerdings werden durch
die Bewegung die Partikel ungleichmäßig verteilt.
Der in der Arbeit verwendete semi lagrange’sche Ansatz versucht die Vorteile beider Verfahren
zu verbinden, in dem entlang der Partikel-Pfade integriert wird und die Zielfunktionen an den
Gitterpunkten ausgewertet werden.
Betrachtet man zur Verdeutlichung die eindimensionalen Shallow Water Equations
∂u
∂u
∂h
+u
+g
= 0,
∂t
∂x
∂x
∂h ∂[u(h − b)]
∂h
+
+g
= 0,
∂t
∂x
∂x
so ergibt sich die lagrange’sche Form als
du
∂g
+g
= 0,
dt
∂x
dh
∂b
∂u
−u
+d
= 0,
dt
∂x
∂x
(2.1)
(2.2)
mit d = h − b und der lagrange’schen Ableitung
d
∂
∂
=
+u
dt
∂t
∂x
in der dx
dt = u(x, t) ist.
Nach der semi lagrange’schen Methode werden die Ableitungen entlang von Partikel-Pfaden,
sogenannten Trajektorien approximiert. Für einen Partikel, der sich zum Zeitpunkt tn+1 an Position xi befindet, betrachtet man auch seine Position einen Zeitschritt früher, zum Zeitpunkt
tn . Diese wird als Ausgangspunkt (departure point) x̃ni bezeichnet, da sie bei einer Rückverfolgung entlang der Trajektorie des Partikels den Punkt bezeichnet, an dem sich der Partikel im
vorherigen Zeitrschritt befunden hat (siehe Abbildung 2.5.
Bezeichnet αin = xi − x̃ni die Verschiebung eines Partikels vom Zeitschritt tn nach tn+1 , so
ergeben sich die Funktionswerte für die Ausgangspunkte als
ũni = un (xi − αin )
h̃ni = hn (xi − αin )
Die Verschiebung αin wird dabei durch 4tun (xi ) approximiert.
Da die x̃ni in der Regel nicht genau auf einen Gitterpunkt fallen, und ein direktes Auswerten
der Funktionen u und h damit nicht möglich ist, werden die Werte durch lineare Interpolation
16
Abbildung 2.5: Berechnung der Ausgangspunkte
gewonnen:
Sei xm = m 4 x der m-te Gitterpunkt, und xm−1 < xi − αi < xm , dann gilt
ũni ≈ un (xi − αin ) ≈
(xi − αin − xm−1 )un (xm ) + (xm − xi + αin )un (xm−1 )
4x
(2.3)
h̃ni ≈ hn (xi − αin ), ≈
(xi − αin − xm−1 )hn (xm ) + (xm − xi + αin )hn (xm−1 )
.
4x
(2.4)
Die lagrange’schen Ableitungen lassen sich also approximieren durch
du
un+1 − ũn
=
dt
4t
hn+1 − h̃n
dh
=
dt
4t
Übernimmt man diese Approximationen für die Gleichungen 2.1 und 2.2, und nimmt weiterhin
die Wasserhöhe d im Intervall (tn , tn+1 ) als konstant an, ergibt sich folgende zeitliche Diskretisierung:
un+1 − ũn
∂hn+1
+g
=0
4t
∂x
(2.5)
hn+1 − h̃n
∂b
∂un+1
− un+1
+ dn
= 0.
4t
∂x
∂x
(2.6)
2.3.5
Die diskretisierten Shallow Water Equations
Nimmt man partielle Ableitung von Gleichung 2.3.5 nach x, können mittels der resultierenden
n+1
Gleichung und die ∂u∂x und un+1 -Terme aus eliminiert werden, und man erhält eine sog.
Helmholtz-Gleichung in hn+1 :
hn+1 + 4t2 g
n
∂b ∂hn+1
∂ 2 hn+1
n
n ∂b
n ∂ ũ
− 4t2 gdn
=
h̃
+
4tũ
−
4td
.
∂x ∂x
∂x2
∂x
∂x
(2.7)
Über die zuvor beschriebenen zentrale Differenzenquotienten gelangt man zu folgender Diskretisierung für den eindimensionalen Fall, deren Lösung das neue Höhenfeld hn+1 ist:
n+1
n+1
− bi−1 hi+1 − hi−1 24x
24x
hn+1 − 2hn+1 + hn+1 i−1
i
i+1
− 4 t2 gdni
24x
b
i+1 − bi−1
= h̃ni + 4tũni +
24x
ũn − ũn i+1
i−1
− 4 tdni
.
24x
hn+1
+ 4t2 g
i
b
i+1
(2.8)
Vollkommen analog zum eindimensionalen Fall verläuft die Herleitung für den zweidimensionalen Fall, und man erhält:
hn+1
i,j
2
+ 4t g
b
n+1
n+1
− bi−1,j hi+1,j − hi−1,j
+
24x
24x
n+1
n+1
bi,j+1 − bi,j−1 hi,j+1 − hi,j−1 i+1,j
− 4 t2 gdni,j
24y
24y
hn+1 − 2hn+1 + hn+1
i−1,j
i,j
4x2
i+1,j
+
n+1
n+1 hn+1
i,j−1 − 2hi,j + hi,j+1
= h̃ni,j
4y 2
bi+1,j − bi−1,j
n bi,j+1 − bi,j−1
+ 4t ũni,j
+ ṽi,j
24x
24y
n
n
n
ũn
−
ũ
ṽ
i+1,j
i−1,j
i,j+1 − ṽi,j−1
n
− 4 tdi,j
+
24x
24y
(2.9)
Da das Bodenprofil b konstant bleibt, kann auf einen zeitlichen Index verzichtet werden. Der
Ablauf zur Lösung der diskreten Shallow Water Equations lässt sich nun wie folgt zusammenfassen:
1. Initialisierung von u0 ,v 0 ,h0 und b.
2. Für jeden Zeitschritt tn+1 :
• Berechnung der Ausgangs-Punkte hn , un und v n (Gleichungen 2.3,2.4).
• Lösung von Gleichung 2.9 zur Berechnung von hn+1 .
18
• Aktualisierung von un+1 und v n+1 (2.3.5 für un+1 , v n+1 analog).
Im Rahmen dieser Arbeit reicht das approximative Lösen von Gleichung 2.49 durch wenige
Iterationen des sogenannten 2.9 aus.
2.3.6
Das Jacobi-Verfahren
Das Jacobi-Verfahren ist ein sogenanntes Iterationsverfahren zur näherungsweisen Lösung für
lineare Gleichungssysteme der Form Ax = b, A ∈ Rn×n und x, b ∈ Rn , die z.B. wie folgt
aufgebaut sind:
a1,1 x1 + a2,1 x2 + . . . +n,1 xn = b1
a1,2 x1 + a2,2 x2 + . . . +n,2 xn = b2
..
.
a1,n x1 + a2,n x2 + . . . +n,n xn = bn
Zur Lösung wird die ite Gleichung nach xi aufgelöst:
xi =
X
1 bi −
ai,j xj
ai,i
j6=i
Diese Substitution wird ausgehend von einem gegebenen Wert x0 für alle xi wiederholt. In
Matrixschreibweise wird die Matrix A des linearen Gleichungssystems Ax = b vorbereitend
in eine Diagonalmatrix D, eine untere Dreiecksmatrix L und eine obere Dreiecksmatrix U
zerlegt, so dass gilt:
A = L + D + U.
Die komponentenweise Iterationsvorschrift lässt sich dann darstellen als
xn+1 = xn + D−1 (b − Ax),
wobei xn+1 die Lösung des nten Iterationsschritt bezeichnet [30]. Das Inverse der Diagonalen
D wird also als Approximation von A−1 verwendet, die Teilmatritzen U und L werden ignoriert.
Damit die Koeffizienten deutlich ersichtlich werden, werden die diskreten SWEs aus Gleichung
2.9 weiter umgeformt
2 4 t2 gdni,j
2 4 t2 gdni,j n+1
+
)hi,j
4x2
4y 2
4t2 g(bi−1,j − bi+1,j ) 4t2 gdni,j n+1
−
)hi−1,j
+(
4 4 x2
4x2
4t2 g(bi+1,j − bi−1,j ) 4t2 gdni,j n+1
+(
−
)hi+1,j
4 4 x2
4x2
4t2 g(bi,j−1 − bi,j+1 ) 4t2 gdni,j n+1
+(
−
)hi,j−1
4 4 y2
4y 2
4t2 g(bi,j+1 − bi,j−1 ) 4t2 gdni,j n+1
−
)hi,j+1
+(
4 4 y2
4y 2
bi+1,j − bi−1,j
n bi,j+1 − bi,j−1
+ ṽi,j
+ 4t ũni,j
24x
24y
n
n
n
ũn
−
ũ
ṽ
i+1,j
i−1,j
i,j+1 − ṽi,j−1
n
− 4 tdi,j
+
24x
24y
(1 +
= h̃ni,j
(2.10)
Notwendige Bedingung für die Konvergenz des Verfahrens (sprich die einzelnen Unbekannten
nähern sich einem Grenzwert an) sind von Null verschiedene Diagonalen-Elemente (ai,i ). Diese Bedingung ist wie aus obiger Gleichung ersichtlich erfüllt, da neben von Null verschiedene
Zeitschrittgrößen 4t und Schwerkraftkonstante g auch eine Wasserhöhe d > 0 vorausgesetzt
wird.
Hinreichende ist die strikte Diagonaldominanz der Matrix A. Nach [30] ist eine Matrix dann
strikt diagonaldominant, wenn sie das starke Zeilensummenkriterium erfüllt:
q∞ := max
i=1...n
n
X
ai,k
< 1,
ai,i
i=1,k6=i
bzw.
|ai,i | >
X
|ai,j |.
j6=i
Betrachtet man die konkreten Koeffizienten aus Gleichung 2.10, so muss gelten
(1 +
(
2 4 t2 gdni,j
2 4 t2 gdni,j
+
)>
4x2
4y 2
4t2 g(bi−1,j − bi+1,j ) 4t2 gdni,j
−
)
4 4 x2
4x2
+(
4t2 g(bi+1,j − bi−1,j ) 4t2 gdni,j
−
)
4 4 x2
4x2
+(
4t2 g(bi,j−1 − bi,j+1 ) 4t2 gdni,j
−
)
4 4 y2
4y 2
+(
4t2 g(bi,j+1 − bi,j−1 ) 4t2 gdni,j
−
).
4 4 y2
4y 2
20
Durch Ausrechnen der Summe der rechten Seite gelangt man zu
2 4 t2 gdni,j
2 4 t2 gdni,j
2 4 t2 gdni,j
2 4 t2 gdni,j
(1 +
+
)>−
−
,
4x2
4y 2
4x2
4y 2
woraus die Gültigkeit der Ungleichung direkt ersichtlich wird und von einer Konvergenz des
Jacobi-Verfahrens ausgegangen werden kann.
Das beschriebene Verfahren zur Diskretisierung der Shallow Water Equations wird in [29]
als nicht energieerhaltend bezeichnet. Obwohl in den zugrundeliegenden Gleichungen keine
Dämpfung enthalten ist, werden die Wellen nach und nach flacher, bishin zur absoluten beruhigung der Wasseroberfläche. Dies lässt sich durch die durch räumliche Diskretisierung und die
implizite Integration eingeführte numerische Dämpfung erklären, und stellt in sofern kein Problem da, als dass dieses „Aussterben“der Wellen genau das ist, was wir in der Natur erwarten
würden.
Als Maß für die Genauigkeit der Lösung kann also nur die Betrachtung des Volumens herangezogen werden. In [29] wird von einem Volumenverlust von fünf Prozent gesprochen, ein Wert
der optisch nicht festzustellen ist, und damit im Rahmen des Akzeptablen liegt. Da eine geometrische Analyse des Volumens - z.B. durch Zerlegung in Tetraeder - zu ungenau ist, bediene
ich mich einer sogenannten Gauß Quadratur.
2.4
Volumenbestimmung
Die Gaußsche Quadraturformel (2n + 2)ter Ordnung für eine beliebige polynomielle Funktion
f über einem Interval [a, b] ist für n = 1 definiert als
I (1) (f ) =
p
p
b−a
f (c − 1/3h) + f (c + 1/3h),
2
b−a
mit c = b+a
2 und h = 2 .
Die zugehörige summierte Gaußsche Quadraturformel hat die Gestalt
1
(1)
Ih (f ) =
hX
f (xj + h0 ) + f (xj+1 − h0 )
2
j=0
1
mit xj = a + jh, h = (b − a)/n und h0 = ( 12 − 2√
)h, und ist eine exakte Repräsentation
3
Rb
von f (x), so lange der Grad des Polynoms f kleiner als drei ist. Auf einen Beweis der Kora
rektheit dieser Aussage will ich an dieser Stelle verzichten, verweise den interessierten Leser
stattdessen auf [41].
Betrachtet man das Höhenfeld für die Wasseroberfläche als zweidimensionale Funktion h(x, y) =
z, und auch das das Bodenprofil beschreibende Höhenfeld als solche, also b(x, y) = z 0 , so lässt
sich das zwischen Boden und Wasseroberfläche eingeschlossene Volumen V 0 bis auf Run-
2.4. VOLUMENBESTIMMUNG
21
dungsfehler genau bestimmen durch
V
=
n−1
X n−1
X
k=0 l=0
−
n−1
X n−1
X
k=0 l=0
1
1
i=0
j=0
1
1
i=0
j=0
hXhX
h(xk,i + h0 , yl,j + h0 ) + h(xk,i+1 − h0 , yl,j+1 − h0 ) (2.6)
2
2
hXhX
b(xk,i + h0 , yl,j + h0 ) + b(xk,i+1 − h0 , yl,j+1 − h0 ).
2
2
für xi,k = k 4 x + i 4 x und yj,l = l 4 y + j 4 y.
Für Polynome bis zum Grad fünf werden drei Stützstellen benötigt:
2
(2)
Ih (f )
h X
1
=
5f (xj + h0 ) + 8f (xj + h) + 5f (xj+1 − h0 ).
18
2
j=0
Das Volumen ergibt sich analog zu 2.7 zu
n−1
X n−1
X
2
n−1
X n−1
X
2
2
h X h X
5h(xk,i + h0 , yl,j + h0 )
18
18
i=0
j=0
k=0 l=0
h
h
+8h(xk,i + , yl,j + ) + 5h(xk,i+1 − h0 , yl,j+1 − h0 )
2
2
V =
2
h X h X
5b(xk,i + h0 , yl,j + h0 )
18
18
i=0
j=0
k=0 l=0
h
h
+8b(xk,i + , yl,j + ) + 5b(xk,i+1 − h0 , yl,j+1 − h0 ) .
2
2
−
(2.7)
22
Kapitel 3
Grafikkarten-Programmierung
3.1
Die programmierbare Grafik-Pipeline
Eine wesentliche Neuerung im Grafikkartensektor der letzten Jahre ist die Programmierbarkeit
der sogenannten Shader-Units. Diese Teile der Grafik-Pipeline berechnen die Farbwerte der
Szenerie an den Knoten der Geometrie und für die Pixel der auf den Bildschirm projizierten
Ausgabe, in Abhängigkeit von Parametern wie z.B. Beleuchtung und Texturierung. Man spricht
von Vertex-Shadern für die Knoten-Verarbeitung und von Fragment- oder Pixel-Shadern für die
Bearbeitung der Pixel.
Die programmierbaren Shader-Units lösen die sogenannte Fixed Function Pipeline ab, in der
Transformation, Beleuchtung und die Verarbeitung der Texturen in der Grafik-Pipeline nur
durch wenige Parameter beeinflussbar waren.
Diese Funktionalität wird nun durch vom Benutzer programmierte Vertex- und FragmentProgramme festgelegt (vgl. Abbildungen 3.1 und 3.2, [31]).
Der Funktionsumfang, der in den Shadern zur Verfügung steht, wird dabei in sogenannten Profilen beschrieben, da er (im Gegensatz zu normalen CPUs) zwischen den einzelnen GrafikkartenGenerationen sowohl für den Vertex-Shader als auch für den Fragment-Shader stark variiert.
Das Vertex-Programm wird für jeden Knoten der Szenengeometrie einmal ausgeführt. Mehrere parallele Vertex-Pipelines auf der Hardware ermöglichen das gleichzeitige Abarbeiten der
Knotenprogramme für verschiedene Vertices. Die Anzahl der zur Verfügung stehenden Pipelines ist abhängig von der eingesetzten Grafik-Hardware. So stehen z.B. auf einer mit Nvidia
GForce 6800 GT Chipsatz ausgestatteten Grafikkarte sechs Vertex-Pipelines zur Verfügung,
während es auf dem neueren GForce 7800GTX Chipsatz bereits acht sind.
23
24
KAPITEL 3. GRAFIKKARTEN-PROGRAMMIERUNG
Abbildung 3.1: Programmierbarkeit bei der Knotenverarbeitung
Abbildung 3.2: Programmierbarkeit bei der Fragmentverarbeitung
Das Fragment-Programm wird für jeden gerenderten Pixel ausgeführt. Die große Anzahl an nötigen Programmdurchläufen wird dabei analog zum Vertex-Shader auf mehrere Pixel-Pipelines
verteilt. Auch hier ist die Anzahl der zur Verfügung stehenden Pipelines abhängig von der
Hardware. Den 16 Pipelines auf der NVidia GForce 6800GT stehen bereits 24 Pipelines auf
der neueren 7800GTX gegenüber.
Die programmierbaren Fragment-Shader sind in dieser Arbeit in besonderem Maße für die
Lösung der Gleichungssysteme relevant. Neben der Verwendung der arithmetischen Rechenwerke wird vor allem von der Möglichkeit Gebrauch gemacht, über sogenannte Texture Image
3.2. GENERAL-PURPOSE COMPUTING ON GRAPHICS PROCESSING UNITS
25
Units aus den Shader-Programmen heraus mit 32bit Genauigkeit Fließkommazahlen aus dem
Texturspeicher zu lesen, und die (Zwischen-)Ergebnisse der Berechnungen auch wieder im
Texturspeicher abzulegen.
Zur Programmierung der Vertex- und Fragmentshader stehen mehrere Sprachen zur Verfügung. Diese reichen von Assembler-ähnlichen, hardwarenahen Sprachen bis hin zu C-ähnlichen
High-Level-Sprachen wie GLSL (GL Shading Language) oder der von NVidia entwickelten
Sprache Cg (C for Graphics), die via Compiler in hardwarenahen Code übersetzt werden. Die
Shader-Programme der Arbeit sind in Cg verfasst, könnten aber auch mit verhältnismäßig geringem Aufwand in eine andere Sprache übertragen werden.
Vertex-Shader werden in dieser Arbeit nur zur Visualisierung verwendet, für das Lösen der
Gleichungssysteme werden sie nicht benötigt. Eine Besonderheit der oben genannten NVidiaGPUs liegt in ihrer Fähigkeit, auch im Vertex-Shader auf den Textur-Speicher zuzugreifen,
was auf GPUs anderer Hersteller bislang nur im Fragment-Shader möglich ist. Diesen Vorgang
nennt man Vertex-Texture-Fetch, oder kurz VTF. Im Implementierungsteil dieser Arbeit wird
sich dieser Besonderheit für eine in Kapitel 4.4 vorgestellte Variante in der Visualisierung zu
nutze gemacht.
3.2
General-Purpose Computing on Graphics Processing Units
GPGPU steht für General-Purpose Computing on Graphics Processing Units, und beschreibt
zusammenfassend die Bemühungen einer wachsenden Gemeinschaft, Grafikkarten für die Lösung von Problemen zu nutzen, die auf den ersten Blick nichts mit deren „traditioneller“ Aufgabe - der Bilderzeugung - zu tun haben, um die Leistung der CPU für die Lösung des gleichen
Problems zu übertreffen.
Vergleicht man die theorethische Spitzenleistung von 63 GFLOPS einer GeForce 6800 Ultra
(GFLOPS steht für ”giga floating point operations per second”, also eine Milliarde Gleitkommaoperationen in der Sekunde) mit den 14.8 GFLOPs eines Intel Pentium 4 SSE, und hält sich
vor Augen, dass sich die Performance zur Zeit jährlich in etwa vervierfacht, werden die Gründe dafür schnell klar. Das vielzitierte Mooresche Gesetz, das die Beobachtung beschreibt, dass
sich die Komplexität und Leistungsfähigkeit von integrierten Schaltkreisen alle 18 Monate in
etwa verdoppelt, wird also von der Grafikkartenentwicklung noch weit übertroffen [38].
Vor allem die steigende Flexibilität der Hardware, die in den letzten Jahren vom Ändern einzelner Bilderzeugugs-Parameter zu voller Programierbarkeit - also dem Ausführen von Mikrocode
auf der Hardware - erweitert wurde, erlauben eine abstrakte Sicht auf die GPU, in der sie als
paralleler Data-Stream-Processor erscheint.
Im Gegensatz zum bei der CPU-Programmierung gebräuchlichen Instruction-Stream-Processing
(Abbildung 3.3), bei dem Daten und Anweisungen im gleichen Speicher residieren und zur
Ausführung abwechselnd in den Cache (einen schnellen, meist in die CPU integrierten PufferSpeicher) geladen werden und dem das klassische von Neumann-Modell zugrunde liegt, wird
beim Data-Stream-Processing (Abbildung 3.4) zunächst der Prozessor mit den auszuführenden
26
Instruktionen konfiguriert, die sich für die zu verarbeitenden Daten-Blöcke nicht ändern.
Beide Ansätze haben ihre Vor- und Nachteile: Beim Instruction-Stream-Processing wird ein
hoher Grad an Flexibilität erreicht. Dadurch dass die Daten-Sequenz aber vollständig von der
Anweisungs-Sequenz bestimmt wird, geht Rechenleistung verloren, wenn die Anweisungen
sich für einen großen Datenblock nicht ändern.
Abbildung 3.3: Instruction-Stream-Processing
Das Data-Stream-Prozessing ist gerade dann von Vorteil. Genügend Speicherbandbreite vorausgesetzt, kann die Abarbeitung der Instruktionen auf verschiedene parallele Pipelines verteilt
werden ( [47]).
Abbildung 3.4: Data-Stream-Processing
Die Daten der Eingabe entsprechen dabei auf der GPU den in Texturen gespeicherten Farbwerten, die in verschiedenen Formaten vorliegen können. Welche Texturformate unterstützt
werden, hängt mit dem verwendeten Grafikkarten-Modell zusammen. Für diese Arbeit werden
128 Bit-tiefe RGBA-Texturen verwendet, die also 32 Bit Fließkomma-Genauigkeit in allen vier
Kanälen erreichen.
3.3. OPTIMIERUNG VON GPU PROGRAMMEN
3.3
27
Optimierung von GPU Programmen
Damit eine GPU-Implementierung den gewünschten Geschwindigkeitsgewinn gegenüber ihrem CPU-Gegenstück erzielt, müssen allerdings einige Besonderheiten beachtet werden, wie
sie ausführlich z.B in [19], [49], [14] oder [24] beschrieben werden. Im folgenden werde ich
einige dieser Merkmale beschreiben, und auf ihre Berücksichtigung in der Implementierung
dieser Arbeit eingehen.
3.3.1
Bustransfer
Bevor Daten überhaupt auf der Grafikkarte verarbeitet werden können, müssen sie je nach
Grafikkarten-Typ über den AGP- oder PCI-Express-Bus zur GPU übertragen werden. Abbildung 3.5 zeigt die verschiedenen Speicherbereiche und deren Zusammenhang [14].
Abbildung 3.5: Die verschiedenen Speicherbereiche
Die Übertragung von der CPU zur GPU stellt einen nicht zu unterschätzenden Flaschenhals dar.
So könnte z.B. die Addition zweier großer Vektoren auf der CPU bereits durchgeführt sein, bevor die Daten überhaupt zur GPU übertragen worden sind. Gleiches gilt für den Rücktransport
der Daten von der GPU zum Hauptspeicher. Diese Kosten amortisieren sich erst, wenn sehr oft
über die Daten iteriert wird, bevor sie zum Hauptspeicher zurücktransferiert werden.
Die Implementierung dieser Arbeit kommt ganz ohne Rücktransfer von der GPU zur CPU
aus. Die Ergebnisse der näherungsweisen Lösung bleiben im Speicher der Grafikkarte, und
werden „vor Ort“ mit den in Kapitel 4 beschriebenen Techniken visualisiert. Abgesehen von
der Übertragung der intialen Geschwindigkeits- und Höhenwerte werden auch keine weiteren
Daten von der CPU zur GPU übertragen.
28
3.3.2
Speicher-Zugriff
Generell können drei Arten von Speicherzugriffs-Mustern unterschieden werden:
• cached: Der gleiche Speicherbereich wird wieder und wieder gelesen. Nach dem ersten
Zugriff liegen die Daten im sog. Textur-Cache, wo sie besonders schnell abrufbar sind.
• sequentiell: Die Zugriffe erfolgen auf im Video-Speicher hintereinander liegende Bereiche, bzw. auf lokale Nachbarschaften wie im Texturspeicher benachbarte Texel.
• zufällig: Die zu lesenden Daten liegen überall über den Video-Speicher verteilt.
Sowohl für die CPU- als auch für die GPU-Progammierung gilt: Gute Performanz hängt eng
mit der Lokalität der Speicher-Verweise zusammen. Zufällige Speicherzugriffe führen zu einer
dramatischen Verschlechterung der erzielten Ergebnisse in Bezug auf die Geschwindigkeit.
Während der CPU Cache mit weit höheren Taktraten agiert als der der GPU, zudem sowohl
lesende wie auch schreibende Zugriffe unterstützt und weitaus größer ist - der Cache der GPU
beschränkt sich typischerweise auf wenige Texel - hat die GPU - deren Hauptzweck das Füllen
von zusammenhängenden Speicherregionen mit Bildinformationen ist - gegenüber der CPU
große Vorteile im sequentiellen Bereich, wie Abbildung 3.6 zeigt.
Abbildung 3.6: Vergleich der Speicher-Zugriffsgeschwindigkeit
Eine Anwendung kann also den größten Gewinn durch eine Portierung auf die GPU erwarten,
wenn sie um einen sequentiellen Speicherzugriff aufgebaut ist.
Der in der Implementierung verwendete Algorithmus trägt dieser Beobachtung Rechenschaft.
Die Berechnung der Höhen- und Geschwindigkeits-Werte an den Gittererpunkten erfolgt streng
sequentiell, und alle zur Bestimmung der zentralen Differenzenquotienten nötigen lesenden
Speicherzugriffe beziehen sich auf unmittelbar benachbarte Texel.
3.3. OPTIMIERUNG VON GPU PROGRAMMEN
3.3.3
29
Arithmetische Intensität
Speicherzugriffs-Muster sind nicht der einzige bestimmende Faktor für eine im Vergleich zur
CPU schnelle GPU Implementierung. Der Hauptvorteil der GPU liegt in der immensen Rechenleistung. So lange die Anwendung von arithmetischen Operationen dominiert wird, und
die Anzahl der Speicherzugriffe (Textur-Lookups) verhältnismäßig gering ist, wird sie auf der
GPU schneller laufen als auf einer CPU.
Um die Latenz einer Texture-Fetch-Operation z.B. in einem Fragment-Shader-Programm zu
verdecken, wird der GPU-interne Scheduler, der für die Verwaltung der Resourcen zuständig
ist, zunächst die Bearbeitung eines benachbarten Fragments aufnehmen. Sobald die TexturEinheit die angeforderten Daten vorliegen hat, wird die Arbeit am nächsten Fragment ausgesetzt (man spricht von Suspending), und im ersten Fragment wieder aufgenommen, um
dort mit den arithmetischen Operationen fortzufahren (Resuming). Daher ist es auch für gute
Programm-Leistung förderlich, wenn nicht alle Textur-Lookups zu Beginn des Shaders ausgeführt werden, sondern sich möglichst gleichmäßig auf den gesamten Code verteilen.
Das Verhältnis von arithmetischen zu Speicher-Operationen bezeichnet man als arithmetische
Intensität einer Anwendung ( [19]).
Die Anzahl der Operationen die eine Anwendung pro aus dem Textur-Speicher gelesenen Wert
ausführen sollte, um die Latenz zu verstecken, liegt derzeit zwischen 7 und 10.
Der in der Implementierung der Arbeit verwendete Shader, der die näherungsweise Lösung
des Gleichungssystems vermittels eines Jacobi-Verfahrens vornimmt, und den Großteil der
Rechenzeit des Algorithmus in Anspruch nimmt, besteht aus etwas mehr als 82 AssemblerInstruktionen, von denen acht Textur-Lookups sind. Rechnete man auf diesen Zahlen basierend
die arithmetische Intensität der Anwendung aus, erhielte man einen Wert von 7.2.
Ein verbreiteter Test (wie er z.B. in [39] verwendet wird), mit dem man einfach überprüfen
kann, ob eine GPU-Anwendung compute bound (in der Leistung von der der arithmetischen
Einheiten in der Pipeline begrenzt) oder memory bound (durch die Speicher-Bandbreite begrenzt) ist, sieht vor, die Texur-Bandbreite zu halbieren. Im konkreten Fall dieser Arbeit bedeutet das mit 64-Bit-tiefen Texturen zu rechnen, anstatt mit 128-Bit. Die Ungenauigkeit der
Lösung spielt für diesen reinen Leistungs-Test keine Rolle.
Ändert sich die beobachtete Geschwindigkeit dadurch nicht, ist der Speicherzugriff nicht der
Engpass, und die Anwendung ist compute bound.
Dieser Test führt bei der hier vorliegenden Implementierung (bei ausgeschalteter Visualisierung) dazu, dass sich die erreichten Frames pro Sekunde mehr als verdreifachen (ein Frame
enstpricht einem näherungweise gelösten Zeitschritt).
Ganz offensichtlich wird der Code intern noch derart optimiert, dass die arithmetische Intensität wesentlich niedriger liegt, als aus der manuellen Auswertung des Codes ersichtlich.
Tatsächlich ergibt eine Analyse der Shaderprogramme mit dem von NVidia bereitgestellten
Tool NVShaderPerf [9], das zur Abarbeitung aller Operationen einer Jacobi-Iteration 33 Zyklen benötigt werden, unter der Annahme, dass ein Textur-Lookup mit einem Takt zu Buche
schlägt.
Da die Anzahl der Textur-Zugriffe nach wie vor bei 10 liegt, ergibt sich eine arithmetische Intensität von nur 2.3.
Die Anwendung ist also in der Tat memory bound, was für numerische Simulationen im all-
30
gemeinen aber keine Besonderheit darstellt, sondern die Regel ist, wie z.B. in den Veröffentlichungen von [15, 18] festgestellt.
Kapitel 4
Implementierung
4.1
Werkzeuge und Bibliotheken
Im folgenden soll nun die Implementierung der Arbeit beschrieben werden. Vorab sei erwähnt,
dass die Implementierung in C++ ausschließlich auf Windows Basis erfolgte. Der Support für
Grafikkarten-Treiber ist auf dieser Plattform deutlich besser als z.B. unter Linux, was sich primär durch den größeren Markt für Spiele auf diesem Betriebssystem erklären lässt.
Dennoch wurden die Entwicklungswerkzeuge und Bibliotheken so gewählt, dass eine Portierung auf Linux und andere Plattformen ohne große Komplikationen möglich ist, da alle entweder als open source Pakete verfügbar oder zumindest frei erhältlich sind. Im einzelnen wurden
verwendet:
• Eclipse (Version 3.1.0, [5])
• CDT (Version 2.1.1, [4])
• MinGW Minimalis GNU for Windows (Version 3.4.2, [32])
• NVidia SDK (Version 9.5, [37])
• NVidia CG Toolkit (Version 1.3, [8])
• GLEW OpenGL Extension Wrangler Library (Version 1.3.3, [13])
• GLUT for Mingw32 (Version 3.7.3, [6])
• Framebufferobject Class (Version 1.0 [7])
Eclipse ist ein open source Projekt, das sich die Bereitstellung einer flexiblen Entwicklungsumgebung zum Ziel gesetzt hat. Ursprünglich für Java-Anwendungen gedacht, steht mit CDT
auch ein Plugin zur Programmierung von C/C++ Applikationen zur Verfügung.
Als Compiler wird der GNU Compiler für Windows MinGW verwendet, der eine spezielle
Version von GLUT, dem OpenGL Utility Toolkit benötigt. Für die Shader-Programmierung
31
32
KAPITEL 4. IMPLEMENTIERUNG
werden das NVidia SDK in Verbindung mit dem NVidia CG Toolkit eingesetzt.
Die GLEW-Bibliothek vereinfacht dabei den Umgang mit den verwendeten OpenGL-Extensions,
die zum Teil direkt, zum Teil aber auch von der Framebufferobject Klasse benutzt werden.
Des weiteren wurde zur Analyse der Shader-Programme das von NVidia bereitgestellte Programm NVShaderPerf [9], und zur optischen Auswertung der erzielten Ergebnisse das VisualisierungsProgramm GMV [1] verwendet.
4.2
Das Rahmenprogramm
Wie bereits im Grundlagen-Kapitel dieser Arbeit beschrieben, wird in jedem Zeitschritt ein
Gleichungssystem aufgestellt. Dafür müssen zunächst die Funktionen für die Geschwindigkeiten ũ und ṽ sowie für die Höhenwerte h̃ an den Ausgangspunkten auf Basis der gegebenen u,v,h und b-Werte berechnet werden (Schritt 1). Sobald diese vorliegen, kann mit dem
iterativen Lösen des Systems begonnen werden (Schritt 2). Mit den so gewonnenen neuen hWerten und den zuvor berechneten Funktionen für die Ausgangspunkte ist es dann möglich,
die Geschwindigkeits-Funktionen u und v für den nächsten Zeitschritt zu aktualisieren (Schritt
3).
Die für die Visualisierung notwendigen neuen h-Werte liegen bereits nach Schritt 2 vor. Jedoch
wird, um unnötig häufiges Umstellen der OpenGL-Projektions-Matrix zu vermeiden (s.u.), die
Visualisierung erst nach Schritt 3 vorgenommen. Der Ablauf des Algorithmus lässt sich also
wie in Abbildung 4.1 gezeigt darstellen.
Abbildung 4.1: Skizze des Programmablaufs
4.2. DAS RAHMENPROGRAMM
4.2.1
33
Initialisierung
Der erste Schritt für den eigentlichen Progammablauf besteht im Anlegen und Füllen geeignet dimensionierter Arrays mit den initialen Werten für u, v, h und b. Dabei entspricht der
Wert des Arrays an Position j × n + i dem Wert für den Gitterpunkt (i, j), wobei n die Anzahl der Punkte in x-Richtung angibt. Die Werte werden in der beiliegenden Implementierung
(Methoden allocateValueArrays, addWater, allocateTextures) prozedural
gesetzt, ein Import der initialen Werte aus einer Bitmap oder einem beliebigen Gittergenerator
wäre als Erweiterung denkbar.
Um das beschriebene System auf der GPU lösen zu können, müssen diese Werte anschließend
in geeignete Texturen überführt werden.
4.2.2
Textur-Datenstrukturen
Betrachtet man ein Gitter mit n × n Punkten, so muss für jeden dieser Punkte ein Texel für
die entsprechenden u, v, h, b, ũ, ṽ, h̃ Werte reserviert werden. Das Anlegen der 128 Bit tiefen
RGBA Texturen (32 Bit pro Kanal) erfolgt via OpenGL (Methode allocateTextures).
Die Textur wird an dieser Stelle noch nicht mit Farbwerten gefüllt, sondern an ein FramebufferObjekt gebunden.
4.2.3
Das Framebuffer-Objekt
Ein Buffer ist in diesem Zusammenhang ein zweidimensionales Array, das Daten pro Pixel speichert. Ein 1024×768 Pixel großer Bildschirm wird dabei auch durch ein Array mit
1024×768 Elementen repräsentiert.
Die Bezeichnung Framebuffer ist eine Zusammenfassung vierer verschiedener Sorten von Buffern:
• Der Color Buffer, in dem jedem Pixel eine Farbe zugeordnet wird. Er stellt die sichtbare
Ausgabe eines (OpenGL-)Programms dar.
• Der Depth Buffer, in dem die Tiefeninfomation für jedes durch ein Pixel repräsentiertes Objekt gehalten wird. Er wird z.B. für die Sichtbarkeits- Berechnung von Objekten
verwendet.
• Der Stencil Buffer, mit dem nicht sichtbare Teile der Ausgabe maskiert werden.
• Der Accumulation Buffer, der zur Komposition der Ausgabe-Pixel aus mehreren Pixeln
dient. Er wird für z.B. für Antialiasing-, Unschärfe- und Schatten- Effekte verwendet.
Genauere Infomationen finden sich z.B. unter [10] und in vielen OpenGL- Tutorials.
Framebuffer-Objekte (FBOs) sind eine OpenGL Erweiterung, die es ermöglicht, off-screen in
andere als den vom verwendeten windowing system (X, Microsoft Windows, etc...) bereitgestellten Framebuffer (dem sichtbaren on-screen Fenster) zu rendern.
Sie ist als Ablösung für die sogenannte PBuffer Extension konzipiert, die dies zwar bereits
ermöglichte, aber einige gravierende Nachteile hatte, von denen hier nur die für die Implementierung relevanten aufgezählt werden sollen ( [22]):
• Plattformabhängigen Implementierung, die eine protable Entwicklung von Applikationen erschwert,
34
• jeder PBuffer ist an seinen eigenen OpenGL Kontext gebunden, woraus ”teure” Context
Switches beim Wechsel des Rendering-Zieles resultieren,
• das Texturformat ist durch das Pixel-Format des PBuffers bestimmt, und
• jeder PBuffer hat seine eigenen Depth-, Aux- und Stencil- Buffer.
Die wesentlichen Neuerungen des Frambuffer-Objekt-Konzepts liegen neben der plattformübergreifend einheitlich definierten Schnittstelle und dem Entfallen eines Context-Switches
beim Wechsel des Rendering-Zieles vor allem in der Art und Weise, wie die verschiedenen Framebuffer attachable images an ein Framebuffer-Objekt „angekoppelt“werden können.
Dies wird in Abbildung 4.2 verdeutlicht. Es wird hier unteschieden zwischen Texture- und
Renderbuffer-Images, von denen erstere im Anschluss an eine Rendering-Operation in das
Framebuffer-Objekt als Textur zur Verfügung stehen. Man spricht bei diesem Vorgang auch
von „Render to Texture“ (siehe z.B. [2]). Die Original-Spezifikation kann unter [3] eingesehen
werden.
Konzeptionell ist ein FBO also nur eine Struktur von Zeigern, nur denen beispielsweise eine
Textur als das Ziel einer Rendering-Operation festgelegt wird.
Abbildung 4.2: Die Architektur des Framebuffer-Objekts
Die Implementierung macht nur von der Möglichkeiten Gebrauch, die das Andocken von
Texture-Images mit sich bringen. Der Depth-Buffer wird nicht benötigt. Obwohl eine Verwendung des Stencil-Buffers zum Einsparen von Berechnungen - auf den Teilen des Gebiets,
in denen kein Wasser vorhanden ist - denkbar ist, wird dieser Teil der Spezifikation zum Zeitpunkt der Implementierung von den verfügbaren OpenGL-Treibern nicht unterstützt.
Wie eingangs erwähnt wird eine Bibliothek für den Umgang mit den Framebuffer-Objekten
eingesetzt, die FramebufferObject Class. Diese kapselt dabei folgenden Aufrufe:
• glGenFramebuffersEXT Generiert eine Framebuffer ID, an der das Objekt zur späteren Verwendung eindeutig identifiziert werden kann.
4.2. DAS RAHMENPROGRAMM
35
• glBindFramebufferEXT Legt das an seiner ID identifizierte Objekt als aktiven Framebuffer fest. Alle Rendering-Operationen zeichnen nun in diesen Framebuffer.
• glFramebufferTexture2DEXT Ordnet einem ColorAttachment eines FramebufferObjektes eine Textur zu. Alle in diesen Framebuffer gerenderten Pixel stehen wie beschrieben danach als Texel der Textur zur Verfügung, und können in späteren RenderingDurchläufen entsprechend verwendet werden.
Da auf eine Textur nicht gleichzeitig schreibend und lesend zugegriffen werden kann, und
der Jacobi-Löser auf Grundlage der Lösung der letzten Iteration und der zuvor berechneten
Departure Points die neue berechnet, werden insgesamt drei Framebuffer-Objekte mit den entsprechenden Texturen benötigt: Zwei Texturen beinhalten die u, v, h und b Werte, die nach
dem „Ping Pong“ Prinzip abwechselnd als Quelle für bzw. als Ziel des Rendering-Durchlaufs
dienen. Aus der ersten werden jeweils die Werte des letzten Iterationschrittes gelesen, und in
den zuvor aktivierten Framebuffer - an den die zweite Textur gebunden ist - komponentenweise
die errechneten Werte des aktuellen Iterationsschritts geschrieben.
Die dritte Textur dient für die Werte der Departure Points ũ, ṽ, h̃. Der „freie“ Kanal dieser im
folgenden als Ausgangs-Punkte-Textur bezeichneten RGBA-Textur wird mit den Höhenwerten
h des letzten berechneten Zeitschritts (nicht Iterationsschritts) belegt, da diese für den JacobiLöser zur Verfügung stehen müssen.
Nachdem die Framebuffer-Objekte entsprechend initialisiert wurden (Methode allocateTextures), wird OpenGL auf einen an die Größe der Texturen angepassten Viewport
(glViewport(0, 0, n, n)) eingestellt. Via glDrawPixels werden die Werte dann
in sukzessive in die Texturen „gezeichnet“. Abbildung 4.3 zeigt die Zuordnung der initialen
Werte zu den entsprechenden Textur-Kanälen. Von nun an stehen die benötigten Werte also als
Texturen, und damit zur Berechnung in den progammierbaren Shadern zur Verfügung.
Abbildung 4.3: Aufteilung der Unbekannten auf die einzelnen Kanäle der Texturen
36
4.3
Fragment-Shader-Programme
Die Angabe eines Profils (siehe Kapitel 3.1) ist neben der Nennung der „Haupt-Methode“
- dem Einstiegspunkt - zum Kompilieren der Cg-Programme zu auf der GPU ausführbarem
Assembler-Code notwendig. Für eine vollständige Übersicht der zur Zeit existierenden, von
Cg unterstützten Profile verweise ich auf [8].
Die Auswahl des Profils und das Laden und Kompilieren der Programme geschieht in der beiliegenden Implementierung in der Methode initShader. Das in dieser Arbeit verwendete
Profil für den Fragment-Shader ist CG_PROFILE_FP40. Obwohl der von CG_PROFILE_FP30
unterstützte Befehlsumfang vollkommen ausreichend wäre, hat ein früher Test auf einer GForce 6800GT einen (wenn auch sehr geringen) Geschwindigkeitsgewinn durch Verwenden des
CG_PROFILE_FP40 ergeben. Tabelle 4.1 zeigt die erreichten Frames pro Sekunde (ein Frame
entspricht dabei der Berechnung der Ausgangspunkte, 15 Jacobi-Iterationen und anschließende Aktualisierung der Geschwindigkeiten) bei ausgeschalteter Visualisierung, jeweils gemittelt
über 60 Sekunden Simulationslaufzeit.
Gittergröße
128×128
256×256
512×512
CG_PROFILE_FP30
67,89
23,94
6,19
CG_PROFILE_FP40
67,73
24,22
6,64
Tabelle 4.1: Frames pro Sekunde in Abhängigkeit vom verwendeten Profil
Dieser Schluss ist wohlgemerkt nicht zwangsläufigerweise für alle Grafikkarten und Treiberversionen zulässig. Die Ergebnisse zeigen aber, dass auch die allgemein vertretene Annahme,
das „niedrigste“ mögliche Profil berge die größten Vorteile, ihre Ausnahmen hat. Generell sollten Applikationen also die verfügbaren Profile auf ihre Leistungsfähigkeit hin testen, um das
für den konkreten Fall optimale zu ermitteln.
Ein Schritt der Berechnung - sei es nun die Berechnung der Ausgangspunkte, eine JacobiIteration oder das Geschwindigkeits-Update - läuft nun im wesentlichen immer nach dem gleichen Muster ab:
• Der OpenGL-Viewport wird auf eine an die Größe des Gitters angepasste Dimension
und orthogonalen Projektionsmodus eingestellt.
• Das ausgewählte Cg Profil wird aktiviert.
• Das entsprechende, zuvor geladene Shader-Programm wird aktiviert.
• Die benötigten Texturen und andere Parametern werden an das Shader-Programm gebunden. Letztere variieren von Fall zu Fall, und werden in den folgenden Abschnitten
beschrieben.
• Das Ziel-Framebuffer-Objekt wird aktiviert.
4.3. FRAGMENT-SHADER-PROGRAMME
37
• Der komplette Viewport wird ausgefüllt. Dafür gibt es zwei Möglichkeiten:
1. Die Ränder des Viewports werden mit einzelnen Linien gezeichnet. Der verbleibende innere Teil wird mit einem Quad überdeckt.
2. Es wird ein einzelnes, „viewport-großes“Quad gezeichnet.
• Deaktivieren der Textur- und anderen Parameter und des Shader-Programms.
Beim Ausfüllen des Viewports ist darauf zu achten, dass zuvor der Polygon- Modus in OpenGL
auf GL_FILL gesetzt wurde.
Das separate Zeichnen der Ränder ermöglicht die Verwendung spezieller Shader-Programme
für die Berechnung der Randwerte. Verzichtet man darauf, so muss in den Shaderprogrammen
für das ganze Gebiet via if-Klauseln der Rand „nachbearbeitet“ werden. Erstere Art der Randbehandlung wird vielfach empfohlen (siehe z.B. [49], [24]).
Die Fragment-Shader-Units der GPU arbeiten parallel auf mehrere Pixeln gleichzeitig, für die
jeweils nur ein Branch des Codes ausgeführt werden kann. Ist dies nicht möglich, fällt die GPU
zurück auf die sogenannte branch predication Strategie, in der beide Branches ausgeführt werden, aber nur einer wirklich eine Änderung im Ergebnis verursacht.
Während der Implementierung wurden beide Ansätze getestet, es konnte aber kein signifikanter Geschwindigkeits-Gewinn durch die Verwendung separater Shader-Programme für die
Ränder festgestellt werden. Dies lässt sich dadurch erklären, dass die Anwendung ohnehin memory bound ist (siehe Kapitel 3.1.2, 3.1.3), und genügend Kapazität für die relativ wenigen
konditionalen zusätzlichen Instruktionen (von einer im Programm für die Jacobi-Iterationen
(das von allen am häufigsten ausgeführt wird), bis zu maximal drei im Programm für das
Geschwindigkeits-Update) zur Verfügung steht. Die separate Randbehandlung ist in der beiliegenden Implementierung standardmäßig deaktiviert. Sie lässt sich aber per KommandozeilenParameter einschalten (siehe Kapitel 4.5).
Ein wichtiger Parameter, der automatisch im Fragment-Shader im Register WPOS zur Verfügung steht und von dort in den Programmen ausgelesen werden kann, ist die Position des
Fragments (Pixels) im Rendering-Ziel. Aufgrund der Wahl des Viewports als an die TexturGröße angepasstes Quadrat, und dem orthogonalen Projektionsmodus gibt dieses Zweitupel
aus float-Werten (Datentyp float2) stets den Mittelpunkt des Fragments an, beginnend
bei (0.5, 0.5) für den linken oberen, bis zu (n − 0.5, n − 0.5) für den rechten unteren Pixel.
Der Index des dem Fragment logisch zugeordneten Gitterpunktes lässt sich also errechnen, in
dem man jeweils 0.5 von den Richtungskomponenten subtrahiert.
Um mittels Textur-Lookup die dem Gitterpunkt zugeordneten Werte zu gelangen, wird die
Textur-Koordinate in der jeweiligen Dimension als Quotient aus Gitter-Index und der Anzahl
der Gitterpunkte (n−1), die in allen Programmen als Parameter übergeben werden muss, gebildet. Dadurch werden die Textur-Koordinaten auf das Interval von (0, 0) für den linken oberen
Texel bis (1, 1) für den rechten unteren Texel begrenzt. Ein tex2D-Aufruf an diesen Koordinaten (siehe [8]) liefert die in den Texturen gespeicherten Funktionswerte als Viertupel aus
float-Werten (Datentyp float4).
Weitere notwendige Parameter, die in allem Shader-Programmen benötigt werden, sind:
• Die Zeitschritt-Größe ∆t,
• die horizontale Gitter-Weite ∆x und
38
• die vertikale Gitter-Weiter ∆y.
Diese werden von OpenGL via cgGetNamedParameter namentlich identifiziert und über
cgSetParameter1f als float-Werte an die Programme übergeben (siehe [8]).
4.3.1
Berechnung der Departure Points
Das Shader-Programm zur Berechnung der Ausgangs-Punkte finden sich in der beiliegenden
Implementierung in der Dateien frag_departurecalc.cg, sowie im Anhang in Abschnitt A.1.1.
Zur Berechnung werden die Werte der Lösung des letzten Zeitschritts benötigt. Diese liegen
wie zuvor beschrieben als Textur vor. Nach Berechnung der Textur-Koordinaten und Auslesen der u-, v- und h-Werte für den Gitterpunkt wird die Verschiebung des an dieser Position (i, j) befindlichen Partikels seit dem letzten Zeitschritt durch ∆t · uni,j · ∆x approximiert.
Durch Subtraktion selbiger von der aktuellen Position im Gitter erhält man eine Approximation für den Ausgangspunkt. Durch Verwendung von floor- und ceil-Funktionen können die
nächst-kleineren bzw. nächst-größeren ganzzahligen Gitterindizes ermittelt, und die zugehörigen Texturkoordinaten bestimmt werden. Die Bestimmung der ũ-, ṽ- und h̃-Werte erfolgt dann
analog zum in Kapitel 2 beschriebenen Verfahren über bilineare Interpolation aus den dort ausgelesenen Werten. Die von Cg bereitgestellte Funktion lerp zur eindimensionalen linearen
Interpolation wird dafür zunächst für die oberen und unteren Funktionswerte ausgeführt, und
anschließend erneut für die Ergebnisse dieser beiden Interpolationen.
Die ũ-, ṽ- und h̃-Werte werden zusammen mit dem h-Wert aus der Eingabe-Textur wie in
Abbildung 4.3 gezeigt in die Ausgabe geschrieben.
Randbehandlung
Betrachtet man einen Partikel des Fluids, der zum Zeitpunkt dieser Berechnung auf dem Rand
liegt, so muss er sich, da er in dem zugrundeliegenden Modell nicht von aussen „eingedrungen“
sein kann, zuvor an einer der beiden folgenden Positionen befunden haben:
1. Er hat im vorherigen Zeitschritt bereits auf dem Rand gelegen (die orthogonal zum Rand
verlaufende Geschwindigkeitskomponente ist gleich Null).
2. Er hat im Inneren des Gebietes gelegen.
Im ersten Fall ist der nächstkleinere ganzzahlige Gitterindex gleich dem nächstgrößeren, nämlich genau der des Randpunktes. Bei der linearen Interpolation wird also in dieser Richtung im
Endeffekt gar nicht interpoliert, sondern direkt der Randwert gewählt. Dies ist für die ũ-, ṽund h̃-Werte korrekt.
Im zweiten Fall sind die kleineren und größeren ganzzahligen Indizes verschieden, liegen aber
alle im Inneren des Gebietes, wodurch die Interpolation das gewünschte Ergebnis liefert.
Eine gesonderte Randbehandlung kann in diesem Schritt also entfallen.
4.3.2
Jacobi-Iteration
Die Shader-Programme zur Berechnung der Lösung eines Schrittes des Jacobi-Verfahrens finden sich in der beiliegenden Implementierung in den Dateien frag_jacobi.cg, bzw.
4.3. FRAGMENT-SHADER-PROGRAMME
39
frag_jacobi_left.cg, frag_jacobi_right.cg, frag_jacobi_low.cg und
frag_jacobi_up.cg. Das Programm zur Berechnung der Werte für die inneren Gitterpunkte findet sich zusätzlich im Anhang im Abschnitt A.1.2.
Zusätzlich zu ∆t, ∆x und ∆y wird der Parameter g für die Gravitations-Konstante benötigt.
Da die Ableitungen wie in Gleichung 2.54 durch zentrale Differenzenquotienten ersetzt wurden, werden zunächst ausgehend von den durch die Fenster-Position gegebenen Textur-Koordinaten
1
des aktuellen Fragments durch Subtraktion bzw. Addition von n−1
auf die x- bzw. y-Komponente
die Koordinaten für die direkt benachbarten Texel bestimmt. tex2D-Lookups für diese Koordinaten in die Textur für die Ausgangs-Punkte, sowie die Textur, die die Ergebnisse der letzten
Iteration enthält, liefern alle Funktionswerte, die für die Berechnung des h-Wertes der neuen
Iteration notwendig sind.
Dieser Wert ist auch der einzige, der von diesem Shader-Programm verändert wird. Die u- und
v-Werte werden erst im Anschluss an alle Iterationen aktualisiert, und der b-Wert ist ohnehin
zeitlich konstant.
Im Anschluss an eine Jacobi-Iteration wird im Rahmenprogramm ein Wechsel der Eingabeund Ziel-Framebuffer-Objekte vorgenommen. Somit stehen die h-Werte einer Iteration in der
darauffolgenden als Eingabe zur Verfügung.
Randbehandlung
Vor der eigentlichen Berechnung werden in diesem Schritt die senkrechten Komponenten der
Geschwindigkeiten an den Randknoten auf Null gesetzt (ui,j = 0 für i = 0, n − 1, vi,j = 0
für j = 0, n − 1). In den konkaven Ecken des Beckens sowohl u als auch v. Diese Art der
Randbehandlung wird als nicht reflektiv bezeichnet, und modelliert das Verhalten der Wellen
wie z.B. in einem festen Becken ( [29]).
Obwohl diese Randbehandlung sich intuitiv für die Aktualisierung der Geschwindigkeiten im
nächsten Schritt anbietet, muss sie doch im Shader-Programm für die Jacobi-Iterationen vorgenommen werden. Andernfalls würde bei der Berechnung der Ausgangspunkte für die Randwerte im darauffolgenden Zeitschritt fälschlicherweise nicht mehr aus den Werten einer inneren
Zelle interpoliert, sondern direkt die Randwerte gewählt werden, was das Ergebnis in der Visualisierung deutlich verfälscht.
Ferner verfügen die Gitterpunkte auf dem Rand des Gebiets naturgemäß über keinen Nachbarn,
der direkt ausserhalb neben dem Rand liegt. Zur Bestimmung der zentralen Differenzenquotienten muss ein linker und rechter, bzw. ein oberer und unterer Nachbar gegeben sein. Sie
müssen also durch einseitige Differenzenquotienten ersetzt werden.
Betrachtet man den linken Rand, so wird z.B. der Term für die erste Ableitung der Funktion u,
u −u
u −u
also 1,j2∆x−1,j , in dem u−1,j nicht definiert ist, ersetzt durch 1,j∆x 0,j .
Um die zweite Ableitung für die Funktion hn+1 am linken Rand, also
hn+1
2,j
n+1
n+1
hn+1
−1,j −2h0,j +h1,j
2
∆x
n+1
n+1
hn+1
0,j −2h1,j +h2,j
.
∆x2
zu
ersetzen, wird zusätzlich noch der Wert
benötigt:
Gleichermaßen verfährt man für die Ableitungen der anderen Funktionen. Dies ist in den speziellen Shader-Programmen für den Rand (frag_jacobi_left.cg, frag_jacobi_up.cg,
etc.) entsprechend implementiert, führt aber zu einer unruhigen, „gekräuselten“ Visualisierung
nahe der Ränder, sowie einem nur sehr schwach bewegten Rand. Dies liegt an der nicht ausreichenden Genauigkeit erster Ordnung dieser einseitigen Ableitungen.
Ein optisch ansprechenderes Ergebnis lässt sich erzielen, wenn man das „Ersetzen“ der Grafik-
40
karte überlässt: Erlaubte Textur-Koordinaten liegen im Bereich [0.0, 1.0]2 . Da die Texturen bei
der Erzeugung auf Clamp-Modus eingestellt wurden, wird ein Wert kleiner Null zu Null, und
ein Wert größer Eins zu Eins. Also liefert ein Textur-Lookup für einen Gitterpunkt neben dem
Rand stets die Werte für den Randpunkt zurück.
u −u
Damit ergibt sich analog zum obigen Beispiel gewissermaßen automatisch 1,j2∆x0,j für die er−u +u1,j
ste, und 0,j
für die zweite Ableitung der Funktion u.
∆x2
Wenn auch vom numerischen Standpunkt aus betrachtet sehr ungenau, und auch nur mit einer
Genauigkeit von erster Ordnung abschätzbar, so ist das Ergebnis doch hinreichend gut für eine
Echtzeit-Visualisierung, wie sie hier angestrebt wird.
4.3.3
Aktualisierung des Geschwindigkeitsfeldes
Das Shader-Programm zur Berechnung der Geschwindigkeitskomponenten u und v aus der Lösung des aktuellen Zeitschrittes finden sich in der beiliegenden Implementierung in der Dateien
frag_velocityupdate.cg. In Abschnitt A.1.3 des Anhangs ist er ausführlich erklärt.
Basierend auf den Werten der letzten Jacobi-Iteration (und damit der näherungsweisen Lösung
des Systems), sowie den in Schritt 1 berechneten Werten für die Ausgangspunkte werden hier
die Geschwindigkeiten u und v in der Werte-Textur durch die neu zu bestimmenden ersetzt
(Gleichung 2.45).
Analog zum Vorgehen in den Jacobi-Schritten werden dazu die Koordinaten der links, rechts,
oben und unten angrenzenden Texel ermittelt, und die Werte aus den Texturen ausgelesen, und
anhand von Gleichung 2.45 die neuen u- und v-Werte ermittelt.
Randbehandlung
Eine Randbehandlung wird in diesem Schritt genau wie im Jacobi-Schritt dadurch notwendig,
dass die Randpunkte keinen direkten Nachbarn ausserhalb des Gebietes aufweisen. Entsprechend werden auch hier die einseitigen Differenzenquotienten entweder durch durch Clampen
am Textur-Rand implizit umgesetzt, wobei darauf geachtet wird, dass die Terme 2∆x und 2∆y
durch ∆x bzw. ∆y ersetzt werden.
4.4
Visualisierung
Während bei einer vergleichbaren CPU-Implementierung das berechnete Höhenfeld im Hauptspeicher liegt, und von dort mit den üblichen OpenGL-Befehlen dargestellt werden kann, liegen
die Daten nach dem Lösen durch die GPU im Texturspeicher der Grafikkarte.
Wie in Kapitel 3.2.1 erläutert, ist ein Rücktransfer vom Grafikkarten-Speicher zum Hauptspeicher zwar machbar, aber da er nach jedem Zeitschritt - also mehrmals pro Sekunde - ausgeführt
werden muss, zu teuer. Es musste eine Möglichkeit gefunden werden, die zur Visualisierung
benötigten Knoten an ihren neuen Positionen zu zeichnen, ohne deren z-Komponente beim
Aufruf der glVertex3f- Befehle zu kennen.
Zum jetzigen Zeitpunkt stehen dafür zwei Techniken zur Auswahl, nämlich VBOs/PBOs, und
der Zugriff auf Texturen im Vertex-Shader durch sogenannte Vertex Texture Fetches.
4.4. VISUALISIERUNG
4.4.1
41
VBOs/PBOs
Die Abkürzungen VBOs und PBOs stehen für Vertex Buffer Objects bzw. Pixel Buffer Objects,
eine OpenGL Erweiterung, die im Februar 2003 vom ARB (OpenGL Architecture Review
Board, [11]) freigegeben wurde ( [45, 46]). Sie schließt eine Lücke in der Rendering-Pipeline,
in dem sie es erstmalig ermöglicht, durch Fragment-Shader erzeugte Daten im Vertex-Shader
wiederzuverwenden, ohne dass die GPU-CPU-Schwelle überwunden werden muss. VBOs sind
als Erweiterung zu den schon seit OpenGL Version 1.1 bekannten Vertex Arrays zu verstehen,
die vor allem auf die Reduktion von Funktionsaufrufen und der Überrepräsentation von Objekten bei der Verwendung „normaler“ OpenGL-Zeichenfunktionen abzielten.
Betrachtet man einen Würfel mit sechs Seiten und acht (gemeinsamen) Punkten, so wird
beim Zeichnen dieses Würfels über eine Folge von sechs Quads jeder Punkt drei mal verarbeitet (über einen glVertex-Aufruf). Es werden also insgesamt 24 Koordinaten-Tupel
vom Client (dem PC, mit Hauptspeicher, AGP-/PCI-Bus und CPU) zum Server (die GPU
mit Video-Speicher) gesendet. Bei der Verwendung zusätzlicher Vertex- Attribute wie TexturKoordinaten, Normalen oder Farb-Werten wird dieser Transfer noch weiter erhöht.
Bei Vertex Arrays hingegen wird zunächst ein Bereich im Server-Speicher mit den Attributen
(Koordinaten, Farb-Werte, Normalen, Textur-Koordinaten) für die im zu zeichnenden Objekt
gemeinsam verwendeten Knoten gefüllt. Der Server wird dann durch glEnableClientStateAufrufe auf die Verwendung dieser Daten vorbereitet, die ihm im Anschluss z.B. durch Zeiger auf die entsprechenden Speicher-Bereiche über die Funktionen glVertexPointer,
glColorPointer, etc. zugänglich gemacht werden.
Die eigentliche Zeichenarbeit erledigt im Anschluss ein Aufruf von glDrawElements, der
neben Parametern wie z.B. für die Art der zu zeichnenden Primitive (GL_POINTS, GL_LINES,
GL_QUADS, etc.) ein Zeiger auf einen mit Indices gefüllten Speicherbereich übergeben wird,
welche die Reihenfolge der Verwendung der zuvor spezifizierten Knoten festlegen. Eine MehrfachÜbertragung der Attribute für den selben Knoten entfällt also.
Der Performance-Gewinn dieser Technik lässt sich mit dem durch die Verwendung von DisplayListen vergleichen. Deren großer Nachteil - die fehlende Möglichkeit, den Inhalt einer einmal
erzeugten Display-Liste zu ändern - entfällt dabei.
Nichts desto trotz müssen die Vertex-Attribute auch bei der Verwendung von Vertex-Arrays für
jedes Rendern des darzustellenden Objektes erneut vom Client zum Server übertragen werden,
sofern sie sich geändert haben.
An diesem Punkt setzt die VBO/PBO-Architektur an. Der Inhalt eines Framebuffers (im speziellen auch eines Framebuffer-Objektes) kann via glReadPixels in ein Pixelbuffer-Objekt
übertragen werden. Wohin die Daten bei disem „Kopiervorgang“ gelangen, ist Sache des Treibers, lässt sich aber durch die Verwendung des usage flag-Parameters bei der Puffer-Initialisierung
beeinflussen. Dieser Parameter ist aus mehreren Teilen zusammengesetzt, Tabelle 4.2 beschreibt
die Teile des Parameters.
Die Verwendung des STREAM_DRAW_ARB-Parameters bietet sich für die Implementierung
an. Die Koordinaten und Normalen der Vertices ändern sich vor jedem Visualisierungs-Schritt,
und werden auch nur einmal zur Anzeige gebracht. Der glReadPixel-Aufruf kopiert die
Daten also aus dem Speicher der Grafikkarte in den Speicher der Grafikkarte, wodurch der
teure Transfer zum Client-Speicher entfällt. Es ist denkbar, dass kein Kopieren im eigentlichen
Sinne vorgenommen wird, sondern der Treiber intern diesen Vorgang durch das Setzen von
Zeigern auf den betroffenen Bereich optimiert, dies ist aber nicht Teil der Spezifikation.
42
Name des Parameters
STATIC_...
DYNAMIC_...
STREAM_...
..._READ_ARB
..._DRAW_ARB
..._COPY_ARB
Definition
„1 zu n“ Beziehung zwischen Erzeugung und Verwendung.
„n zu n“ Beziehung zwischen Erzeugung und Verwendung.
„1 zu 1“ Beziehung zwischen Erzeugung und Verwendung.
Der Client verwendet die Daten. AGP oder System-Speicher bevorzugt.
Der Server verwendet die Daten. Schneller Video-Speicher bevorzugt.
Beide Seiten verwenden die Daten.
Tabelle 4.2: glBufferDataARB-Parameter
Um die im PBO gehaltenen Daten im Anschluss verwenden zu können, wird durch einen erneuten Aufruf von glBindBufferARB - diesmal in Verbindung mit dem GL_ARRAY_BUFFER_ARBParameter - der Speicherbereich mit den Vertex-Koordinaten neu „gebunden“, und über einen
glVertexPointer-Aufruf dem Server zur Visualisierung übergeben.
Die Koordinaten jedes Knotens des Gitters müssen also in einem separaten Fragment-ShaderDurchlauf für jeden Visualisierungsschritt neu berechnet werden, indem die RGB-Werte einer
eigens dafür erzeugten, an ein Framebuffer-Object gebundenen Textur mit den x, y und z Koordinaten gefüllt werden. Per glReadPixels werden die Koordinaten wie beschrieben in ein
PBO kopiert, und im Anschluss (als VBO neu gebunden) dem Server zur Anzeige übergeben.
Das Shader-Programm für diesen Schritt findet sich in der beiliegenden Implementierung in der
Datei frag_coordinates.cg, und wird im Anhang in Abschnitt A.1.4 genauer erläutert.
Um eine realistische Darstellung der Wasseroberfläche zu ermöglichen, werden neben den
Vertex-Koordinaten auch die Normalen der Oberfläche benötigt, anhand derer später eine LichtReflektion bzw. Brechnung berechnet werden kann. Dazu wird analog zur Berechnung der Koordinaten in einem weiteren zusätzlichen Fragment- Shader-Durchlauf eine Vertex-Normale für
alle Knoten berechnet.
Abbildung 4.4: Berechnung der Vertex-Normalen
4.4. VISUALISIERUNG
43
Aus den in Abbildung 4.4 rot dargestellten Kanten-Vektoren wird durch Bildung des Kreuzproduktes die in Grün gezeichnete Normale des entsprechenden Flächenstücks gebildet. Durch
Mittelwert-Bildung erhält man die Normale für den Knoten (blau).
Implementiert ist dieses Vorgehen in der beigelegten Datei frag_normals.cg, eine genaue
Erklärung der verwendeten Befehle findet sich in Abschnitt A.1.5 im Anhang.
4.4.2
Vertex Texture Fetch
Mit der vorletzen Generation von Grafikkarten (GForce 6-Serie) wurde den Entwicklern die
Möglichkeit gegeben, nicht nur im Fragment-Shader auf Texturen zuzugreifen, sondern auch
im Vertex-Shader. Diese als Vertex Texture Fetch bezeichnete Technik lässt sich in der Implementierung dieser Arbeit hervorragend für ein dynamisches Displacement-Mapping der für die
Visualisierung der Wasseroberfläche verwendeten Knoten ausnutzen.
Die Wasseroberfläche wird dafür zunächst als flaches Gitter mit beliebiger, konstanter Höhe
gerendert. Den Knoten werden dabei Textur-Koordinaten zugeordnet, anhand derer die nach
Abschluss der Berechnung als Textur im Grafikkarten-Speicher vorliegen Simulationsergebnisse - insbesondere die neuen Höhenwerte - identifiziert werden können. Ein Vertex-ShaderProgramm kann nun auf die den Knoten zugeordneten Textur-Werte zugreifen. Gesonderte
Fragment-Shader-Durchläufe für die Berechnung der Koordinaten bzw. der Vertex-Normalen
können also entfallen, da dies im Vertex-Shader implementiert ist.
4.4.3
Reflektion
Ist man nur an einer Visualisierung der Höhenwerte interessiert, so könnte diese bereits nach
dem Lösen des Systems erfolgen (Abb. 4.1), da das neue Geschwindigkeits-Feld dafür keine
Rolle spielt. Liegen diese Werte zum Zeitpunkt der Visualisierung bereits vor, wird z.B. ein
Einfärben der gerenderten Wasserfläche abhängig von den vorherrschenden Geschwidigkeiten
möglich.
Im folgenden wird jedoch erklärt, wie sich der Farbwert eines Pixels der Wasseroberfläche auf
eine möglichst naturgetreue Art und Weise bestimmen lässt. Dazu muss zunächst der Einfluss
des an der Oberfläche reflektierten Lichts der Umgebung berücksichtigt werden. Nach dem
normalen Reflexionsgesetz gilt: „Einfallswinkel gleich Ausfallswinkel“. Fällt ein Strahl I im
Winkel ΘI auf eine Oberfläche, deren Ausrichtung durch eine Normale N bestimmt ist, so
muss der Winkel zwischen dem reflektierten Strahl R und der Normalen ΘR gleich ΘI sein.
Abbildung 4.5 veranschaulicht diesen Zusammenhang.
Zur Bestimmung von I im Vertex-Shader wird neben dem Ortsvektor des Oberflächenpunktes P (der aktuelle Vertex) auch der Ortsvektor V des Augenpunktes benötigt. Dieser wird als
uniformer Parameter an das Programm übergeben. I ergibt sich damit als Differenz aus P und
V.
Die Berechnung des Reflektionsvektors für I und der zuvor ermittelten normierten VertexNormale N erledigt die Cg-eigene Funktion reflect, die als Parameter eben diese beiden Vektoren erhält. Der Reflektionsvektor für jeden Vertex wird in die Ausgabe des VertexShaders geschrieben, und vom Rasterisierer für jeden Pixel zwischen den Knoten interpoliert.
Dort wird dieser Vektor zum Lookup in eine sogenannte Environment Map verwendet, die die
Farbinformationen der Umgebung enthält.
44
Abbildung 4.5: Lichtreflektion an einer Oberfläche
Cube Maps
Alle gängigen neuen Grafikkarten unterstützen sogenannte Cube Map-Texturen, eine OpenGLExtension die bereits im Jahr 1999 verabschiedet wurde [44].
Eine Cube Map besteht aus sechs quadratischen Bildern, die wie die Oberfläche eines Würfels
zu einander passen. Zusammengenommen ergibt sich dadurch ein omnidirektionales Bild, das
zur Repräsentation der weit entfernten Umgebung einer Szene oder eines Objektes, der Environment Map, benutzt wird. Abbildung 4.6 zeigt ein Beispiel einer solchen Cube Map.
Abbildung 4.6: Eine Cube Map
4.4. VISUALISIERUNG
45
Beim Erzeugen der Cube Map werden die einzelnen Seiten des Würfels anhand ihrer Lage
im Raum identifiziert: GL_TEXTURE_CUBE_MAP_POSITIVE_X_EXT bezeichnet die rechte Seite des Würfels, GL_TEXTURE_CUBE_MAP_POSITIVE_Y_EXT die hintere, etc. Die
einzelnen Bilder werden dabei wie ganz normale 2D-Texturen geladen. Weiterführende Erklärungen zu Environment Maps, Cubemaps und der Verwendung dieser in CG finden sich in
vielen Tutorials im Internet (siehe z.B. [25]).
4.4.4
Refraktion
Der zweite wichtige Einfluss auf die Farbe eines Pixels der Wasseroberfläche ist der durch Refraktion oder Lichtbrechung beigetragene Anteil der Farbe des Untergrundes, über dem sich
die Wasserfläche befindet.
Das Snelliussches Brechungsgesetz (benannt nach dem niederländischen Mathematiker Willebrord van Roijen Snell, 1580-1626) beschreibt die Brechung eines Lichtstrahls beliebiger
Wellenlänge beim Übergang von einem transparenten Medium in ein anderes mit anderem Brechungsindex. Der Brechnungsindex einiger Elemente ist in Tabelle 4.3 aufgeführt. Das SnelliMaterial
Luft
Wasser
Diamant
Glas
Brechungsindex
1.0003
1.3333
2.4
1.5
Tabelle 4.3: Brechungsindizes einiger Elemente
ussches Gesetz muss nicht eigens implementiert werden, sondern ist im Cg Funktionsumfang
in der Funktion refract enthalten. Als Parameter werden analog zur Reflektion der Vektor
des einfallenden Strahls I, die Oberflächennormale N sowie das Verhältnis η1 /η2 der Brechungsindizes der beiden Medien. Beim Übergang des Strahls von Luft zu Wasser liegt dieser
also bei 1.0003
1.3333 . Abbildung 4.7 veranschaulicht den Zusammenhang.
Der berechnete Vektor des gebrochenen Lichtstrahls wird im Anschluss wieder in die Ausgabe des Vertex-Shaders geschrieben, und für den Fragment-Shader zwischen den benachbarten
Knoten interpoliert. Dort wird er zum Lookup des durch Brechung beigetragenen Farbwertes
in die zuvor beschriebene Environment Map verwendet.
Nachdem im Fragment-Shader für jeden Pixel die Farbwerte für das gebrochene und reflektierte Licht vorliegen, muss zwischen diesen geeignet interpoliert werden, um ein optisch ansprechendes Ergebnis zu erzielen. Betrachtet man in der Natur eine Wasseroberfläche, so kann
man den Boden nur dann sehen (also den durch Brechung, beigetragenen Teil des Lichts) wenn
man fast senkrecht von oben darauf blickt. Bei flacherem Winkel hingegen wird sehr viel mehr
Licht an der Oberfläche reflektiert. Dieses Phänomen wird als Fresnel-Effekt bezeichnet, der
an dieser Stelle aufgrund der hohen Komplexität nicht im Detail beschrieben werden kann. Im
folgenden sei jedoch eine schnelle, häufig in graphischen Anwendungen verwendete empirische Annäherung beschrieben.
46
Abbildung 4.7: Lichtbrechung an einer Oberfläche
Fresnel-Term
Der reflektierte Anteil am Farbwert eines Oberflächenpunktes cref lässt sich anhand von Gleichung 4.1 bestimmen:
cref = max(0, min(1, bias + scale × (1 + I · N )power )).
(4.1)
Dabei bezeichnet I den einfallenden Strahl und N die Oberflächennormale auf Auftreffpunkt.
Falls I annähernd mit N übereinstimmt, ergibt sich für den Reflexionskoeffizient ein Wert nahe
an null. Weichen nun I und N zunehmend voneinander ab, steigt der Koeffizient schnell und
stetig an, bis zu einem Punkt an dem Totalreflexion (cref = 1) erreicht ist.
Die Werte, die den Parametern bias, scale und power gegeben werden, sind letztendlich geschmackssache, und können im beiliegenden Shader-Quelltext geändert werden.
Der endgültige Farbwert des Pixels lässt sich anhand von Gleichung 4.2 ermitteln.
color = cref × ref lectedColor + (1 − cref ) × ref ractedColor
(4.2)
Dieser Wert wird in der Implementierung für jeden Vertex bestimmt, und in die Ausgabe des
Vertex-Shaders geschrieben. Der Rasterisierer der GPU übernimmt eine Interpolation für die
zwischen benachbarten Vertices liegenden Pixel.
Nach diesen im Vertex-Shader verrichteten Vorarbeiten wird im für die WasseroberflächenVisualisierung gebundenen Fragment-Shader-Programm nur noch der Environment-Map-Lookup
entlang der berechneten Reflexions- und Refraktions-Vektoren vorgenommen, und das Ergebnis anhand des Fresnel-Koeffizienten gemischt.
Zur Darstellung von mitschwimmenden Objekte (Bojen, etc.) müssen die u- und v-Werte für
4.5. BEDIENUNG
47
deren letzte Position ausgelesen und interpoliert, und die Verschiebung für den neuen Zeitschritt berechnet werden. Prototypisch realisiert ist dies in den Methoden drawParticles
und updateParticlePositions. Die Objekte haben dabei keinen Einfluss auf Bewegung des Wassers.
Die für das Rendern des Wassers eingesetzten Shader-Programme sind in der Implementierung
in den Dateien vert_reflect_refract.cg und frag_surface.cg (VBO/PBO-Modus),
bzw. in vert_displacement.cg (VTF-Modus) enthalten. Eine genauere Erklärung findet
sich im Anhang (Abschnitte A.1.6, A.1.7).
4.5
Bedienung
Die Parametrisierung des Programms erfolgt beim Aufruf über die Kommandozeile. Die folgende Liste beschreibt die frei wählbaren Parameter und deren Verwendung. Alle Parameter
sind optional. Fehlen sie, wird auf eine Default-Einstellung zurückgegriffen.
• -n # # steht für die Anzahl der Gitterpunkte, mit denen das Gebiet in x- und y-Richtung
diskretisiert wird (Default: 256).
• -iterations # # gibt die Anzal der Jacobi-Iterationen pro Zeitschritt an (Default:
10).
• -timestep # # steht für die Zeitschrittweite ∆t (Default: 0.05).
• -sidelength # # bezeichnet die Seitenlänge des Beckens (Defalut: 10). Aus dieser
Angabe wird in Verbindung mit der Anzahl der Knoten ∆x und ∆y bestimmt.
• -width # # ist gleich der Breite des Ausgabefensters in Pixel (Default: 800).
• -height # # steht für die Fensterhöhe in Pixel (Default: 600).
• -maxtime # # gibt die maximale Simulationslaufzeit in Sekunden an (Default: unendlich).
• -vtf Ist diese Option angegeben, wird die VTF-Methode der Visualisierung verwendet
(Default ist Visualisierung mittels VBO/PBO).
• -volumeCalcTime # # gibt den Zeitpunkt an (bis auf fünf Nachkommastellen genau), an dem eine Volumenberechnung erfolgen soll. Die Ausgabe des Ergebnisses erfolgt in die Konsole. Dieser Parameter kann mehrmals angegeben werden.
• -exportTime # # gibt den Zeitpunkt an (bis auf fünf Nachkommastellen genau),an
dem das Ergebnis der Berechnungen in eine GMV-Datei exportiert werden soll. Ausgabename der Datei ist #.gmv, wobei # für den gewählten Zeitpunkt steht. Dieser Parameter
kann mehrmals verwendet werden.
• -border Durch setzen dieses Flags wird die Berechnung der Randwerte in separaten
Shader-Programmen aktiviert (Default: aus).
• -waterlevel # # gibt die Höhe der Wasseroberfläche h über dem gesamten Bereich
an (Default: 2.00).
48
• -bottomlevel # # gibt die Höhe Höhe des Bodens b über dem gesamten Bereich an
(Default: 1.0).
• -block x,y,w,h,z fügt einen „Block“ im Becken an der angegebenen Stelle ein.
’x’ bezeichnet den Index des Gitters in x-Richtung, ’y’ den Index in y-Richtung, ’w’
steht für die Ausdehnung in Gitterpunkten in x-Richtung, ’h’ für die Ausdehnung in yRichtung, ’z’ gibt die Höhe an. Dieser Parameter kann mehrmals verwendet werden, eine
„sinnvolle“ und zulässige Platzierung wird nicht überprüft.
• -peak x,y,w,h,z Fügt eine „Wassersäule“ im Becken an der angegebenen Stelle
ein. ’x’ bezeichnet den Index des Gitters in x-Richtung, ’y’ den Index in y-Richtung,
’w’ steht für die Ausdehnung in Gitterpunkten in x-Richtung, ’h’ für die Ausdehnung in
y-Richtung, ’z’ gibt die Höhe an. Dieser Parameter kann mehrmals verwendet werden,
bei Fehlen des Parameters wird eine einzelne Wassersäule in der Beckenmitte plaziert
(analog zu der in Kapitel 5.3 beschriebenen. Eine Validierung der gewählten Werte findet
nicht statt.
Neben diesen Parametern für den Programmstart stehen zur Laufzeit die folgenden Tasten zur
Verfügung:
• ’r’,’R’ schaltet die Rotation der Kamera ein und aus.
• ’g’,’G’ erzeugt eine Ausgabe des aktuellen Simulationszustands im GMV-Format.
Ausgabename der Datei ist #.gmv, wobei # wieder für die Anzahl der gerechneten Zeitschritte steht.
Kapitel 5
Ergebnisse
5.1
Visuelles Ergebnis
Abbildungen 5.1 bis 5.4 zeigen eine Reihe von Bildschirmfotos der Visualisierung eines flachen Beckens. Die Simulation, auf der diese Bilder basieren, löst die Shallow Water Equations
für ein Becken mit jeweils zehn Metern Seitenlänge, das durch ein Gitter mit 256×256 Punkten
räumlich diskretisiert wurde, bei einer Zeitschrittgröße von 0,05 Sekunden. In der Initialisierung wurden mehrere „Wassersäulen“ willkürlich auf der Wasseroberfläche verteilt.
Die Visualisierung beinhaltet wie in Kapitel 4.4 beschrieben die Berechnung von reflektierten Lichteinflüssen aus einer Umgebungskarte. Die an der Oberfläche gebrochenen „Strahlen“
werden ebenfalls berechnet, und lassen den an einen gekachelten Schwimmbecken-Boden angelehnten Beckenboden erkennen. Beide Einflüsse auf den Farbwert werden gemäß des bestimmten Fresnel-Koeffizienten mit einander vermischt.
Die Bilder entstanden jeweils im Abstand von einigen Sekunden Programmlaufzeit.
Abbildung 5.7 zeigt das Ergebnis einer Simulation mit gleichen Parametern, mit zufällig eingebauten rechteckigen Hindernissen. Die Bilder entstanden wieder innerhalb der ersten Sekunden
der Programmlaufzeit.
Es sei an dieser Stelle angemerkt, dass die FPS (Frames pro Sekunde), die im Fenstertitel
angegeben sind, nicht repräsentativ sind. Sie wurden durch das Stoppen der Simulation zur
Screenshot-Erzeugung verfälscht.
5.2
Geschwindigkeit
Als Maß für die erzielte Geschwindigkeit der Implementierung gelten die erreichten Bilder
(Frames) pro Sekunde. Da die Änderungen in den Laufzeiten abhängig von einer ein- oder
ausgeschalteten separaten Randbehandlung kaum messbar sind, wurde exemplarisch nur der
49
50
KAPITEL 5. ERGEBNISSE
Abbildung 5.1: Visualisierungsergebnis, flaches Becken
Fall ohne diese betrachtet.
Die Verwendung von Display-Listen für die Darstellung des Becken-Bodens ist bei den durchgeführten Testläufen obligatorisch, da immediate mode rendering unnötigt (das Bodenprofil
ändert sich nicht) und einfach zu kostspielig ist. Bei einer Gittergröße von 256 Knoten in jeder
Dimension zum Beispiel sinkt die Framerate durch Verzicht auf Display-Listen im VertexTexture-Fetch-Modus von 26.6 auf 15.5 Bilder pro Sekunde bei 10 Jacobi-Iterationen auf einer
NVidia 6800GT Grafikkarte. Der Verlust nimmt mit steigender Zahl von Gitterpunkten weiter
zu.
Die angegebenen FPS-Werte wurden jeweils über 30 Sekunden Programm-Laufzeit gemittelt,
wobei die erste Sekunde, in der die komplette Initialisierung der Simulation mit Datentransfer
zur GPU, dem Laden der Shader-Programme, der Erzeugung der Bodengeometrie etc. nicht
mit eingerechnet wurde. Damit ein Vergleich zwischen Grafikkarten der letzen und vorletzen
Generation, und damit auch ein Ausblick auf zu erwartende Ergebnisse mit Grafikkarten der
nächsten Generation möglich ist, wurden die Tests mit identischer Konfiguration sowohl auf
einer NVidia 6800GT, wie auch auf einer NVidia 7800GTX Grafikkarte gerechnet, deren relevante technische Spezifikationen in Tabellen 5.2 und 5.1 aufgeführt sind (siehe [35], [36]).
5.2. GESCHWINDIGKEIT
51
Bus-Technologie
Speicher
Speicher Schnittstelle
Speicher Bandbreite (GB/Sek)
Vertex-Pipelines
Pixel-Pipelines
PCI Express
256MB
256-bit
54.4
8
24
Tabelle 5.1: Technische Spezifikation der verwendeten NVIDIA 7800GTX GPU
Bus-Technologie
Speicher
Speicher Schnittstelle
Speicher Bandbreite (GB/Sek)
Vertex-Pipelines
Pixel-Pipelines
AGP
128MB
256-bit
35.2
6
16
Tabelle 5.2: Technische Spezifikation der verwendeten NVidia 6800GT GPU
Für die Geschwindigkeitsanalyse ist neben der der Dimension des Gitters lediglich die Anzahl
52
der Jacobi-Iterationen pro Zeitschritt, und die Größe des Fensters der Ausgabe interessant. Parameter wie der Abstand der Gitterpunkte oder die Zeitschritt-Weite beeinflussen zwar das Ergebnis der Simulation, jedoch nicht die Geschwindigkeit der Darstellung derselben. Die Tests
wurden exemplarisch mit fünf, zehn und fünfzehn Jacobi-Iterationen durchgeführt.
Je größer das Fenster für die Darstellung ist, desto mehr Farbwerte müssen für die Pixel der
Wasseroberfläche durch Cubemap-Lookups für Reflexion und Brechung berechnet werden.
Der Unterschied in den erreichten Frame-Raten ist jedoch verhältnismäßig gering. Betrachtet
man ein Gitter mit 256 mal 256 Punkten, und führt die Simulation mit 10 Jacobi-Iterationen
durch, so sinkt die Frame-Rate von 19.8 FPS bei einer Fenstergröße von 400 mal 300 Pixeln,
die aufgrund der Wahl des Augenpunktes vollständig mit Wasseroberfläche „bedeckt“sind, nur
auf 19.5 FPS bei einer Fenstergröße von 1200 mal 900 Pixeln. Die nachfolgend angegebenen
Werte beziehen sich daher alle auf eine ”mittlere” Fenstergröße von 800 mal 600 Pixel.
Da sich ein Unterschied in der Geschwindigkeit der Visualisierung abhängig von der verwendeten Technik (Vertex-Texture-Fetch bzw. VBO/PBO) auf den eingesetzten GPUs aber durchaus
feststellen lässt, wurden alle Tests für beide Techniken vollzogen.
Es sei an dieser Stelle angemerkt, dass die Synchronisation zwischen der Bildwiederholrate
des Monitors und der Grafikkarte für diese Tests im Treiber deaktiviert werden muss. Die gemessenen Frames pro Sekunde sind sonst durch die Monitor-Frequenz nach oben beschränkt.
Tabellen 5.3 und 5.4 zeigen die erzielten Frameraten in Abhängigkeit von der Gittergröße und
Anzahl der Iterationen.
53
Gittergröße
64×64
128×128
256×256
512×512
FPS, 5 Iter.
377,62
110,34
26,39
6,71
FPS, 10 Iter.
295,11
78,84
19,18
4,88
FPS, 15 Iter.
243,03
61,69
15,02
3,84
Tabelle 5.3: NVidia 6800GT, Vertex Texture Fetch
Gittergröße
64×64
128×128
256×256
512×512
FPS, 5 Iter.
344,32
100,5
26,17
6,89
FPS, 10 Iter.
278,89
74,84
18,87
4,92
FPS, 15 Iter.
231,54
58,69
14,84
3,86
Tabelle 5.4: NVidia 6800GT, VBO/PBO
Eine logarithmische Skalierung der Y-Achse in den in Abbildungen 5.5 und 5.6 (GeForce
6800GT) bzw. 5.8 und 5.9 (GeForce 7000GTX) dargestellten Diagrammen macht deutlich,
dass die Framerate linear mit der Problemgröße abnimmt. Die via Vertex-Texture-Fetch visua-
54
lisierte Wasseroberfläche erlaubt generell leicht höhere Frame-Raten als eine Visualisierung
mittels VBOs/PBOs. Der Geschwindigkeitsgewinn liegt bei 9,6% bei der kleinsten Problemgröße mit nur fünf Jacobi-Iterationen, und nimmt kontinuierlich mit steigender Problemgröße
und höherer Iterationsanzahl ab, auf bis zu weniger als 0.5% für das feinste Gitter mit höchster
Iterationszahl.
Abbildung 5.5: NVidia 6800GT, Vertex Texture Fetch
Abbildung 5.6: NVidia 6800GT, VBO/PBO
55
Die Ursachen dafür liegen zum einen darin, dass der Berechnungsaufwand für die Simulation in diesen Fällen zum Teil weit über dem für die Visualisierung liegt, und die Vorteile der
Vertex-Texture-Fetch-Implementierung - nämlich eine geringere Anzahl an Texturzugriffen für
die Visualisierung - sich nicht mehr so deutlich im Ergebnis wiederspiegeln.
Zum anderen werden die für die Visualisierung benötigten arithmetischen Operationen, sprich
das Bestimmen von Vertex-Koordinaten und -Normalen, im VTF-Modus komplett in die VertexShader verlegt. Deren im Vergleich mit den Pixel-Pipelines recht kleine Anzahl muss mit steigender Knotenzahl mehr und mehr Arbeit verrichten, wodurch diese nicht mehr so effizient
parallelisiert werden kann wie im VBO/PBO- Modus. Diese Tendenz wird durch die in Tabellen 5.5 und 5.6 abgebildeten Ergebnisse der Performance-Tests auf der NVidia 7800GTX GPU
noch deutlicher sichtbar (siehe auch Abbildungen 5.8 und 5.9).
Gittergröße
64×64
128×128
256×256
512×512
FPS, 5 Iter.
692,31
258,23
64,36
16,02
FPS, 10 Iter.
590,82
216,78
54,45
13,65
FPS, 15 Iter.
514,97
186,66
47,24
11,86
Tabelle 5.5: NVidia 7800GTX, Vertex Texture Fetch
Gittergröße
64×64
128×128
256×256
512×512
FPS, 5 Iter.
714,79
282,69
78,48
19,44
FPS, 10 Iter.
607,39
230,31
63,12
15,64
FPS, 15 Iter.
525,61
195,02
52,79
13,47
Tabelle 5.6: NVidia 7800GTX, VBO/PBO
56
Abbildung 5.7: Visualisierungsergebnis, Hindernisse
57
Abbildung 5.8: NVidia 7800GTX, Vertex Texture Fetch
Abbildung 5.9: NVidia 7800GTX, VBO/PBO
Die 7800GTX verfügt über das 1.5fache der parallelen Pixel-Pipelines der 6800GT, aber nur
2 Vertex Shader mehr. Hinzu kommt, dass der deutlich schneller Speichertakt dieser Karte die
VBO/PBO-Implementierung zusätzlich begünstigt. Der Geschwindigkeitsgewinn reicht bis zu
21,5% bei großer Gittergröße und niedriger Iterationszahl. Kleinere Gittergrößen dämpfen diesen Gewinn durch eine bessere Auslastung der Vertex-Shader, ebenso wie steigende Iterationszahlen durch eine Verlagerung der Hauptlast der Anwendung auf den Simulationsteil. Dennoch
lässt sich auch für die kleinste Gittergröße und höchsten Iterationszahlen noch eine Steigerung
von 2% für das VBO/PBO-Verfahren verbuchen.
58
Macht man sich noch einmal bewusst, das eine Gittergröße von 512 mal 512 Knoten für ein
Gleichungssystem mit 786.432 Unbekannten steht (u,v und h), welches bei kleiner Iterationszahl auf einer GPU neueren Typs nahezu 20 mal pro Sekunde mit optischer Genauigkeit gelöst
und anprechend visualisiert werden kann, ist die erzielbare Geschwindigket in Hinblick auf
Echtzeitanwendungen sehr gut.
5.3
Genauigkeit
Obwohl das Ziel des hier vorgestellten Verfahrens die optisch korrekte Simulation und Darstellung von bewegtem Wasser war, soll im folgenden auch die numerische Genauigkeit untersucht werden, um seine Relevanz für praktische Anwendungen ausserhalb des reinen GrafikUmfeldes zu klären.
Mit dem in Kapitel 2.3 vorgestellten Integrationsverfahren, der Gauss-Quadratur, wird das zwischen Wasseroberfläche und Boden eingeschlossene Volumen über einen längeren Simulationszeitraum für verschiedene Feinheits-Stufen in der räumlichen Diskretisierung und durch
Veränderung der Iterationsanzahl erreichte Lösungsgenauigkeit beobachtet.
Als Testszenario dient ein „Wasserbecken“ mit 10 mal 10 Metern Seitenlänge, und ebenem
Bodenprofil. Der initiale Wasserstand über dem gesamten Becken liegt bei einem Meter. Zusätlich wird in der Mitte des Beckens eine quadratische „Wassersäule“von einem Meter Höhe
platziert, die durch die Schwerkraft getrieben in sich zusammenfällt, und für eine kreisförmige
Wellenausbreitung in der Beckenmitte sorgt. Die ”Eckpunkte” dieser Wassersäule sind abhängig von der Anzahl der Gitterpunkte, und liegen bei ((n/2)−(n/10), (n/2)−(n/10)), ((n/2)+
(n/10), (n/2) − (n/10)), ((n/2) + (n/10), (n/2) + (n/10)) und ((n/2) − (n/10), (n/2) +
(n/10)). Das totale Volumen zum Zeitpunkt t0 kann somit analytisch exakt bestimmt werden,
und beträgt 104.
Da vor allem der stark bewegte Zeitraum zu Beginn der Simualtion von Interesse ist, wurden
das Volumen während der ersten 10 Sekunden sekündlich berechnet. Je weiter sich die Wasseroberfläche ihrem Ruhezustand annähert, um so geringer ist die Veränderungen im Volumen,
weshalb eine Auswertung alle fünfzehn Sekunden bis zum Abbruch der Simulation nach drei
Minuten ausreicht. Die Zeitschrittgröße 4t wurde auf 0.05 Sekunden festgesetzt.
Alle hier durchgeführten Tests verzichten dabei auf eine separate Randbehandlung in eigenen
Shadern. Die Randbehandlung wird wie in Kapitel 4.3.2 beschrieben implizit durch Clampen
am Texturrand bewerkstelligt.
5.3. GENAUIGKEIT
T (Sek.)
1
2
3
4
5
6
7
8
9
10
15
30
45
60
75
90
105
120
135
150
165
180
59
V (5 Iter.)
99,77
97,47
98,54
98,75
98,1
97,59
98,04
98,07
97,54
97,48
97,39
96,6
96,13
95,79
95,51
95,27
95,05
94,85
94,66
94,47
94,28
94,16
V (10 Iter.)
99,28
97,42
98,42
98,37
97,54
97,68
97,95
97,56
97,34
97,57
97,12
96,57
96,19
95,94
95,75
95,61
95,48
95,36
95,25
95,15
95,05
94,95
V (15 Iter.)
99,13
97,38
98,35
98,25
97,44
97,65
97,87
97,44
97,32
97,52
97,06
96,55
96,2
95,96
95,78
95,63
95,5
95,39
95,28
95,17
95,07
94,96
V (20 Iter.)
99,08
97,37
98,32
98,21
97,41
97,64
97,84
97,41
97,3
97,5
97,04
96,54
96,2
95,96
95,79
95,66
95,54
95,43
95,33
95,23
95,13
95,03
Tabelle 5.7: Volumenentwicklung für ein 50×50 Gitter
Tabelle 5.7 und Abbildung 5.10 zeigt das errechnete Volumen für das mit 50 mal 50 Punkten
räumlich diskretisierte Becken zu verschiedenen Zeitpunkten und in Abhängigkeit von der Anzahl der durchgeführten Jacobi- Iterationen.
Bereits nach Verstreichen der ersten Sekunde hat sich das Volumen auf unter 100 reduziert.
Die durch die Wassersäule entstandene Welle erreicht ungefähr zum Zeitpunkt t = 2 Sekunden
den Rand des Beckens. Von diesem Zeitpunkt an schwankt das betrachtete Volumen bei zehn,
fünzehn und zwanzig durchgeführten Jacobi-Iterationen pro Zeitschritt nahezu identisch um
einen rasch fallenden Mittelwert.
Nach 30 Sekunden hat sich die Oberfläche weitgehend beruhigt, und der errechnete Wert liegt
bei ca. 96,55. Dies entspricht einem Verlust von 7,1% vom exakten Startvolumen von 104.
Dieser Wert liegt zwar nahe an den in [29] angegebenen 5%, offenbar ist die räumliche Diskretisierung für das betrachtete Gebiet mit nur 50 Punkten in jeder Dimension jedoch nicht fein
genug für das Verfahren.
Das Volumen fällt auch nach Beruhigung der Wasseroberfläche bei allen angegebenen Iterationszahlen langsam aber stetig ab, eine Tendenz, die sich auch bei den feineren räumlichen
Diskretisierungen erkennen lässt.
60
T (Sek.)
1
2
3
4
5
6
7
8
9
10
15
30
45
60
75
90
105
120
135
150
165
180
V (5 Iter.)
102,11
101,6
100,4
101,08
101,32
101,37
101,08
100,42
100,53
100,82
100,46
99,78
99,36
98,98
98,62
98,3
98
97,73
97,47
97,23
97,01
96,79
V (10 Iter.)
101,83
100,62
100,84
101,16
101,1
100,52
100,44
100,74
100,77
100,4
100,13
99,79
99,4
99,09
98,83
98,59
98,37
98,17
97,99
97,83
97,68
97,54
V (15 Iter.)
101,58
100,32
100,82
100,99
100,65
100,24
100,54
100,61
100,27
100,16
100,19
99,67
99,33
99,06
98,82
98,62
98,44
98,27
98,12
98
97,89
97,81
V (20 Iter.)
101,38
100,21
100,74
100,8
100,33
100,22
100,49
100,34
100,04
100,18
100
99,54
99,25
99
98,79
98,6
98,43
98,29
98,16
98,05
97,95
97,86
Ähnlich wie im zuvor betrachteten 50×50 Gitter, schwankt das Volumen auch in Tabelle 5.8
bzw. Abb. 5.11 gezeigten Fall einer 100×100 Punkte Diskretisierung ab der zweiten Sekunde
Simulationszeit recht stark. Bis auf den unzureichend genau gelösten Fall von fünf JacobiIterationen ist der Volumenverlust bei Erreichen des Ruhezustandes bereits deutlich geringer
ausgeprägt. Der Verlust von etwa 4.1% zum Zeitpunkt von 30 Sekunden deckt sich damit mit
dem der CPU-Implementierung in [29].
5.3. GENAUIGKEIT
T (Sek.)
1
2
3
4
5
6
7
8
9
10
15
30
45
60
75
90
105
120
135
150
165
180
61
V (5 Iter.)
103,13
103,13
103,1
102,56
101,94
102,11
102,43
102,54
102,6
102,64
101,82
102,04
101,42
101,19
100,91
100,55
100,36
100,04
99,83
99,57
99,34
99,12
V (10 Iter.)
103,06
103,04
102,47
102,04
102,42
102,56
102,63
102,64
102,53
102,12
102,37
101,81
101,45
101,24
101,04
100,82
100,6
100,38
100,18
99,99
99,8
99,63
V (15 Iter.)
102,99
102,86
102,09
102,31
102,5
102,58
102,55
102,29
101,97
102,11
101,87
101,81
101,46
101,23
101,03
100,82
100,64
100,46
100,29
100,13
99,98
99,83
V (20 Iter.)
102,92
102,62
102,03
102,37
102,5
102,49
102,28
101,95
102,08
102,24
102,05
101,65
101,38
101,17
100,97
100,8
100,64
100,5
100,36
100,24
100,12
100
Die in Abbildung 5.12 bzw. Tabelle 5.9 dargestellten Ergebnisse einer 200×200 Punkte Diskretisierung zeigen immer noch die Tendenz des Volumenverlustes. Es ist aber bereits zu erkennen,
dass dieser erst einsetzt, nachdem die Welle den Beckenrand erreicht hat.
Dies erklärt sich durch die Ungenauigkeit der Lösung am Rand, die wie in Kapitel 4.3.2
beschrieben keine Genauigkeit zweiter Ordnung aufweist, wie im Beckeninneren. Aufgrund
der feineren räumlichen Diskretisierung wird im Vergleich zu den gröberen Diskretisierungen
überproportional mehr im Inneren gerechnet, wodurch dieser Effekt nicht mehr ganz so stark
ins Gewicht fällt.
Rein optisch fällt dieser Volumenverlust auch nach mehreren Minuten zwar nicht auf, dürfte
aber für eine praktische Anwendung ausserhalb des reinen Computer-Grafik-Umfeldes durchaus von Bedeutung sein.
62
T (Sek.)
1
2
3
4
5
6
7
8
9
10
15
30
45
60
75
90
105
120
135
150
165
180
V (5 Iter.)
103,44
103,44
103,44
103,43
103,36
102,92
102,54
102,43
102,66
102,85
103,04
102,76
102,46
102,1
101,74
101,46
101,22
101,02
100,83
100,64
100,45
100,25
V (10 Iter.)
103,4
103,41
103,4
103,13
102,65
102,61
102,88
102,98
103,03
103,06
102,51
102,66
102,17
102,19
101,82
101,77
101,49
101,38
101,15
101,02
100,82
100,68
V (15 Iter.)
103,37
103,37
103,26
102,74
102,66
102,91
103
103,05
103,07
103,05
102,76
102,36
102,19
102,08
101,92
101,72
101,52
101,34
101,19
101,04
100,89
100,74
V (20 Iter.)
103,35
103,33
103,03
102,61
102,84
102,96
103,02
103,04
103,01
102,81
102,85
102,54
102,26
102,02
101,82
101,65
101,5
101,35
101,2
101,06
100,93
100,79
Analog zur 200×200 Punkte Diskretisierung verhält sich der in Abbildung 5.13 bzw. Tabelle
5.10 dargestellte Fall mit einer Auflösung von 300×300 Punkten bei einer langen Simulationslaufzeit gleich für alle durchgeführten Variationen in der Iterationszahl des Lösers bis auf
die nur sehr unzureichend gelöste Variante mit fünf Iterationen. Diese weist die größte Abweichung vom Startvolumen auf.
Hier ist dadurch, dass die Welle später als in den zuvor beschriebenen Fällen den Rand erreicht
(ein Effekt, der in diesem Abschnitt noch genauer Untersucht wird), noch deutlicher zu erkennen, dass der Verlust des Volumens erst einsetzt, wenn die Berechnung der Ränder eine Rolle
spielt.
5.3. GENAUIGKEIT
T (Sek.)
1
2
3
4
5
6
7
8
9
10
15
30
45
60
75
90
105
120
135
150
165
180
63
V (5 Iter.)
103,58
103,58
103,58
103,58
103,58
103,57
103,45
103,12
102,85
102,7
103,14
102,64
102,53
102,66
102,46
102,18
101,86
101,6
101,54
101,44
101,23
100,96
V (10 Iter.)
103,57
103,57
103,56
103,56
103,43
103,06
102,84
102,9
103,09
103,17
103,28
103,03
102,6
102,39
102,32
102,24
102,11
101,93
101,71
101,51
101,35
101,23
V (15 Iter.)
103,55
103,55
103,54
103,45
103,07
102,87
103,03
103,17
103,22
103,26
103,07
102,85
102,8
102,41
102,41
102,17
102,03
101,92
101,71
101,61
101,44
101,3
V (20 Iter.)
103,53
103,53
103,51
103,23
102,91
103,02
103,17
103,22
103,26
103,28
102,83
102,94
102,63
102,43
102,34
102,08
101,98
101,8
101,62
101,49
101,31
101,17
Abbildung 5.14 und Tabelle 5.11 zeigen die Volumenentwicklung für den am feinsten diskretisierten Testfall bei 400×400 Gitterpunkten. Die Abweichung vom Startvolumen beträgt
zum Ende der Simulation nach drei Minuten nur noch 2,8%. Zusammenfassend lässt sich sagen, dass die in [29] vorgestellten Ergebnisse die Volumenerhaltung betreffend in dieser GPUImplementierung durchaus erreicht werden. Rein optisch ist der Verlust nicht festzustellen,
auch die Schwankung des Volumens wenn die beschriebene Welle den Rand erreicht, fällt einem Betrachter nicht auf.
Berechnet man die Ränder wie in Kapitel 4.3.2 beschrieben separat, kann man den gegenteiligen Effekt beobachten: Das Volumen steigt nach Ende der Simulation langsam, aber kontinuierlich an. Eine auf höhere numerische Genauigkeit ausgelegte Implementierung müsste also
bei der Randbehandlung einseitige Ableitungen höherer Ordnung wählen.
Auffallend an den konstant mit Zeitschrittweite 4t = 0.05 gerechneten Simulationen ist der
Umstand, dass die Welle, obwohl sie immer vom gleichen Punkt in der Mitte des Beckens ausgeht, immer später den Rand erreicht, je feiner das Gebiet räumlich diskretisiert wurde.
Wenn das Verfahren in der Zeit voll explizit wäre, würde es einer Zeitschrittgröße von n12 bedürfen, wobei n wieder die Anzahl der Gitterpunkte pro Dimension (in den Testfällen also
100,200,300 und 400) ist. Dadurch, dass das Verfahren halbimplizit in der Zeit ist, schwächen
sich diese unteren Schranken auf bis zu n1 ab. Abbildung 5.15 zeigt einen Schnitt durch die
Wasseroberflächen bei einer räumlichen Diskretisierung von (von oben nach unten) 400×400,
64
300×300, 200×200 und 100×100 Punkten, jeweils zu einer Simulationszeit von 0,5 Sekun1
den. Die Zeitschrittweite war bei allen Versuchen auf 0.0025, also 400
festgelegt. Wenn auch
auf die Feinheit der räumlichen Diskretisierung zurückzuführende Unterschiede im Ergebnis
zu erkennen sind, so wird auch deutlich, dass sich die Welle in allen Abbildungen etwa gleich
weit vom Mittelpunkt wegbewegt hat. Diese Zeitschritt-Größe ist also geeignet klein gewählt,
um eine zeitliche Stabilität der Simulation zu gewährleisten.
Experimente haben ergeben, dass diese Stabilität bis zu einer Zeitschrittgröße von ca. 0,0075
Sekunden bei einem Gitter von 400×400 Punkten gewährleistet ist. Verdoppelt man die Gitterweite, diskretisiert das gleiche Gebiet mit z.B. nur noch 200×200 Punkten, verdoppelt sich
auch in etwa die zulässige Zeitschrittweite.
Danach verringert sich die Ausdehnung der Welle im gleichen Simulationszeitraum, wie Abbildung 5.16 zeigt. Die Querschnitte veranschaulichen wieder die Ausbreitung nach je 0,5 Sekunden Simulationszeit, bei einer festen räumlichen Diskretisierung von 400 Punkten in jeder
Dimension. Der Parameter ∆t wurde dabei (von oben nach unten) ausgehend von 0,0075 um
jeweils 0,0025 erhöht, was zu einem sichtbaren Unterschied in der Geschwindigkeit der Ausbreitung der Welle führt.
Da man von Echtheitsberechnungen spricht, wenn sich die real verstreichende Zeit mit der Simulationszeit - in diesem Fall das Produkt der Zeitschrittweite 4t und der Anzahl der gerechneten/visualisierten Zeitschritte - deckt, lässt sich der Echtzeit-Anspruch der Implementierung
auf heute verfügbaren GPUs nur für kleinere Gittergrößen aufrechterhalten.
5.4
Zusammenfassung und Ausblick
Die Entwicklung - vor allem die Implementierung - wurde leider immer wieder behindert
durch mangelnde oder falsche Dokumentation, fehlende Werkzeuge zur Fehleranalyse und Behebung des hardwarenahen Codes für die Grafikkarten- Programmierung. Hier bleibt nur zu
wünschen, dass dieses Manko in Zukunft behoben werden wird.
Das gesetzte Ziel dieser Arbeit - die Simulation und Visualisierung von Wasser in Echtzeit auf
Basis der Shallow Water Equations - wurde trotzdem erreicht, jedoch sind die Problemgrößen,
für die diese Aussage gilt, stark abhängig von der eingesetzten Grafik-Hardware. Die rasante
Entwicklung auf diesem Gebiet lässt jedoch die berechtigte Hoffnung zu, dass in naher Zukunft
mit dem hier vorgestellten Verfahren auch wesentlich größere Probleme effizient berechnet und
visualisiert werden können. Die erzielten Geschwindigkeiten dieser Implementierung für das
Lösen der Shallow Water Equations liegen aber immer noch deutlich über denen einer vergleichbaren CPU-Implementierung.
Gerade bei Problemen, die eine große Anzahl von verschiedenen möglichen Eingaben berücksichtigen müssen, ist eine jede Verbesserung in den erreichten Geschwindigkeiten von großem
Vorteil. Man stelle sich zum Beispiel einen Küsten-Streifen vor, der durch eine Reihe von zu
plazierenden Wellenbrechern vor großen Flutwellen geschützt werden soll. Die optimalen Positionen der Wellenbrecher könnten z.B. von einem genetischen Algorithmus berechnet werden,
der aus den Ergebnissen vieler durchgeführter Simulationen lernt. Hier ist ein schnelles Verfahren zur Lösung sehr wichtig.
Letztendlich bleibt es dem Benutzer überlassen, ob er an „optischer Genauigkeit“ in Echtzeit
oder einem genaueren Simulationsergebnis interessiert ist.
5.4. ZUSAMMENFASSUNG UND AUSBLICK
Abbildung 5.10: Volumenentwicklung bei 50×50 Gitterpunkten
65
66
67
68
Abbildung 5.15: Ausbreitung der Welle nach einer halben Sekunde bei (von oben
nach unten) 400, 300, 200 und 100 Gitterpunkten in jede Dimension
Abbildung 5.16: Volumenentwicklung bei 400×400 Gitterpunkten bei Zeitschrittweiten von (von oben nach unten) 0.0075, 0.01, 0.0125, 0.015
69
70
Anhang A
Code-Auszüge
A.1
Shader-Programme
A.1.1
Berechnung der Departure Points
Der folgende Fragment-Shader-Code wird zur Berechnung der Ausgangspunkte-Textur verwendet, und vor den Jacobi-Iterationen ausgeführt.
1 float4 main (uniform sampler2D valueTexture,
2
uniform float deltaT,
3
uniform float deltaX,
4
uniform float deltaY,
5
uniform float n,
6
float2 pos: WPOS) : COLOR {
7
8
float2 gridindex = float2((pos.x-0.5),(pos.y-0.5));
9
float2 texcoords = float2((gridindex.x / (n-1)),
10
(gridindex.y / (n-1)));
11
float4 values = tex2D(valueTexture, texcoords );
12
13
float2 alpha = float2(0,0);
14
alpha.x = deltaT * (values.x * deltaX);
15
alpha.y = deltaT * (values.y * deltaY);
16
17
float x = clamp((gridindex.x - alpha.x),0,(n-1));
18
float y = clamp((gridindex.y - alpha.y),0,(n-1));
19
20
float minx = ((floor(x)) / (n-1));
21
float maxx = ((ceil(x)) / (n-1));
22
float miny = ((floor(y)) / (n-1));
71
72
ANHANG A. CODE-AUSZÜGE
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
44
float maxy = ((ceil(y)) / (n-1));
float p =(x - floor(x));
float q =(y - floor(y));
float4
float4
float4
float4
ul
ur
lr
ll
=
=
=
=
float4 ulur
float4 lllr
tex2D(valueTexture,
tex2D(valueTexture,
tex2D(valueTexture,
tex2D(valueTexture,
float2(minx,miny));
float2(maxx,miny));
float2(maxx,maxy));
float2(minx,maxy));
= lerp(ul,ur,p);
= lerp(ll,lr,p);
float4 inter = lerp(ulur,lllr,q);
inter.a = values.b;
if (values.b <= values.a) {
inter.r = 0.0;
inter.g = 0.0;
}
return inter;
}
1-6 Deklaration der Hauptmethode
8 Bestimmung des Gitterindex aus dem Mittelpunkt der Pixel-Koordinate
9-10 Bestimmung der Texturkoordinaten für den Gitterpunkt
11 Textur-Lookup für u, v, h und b des Gitterpunktes
13-15 Berechnung des Ausgangspunktes
17-23 Berechnung der Texturkoordinaten für die „Eckpunkte“ der den Ausgangspunkt umschließenden „Zelle“
25-26 Bestimmen der Interpolationsfaktoren
28-31 Textur-Lookups für die Eckpunkte
33-36 Interpolation von ũ, ṽ und h̃ aus den Eckpunkten
37 Übertragung von h in den Alpha-Kanal der Ausgabe
39-42 Null-Setzen der Geschwindigkeiten für den Fall, dass die Bodenhöhe größer als die Wasserhöhe ist
44 Ausgabe der Werte
A.1. SHADER-PROGRAMME
A.1.2
73
Jacobi
Der folgende Fragment-Shader-Code implementiert eine Iteration des Jacobi-Verfahrens. Er
wird für die Knoten im Inneren des Gebietes verwendet, kann aber auch wie in Kapitel 4.3.2
beschrieben auf dem Rand verwendet werden.
02
uniform sampler2D departureTexture,
03
04
05
06
uniform float n,
07
uniform float g,
08
09
10
float2 gridindex
= float2((pos.x-0.5),(pos.y-0.5));
11
float2 texcoords
= float2((gridindex.x / (n-1)),
12
13
float2 leftCoords
= float2(texcoords.x - (1/(n-1)), texcoords.y);
14
float2 rightCoords = float2(texcoords.x + (1/(n-1)), texcoords.y);
15
float2 upCoords
= float2(texcoords.x, texcoords.y - (1/(n-1)));
16
float2 lowCoords
= float2(texcoords.x, texcoords.y + (1/(n-1)));
17
18
float4 centerVal
= tex2D(departureTexture, texcoords);
19
float4 leftVal
= tex2D(departureTexture, leftCoords );
20
float4 rightVal
= tex2D(departureTexture, rightCoords);
21
float4 lowVal
= tex2D(departureTexture, lowCoords);
22
float4 upVal
= tex2D(departureTexture, upCoords);
23
24
float4 oldValCenter = tex2D(valueTexture, texcoords);
25
float4 oldValLeft
= tex2D(valueTexture, leftCoords);
26
float4 oldValRight = tex2D(valueTexture, rightCoords);
27
float4 oldValUp
= tex2D(valueTexture, upCoords);
28
float4 oldValLow
= tex2D(valueTexture, lowCoords);
29
30
float xSquare
= deltaX * deltaX;
31
float ySquare
= deltaY * deltaY;
32
float tSquare
= deltaT * deltaT;
33
float tSquareG = tSquare * g ;
34
float tSquareGd = tSquareG * d ;
35
float d = (centerVal.a - oldValCenter.a);
36
37
if (gridindex.x<=1.0 ||gridindex.x>=(n-1)) oldValCenter.r=0;
38
if (gridindex.y<=1.0 ||gridindex.y>=(n-1)) oldValCenter.g=0;
39
float b = centerVal.b
40
+ deltaT*((centerVal.r*(oldValRight.a-oldValLeft.a)/(2*deltaX))
74
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 }
+(centerVal.g*( oldValLow.a - oldValUp.a )/(2*deltaY)))
- deltaT*d*(((rightVal.r-leftVal.r)/(2*deltaX))
+(( lowVal.g - upVal.g )/(2*deltaY)));
float dd=1+2*tSquareGd*((xSquare+ySquare)/(xSquare*ySquare));
float Ax = oldValCenter.b+ tSquareG * (
((oldValRight.a - oldValLeft.a) / (2 * deltaX))
*((oldValRight.b - oldValLeft.b) / (2 * deltaX))
+((oldValLow.a
- oldValUp.a) / (2 * deltaY))
*((oldValLow.b - oldValUp.b) / (2*deltaY)))
- tSquareGd * (
((oldValLeft.b-(2*oldValCenter.b)+oldValRight.b)/xSquare)
+((oldValUp.b-(2*oldValCenter.b)+oldValLow.b)/ySquare));
float4 retValue = oldValCenter;
retValue.b = oldValCenter.b + ((1.0/dd) * (b - Ax));
if (retValue.b <= (oldValCenter.a)) { retValue.b = centerVal.a; }
return retValue;
13-16 Bestimmung der Texturkoordinaten der benachbarten Gitterpunkte
18-22 Texturlookups für ũ, ṽ und h̃, sowie den Höhenwert h des letzten Zeitschritts
24-28 Texturlookups für u, v, b sowie den Höhenwert h des letzten Iterationsschritts
31-35 Deklaration von Hilfsvariablen
37-38 Null-Setzen der Geschwindigkeiten auf dem Rand.
39-43 Berechnen der „rechten Seite“ des Gleichungssystems (b)
45 Berechnen des Faktors für das Hauptdiagonal-Element
47-55 Berechnung der „linken Seite“ des Gleichungssystems (Ax) aus der Lösung des letzten
Iterationsschritts
58 Korrektur der Lösung des letzten Iterationsschritts
75
60 Festsetzen des Höhenwertes für den Fall, dass Höhenwert des Bodens über dem der
Wasseroberfläche liegt
62 Ausgabe der Ergebnisse des Iterationsschritts
A.1.3
Aktualisierung der Geschwindigkeiten
Der im folgenden abgebildete Fragment-Shader-Code wird für die Aktualisierung der Geschwindigkeiten u und v im Anschluss an die Jacobi-Iterationen ausgeführt.
02
uniform sampler2D departureTexture,
03
04
05
06
uniform float n,
07
uniform float g,
08
09
10
11
float2 texcoords = float2((gridindex.x/(n-1)),
12
13
14
float2 leftCoords = float2(texcoords.x-(1/(n-1)), texcoords.y);
15
float2 rightCoords = float2(texcoords.x+(1/(n-1)), texcoords.y);
16
float2 upCoords
= float2(texcoords.x, texcoords.y-(1/(n-1)));
17
float2 lowCoords
= float2(texcoords.x, texcoords.y+(1/(n-1)));
18
19
float4 oldDepartureValues = tex2D(departureTexture, texcoords);
20
float4 newCenter
= tex2D(valueTexture, texcoords);
21
22
float4 newLeft = tex2D(valueTexture,leftCoords);
23
float4 newRight = tex2D(valueTexture,rightCoords);
24
float4 newUp
= tex2D(valueTexture,upCoords);
25
float4 newLow
= tex2D(valueTexture,lowCoords);
26
27
float4 retValue = newCenter;
28
29
retValue.r = oldDepartureValues.r
30
- (deltaT*g*(newRight.b-newLeft.b)/(2*deltaX));
31
retValue.g = oldDepartureValues.g
32
- (deltaT*g*(newLow.b-newUp.b)/(2*deltaY));
33
34
if (newCenter.b <= newCenter.a) {
35
retValue.b = oldDepartureValues.a;
36
retValue.r = 0;
37
retValue.g = 0;
76
38
39
40
41
42
43
44
45
46
47
48
49 }
}
if (newLeft.b <= newLeft.a ||newRight.b <=newRight.a) {
retValue.r = 0;
} else if (newUp.b <= newUp.a ||newLow.b <= newLow.a) {
retValue.g = 0;
}
return retValue;
19 Textur-Lookup für ũ, ṽ und h̃
20-25 Textur-Lookups für u,v und h des aktuellen Gitterpunktes und seiner Nachbarn
27-32 Aktualisierung der Geschwindigkeiten
34-46 Null-Setzen der Geschwindigkeiten an den Rändern
48 Ausgabe der aktualisierten Geschwindigkeiten u und v, h und b.
A.1.4
Koordinaten-Erzeugung
Das folgende Fragment-Shader-Programm wird zur Berechnung der Knotenkoordinaten für
die VBO/PBO Visualisierungs-Methode der Wasseroberfläche verwendet, und im Anschluss
an die erfolgte Lösung eines Zeitschrittes verwendet.
01 float4 main(uniform sampler2D valueTexture ,
02
03
04
uniform float xoffset,
05
uniform float yoffset,
06
uniform float n,
07
08
09
10
11
12
13
14
15
16
17
18
19
20 }
float4 values
77
= tex2D(valueTexture, texcoords);
float x = xoffset + (gridindex.x * deltaX);
float y = yoffset + (gridindex.y * deltaY);
float4 retValue =
return retValue;
float4(x,y,values.b,1);
12 Texturlookup für den Höhenwert h
14-15 Berechnung der x- und y-Koordinaten des Knotens aus dem übergebenen Offset und dem
Gitterindex
17 Zuordnung der x-, y- und h- Werte zum Ausgabewert. Der Alpha-Wert wird auf 1 gesetzt.
18 Ausgabe der den Koordinaten entsprechenden Farbwerte.
A.1.5
Normalen-Erzeugung
Die Berechnung der Knoten-Normalen durch dieses Fragment-Shader-Programm erfolgt nach
der Berechnung der Koordinaten.
01 float3 main(uniform sampler2D valueTexture ,
02
03
04
uniform float n,
05
06
07
08
09
10
11
float4 displacement = tex2D(valueTexture, texcoords);
12
13
float2 leftCoords = float2(texcoords.x-(1/(n-1)), texcoords.y);
14
float2 rightCoords = float2(texcoords.x+(1/(n-1)), texcoords.y);
15
float2 upCoords
= float2(texcoords.x, texcoords.y-(1/(n-1)));
16
float2 lowCoords
= float2(texcoords.x, texcoords.y+(1/(n-1)));
17
78
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 }
=
=
=
=
tex2D(valueTexture,
tex2D(valueTexture,
tex2D(valueTexture,
tex2D(valueTexture,
float4
float4
float4
float4
left
right
up
low
float3
float3
float3
float3
toLeft
toRight
toUp
toLow
float3
float3
float3
float3
ulNormal
urNormal
lrNormal
llNormal
=
=
=
=
=
=
=
=
leftCoords);
rightCoords);
upCoords);
lowCoords);
normalize(float3(-deltaX,0,left.b-displacement.b));
normalize(float3(deltaX,0,right.b-displacement.b));
normalize(float3(0,deltaY,up.b-displacement.b));
normalize(float3(0,-deltaY,low.b-displacement.b));
cross(toUp,toRight);
cross(toRight, toLow);
cross(toLow, toLeft);
cross(toLeft, toUp);
float3 normal = (ulNormal + lrNormal + llNormal + urNormal) / 4;
normal = normalize(float3(-normal.x,normal.y,-normal.z));
return normal;
11 Texturlookup für den Höhenwert h
18-21 Textur-Lookups für die h-Werte der benachbarten Gitterpunkte
23-26 Bestimmen der „Kantenvektoren“
28-31 Bestimmen der Normalen der benachbarten Flächen aus den Kantenvektoren (Kreuzprodukt)
33-34 Interpolation und Normalisierung der Normalen des Knotens aus den Normalen der benachbarten Flächen
A.1.6
Reflektion, Brechung und Fresnel-Term
Das folgende Vertex-Shader-Programm berechnet die Brechungs- und Reflektions- Vektoren
für jeden Knoten der die Wasseroberfläche beschreibenden Geometrie, sowie den Fresnel-Term
für die Interpolation der Farbwerte im darauffolgenden Fragment-Shader-Durchgang.
01 struct vertex {
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
79
float4 color
: COLOR;
float4 position : POSITION;
float3 normal
: TEXCOORD0;
};
struct fragment {
float4 position
float fresnelTerm
float3 refract
float3 reflect
};
:
:
:
:
POSITION;
TEXCOORD1;
TEXCOORD2;
TEXCOORD3;
uniform float4x4 modelViewProj
: state.matrix.mvp;
fixed fast_fresnel(float3 I, float3 N, float3 fresnelValues) {
fixed power = fresnelValues.x;
fixed scale = fresnelValues.y;
fixed bias = fresnelValues.z;
return bias + pow(1.0 + dot(I, N), power) * scale;
}
fragment main(vertex IN, uniform float3 eyepos) {
const float refractFactor = 0.75024375;
fragment OUT;
OUT.position = mul(modelViewProj,IN.position);
float3 I
= normalize(IN.position.xyz - eyepos);
OUT.reflect = reflect(I,IN.normal);
OUT.refract = refract(I,IN.normal,refractFactor);
OUT.fresnelTerm = fast_fresnel(I,IN.normal,float3(2.0,1.0,0.2));
return OUT;
}
1-5 Deklaration des Eingabe-Structs (Knoten-Attribute)
7-12 Deklaration des Ausgabe-Structs (Fragment-Attribute)
14 Referenzierung der Model-View-Projection-Matrix (MVP)
16-21 Deklaration einer Hilfsmethode zur Berechnung des Fresnel-Terms
23 Deklaration der Hauptmethode
80
25 Deklaration des konstanten Licht-Brechungsfaktors beim Übergang von Luft in Wasser
27 Erzeugung einer Instanz des Ausgabe-Structs
28 Berechnung der Pixel-Position durch Multiplikation der Knotenposition mit der MVPMatrix
30 Bestimmen des Vektors vom „Auge“ zum Oberflächenpunkt
31 Berechnung des an der Oberfläche reflektierten Vektors
32 Berechnung des an der Oberfläche gebrochenen Vektors
33 Berechnung des Fresnel-Terms durch die Hilfsmethode
36 Ausgabe der Information
A.1.7
Environment-Mapping
Der letze der verwendeten Fragment-Shader führt anhand der zuvor berechneten Reflektions
und Brechungs-Vektoren die Lookups in die Umgebungskarten durch.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
struct fragment {
float4 position
float fresnelTerm
float3 refract
float3 reflect
};
:
:
:
:
POSITION;
TEXCOORD1;
TEXCOORD2;
TEXCOORD3;
float4 main (fragment IN,
uniform samplerCUBE cubeMap) : COLOR {
float4 color = lerp(texCUBE(cubeMap,IN.reflect),
texCUBE(cubeMap,IN.refract),
IN.fresnelTerm);
return color;
}
1-6 Deklaration des Eingabe-Structs (Pixel-Attribute)
8-9 Deklaration der Haupt-Methode
11-13 Lookups entlang der Brechungs- und Reflektions-Vektoren, und Mischen der Farbwerte
in einem durch den Fresnel-Term gegebenen Verhältnis
15 Ausgabe des Farbwertes
Literaturverzeichnis
[1] The General Mesh
GMVHome.html.
Viewer.
http://www-xdiv.lanl.gov/XCM/gmv/
[2] OpenGL Render-to-Texture, 2002. NVIDIA Corporation Game Developer Conference
2002, http://developer.nvidia.com/object/gdc_oglrtt.html.
[3] EXT_framebuffer_object
OpenGL
Extension
Specification,
http://www.opengl.org/documentation/extensions/
EXT_framebuffer_object.txt.
2005.
[4] C/C++ Development Tools, 2006. http://www.eclipse.org/cdt.
[5] Eclipse IDE, 2006. http://www.eclipse.org.
[6] GLUT for Mingw32, 2006.
glut.htm.
http://mywebpage.netscape.com/PtrPck/
[7] GPGPU Programming Resources, 2006. http://sourceforge.net/projects/
gpgpu.
[8] NVIDIA CG Toolkit, 2006.
cg_toolkit.html.
http://developer.nvidia.com/object/
[9] NVShaderPerf , 2006. ://developer.nvidia.com/object/nvshaderperf_home.html.
[10] OpenGL - The Industry’s Foundation for High Performance Graphics, 2006.
http://www.opengl.org/.
[11] The OpenGL Architecture Review Board, 2006. http://www.opengl.org/about/
arb/.
[12] Telemac,
numerical
modelling
system
for
hydraulics
developed
by
EDF-DRD
and
distributed
by
SOGREAH,
hydroinformatics,
2006.
http://www.telemacsystem.com/gb/default.html.
[13] The
OpenGL
Extension
http://glew.sourceforge.net.
Wrangler
Library,
2006.
[14] C EBENOYAN , C.: GPU Gems. Addison Wesley, 2005. Chapter 28, Graphics Pipeline
Performance.
81
82
LITERATURVERZEICHNIS
[15] A LTIERI , M., C. B ECKER und S. T UREK: On the realistic performance of Linear Algebra components in iterative solvers. In: B UNGARTZ , H.-J., F. D URST und C. Z ENGER
(Hrsg.): High Performance Scientific and Engineering Computing: Proceedings of the
International FORTWIHR Conference on HPSEC, Munich, March 16–18, 1998, Bd. 8
d. Reihe Lecture Notes in Computational Science and Engineering, S. 3–12. Springer,
Berlin, 1999. ISBN 3-540-65730-4.
[16] BAUMGART, B.: Winged-Edge Polyhedron Representation for Computer Vision, 1975.
http://www.baumgart.org/winged-edge/winged-edge.html.
[17] BAUMGARTNER , A. und L IEBSCHER , H.-J.: Allgemeine Hydrologie - Quantitative Hydrologie. - In: Lehrbuch der Hydrologie Bd. 1. Gebr. Borntraeger, 1996. 2. Auflage.
[18] B ECKER , C., S. K ILIAN und S. T UREK: Hardware–oriented Numerics and concepts for
PDE software. In: FUTURE 1095, S. 1–23. Elsevier, 2003. International Conference on
Computational Science ICCS2002, Amsterdam.
[19] B UCK , I.: GPU Gems 2. Addison Wesley, 2005. Chapter 32, Taking the Plunge into GPU
Computing, Ian Buck.
[20] C ARPENDALE , S.: CPSC 453: Introduction to Computer Graphics. Techn. Ber., Department of Computer Science, University of Calgary, 2003.
[21] D ÖRFLER , W. und P ESCHEK , W.: Einführung in die Mathematik für Informatiker. Carl
Hanser Verlag München Wien, 1998.
[22] G REEN ,
S.:
The
OpenGL
Framebuffer
Object
Extension,
2005.
NVIDIA
Corporation
Game
Developer
Conference
2005
,
http://download.nvidia.com/developer/presentations/2005/GDC/
OpenGL_Day/OpenGL_FrameBuffer_Object.pdf.
[23] G ROSSMANN , C. und ROOS , H.-G.: Numerik partieller Differentialgleichungen. Teubner, 1994. 2. Auflage.
[24] H ARRIS , M.: GPU Gems 2. Addison Wesley, 2005. Chapter 34, GPU Flow-Control
Idioms.
[25] K ABEK ,
C.:
Einblick
über
die
Anwendungsmöglichkeiten
von
Cg,
2004.
http://people.fh-landshut.de/ gschied/opengl/
13-cganwendung-ckabek/.
[26] K INZELBACH , W. und RUTSCHMANN , P.: Vorlesungskript Hydraulik 2 - ETH Zürich,
2005. http://water2.uibk.ac.at/de/0/de_k0_s1_4.html.
[27] K LOTZ ,
M.:
Herleitung
der
Navier-Stokes-Gleichungen.
http://www.wissenschaft-online.de/spektrum/projekt2/gaes15.htm,
2006.
[28] L AWSON , S.: Physically Based Modeling. Techn. Ber., Department of Computing and
Informatics at the University of Lincoln, 2005.
83
[29] L AYTON , A.T. und VAN DEN PANNE , M.: A numerically efficient and stable algorithm
for animating water waves. The Visual Computer, (18):4153, 2002.
[30] M EISTER , A.: Numerik linearer Gleichungssysteme. Vieweg, 1999. ISBN 3-528-031352.
[31] M ÜLLER , H.: Digitale Bilderzeugung, Jul 2004. Vorlesungsskript, Universität Dortmund,
http://ls7-www.cs.uni-dortmund.de/students/lectures/
doc_dbe/ss04/skript.shtml.
[32] M UMIT
K HAN:
MinGW
http://www.mingw.org.
-
Minimalist
GNU
for
Windows,
2006.
[33] N EDEL , L und T HALMANN , D.: Anatomic modeling of deformable human bodies. The
Visual Computer, (16):306–321, 2000.
[34] NVIDIA: Particle System Dynamics. Techn. Ber., School of Computer Science, Carnegie
Mellon University, 2001.
[35] NVIDIA: NVIDIA 6800 GPUs, 2006.
geforce_6800.html.
http://www.nvidia.com/page/
[36] NVIDIA: NVidia 7800 GPUs, 2006.
geforce_7800.html.
http://www.nvidia.com/page/
[37] NVIDIA: NVIDIA SDK, 2006.
sdk_home.html.
http://developer.nvidia.com/object/
[38] OWENS , J. D., L UEBKE , D., G OVINDARAJU , N., H ARRIS , M., K RÜGER , J., L EFOHN ,
A. E. und P URCELL , T. J.: A Survey of General-Purpose Computation on Graphics
Hardware. Techn. Ber., Eurographics 2005, 2005. State of The Art Report.
[39] P HARR , M. und R. F ERNANDO: GPU Gems 2 : Programming Techniques for HighPerformance Graphics and General-Purpose Computation. Addison-Wesley Professional, March 2005.
[40] P ROVO , X.: Deformation Constraints in a Mass?Spring Model to Describe Rigid Cloth
Behavior. Techn. Ber., Institut National de Recherche en Informatique et Automatique,
2002. http://www.rocq.inria.fr/syntim/research/provot.
[41] R ANNACHER , R.: Einführung in die Numerische Mathematik, 2005. Vorlesungsskript,
Institut für Angewandte Mathematik Universität Heidelberg.
[42] R ANNACHER , R.: Vorlesungskripten Prof. R. Rannacher Numerische Mathematik, 2005.
http://numerik.iwr.uni-heidelberg.de/l̃ehre/notes/.
[43] S CHWARZ , H.R.: Numerische Mathematik. Teubner, 1984.
[44] SGI: ARB_texture_cube_map, 1999.
http://oss.sgi.com/projects/
ogl-sample/registry/ARB/texture_cube_map.txt.
84
[45] SGI: ARB_pixel_buffer_object, 2003.
http://oss.sgi.com/projects/
ogl-sample/registry/ARB/ pixel_buffer_object.txt.
[46] SGI:
ARB_vertex_buffer_object
Extension
Specification,
http://oss.sgi.com/projects/ ogl-sample/registry/ARB/
vertex_buffer_object.txt.
2003.
[47] S TRZODKA , R., D OGGETT, M. und KOLB , A: Scientific Simulations on Programmable
Graphics Hardware. Techn. Ber., Caesar Research Center Bonn, ATI Research, Universität Siegen, 2005.
[48] W ITKIN , A. und BARAFF , D.: Physically Based Modeling Differential Equation Basics.
Techn. Ber., Pixar Animation Studios, 2001.
[49] W OOLLEY, C.: GPU Gems 2. Addison Wesley, 2005. Chapter 35, GPU Program Optimization.

– Diplomarbeit –

Transcrição

Documentos relacionados

ENGTS450 DIRECTCU/DI/1GD5

Schwimmerventile Float valves Nr. 630

Jetzt ansehen

Für Alle Responsive Webdesign - opentext

Systemvoraussetzungen V19

Abit IN9 32X-MAX "Beast" (Sound, 2x G

Grafikkarten - Programmierung

Entwicklung eines hybriden, GPU – unterstützten

Direct3D vs. OpenGL

Full-Service Lösungsanbieter für professionelle 4K-, 3D

Ergebnisbericht über Forschung und Entwicklung 2006

Verkaufsliste_04. August 2008 - GDW-Nord