Physics Based Simulation on
GPU‘s
computer graphics & visualization
Benjamin Herrmann
Technologie
MemoryObjects (OpenGL):
- Textur
- Render Target
- Vertex Array
Simulation (praktisch) ohne
Datentransfer CPU
GPU
 Verwendungsunabhängiger Speicherblock auf

Graphikkarte
Hauptprogrammlogik in Fragment-Programm
Benjamin Herrmann
computer graphics & visualization
Körperdarstellung
- Körper als Massenpunkte (Partikel) mit Distanz-
-
Bedingung zwischen je zwei Partikeln
Entspricht ungerichtetem Graphen mit Knoten- und
Kantenbelegung
Benjamin Herrmann
computer graphics & visualization
Partikel-System
- Hier besteht ein Partikel-System aus
- Partikeln mit den Attributen:
-
Masse (tatsächlich wird deren Reziprokes gespeichert)
Position (3 Freiheitsgrade pro Partikel)
Alte Position (für Verlet Integrations Schema)
Beschleunigung (ergibt sich als Summe aller externen Kräfte
auf den Partikel unter Berücksichtigung seiner Masse)
- Normalen Vektor (3 Komponenten, zum Rendern und für
einige Collision Responses)
- Constraints mit den Attributen:
- Index des Start Partikels
- Index des End Partikels
- (Anfangs-) Länge
Benjamin Herrmann
computer graphics & visualization
Inhalt
Grobe Gliederung (Komponenten):
- Verlet Integration
- Constraint Solver
- Collision-Detection und Collision-Response
Benjamin Herrmann
computer graphics & visualization
Verlet Integration
- Unabhängig für jeden Partikel (unconstrained
-
dynamics)
Speichere zum Zeitpunkt t pro Partikel:
x(t) und x(t-t)
Nur implizite Geschwindigkeit (vgl. Euler:
Geschwindigkeit und Position separat aktualisiert)
Damit Geschwindigkeit immer an tatsächliche
Bewegung angepasst
Benjamin Herrmann
computer graphics & visualization
Verlet Integration
1
2
Intuitiv: x(t  t )  x(t )  x(t )  x(t  t )   a(t )  t
2
Fehlerentwicklung (für x1,x2 und x3, x0=0)
1
 a 0 t 2
2
v
1
 a 0 t 2
2
1
 a1t 2
2
v3
v2
1
a 2 t 2
2
1
a1t 2
2
x1  x0
v1
v0
t1
0 = t0
x2  x1
t2
t3
t
t
Benjamin Herrmann
computer graphics & visualization
Verlet Integration
Korrekt: x(t  t )  x(t )  x(t )  x(t  t )  a(t )  t 2
Fehlerentwicklung (für x1,x2 und x3, x0=0)
1
a 0 t 2
2
v
1
a1t 2
2
v3
a2 t 2
v2
v1
1
a 2 t 2
2
a1t 2
a0 t 2
v0
t1
0 = t0
x 2  x1
x1  x0
t2
t3
t
t
Benjamin Herrmann
computer graphics & visualization
Verlet Integration - Implementierung
Benjamin Herrmann
computer graphics & visualization
Verlet Integration - Implementierung
- Benötige MemoryObjects für folgende
Partikelattribute:
- „Aktuelle“ Positionen aller Partikel
- „Alte“ Positionen aller Partikel
- Beschleunigungen aller Partikel
- Massen aller Partikel (kann in beliebiger der obigen
Texturen gespeichert werden)
- Zusätzliches MemoryObject für Ping-Pong
- Zeigervertauschung, um die Partikelattribute für
den nächsten Simulationsschritt zu aktualisieren:
- Aktuelle Positionen <-> Alte Positionen
- Aktuelle Positionen <-> Ergebnis der Integration
Benjamin Herrmann
computer graphics & visualization
Verlet Integration
- WorldBox (AA): wmin=(wx,wy,wz), wmax=(Wx,Wy,Wz)
-
=> Projektion: min( max(wmin,x(t)), wmax )
Reibung:
- Projektionstiefe berücksichtigen
- Faktor d um Luftwiederstand zu simulieren
- Demo 1
Benjamin Herrmann
computer graphics & visualization
Constraints
- Hinzufügen topologischer Informationen, um
-
Festkörper zu simulieren
=> Distanz-Bedingungen zwischen je 2 Partikeln
pj
Lokale Lösung:
p
pj
j
cij
cij
pi
pi
cij
Massen abhängig (xj analog):
1 x j  xi  cij (x j  xi )
xi '  xi  

mi  1

x j  xi
  1 
 mi m j 


pi
Benjamin Herrmann
computer graphics & visualization
Constraints
-
Globale Lösung für Distanz-Bedingungen durch:
- Auflösen der lokalen Distanz-Bedingungen in fester
Reihenfolge (berücksichtigt aktuelle Positionen)
=> Es können nur unabhängige Constraints parallel
verarbeitet werden (Matching):
v0
v1
v2
v0
v1
v2
v0
v1
v2
v0
v1
v2
v0
v1
v2
v0
v1
v2
v3
v4
v5
v3
v4
v5
v3
v4
v5
v3
v4
v5
v3
v4
v5
v3
v4
v5
v6
v7
v8
v6
v7
v8
v6
v7
v8
v6
v7
v8
v6
v7
v8
v6
v7
v8
mindestens h interne Render Passes, wobei h der
maximale Knotengrad ist.
Benjamin Herrmann
computer graphics & visualization
Constraints
- Paralleles Lösen aller lokalen Distanz-Bedingungen, indem
für jeden Constraint cij der Ausgleichsvektor
x j  xi  cij (x j  xi )
dij 

 1

x j  xi
  1 
 mi m j 


ermittelt wird. Aufsummieren und Mitteln (Stabilität) aller
dij für die an einen Partikel angrenzende Kanten ergibt den
nötigen Offset pro Partikel (vgl. Feder-Masse System)
=> „Durchhängen“ im
Gleichgewichtszustand:
p3 (fixiert)
g
p2
p1
p0
Benjamin Herrmann
computer graphics & visualization
Constraints
- Datenstrukturen zur Speicherung der Topologie
- Knotenbasiert:
-
h Nachbarschafts-Texturen Nk (1kh).
Sei (si,ti) die Textur Koordinate für Partikel i, dann
speichert Nk in Texel (si,ti) das Tupel (sj,tj,lij), falls
Partikel j der k-te Nachbar von Partikel i ist.
Kantenbasiert:
- Kantentextur, die für Kante cij das Tupel (si,ti,sj,tj) speichert.
- Textur, die die Länge aller Kanten speichert.
- Nachfolgend implementiert und besprochen:
- Knotenbasiert: unter Berücksichtigung der aktuellen
-
Position
Paralleles Auflösen der Constraints:
- Kantenbasiertes Gathering
- Kantenbasiertes Scattering
Benjamin Herrmann
computer graphics & visualization
Constraints – Knotenbasiert
-
-
-
Mit aktualisierten Positionen nur mit h internen Rendering
Passes möglich!
Pro Pass müssen genau wh Fragmente generiert werden,
wobei w,h die Breite und Höhe der Partikel-Texturen sind.
Pro Pass k und pro Partikel i:
-
-
1 direkter Texture-fetch für die eigene Position
1 dependant Texture-fetch für die Position des k-ten Nachbarn
(aus Nk)
Berechnung der aktuellen Position von Partikel i
(1kh): Nk besteht nur aus vollständigen Kanten eines
Matchings.
Zwischen zwei Rendering Passes: Ping-Pong, damit immer die
aktualisierten Positionen benutzt werden.
dij wird pro Kante zweimal berechnet => Kantenbasiert
Benjamin Herrmann
computer graphics & visualization
Constraints – Kantenbasiert (Gathering)
- 1. Rendering Pass rendert ein Fragment pro Kante
-
cij und berechnet aus zwei dependant texturefetches den Vektor dij.
=> Offset Textur
2. Rendering Pass rendert ein Fragment pro
Partikel. Für alle Partikel i:
- Summiere die maximal h Offsetvektoren zu den zu i
-
inzidenten Kanten. Dazu sind h Inzidenz-Texturen
notwendig (vgl. Nachbarschafts-Texturen) sowie h
dependant texture-fetches.
Teile den Gesamt-Offsetvektor durch den Grad des
Partikels (entweder immer h oder mit in Inzidenz-Texturen
speichern).
Benjamin Herrmann
computer graphics & visualization
Constraints – Kantenbasiert (Scattering)
- 1. Rendering Pass wie vorher => Offset-Textur
- 2. Rendering Pass benutzt Kantentextur als
-
VertexArray und das Positions MemoryObject als
Render Target.
Clip Space Koordinaten entsprechend dem StartKnoten einer Kante generiert.
3. Rendering Pass: wie 2. Pass aber mit EndKnoten.
Anmerkung:
Clamping => Rendering Passes 2pos/2neg und3pos/3neg, welche positive/negative Komponenten
der Offset Vektoren in seperate Texturen blenden.
Benjamin Herrmann
computer graphics & visualization
Constraint - Demos
- Demo2:
-
ebenso wie Demo1 nur diesmal mit
eingeschaltetem Constraint Solver
Demo3: Knotenbasiert
Demo4: Kantenbasiert – Gathering
Demo5: Scattering - Scattering
Benjamin Herrmann
computer graphics & visualization
Collision Detection
- Partikelbasierte Kollisionserkennung => O(n²)
-
Vergleiche
Binning der AABB des Partikelsystems
- Reduziert die Anzahl der notwendigen Partikelvergleiche
- Ggf. Jittering
- Größe der Bins
Benjamin Herrmann
computer graphics & visualization
Collision Detection - AABB
- Berechnung der AABB (Bmin/Bmax) auf GPU:
- 2 Rendering Passes je aller Partikelpositionen auf ein
-
einzelnes Fragment mit blenden (Komponentenweise min
bzw. max)
2ln(max(w,h)) Rendering Passes über je (1/4)kwh
(k=1,...) Partikel:
x00
x01
0
0
0
0
h
x10 = min(x 0, x 1, x 2, x 3)
x03
x10
x11
x13
x12
...
x02
w
Candidate-fragments
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Implementierung
1. Rendering Pass:
Ordne jedem Partikel eine BinID zu =>ZuordnungsMemoryObject. Texel ist Tupel (si,ti,id)
2. Rendering Pass:
- Benutze Zuordnungs-MemoryObject als VertexArray
- Dereferenziere VertexArry als GL_POINTS.
- Rendere in Bin MemoryObject (Einsortieren der Partikel).
3. Rendering Pass:
Benutze Bin MemoryObject und Zuordnungs
MemoryObject als Textur und rendere über alle
Partikel => Kontrolliere für jeden Partikel, ob
zugeordneter Bin bereits belegt ist.
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Implementierung
1. Rendering Pass:
Ordne jedem Partikel eine BinID zu =>ZuordnungsMemoryObject. Texel ist Tupel (si,ti,id)
2. Rendering Pass:
- Benutze Zuordnungs-MemoryObject als VertexArray
- Dereferenziere VertexArry als GL_POINTS.
- Rendere in Bin MemoryObject (Einsortieren der Partikel).
3. Rendering Pass:
Benutze Bin MemoryObject und Zuordnungs
MemoryObject als Textur und rendere über alle
Partikel => Kontrolliere für jeden Partikel, ob
zugeordneter Bin bereits belegt ist.
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Boolean Binning
- Bin MemoryObject hat GL_RGBA8 Format
- Jede 8-bit Komponente repräsentiert einen Bin
-
(Maske) und speichert die Anzahl der Partikel darin.
Alles größer 1 zählt als Kollision
Rendern in Bin MemoryObject durch normales
Blending
Platzverbrauch ideal, aber kleine Bins nötig
Nur Kollision Ja/Nein, keine Information über
„Kollisions-Partner“
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Stencil Routing
- Implementiert für maximal 4 Partikel pro Bin
-
(beliebig auf x² Partikel erweiterbar)
Bin MemoryObject benutzt Fließkomma-Genauigkeit
Je 4 Texel entsprechen einem Bin
Statt einzelner Fragmente werden ‚Fat Points‘
gerendert (hier: glPointSize(2.0f))
StencilBuffer vor Pass 2 (Einsortieren) vorbelegt mit
Muster:
0
1
0
1
- Stencil-Test testet auf
2
3
2
3
Gleichheit mit 3
- Stencil-Wert immer um
0
1
0
1
1 erhöht
2
3
2
3
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Stencil Routing
- Beispielablauf (Fragmentreihenfolge a priori
unbekannt):
0
1
1
2
(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
...
2
3
3
4
(0,0,0,0)
(0,0,0,0)
(0,0,0,0)
(s,t,0,0)
- Speichert Textur-Koordinaten der bis zu 4 Partikel
-
pro Bin => beliebige Attribute des „Kollisions
Partners“ zugreifbar
16 Mal größeres Bin MemoryObject als bei Boolean
Binning (sogar 64 Mal so viel Speicher)
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Stencil Routing
- Partikel i kollidiert mit Partikel j, falls:
- Textur-Koordinaten von beiden befinden sich im gleichen
-
Bin
Ihr Abstand ist geringer als eine vorgegebene Grenze
(wichtig, wenn mehrere Bins auf den gleichen Fat-Point
gerendert werden)
- Komplexere Kollisions-Bestimmung => Stencil
-
Routing ist langsamer als Boolean Binning
Aber komplexere Collision-Responses möglich, die
Attribute des „Kollisions-Partners“ einbeziehen.
Zum Beispiel: - Position
- (implizite) Geschwindigkeit
Benjamin Herrmann
computer graphics & visualization
Collision Detection – Demos
-
Demo 6:
-
Demo 7:
-
Demo 8:
-
Demo 9:
-
Demo 10:
-
Demo 11:
Demo 12:
Self-Collision bei Cloth (Nur Kollisionerkennung, keine Response)
Self-Collision bei Cloth (Collision- Response stößt
Partikel ab)
Self-Collision bei Cloth (Collision- Response
ändert relative
Geschwindigkeit)
Kollision vieler Objekte (CollisionResponse ändert Partikelpositionen)
Kollision vieler Objekte (s.o., aber
anderer Kollisionsabstand)
Massenabhängigkeit (schwere Würfel)
Massenabhängigkeit (leichte Würfel)
Benjamin Herrmann
computer graphics & visualization
Bemerkungen
- Normalenberechnung
- Wind: Skalarprodukt des (unnormalisierten) Wind-
Vektors mit dem (unnormalisierten)
Normalenvektor jedes Dreiecks.
Performance
- Ping Pong vs. Unroll
- Taylorapproximation der Wurzelfunktion bei Constraint
-
Solvern
Index MemoryObject vs. system memory Index Array
Vertex Programm Bandbreite reduzieren: Bilineare
Interpolations Textur (Geschwindigkeitsgewinn durch
geringere Auflösung wg. größerer Lokalität -> Caching)
- GPU basiertes Picking
Benjamin Herrmann
computer graphics & visualization
Letzte Demos
- Demo 13: Fahne (Wind und Picking)
- Demo 14: Performance Layout
Benjamin Herrmann
computer graphics & visualization
Performance
Alle Tests ohne Rendern und auf
- Pentium 3.2 GHz mit 1.5 GB RAM
- ATI X600 mit 256 MB TRAM
128x128
GPU
128x128
CPU
256x256
GPU
256x256
CPU
512x512
GPU
512x512
CPU
Scattering
0.4fps
-
-
-
-
-
Gathering
186fps
48.45fps
58fps
12.43fps
16.45fps
0.15fps
Knoten
282fps
76fps
108fps
19.38
28.25fps
0.18fps
+AABB
212fps
74fps
84fps
18.83
22.6fps
0.17fps
+BB
174fps
32fps
62fps
7.52fps
15.5fps
-
+SR
116fps
32Fps
40.7fps
7.52fps
9.69fps
-
Benjamin Herrmann
computer graphics & visualization
Zusammenfassung
+ Weit schneller als die CPU-Implementierung der
Algorithmen
+ Graphik Hardware Entwicklung verdreifacht Moore‘s
Law
– Algorithmen stark vereinfacht
– Partikelsystem, das unabhängig aktualisiert werden
kann ist sehr gut auf GPU zugeschnitten, ebenso
sind komplexere Algorithmen mit zugeschnittenen
Datenstrukturen denkbar bei denen eine CPU
Lösung (noch) besser abschneidet
=> In Anbetracht der Entwicklung sind GPU basierte
Simulationen allerdings sehr interessant
Benjamin Herrmann
computer graphics & visualization
Danke für die Aufmerksamkeit!
Fragen?
Benjamin Herrmann
computer graphics & visualization

PowerPoint-Präsentation