TU Darmstadt / ULB / TUprints

Interactive Physically Based Simulation - Efficient Higher-Order Elements, Multigrid Approaches and Massively Parallel Data Structures

Weber, Daniel :
Interactive Physically Based Simulation - Efficient Higher-Order Elements, Multigrid Approaches and Massively Parallel Data Structures.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2016)

[img] Text
DissertationDanielWeber_final.pdf
Available under Creative Commons Attribution Non-commercial No-derivatives 3.0 de.

Download (19MB)
Item Type: Ph.D. Thesis
Title: Interactive Physically Based Simulation - Efficient Higher-Order Elements, Multigrid Approaches and Massively Parallel Data Structures
Language: English
Abstract:

This thesis covers interactive physically based simulation for applications such as computer games or virtual environments. Interactivity, i.e., the option that a user can influence a system, imposes challenging requirements on the simulation algorithms. A simple way to achieve this goal is to drastically limit the resolution in order to guarantee this low computation time. However, with current methods the number of degrees of freedom will be rather low, which results in a low degree of realism. This is due to the fact that not every detail that is important for realistically representing the physical system can be resolved.

This thesis contributes to interactive physically based simulation by developing novel methods and data structures. These can be associated with the three pillars of this thesis: more accurate discrete representations, efficient methods for linear systems, and data structures and methods for massively parallel computing. The novel approaches are evaluated in two application areas relevant in computer generated animation: simulation of dynamic volumetric deformation and fluid dynamics. The resulting accelerations allow for a higher degree of realism because the number of elements or the resolution can be significantly increased.

Alternative Abstract:
Alternative AbstractLanguage
Physikalisch-basierte Simulationen sind ein wichtiger Bestandteil in vielen Applikationen in der Computergraphik. Computeranimationen, Computerspiele oder virtuelle Umgebungen wirken deutlich realistischer, wenn physikalische Phänomene wie beispielsweise die Bewegung von Rauch, Flüssigkeiten und die elastische Verformung von deformierbaren Körpern realitätsgetreu nachgeahmt werden können. Um möglichst plausible und natürlich wirkende Bewegungsabläufe zu generieren, ist es von Vorteil, die Physik auf Basis der Kontinuumsmechanik zu modellieren, die durch partielle Differenzialgleichungen beschrieben werden und ebenfalls in den Ingenieurwissenschaften Anwendung finden. Dabei werden Energie-, Impuls- und Massenerhaltung gefordert, und die resultierenden Differenzialgleichungen setzen räumliche und zeitliche Ableitung der gesuchten Größen miteinander in Bezug. Zur Berechnung der Bewegung muss in vielen Fällen das Simulationsgebiet vernetzt und ein numerisches Verfahren zur Approximation der Lösung auf dem Rechengitter angewendet werden. Diese numerischen Verfahren sind im Allgemeinen sehr rechenaufwendig und benötigen lange Zeit, um den Bewegungsablauf zu bestimmen. Die Anzahl der Freiheitsgrade des Rechennetzes hat hierbei meist direkten Einfluss auf die Rechenzeit. Für einige Applikationen wie beispielsweise Computerspiele oder virtuelle Umgebungen ist Interaktivität in Simulationen von zentraler Bedeutung. Interaktiv in diesem Kontext bedeutet, dass die Berechnungszeit eines einzelnen Simulationsschritts unter einhundert Millisekunden betragen muss, sodass ein Benutzer die Simulation als Animation wahrnimmt und gleichzeitig mit ihr interagieren kann. Solche kurzen Berechnungszeiten können mit aktuellen Methoden meist nur erreicht werden, wenn Rechengitter mit einer sehr geringen Anzahl an Freiheitsgraden verwendet werden. Diese können aber meist nicht die gewünschten physikalischen Effekte ausreichend auflösen. Ziel dieser Arbeit ist es, Interaktivität in physikalisch-basierten Simulationen zu erreichen und gleichzeitig den Detailgrad zu erhöhen. Simulationen mit hochaufgelösten Rechengittern und diesen zeitlichen Anforderungen sind mit aktuellen Methoden nur schwer zu erreichen. Deshalb werden neuartige Methoden entwickelt, die den drei Säulen dieser Arbeit zugeordnet werden können: Präzisere diskrete Repräsentationsformen, effiziente Methoden für lineare Gleichungssysteme sowie Datenstrukturen und Methoden für massiv-paralleles Rechnen. Diese Methoden werden in zwei relevanten Gebieten der Computeranimation, der Strömungssimulation und der Simulation von deformierbaren Materialien, angewendet und evaluiert. Die neuartigen Ansätze beschleunigen physikalisch-basierte Simulationen signifikant und ermöglichen bei interaktiver Rechenzeit mehr Freiheitsgrade und dadurch deutlich mehr Detailreichtum. Präzisere diskrete Repräsentationsformen erzielen eine höhere Genauigkeit pro Element im Rechengitter und erlauben damit eine deutlich geringere Netzauflösung bei gleichbleibender Qualität. In diesem Kontext wird untersucht, wie Polynome höherer Ordnung in Bernstein-Bézier-Form für die Simulation von Deformation auf Tetraedernetzen eingesetzt werden können und welchen Einfluss dies auf die Qualität und die Rechengeschwindigkeit hat. Weiterhin wird im Umfeld der Strömungssimulation eine verbesserte Modellierung und genauere Repräsentation von eingebetteter Geometrie in Form von teilgefüllten Zellen auf regulären Gittern entwickelt. Damit kann insbesondere Geometrie, die nicht am regulären Gitter ausgerichtet ist, vom Simulator besser aufgelöst und damit genaueres Strömungsverhalten erreicht werden. In vielen Fällen wird der größte Teil der Rechenzeit vom Aufbau und der Lösung der großen linearen Gleichungssysteme beansprucht, die bei der numerischen Diskretisierung der partiellen Differenzialgleichungen entstehen. Daher werden in dieser Arbeit effiziente Methoden für lineare Gleichungssysteme entwickelt und analysiert, welche diesen zeitaufwendigen Prozess beschleunigen. Zum effizienteren Aufbau von Gleichungssystemen wird eine netzbasierte Methode entwickelt, die aufgrund von Nachbarschaftsinformationen in Tetraedernetzen schneller das lineare Gleichungssystem konstruieren kann. Weiterhin werden auf Basis der präziseren diskreten Repräsentationsformen zwei neuartige Mehrgittermethoden entwickelt, die auf einer Hierarchie von polynomialen Repräsentationen bzw. auf Hierarchien von Diskretisierungen mit teilgefüllten Zellen basieren. Die entstehenden Gleichungssystemlöser sind deutlich schneller als konventionelle Methoden und ermöglichen damit höhere Auflösungen bei gleichem Budget für die Rechenzeit. Weiterhin werden Datenstrukturen und Methoden für massiv-paralleles Rechnen entwickelt, die speziell auf eine effiziente parallele Ausführbarkeit ausgerichtet sind. Insbesondere für das effiziente, massiv-parallele Rechnen auf Graphikkarten (graphics processing units – GPUs), d.h. die Ausführung auf Tausenden von Prozessoren sind bestimmte Anforderungen zu berücksichtigen, die hier untersucht werden. Eine Datenstruktur für dünnbesetzte Matrizen, die speziell für Deformationssimulationen auf Tetraedernetzen entworfen wurde, optimiert Matrix-Vektor Multiplikationen und ermöglicht damit eine schnelle Lösung von linearen Gleichungssystemen. Weiterhin werden für ein GPU-basiertes Standardverfahren zum Lösen von linearen Gleichungssystemen kleine GPU-Programme zusammengeführt, um den Overhead der Ausführung zu minimieren. Dies ist insbesondere für interaktive Simulationen vorteilhaft, da der zusätzliche Zeitaufwand einen nicht unerheblichen Teil der Rechenzeit ausmachen kann. Weiterhin wird eine Datenstruktur entwickelt, die für teilgefüllte Zellen in Strömungssimulationsszenarien die Datenhaltung minimiert und damit ebenfalls das Lösen von linearen Gleichungssystemen beschleunigt. Die Methoden, die in dieser Arbeit entwickelt werden, tragen dazu bei, physikalisch-basierte Simulationen signifikant zu beschleunigen. Dies ermöglicht einen deutlich höheren Detailgrad, der durch eine feinere Netzauflösung bei gleicher Rechenzeit erreicht werden kann. Durch die Kombination von den Methoden aus allen drei Säulen kann die Anzahl der Elemente in interaktiven Simulationen deutlich erhöht werden.German
Place of Publication: Darmstadt
Uncontrolled Keywords: computer animation, simulation, interactive simulation, physically based modeling, partial differential equations, multigrid, higher-order elements, massively parallel computing
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Interactive Graphics Systems
Date Deposited: 19 Feb 2016 12:02
Last Modified: 19 Feb 2016 12:02
URN: urn:nbn:de:tuda-tuprints-53257
Referees: Stork, Prof. Dr. André and Fellner, Prof. Dr. Dieter and Goesele, Prof. Dr. Michael
Refereed: 7 December 2015
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/5325
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year