Real-time water simulation using the finite element method

Abstract

Wassersimulation in der Computergrafik war in den letzten Jahren der Schwerpunkt von zahlreichen Forschungsarbeiten. Die darin vorgestellten Algorithmen lassen sich klassifizieren in Offlinesimulationsalgorithmen und Echtzeitsimulationsalgorithmen, welche sich stark in ihren Fähigkeiten unterscheiden.<br />Offlinesimulationsalgorithmen sind meist in der Lage Wasser mit vollem Detail in 3D zu simulieren, da die Verarbeitungszeit pro Frame nicht sehr limitiert ist. Echtzeitsimulationsalgorithmen legen aber der Verarbeitungszeit pro Frame ein striktes Limit auf, wodurch viele Applikationen Wasser nur die 2D Flächen approximieren. Das funktioniert aber nur gut für stilles Wasser, da Effekte wie brechende Wellen oder einfach Wasser in einen Tank schütten nicht simuliert werden können. Um dieses zu erreichen, muss auf 3D Wassersimulationsalgorithmen gesetzt werden, welche eine enorme Menge von Verarbeitungsressourcen fordern, sodass selbst bei Verwendung von modernen Grafikprozessoren (graphics processing units, GPUs) ein optimierter Algorithmus nötig ist.<br />Es gibt zwei Arten von 3D Wassersimulationsansätze: partikelbasierte Lagrange und grid- oder meshbasierte Euler Ansätze, von welchen letztere den Schwerpunkt dieser Arbeit bilden. Aktuelle echtzeitfähige Euler Wassersimulationsalgorithmen beruhen auf vielen Approximationen, durch welche entweder die Wassermenge ohne Grund weniger wird oder die Allgemeingültigkeit des Algorithmus verringern. In dieser Arbeit wird ein neuer Euler Wassersimulationsalgorithmus vorgestellt, welcher auf einem Octree basierten Mesh aufbaut, welches sich automatisch an jede gegebene Wassergeometrie anpasst. Dadurch ist sichergestellt, dass die Methode sehr allgemeingültig und in fast jeder Situation performant ist.<br />Die bei 3D Wassersimulationen involvierten Gleichungen werden mit der finiten Elemente Methode so diskretisiert, dass das resultierende lineare Gleichungssystem effizient gelöst werden kann. Dadurch ist es möglich den Algorithmus auf modernen GPUs in Echtzeit laufen zu lassen.<br />

Water simulation in computer graphics has been the focus of many research papers in the last years. The proposed algorithms can be classified into offline simulation algorithms and real-time simulation algorithms, which have a big difference in their capabilities. Offline simulation algorithms can mostly simulate water with full detail in 3D because the processing time per frame is not limited very much.<br />Real-time simulation algorithms, on the other hand, impose a hard limit on the processing time per frame and therefore many applications only rely on approximating water with 2D surfaces. While this works well for still water, effects such as breaking waves or simply pouring water into a tank, cannot be simulated. To accomplish this one has to rely on 3D water simulation algorithms, which require a massive amount of processing resources, such that even when using current graphics processing units (GPUs) an optimized algorithm is required.<br />There are two types of 3D water simulation approaches: particle-based Lagrangian and grid- or mesh-based Eulerian approaches, of which the latter will be the main focus of this thesis. Current real-time capable Eulerian water simulation algorithms rely on many approximations which either cause water to leak without reason or decrease the generality of the algorithm. In this thesis a novel Eulerian fluid simulation algorithm is proposed, which relies on on a octree-based mesh that automatically adapts to any given water geometry. By this it is made sure that the algorithm is very general and that it provides good performance in almost any given situation. The equations evolved in 3D water simulation are discretized with the finite element method in a way, such that the resulting linear equation system can be solved efficiently. Therefore it is possible to let the algorithm run in real-time on current GPUs.