GPU-basierte Simulation dynamischer Terrains

TU-Dresden

Lehrstuhl für Computergrafik

und Visualisierung GPU-basierte Simulation dynamischer

Terrains

DiplomverteidigungMaik Lathan2008

Diplomverteidigung - Maik Lathan - TU-Dresden - 2008

Dynamische Terrains in der Computergrafik

GPU-basierte Simulation dynamischer Terrains

Die Anwendung – Sandbox.exe

Mögliche Erweiterungen von „Sandbox“

Motivation

Simulation natürlicher Phänomene in der Computergrafik realistische virtuelle Umgebungen

Dynamische Terrains sind Grundlage verschiedener Anwendungen: WisVis, Filmindustrie, Spielindustrie, Militär

Bodenmechanik als Grundlage für Terrainverhalten Umfangreiche physikalische Phänomene

Berechnungen erfordern hohe Rechenleistung bisher effiziente Darstellung statischer Terrains

Leistung von Graphics Processing Unit (GPU) verwenden Bodenmechanik in Echtzeit simulieren und darstellen


Zielstellung


1

2

3


Grundlagen der Bodenmechanik I

Boden besteht aus granularen Partikeln Beispiel: Kies, Schotter, (Zucker)

Merkmale: Form, Farbe, Masse, chemischer Aufbau

Reibung zwischen Partikeln Aufschüttung bildet stabile Halde (Anstieg θ)

Wird Reibung überwunden, beginnt Boden zu fließen Festkörper & Flüssigkeit

Übergang zwischen „fest“ und „flüssig“ Bruchebene

Halde mit Gefälle

Bruchebene

Entmischung


Grundlagen der Bodenmechanik II

Boden durch physikalisches Modell abbildenHöhensäulen [Li1993]Diskrete-Elemente [Cu1979]

Höhensäulen: Bodenvolumen diskret als „Säulen“ auf 2D-Raster abbilden

Berechnungen auf Basis der Höhendifferenz von Säulen

Diskrete-Elemente: Sandkörner als sphärische Partikel abbilden

Berechnung auf geometrischer Basis bzw. Wechselwirkungen zwischen Partikeln

Höhensäulen

Sphärisches Partikel

Partikelverbund

Allgemeine GPU-Berechnungen

Darstellungsfähigkeiten für allgemeine Berechnungen verwenden

Algorithmen auf paralleler GPU-Architektur implementieren

Vereinfachte CPU-GPU-Analogien: Funktionsaufruf Darstellung Innere Funktion Pixel-Shader Array Textur


Stark vereinfachte Shader-Modell 4.0 Architektur (DirectX10)


Terrain-Modell

Sphärische Diskrete-Elemente bilden Erdboden Zustand: Ort x, Impuls p, Masse m, Radius r

Wechselwirkung bei Kollision: Partikel j Partikel i Kollisionskraft, Dämpfungskraft: FC+FD

n ip

jp relp

tanp

rp

x

Partikel

sonstndrk

drndrkFC ,)2(

02,)2(

tanppF relD

ijrel ppp

)(tan npnpp relrel

ix jx

d

ddn


Verfahren I

Diskrete-Elemente bilden Partikelsystem in Simulationsraum SR simuliert

Inter-Partikelkollision beschleunigen Partikel in Voxelgitter einsortieren

Objekt-Partikelkollision beschleunigen Voxelgitter nutzen

Terrainoberfläche aus Partikel generieren optimierter Marching-Cubes-Algorithmus

Verfahren ist Kaskade von GPU-Shadern


Verfahren II

Shader-Verbund der Simulation


(A) GPU-Voxelgitter

Besteht aus homogenen Volumenelementen Partikel je Zeitschritt neu einsortiert

Voxelgitter besteht aus 3D-Textur und 1D-Textur Primäreinsortierung in 3D-Textur, sekundär in 1D-Textur als

Liste

Voxel

Grid

loxVoxel

GittersdesUrsprungGrido

nlängeVoxelkanteVoxell

41

3Voxel

3 4 …Partikel 3 bereits

einsortiert

4 1 …

0 1 2 3 4 5 6 7Voxel4, 3, 1


(B) GPU-Kollision und Reaktion I

Dreiecksbasierte Objekte kollidieren mit Partikeln Terrain direkt manipulierbar

Suchraum für Kollision effizient einschränken Kollisionserkennung und -reaktion in 2 Phasen

1. Grobe Suche, 2. exakte Kollision Grobe Suche:

Voxelgitter ausnutzen Achsenorientierte Begrenzungsbox definiert Voxelvolumen

Exakte Kollision: Partikel in Objektvoxeln berücksichtigen Hierarchischer Schnitttest Kugel-Dreieck


(B) GPU-Kollision und Reaktion II

Simulationsraum SR

7 6 54

3 2

Grobe Suche AOBB an Voxelgitter anpassen Voxel bestimmen

Exakte Kollision (Partikel 8)

Punkt-In-Dreieck? Kugel-Berührt-Kante? Kugel-Berührt-Ecke?

Wirkende Kraft ermitteln (Modell) Kraft in Textur speichern

F

91

8


(C) GPU-Partikelsystem I

Simulation basiert auf Newton‘scher Mechanik Simulationszeitschritt 100ms Partikelzustand in 2x 2D-Texturen gespeichert

Berechnungen durch gerastertes Vollbildrechteck

Je Texel ein Partikel!


(C) GPU-Partikelsystem II

Kräfte akkumulieren FGes und System integrieren Gravitation (konstant je Partikel) Partikel-Simulationsraum-Kollision Partikel-Objekt-Kollision Partikel-Partikel-Kollision

Voxelgitter für Partikel-Partikel-Kollision nutzen 27 Nachbarvoxel betrachten

Zustandstextur der Partikel aktualisieren

tFpp Ges' tmpxx '' ttszeitschriSimulationt


(D) GPU-Oberflächenrekonstruktion I

Partikelsystem in Terrainoberfläche umwandeln Phase 1: Skalarfeld berechnen Phase 2: Marching-Cubes generiert Oberfläche Marching-Cubes verwendet Voxelgitter als Grundlage Geometry-Shader generiert Oberflächendreiecke

(D) GPU-Oberflächenrekonstruktion II

Modell der Oberflächenrekonstruktion


sonst,0

rr,41

r2r

r2r

crit

2

crit

4

crit

Fieldf

tGitterpunkPartikelAbstand r

Radiuskritscherrcrit [Triquet2001]

(D) GPU-Oberflächenrekonstruktion III

Phase 1 – Skalarfeld Feldfunktion je Gitterpunkt je Partikel auswerten Schichten ermitteln, die Partikel überdeckt Je Schicht ein Rechteck im Voxelgitter darstellen Feldwerte summieren AlphaBlending



(D) GPU-Oberflächenrekonstruktion IV

Phase 2: Marching-Cubes Dreiecksnetz Platten durchwandern, jedes Voxel Angrenzende Schichten auswerten 8 Ecken Dreiecke erzeugen VertexBuffer


Ergebnisse

DEMO


Zusammenfassung

Verfahren komplett mit GPU berechnet (DirectX10) Partikelsystem, Kollisionsreaktion und

Oberflächenkonstruktion dynamische Terrainsimulation

Verfahren basiert auf physikalisch plausibler DEM-Methode Erosion, Einschläge, Lawinen

Objekte können mit Terrain interagieren Materialtransport

Volumetrischer Erdboden Höhlen, Durchdringungen

Echtzeitfähig mit 10.000 Partikeln


Ausblick

Beschränkung des Simulationsraums aufheben 3D-Hash anstatt Voxelgitter nutzen

Partikelanzahl reduzieren (viele nicht sichtbar) Partikelanzahl- und Größe an Erfordernis anpassen

Physikalische Simulation auf Aktionsvolumen einschränken wodurch definieren sich die Volumen?

Terrain auf hoch paralleler Architektur berechnen (IBM Cell, NV TESLA) einzelne Bereiche mit SPU/GPU berechnen/simulieren


Ende

Vielen Dank für Ihre Aufmerksamkeit

Documents

GPU-basierte Simulation dynamischer Terrains