Sprachen

Smoothed-Particle-Lab - WS 2009/2010, SS 2010

Thema: 
Smoothed-Particle-Lab – Ein Software-System zur Modellierung und Simulation dynamischer, physikalischer Systeme
Zeitraum: 
WS 2009/2010, SS 2010
Umfang: 
8 SWS pro Semester
Veranstalter: 

Prof. Dr. Heinrich Müller, Informatik VII (Graphische Systeme),
OH16, R.124, Tel.:6324, E-Mail: mueller@ls7.cz.uni-dortmund.de

Dipl.-Inf. Denis Fisseler, Informatik VII (Graphische Systeme),
OH16, R.120, Tel.: 6328, E-Mail: fisseler@ls7.cs.uni-dortmund.de

Dipl.-Inf. Marcel Gaspar, Informatik VII (Graphische Systeme),
OH16, R.118, Tel.: 6372, E-Mail: gaspar@ls7.cs.uni-dortmund.de

Einzelpräsentation: 
Montag, den 25.05. um 11.00 Uhr in der OH14, Raum E04
Materialien: 

Video 1 - SPH-Spray
Video 2 - SPH-Wallbreak
Zum Abspielen der Videos ist ein geeigneter Player und der Xvid-Codec erforderlich.

Thematik: 

a) Motivation: Physikbasierte Modellierung und Simulation sind wesentliche Hilfsmittel der heutigen Computergraphik. So ist die physikalische Optik Grundlage für die Erzeugung realistischer Graphiken und die Mechanik die Basis für die Erzeugung realistischer dynamischer Systeme für Strömungen (z.B.Wasser, Feuer, Rauch) und deformierbare Körper. Exemplarische Darstellungen vermitteln hierzu die Abbildungen 1(e)-(h) und Abbildung 2, welche in vergleichbarer Ausprägung in Computerspielen und Computeranimationen zur Anwendung kommen. Die Realisierung derartiger Darstellungen beruht in klassischen Umsetzungen auf der Finite-Elemente-Methode [3]. Da diese aber eine Vernetzung des Objektes voraussetzt (Abb.3), erweisen sich derartige Ansätze bei dynamischen Umgebungen durch notwendige Netzaktualisierungen und dem damit verbundenen Rechenaufwand vielfach als nachteilig. Daher haben in den letzten Jahren im Kontext der Computergraphik, aber auch in der Physik und in den Ingenieurwissenschaften, zunehmend netzfreie Methoden eine erhöhte Aufmerksamkeit erfahren. Ihre höhere Effizienz überwiegt in vielen Fällen die potentziellen Ungenauigkeiten, welche insbesondere im Fall der Computergraphik von untergeordneter Bedeutung sind. Die Grundidee von netzfreien Methoden ist die Verwendung einer endlichen Menge von Stützstellen („Partikeln“) expr_01, die über das Objekt gestreut und mit Zustandsvariablen

(a) (b) (c) (d)
(e) (f) (g) (h)

Abbildung 1: (a)-(d) Darstellung der zugrundeliegenden Partikel im Anschnitt (Quelle: [1]) und (e)-(h) Visualisierung einer auf SPH basierenden Flüssigkeitssimulation

(a) (b) (c) (d)

Abbildung 2: Partikelbasierte Deformationssimulation: (a) Partikelrepräsentation der physikalischen (linke Hälfte) und der visuellen Modellierung (rechte Hälfte); (b) Originalmodell; (c) Elastisch deformiertes Modell; (d) Plastisch deformiertes Modell (Quelle: [6])

expr_02, z.B. für Dichte und Geschwindigkeit, attributiert werden. Mittels Interpolation oder Approximation des Systemzustands durch ein Verfahren der Streudateninterpolation [5] lässt sich der Zustand an jedem Punkt p des Objektes gemäß

expr_03

berechnen. Dabei sind expr_04, sogenannte Basisfunktionen, welche die Zustandsvariablen der Partikel fi in ihre Umgebung „ausstrahlen“ lassen („smoothed particles“). Die Zustandsänderung des Systems kann durch partielle Differentialgleichungen der Physik, z.B. Navier-Stokes-Gleichungen für Strömungen oder Modelle für elastische Materialien beschrieben werden, die sich durch Zeitdiskretisierung unmittelbar in strukturell einfache Algorithmen umsetzen lassen. Besondere algorithmische Aspekte aus Sicht der Informatik sind die Suche nach Nachbarpunkten und die Kollisionsdetektion. Bekannte Ausprägungen des Smoothed-Particle-Ansatzes sind die Smoothed-Particle-Hydrodynamics (SPH) für Strömungen und die Moving-Least-Squares-Approximation (MLS) für Körperdeformationen.

Eine gute Einführung in Smoothed-Particle-Methoden sowie die erwähnten physikalischen Modelle vermittelt das kürzlich publizierte Tutorial [1]. Basisdarstellungen und deren Verwendung sollten den Hörern der einschlägigen Vorlesungen „Mensch-Maschine-Interaktion“ und insbesondere "Geometrisches Modellieren", "Datenvisualisierung" oder "Graphische Datenverarbeitung" bekannt sein. Hingegen soll der Schwerpunkt der PG nicht auf partiellen Differentialgleichungen liegen.

Abbildung 3: Visualisierung eines FE-Geschwindigkeitsfeldes in drei Gitterebenen (Quelle: Diplomarbeit Matthias Miemczyk, 2007)Abbildung 3: Visualisierung eines FE-Geschwindigkeitsfeldes in drei Gitterebenen (Quelle: Diplomarbeit Matthias Miemczyk, 2007)

Für die FE-Methode gibt es komfortable Modellierungs- und Simulationssysteme, beispielsweise Abaqus (http://www.abaqus.de) oder ANSYS (http://www.ansys.com), welche die Erstellung eines Modells für eine gegebene Anwendung, die Durchführung der Simulation durch Löser sowie die Visualisierung des Systemzustands erlauben. In der Konsequenz tragen sie damit zur effizienten Modellerstellung und Überprüfung der Plausibilität der Simulation bei. Hingegen sind die Smoothed-Particle-basierten Arbeiten in der Computergraphik der Realisierung spezieller Effekte gewidmet, häufig mit dem Bestreben der Echtzeitberechnung mit anwendungsbezogener graphischer Ausgabe. Dies führt in der Regel zu hoch optimierten speziellen Programmen unter Ausnutzung spezifischer Hardware-Architekturen, etwa von Graphikkarten. Hier setzt die Aufgabe der PG an.

 

b) Aufgabenbeschreibung: Die Aufgabe der PG ist die Entwicklung eines Software-Systems zur Modellierung und Simulation dynamischer physikalischer Systeme basierend auf der Smoothed-Particle-Methode, kurz "Smoothed-Particle-Lab", welches folgende funktionelle Komponenten umfassen soll:

  • Löser: Eine Zielsetzung ist die zur Verfügungstellung von SPH-Lösern und MLS-Lösern. Im Vordergrund soll dabei eine generische Struktur stehen, eventuell modelliert in einem objektorientierten Rahmen, der die Spezialisierung auf Anwendungskontexte, z.B. einphasige Strömung, mehrphasige Strömung, Interaktion zwischen Strömung und flexiblen Objekten und Interaktion mehrerer flexibler Objekte einfach realisierbar macht. Primär ist dabei die Strukturierung in den Vordergrund zu stellen, der Effizienz aber soweit Beachtung zu schenken, dass praktikable Berechungszeiten erzielbar werden.
  • Anwendungsvisualisierung: In der Computergraphik haben simulierte Prozesse auch eine natürliche visuelle Komponente, insbesondere wenn sie der realen Welt entstammen (s. Abb. 1 (e)-(h)). Dementsprechend soll das Smoothed-Particle-Lab eine Schnittstelle zur realitätsnahen Visualisierung vorsehen. Hierzu kann auf existierende Graphikbibliotheken, z.B. OpenGL [7], aufgebaut werden. Eine Online-Echtzeitvisualisierung parallel zur Berechnung ist nicht notwendig.
  • Modellerstellung: Dieser Aspekt thematisiert die Bereitstellung des Partikelmodells, auf dem die Simulation durchzuführen ist. Aufgaben sind die Definition von Ort und Attributen der Initialpartikel, die Definition starrer Modellteile, z.B. die Landschaft in Abb. 1, sowie die Definition der Werte von globalen Simulationsparametern. Eine mögliche Bereitstellungsform sind Dateiformate, die teilweise von externen Programmen mit Information versorgt werden. Ergänzt werden können prozedurale Modellierer für Teilaspekte, etwa die Partikelgenerierung. Die Beschreibung soll dabei flexibel an die Anforderungen des Lösers angepasst werden können, wofür sich beispielsweise XML [4] anbietet.
  • Metavisualisierung: Gegenstand der Metavisualisierung ist die Visualisierung von Information über den Zustand der Simulation. Exemplarisch zu nennen sind die Partikelverteilung (s. Abb.1(a)-(d)), Partikelattribute wie Masse, Dichte und Geschwindigkeit in Farbcodierung, welche bei Finite-Elemente-Simulationen gebräuchlich sind (s. Abb. 3), oder Visualisierungen von Datenstrukturen, etwa für die Analyse der Nachbarschaftssuche von Punkten.

Bei der objektorientierten Umsetzung dieser Anforderungen in ein Softwaresystem sollen die Entwurfsphasen des Software-Engineering beachtet werden [2] und adäquate Werkzeuge (Quellcodeverwaltung, Wiki, Bugtracking) eingesetzt werden. Dieses geht mit der angestrebten modularen Umsetzung einher, welche eine spätere einfache Erweiterung des Systems erlaubt.

Minimalziele: 
  • Spezifikation der Funktionalitäten des Smoothed-Particle-Labs ausgehend von der Darstellung in der Aufgabenstellung.
  • Entwurf eines Software-Systems zur Bereitstellung der geschilderten Funktionalitäten.
  • Implementierung des Software-Systems in einem Umfang, der die Tragfähigkeit des Entwurfs erkennen lässt und das System prinzipiell anwendbar macht.
  • Erprobung des Systems an mindestens einem "überschaubaren" Demonstrationsbeispiel zum Nachweis der Tragfähigkeit des Systems.
Teilnahmevorraussetzungen: 
  • Eine der Vorlesungen Mensch-Maschine-Interaktion (Graphische Systeme) oder Eingebettete Systeme. [V]
  • Eine der Vorlesungen Digitale Bilderzeugung, Graphische Datenverarbeitung, Geometrisches Modellieren, Datenvisualisierung oder Digitale Bildverarbeitung [ W]
  • Kenntnisse in objektorientierter Programmierung und einer Programmiersprache, z.B. Java oder C++. [V]
  • Kenntnisse in OpenGL-Programmierung. [W]

Legende: [V] vorausgesetzt, [W] wünschenswert

Literatur: 

[1] B. Adams and M. Wicke. Meshless approximation methods and applications in physics basedmodeling and animation. In Ken Museth and Daniel Weiskopf, editors, Eurographics 2009 - Tutorials, pages 213-239, Munich, Germany, 2009. Eurographics Association.
[2] H. Balzert. Lehrbuch der Software-Technik. Spektrum Akademischer Verlag, November 1997.
[3] D. Braess. Finite Elemente, Theorie, schnelle Löser und Anwendungen in der Elastizitätstheorie. Springer-Verlag, Berlin, 1997.
[4] T. Bray, J. Paoli, and C. Sperberg-McQueen. Extensible markup language (xml) 1.0. Recommendation, World Wide Web Consortium (W3C), 1998. http://www.w3.org/TR/1998/REC-xml-19980210.
[5] J. Hoschek and D. Lasser. Grundlagen der Geometrischen Datenverarbeitung. B.G. Teubner, Stuttgart, 1989.
[6] M. Müller, R. Keiser, A. Nealen, M. Pauly, M. Gross and M. Alexa. Point based animation of elastic, plastic and melting objects. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, pages 141-151, Aire-la-Ville, Switzerland, 2004, Eurographics Association.
[7] Opengl, D. Shreiner, M. Woo, J. Neider, ant T. Davis. OpenGL(R) Programming Guide : The Official Guide to Learning OpenGL(R), Version 2 (5th Edition). Addison-Wesley Professional, August 2005.

Rechtliche Hinweise: 
Die Ergebnisse der Projektarbeit inklusive der dabei erstellten Software sollen der Fakultät für Informatik uneingeschränkt zur freien Forschung zur Verfügung stehen. Darüber hinaus sind keine Einschränkungen der Verwertungsrechte an den Ergebnissen der Projektgruppe und keine Vertraulichkeitsvereinbarungen vorgesehen.