Paper

Abstract
Diese Arbeit soll einen Überblick über eine Methode der Fluidsimulation und die Animation von Sand als Fluid
im Speziellen geben. Mittels der Methoden die im Paper „Animating Sand as a Fluid“, von Yongning Zhu,
genutzt wurden, wird dafür zunächst ein Algorithmus zur Fluidsimulation anhand von Partikeln mit Gitter als
Hilfsstruktur vorgestellt. Danach wird gezeigt mit welchen Erweiterungen man diese Methode der
Fluidsimulation auch zur Animation von Sand als Fluid nutzen kann. Abschließend wird noch eine Methode zur
Oberflächenrekonstruktion mittels Fluidpartikeln beschrieben.
1. Einleitung
Es gibt verschiedene Ansätze zur Animation von Sand. Ein Ansatz ist es jedes Sandkorn als einzelnen
Starrkörper zu simulieren, wie zum Beispiel in [5]. Dieser Ansatz ist gut geeignet solange man eine geringe
Anzahl an Sandkörnern betrachten möchte. Um auch eine größere Menge Sand animieren zu können nutzt
man andere Ansätze die nicht mehr die Sandkörner einzeln, sondern den gesamten Sand als Kontinuum
betrachten und dieses Kontinuum anhand von Partikel- oder Gitter-basierten Methoden simulieren.
Einen solchen Ansatz lieferte Yongning Zhu in seinem Paper „Animating Sand as a Fluid“, in dem der Sand als
Kontinuum anhand von Partikeln, mit Hilfsgitter für Berechnungen, animiert wird. In dieser Arbeit soll nun ein
Überblick über die genutzten Methoden in diesem Paper geboten werden. Kapitel 2 beschreibt hierfür die
genutze Fluidsimulation, Kapitel 3 die nötigen Erweiterungen um die Fluidsimulation auch zur Animation von
Sand verwenden zu können und Kapitel 4 zeigt eine Möglichkeit zur Oberflächenrekonstruktion anhand der
fluid-definierenden Partikel.
2. Fluidsimulation
Zur Durchführung der Fluidsimulation wurden bestehende Modelle wie die Particle-in-Cell Methode (PIC) [4]
und die Fluid-Implicit-Particle (FLIP) [1] Methode für den Fall einer nicht komprimierbaren Fluidströmung
adaptiert. Beide Methoden nutzen bereits eine Mischung aus Partikeln und Gittern um ein Fluid zu simulieren.
In der hier vorgestellten Methode dient das Gitter als reine Hilfsstruktur für die Fluidsimulation auf der die
Werte der Partikel aktualisiert werden, insbesondere hat man dadurch den Vorteil das man nicht in jedem
Zeitschritt das selbe Gitter benötigt, sondern dieses an die aktuellen Positionen der Fluidpartikel anpassen kann
[6].
Zur Berechnung der Geschwindigkeitsänderungen wird folgende, an inkompressible Strömungen angepasste,
Navier-Stokes-Gleichung genutzt:
Diese Gleichung lässt sich in vier Teile zerlegen, welche einzeln berechnet werden und danach addiert werden
können:


: Die Advektion beschreibt wie ein Fluid bestimmte Werte oder Objekte auf dem
Geschwindigkeitsfeld mit transportiert. (z.B. behalten die Partikel ihre Geschwindigkeit, wenn sie
bewegt werden)
: Der Einfluss von externen Kräften die auf das Volumen wirken. (z.b. Gravitation)

: Die Diffusion bewirkt eine Glättung des Vektorfelds, deren Stärke von der Viskosität des Fluids
abhängt.

: stellt sicher, dass das Geschwindigkeitsfeld divergenzfrei bleibt – also die Kontinuitätsgleichung
für inkompressible Fluide erfüllt ist (
. Dies sichert die Inkompressibilität des Fluids.
Dabei ist eine Geschwindigkeitskomponente des Geschwindigkeitsvektorfelds,
die Dichte und der Druck.
die Viskosität des Fluids,
Zur Durchführung der Fluidsimulation kann man den folgenden Algorithmus nutzen (in Anlehung an [6]):
 Initialisierung der Partikelpositionen und Partikelgeschwindigkeiten
 Für jeden Zeitschritt:
o Übertragung der Partikelwerte auf das Gitter
o Berechnung der neuen Werte auf dem Gitter
o Übertragung der aktualisierten Werte auf die Partikel
o Partikelpositionen aktualisieren
Abbildung 1 veranschaulicht diesen Algorithmus. Im Folgenden werden nun die einzelnen Schritte kurz
beschrieben.
(a)
(b)
(c)
(d)
(e)
Abb. 1 [7]: Algorithmus zur Fluidsimulation. (a) Initialisierung der Partikel, (b) Übertragung auf Gitterpunkte, (c) Update der Gitterwerte, (d)
Übertragung auf Partikel, (e) Bewegen der Partikel (Geschwindigkeiten werden mit transportiert).
2.1 Initialisierung der Partikel
Für jede Gitterzelle werden acht Partikel erstellt, die randomly jittered in ihren Teilzellen verteilt werden – das
bedeutet das die Partikel in ihrer Teilzelle zufällig verteilt sind. Als Hilfe für die spätere
Oberflächenrekonstruktion (siehe Kapitel 4) legt man zusätzlich fest, dass Partikel in der Nähe der
Fluidoberfläche exakt eine halbe Zelle von der Oberfläche entfernt sein müssen.
2.2 Übertragung der Partikelwerte auf das Gitter und Aktualisierung der Werte
Anhand von trilinearer Interpolation werden die Partikelgeschwindigkeiten auf die zugehörigen Gitterpunkte
übertragen. Danach werden alle Gitterzellen markiert, welche zumindest ein Partikel beinhalten. Im
unmarkierten Bereich (Zellen welche kein Partikel enthalten) wird ein Abstandsfeld konstruiert, welches
genutzt wird um das Geschwindigkeitsfeld außerhalb des Fluids anhand einer partiellen Differentialgleichung
auszudehnen [7].
Desweiteren wird der Einfluss der Gravitation auf die Geschwindigkeitskomponenten zu den Gitterwerten
addiert und Randbedingungen sowie Inkompressibilität erzwungen (ähnlich wie in [3]). Abschließend wird das
aktualisierte Geschwindigkeitsfeld erneut ausgedehnt.
2.3 Übertragung der aktualiserten Werte auf die Partikel
Die auf dem Gitter aktualisierten Geschwindigkeitswerte werden nun wieder auf die Partikel übertragen. Je
nachdem ob man ein viskoses oder nicht-viskoses Fluid simulieren möchte nutzt man hierfür entweder eine
trilineare Interpolation der Geschwindigkeit (PIC) oder eine trilineare Interpolation der
Geschwindigkeitsänderung (FLIP).
Für viskose Strömungen (z.B. bei Sand) werden nur die aktualisierten Geschwindigkeiten, nach den
Berechnungen auf dem Gitter, für die Interpolation genutzt. Für nicht-viskose Strömungen (z.B. bei Wasser)
werden nach dem Übertragen der Partikelwerte auf die Gitterpunkte die Anfangsgeschwindigkeiten an den
Gitterpunkten gespeichert, die Berechnungen durchgeführt und schließlich die Geschwindigkeitsänderung
berechnet indem man die Anfangsgeschwindigkeit von der aktualisierten Geschwindigkeit subtrahiert. Die
Werte für die Geschwindigkeitsänderung werden dann interpoliert um die aktuellen Werte der Partikel zu
bestimmen.
Diese Unterscheidung bringt den Vorteil, dass bei nicht-viskosen Strömungen kleinste Geschwindigkeiten
erhalten bleiben, während man sich bei viskosen Strömungen die numerische Zähigkeit von PIC zu Nutze macht
um die kleinsten Geschwindigkeiten zu glätten [6] und somit ein zähflüssigeres Verhalten des Fluids erreicht.
2.4 Aktualisierung der Partikelpositionen
Anhand des berechneten Geschwindigkeitsfelds kann man nun die Partikel bewegen. [6] nutzen hierfür einen
simplen RK2 ODE solver, der die Partikel in fünf Zwischenschritten pro Zeitschritt bewegt. Jeder Zwischenschritt
ist dabei durch eine CFL-Bedingung beschränkt, die bewirkt, dass sich jedes Partikel pro Zwischenschritt nicht
mehr als eine Gitterzelle weit bewegen darf. Die Partikelgeschwindigkeiten werden auf dem Partikel mit
transportiert.
Desweiteren werden Partikel die feste Oberflächen durchdringen erkannt und entlang der Normalen der
Oberfläche wieder aus der Oberfläche bewegt um Artefakte (Partikel die in Wänden feststecken) zu vermeiden.
Durch genauere Berechnung des Drucks und bessere Randbedingungen können solche Artefakte vermieden
werden [7].
3. Animation von Sand als Fluid
Nun soll gezeigt werden wie man die vorgestellte Fluidsimulation erweitern kann um auch Sand als Fluid zu
animieren. Die Standardvorgehensweise um das Verhalten von Sand oder anderen köhasionslosen Materialen
zu beschreiben ist es, zunächst eine Definition für die Materialverformung zu bestimmen und danach eine
Elastizitätsbeziehung festzulegen und einen Finite Elemente solver zu nutzen um den Sand zu animieren.
Um sich aber die zusätzliche Komplexität der Finiten Elemente sparen zu können, werden für den Ansatz aus
[6] nach der Definition der Materialverformung vereinfachende Annahmen getroffen um den in Kapitel 2
vorgestellten Ansatz zur Fluidsimulation auch für die Sandanimation nutzen zu können.
3.1 Definition der Materialverformung
Zur Definition der Materialverformung wird das Mohr-Coulomb-Gesetz für statische Reibung genutzt:
√
Hierbei ist die Scherspannung, welche die Partikel aneinander gleiten lässt, der Reibungswert des
Materials und
der Druck der die Partikel aneinander drückt. Die Ungleichung besagt, dass die
Scherspannung solange durch den Druck ausgeglichen wird, so lange der Druck proportional stark genug ist.
Dies bedeutet also solang der Druck stark genug ist findet keine Materialverformung statt (der Sand darf nicht
fließen), wenn die Scherspannung aber zu gross wird so darf der Sand fließen und man wendet dafür eine
einfache Flussregel an: der Sand darf sich in Richtung der Scherspannung ausbreiten.
Da kleine numerische Fehler bei der Berechnung zu einem Gleiten im Sand, und somit zu einem instabilen
Verhalten des Sands im Ruhezustand, führen können, erweitert man die Ungleichung noch um einen
Kohäsionskoeffizienten c:
√
Dieser Koeffizient bewirkt, dass eine höhere Scherspannung benötigt wird bevor der Sand fließen darf. Dadurch
erhält man ein stabiles Verhalten des Sands im Ruhezustand, hat aber gleichzeitig keinen sichtbaren Effekt auf
das Verhalten des Sands wenn der Sand in Bewegung sein sollte erzeugt. Für kohäsionsfreie Materialien wie
Sand erzeugt dieses Vorgehen plausible, stabile Ergebnisse, für Materialien mit wirklicher Kohäsion ist das
Vorgehen hingegen zu stabil [7].
3.2 Vereinfachende Annahmen zur Modellierung des Sands
Als nächsten Schritt werden vereinfachende Annahmen für das Sandmodell getroffen. Eine erste Vereinfachung
ist, dass man die kaum sichtbare elastische Verformung des Sands im Ruhezustand sowie die minimalen
Volumenänderungen zu Beginn beziehungsweise Ende des Flusses nicht beachtet [6].
Desweiteren nimmt man auch an, dass der Druck um das gesamte Geschwindigkeitsfeld inkompressibel zu
machen ähnlich dem richtigen Druck im Sand ist, was sicherlich inkorrekt ist, aber bis auf wenige Fälle plausible
Resultate liefert [6]. Beispielsweise würde eine Sanduhr die mit dieser Annahme simuliert wird ein falsches
Verhalten zeigen, da durch die Annahme der Druck im Sand je höher ist desto höher der Sandhaufen ist, was
dazu führt das der Sand in der Sanduhr schneller fließt je mehr Sand im oberen Teil ist.
Mittels dieser Annahmen kann man den Bereich in dem sich der Sand befindet aufteilen in Zellen mit starrer
Bewegung und Zellen mit inkompressibler Scherströmung. Um diese Aufteilung durchzuführen wird eine
Fließflächenbedingung aufgestellt. Hierfür berechnet man den Formänderungsgeschwindigkeitstensor der
einzelnen Zellen und mit Hilfe dessen die Reibungsspannung für den Sand in Bewegung und den minimal
benötigten Druck für starre Zellen. Dann vergleicht man den minimal benötigten Druck mit der maximalen
Reibungsspannung und legt die Zellen je nach Ergebnis als starr oder fließend fest [7].
Als weitere Vereinfachung sucht man als nächstes Gruppen von starren Zellen (sogenannte starre Regionen)
und verfestigt deren Geschwindigkeiten. Zur Verfestigung der Geschwindigkeit wird das Geschwindigkeitsfeld
jeder einzelnen starren Region in den Raum einer entsprechenden Starrkörperbewegung projiziert.
Starrkörperbewegungen sind definiert durch die lineare Geschwindigkeit am Massenmittelpunkt und der
Winkelgeschwindigkeit des Starrkörpers, welche man anhand der gegebenen Geschwindigkeiten und eines
Drehimpulserhaltungssatzes einfach berechnen kann (siehe [7]). Durch die Verfestigung erhält man eine
einheitliche Geschwindigkeit für die jeweiligen starren Regionen.
3.3 Reibungsrandbegingungen
Somit hat man das Verhalten der Sandpartikel untereinander festgelegt. Um auch die Interaktion zwischen den
Sandpartikeln und anderen Objekten beschreiben zu können, legt man Reibungsrandbedingungen fest. Hierfür
wird die Reibungsformel von Bridson et al. [2] genutzt, was eine wichtige Erweiterung für die Fluidsimulation
ist, da die Randbedingungen in der Animationsliteratur bisher entweder keinerlei Gleiten (Sand klebt auch an
vertikalen Wänden) oder dauerhaftes Gleiten erlaubt haben [6] (siehe Abbildung 2).
Abbildung 2 [7]: Animation des Sandhasen ohne Reibungsformel.
Die Reibungsformel unterscheidet wie folgt zwischen statischer und kinetischer Reibung:
 Bei statischer Reibung (Sand im Ruhezustand): Die Geschwindigkeit in Tangentialrichtung wird Null
gesetzt. Dies bewirkt das der Sand, wenn er nicht in Bewegung ist, sich auch nicht zu bewegen beginnt
( keinerlei Gleiten).
 Bei kinetischer Reibung (Sand ist in Bewegung): Die Geschwindigkeit in Tangentialrichtung wird
proportional reduziert. Dies bewirkt das der Sand, wenn er in Bewegung ist, abgebremst wird und
schließlich gestoppt wird.
Abbildung 3 veranschaulicht die Verbesserung welche die Nutzung der Reibungsformel bringt: anstatt das sich
der Sand wie in Abbildung 2 bis zu den Rändern ausbreiten kann, werden die Sandpartikel nun abgebremst und
man erreicht damit ein plausibleres Verhalten des Sands.
Abbildung 3 [6]: Animation des Sandhasen mit Reibungsformel.
3.4 Erweiterter Algorithmus zur Animation des Sands als Fluid
Man kann den in Kapitel 2 vorgestellten Algorithmus zur Fluidsimulation nun wie folgt erweitern, um Sand als
Fluid zu animieren [6]:
Für jeden Zeitschritt:
 Ausführung der gewöhnlichen Schritte der Fluidsimulation (Advektion, Gravitation, Randbedingungen,
Druck, Inkompressibilität)
 Berechnung des Formänderungsgeschwindigkeitstensors (strain rate tensor) für alle Zellen anhand von
zentralen Differenzen
 Markierung der Zellen als starre Zelle oder Zelle mit inkompressibler Scherströmung
 Finden von starren Regionen und Verfestigung ihrer Geschwindigkeiten
 Aktualisierung verbleibender Geschwindigkeitswerte mit der Reibunsspannung
4. Oberflächenrekunstruktion anhand Abstandsfeld von Partikeln
Durch die vorgestellten Methoden hat man nun die Möglichkeit Fluide und auch Sand zu simulieren. Diese
Simulationen liefern die Positionen der Partikel welche das Fluid definieren. Um diese Informationen auch für
hochqualitatives Rendering nutzen zu können, wird eine Methode zur Umhüllung der Partikel benötigt um eine
Oberfläche definieren zu können.
Eine Möglichkeit dies zu erreichen ist, indem man versucht eine exakte Rekonstruktion des
vorzeichenbehafteten Abstandsfelds der Partikel zu generieren [6]. Hierfür geht man wie folgt vor (für jeden
Gitterpunkt):
 Finde naheliegende Partikel in festgelegtem Radius um den Gitterpunkt ( )
 Bilde gewichtetes Mittel der Positionen ( ̅ ) und Radien ̅) aller naheliegender Partikel (Gewichtung
findet anhand einer Kernelfunktion und dem Abstand des Gitterpunkts zu den jeweiligen
benachbarten Punkten im Verhältnis zum Radius statt.)
 Berechne Abstand
des Gitterpunkts zu naheligenden Partikeln, anhand folgender Formel:
|
̅|
̅
Das so konstruierte vorzeichenbehaftete Abstandsfeld kann dazu genutzt werden eine Oberfläche zu
bestimmen, indem man nach Paaren von benachbarten Gitterpunkten sucht die unterschiedliche Vorzeichen
für die Abstandswerte haben und somit zwischen diesen Punkten ein Punkt mit Abstand
sein muss.
Gängige Verfahren um eine solche Oberfläche (Isosurface) zu bestimmen sind der Marching Cubes Algorithmus
oder das Isosurface Ray Casting.
Das größte Problem bei dieser Vorgehensweise ist in konkaven Regionen zu finden. Hier kann es passieren das
der gemittelte Wert für die Position der benachbarten Partikel eines Gitterpunkts irrtümlich außerhalb der
eigentlichen Fluidoberfläche liegt, was zu störenden Artefakten auf der Oberfläche führt. Diesem Problem kann
man entgegenwirken in dem man das Abstandsfeld auf einem höher aufgelösten Gitter abtastet und dann
einen Glättungsdurchgang für die Oberfläche ausführt [6].
Ein weiteres Problem stellen die Radien dar, die für eine exakte Rekonstruktion des Abstandsfeldes genaue
Abschätzungen des Abstands der Partikel zur Fluidoberfläche sein müssten. Da passende Methoden fehlen die
solche Abschätzungen gleichzeitg schnell und präzise genug berechnen können, setzt man daher die Radien auf
einen festen Wert (den konstanten durchschnittlichen Partikelabstand) und legt einen Initialabstand der
Partikel nahe der Fluidoberfläche fest [7].
Der grosse Vorteil dieser Rekonstruktionsmethode sind die geringen Kosten pro Frame und die Unabhängigkeit
der Frames, welche es ermöglicht die Berechnungen einfach auf mehreren CPUs oder Maschinen parallel
durchzuführen [6].
5. Konklusion
Somit haben wir gesehen wie man eine Fluidsimulation effizient und durch die verschiedenen Ansätze für
(nicht-)viskose Strömungen auch flexibel durchführen kann. Desweiteren wurde gezeigt welche Erweiterungen
genutzt werden können um diese Fluidsimulation auch zur Animation von Sand einsetzen zu können und eine
Methode um anhand der Fluidpartikel ein Abstandsfeld zu schaffen, welches zur Oberflächenrekonstruktion
genutzt werden kann.
Quellen
[1] Brackbill, J. U., & Ruppel, H. M. (1986). FLIP: A method for adaptively zoned, particle-in-cell calculations of fluid flows in two dimensions.
Journal of Computational Physics, 65(2), 314-343.
[2] Bridson, R., Fedkiw, R., & Anderson, J. (2002, July). Robust treatment of collisions, contact and friction for cloth animation. In ACM
Transactions on Graphics (ToG) (Vol. 21, No. 3, pp. 594-603). ACM.
[3] Enright, D., Marschner, S., & Fedkiw, R. (2002). Animation and rendering of complex water surfaces. ACM Transactions on Graphics
(TOG), 21(3), 736-744.
[4] Harlow, F. H. (1962). The particle-in-cell method for numerical solution of problems in fluid dynamics (No. LADC-5288). Los Alamos
Scientific Lab., N. Mex..
[5] Milenkovic, V. J. (1996, August). Position-based physics: simulating the motion of many highly interacting spheres and polyhedra. In
Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (pp. 129-136). ACM.
[6] Zhu, Y., & Bridson, R. (2005, July). Animating sand as a fluid. In ACM Transactions on Graphics (TOG) (Vol. 24, No. 3, pp. 965-972). ACM.
[7] Zhu, Y. (2005). Animating Sand as a Fluid (Doctoral dissertation, The University of British Columbia).