2 Punkte von GN⁺ 2023-12-20 | 1 Kommentare | Auf WhatsApp teilen
  • GPU-basierte Echtzeit-Feuersimulation lässt sich als WebGL-Demo umsetzen, indem Fluiddynamik, gitterbasierte Parallelberechnung sowie Verbrennungs-, Auftriebs- und Rendering-Modelle kombiniert werden
  • Das Grundmodell nimmt eine inkompressible und nichtviskose Strömung an und erreicht Stabilität und Parallelisierbarkeit durch semi-lagrangesche Advektion, die Skalarfelder wie Farbstoff, Temperatur und Brennstoff mit dem Geschwindigkeitsfeld transportiert
  • In den Navier-Stokes-Schritten wird das Geschwindigkeitsfeld zunächst mit sich selbst advehiert, danach wird die Divergenz per Druckprojektion reduziert; die Poisson-Gleichung wird mit GPU-freundlichen Näherungsverfahren wie Jacobi-Iteration behandelt
  • Gitterinterpolation und semi-lagrangesche Verfahren erster Ordnung schwächen turbulente Wirbel ab, daher ergänzen vorticity confinement und curl noise kleine Rotationsdetails
  • Feuer ergänzt Brennstoffdichte und Temperaturfeld, berechnet Verbrennung, Abkühlung und thermischen Auftrieb und rendert mit Schwarzkörperstrahlungsfarben nach Planck’s Law, sodass ein rauchartiges Fluid wie Flammen wirkt

Gesamtablauf einer Feuersimulation auf der GPU

  • Feuer ist in der Grafik ein interessantes Problem, wurde früher aber meist mit nicht physikbasierten Methoden imitiert
    • Lord of the Rings verwendete wegen der hohen Kosten von Fluidsimulationen viele Rauch-Sprites
    • Auch Echtzeitanwendungen wie Videospiele stützten sich fast vollständig auf nichtphysikalische Ansätze
  • In den letzten zehn Jahren haben GPUs schnelle Fluidsimulationen deutlich einfacher gemacht, und grundlegende Fluiddynamik-Algorithmen lassen sich auf der GPU intuitiv implementieren
    • ILM nutzte solche Techniken 2009 für die Modellierung und das Rendering von Feuer in Harry Potter
    • NVIDIA stellte 2014 FlameWorks vor, ein Effektsystem für Feuer und Rauch in Spielen
  • Die Implementierung ist als WebGL-Demo aufgebaut; mathematisch sind Kenntnisse in Vektoranalysis und Differentialgleichungen erforderlich
  • Der Quellcode liegt auf GitHub

Zuerst wird das Fluid modelliert

  • Bevor Feuer erzeugt werden kann, muss ein Fluid simuliert werden; hier wird ein inkompressibles (incompressible) und nichtviskoses (inviscid) Fluid angenommen
  • Ein 2D-Geschwindigkeitsfeld u(x, t) wird als N × N-Gitter dargestellt, wobei jeder Gitterpunkt den Geschwindigkeitswert an dieser Position enthält
  • Der Prozess, bei dem ein Skalarfeld ψ(x, t) wie etwa Farbstoffdichte entsprechend der Fluidgeschwindigkeit bewegt wird, heißt Advektion (advection)
  • Ein Ansatz, bei dem jeder Gitterpunkt einfach nach vorn verschoben wird, ist schwer zu parallelisieren; mehrere Gitterpunkte können auf denselben Zielgitterpunkt wandern, und bei größeren Zeitschritten kann das Verfahren instabil werden

Stabile Advektion: semi-lagrangesches Verfahren

  • Mit dem Massenerhaltungssatz und dem Divergenzsatz lässt sich die Gleichung für die Skalaradvektion in einer inkompressiblen Strömung zu ∂ψ/∂t = -u · ∇ψ zusammenfassen
  • Ein stabiles Verfahren besteht darin, von jedem aktuellen Gitterpunkt aus nicht entlang der Geschwindigkeit nach vorn zu gehen, sondern die Bewegungsrichtung rückwärts zu verfolgen und den Wert an der vorherigen Position zu übernehmen
  • Dieses Verfahren ist Semi-Lagrangian advection und wurde 1999 von Jos Stam entwickelt
    • Jeder Gitterpunkt wird pro Iteration nur einmal aktualisiert, was die Parallelisierung auf der GPU einfach macht
    • Kein Gitterpunkt wird auf einen Wert aktualisiert, der größer ist als das Maximum der bestehenden Gitterpunkte, daher ist das Verfahren bedingungslos stabil
  • Wenn ein festes Geschwindigkeitsfeld die Inkompressibilitätsbedingung erfüllt, lassen sich Skalarfelder wie Farbstoff stabil transportieren

Aktualisierung des Geschwindigkeitsfelds mit Navier-Stokes

  • Die Navier-Stokes equations definieren, wie sich das Geschwindigkeitsfeld eines Fluids in einer inkompressiblen Strömung über die Zeit verändert
  • Unter der Annahme eines nichtviskosen Fluids wird der Viskositätsterm entfernt; ignoriert man zunächst auch äußere Kräfte, bleiben zwei zentrale Terme übrig
    • self-advection, bei der das Geschwindigkeitsfeld sich selbst transportiert
    • pressure, um die Inkompressibilitätsbedingung zu erfüllen
  • Die Simulationsschleife läuft grob in folgender Reihenfolge ab
    • Das Geschwindigkeitsfeld u wird mit sich selbst advehiert
    • Der Druck p wird berechnet
    • Durch u = u - gradient(p) wird der Druckgradient abgezogen, um Inkompressibilität zu erzwingen
    • Mit dem neuen Geschwindigkeitsfeld wird das Dichtefeld advehiert

Die Druckberechnung ist wegen der Poisson-Gleichung der Engpass

  • Es ist nicht garantiert, dass das nach der Selbstadvektion erhaltene Kandidaten-Geschwindigkeitsfeld u' die Bedingung Divergenz 0 erfüllt, daher muss es über den Druck korrigiert werden
  • Umgeformt ergibt die Bedingung eine Poisson equation der Form ∇²p = ∇ · u'
  • Diskretisiert man Divergenz und Laplace-Operator auf dem Gitter, entsteht für ein N × N-Gitter ein lineares System mit linearen Gleichungen und Unbekannten
  • Exakte Verfahren zum Lösen linearer Systeme werden mit der Gittergröße überlinear teurer und sind daher für Echtzeitsimulationen belastend
  • Auf der GPU kann statt einer exakten Lösung iterativ eine hinreichend gute Näherung berechnet werden
    • Die Jacobi method aktualisiert die Schätzung jedes Elements parallel und passt daher gut zu einer GPU-Implementierung
    • Auch schneller konvergierende Verfahren wie Conjugate Gradient und Multigrid lassen sich auf der GPU implementieren
    • Bei Rauch und Feuer sind Volumenänderungen nicht so deutlich sichtbar wie bei Wasser, daher können Advektionsqualität oder einfache Implementierung wichtiger sein als Druckgenauigkeit

Wirbeldetails werden wiederbelebt

  • Wird das Geschwindigkeitsfeld auf einem Gitter gespeichert, kommt es bei der Interpolation zu unerwünschter numerischer Glättung
  • Zusammen mit der groben Näherung semi-lagrangescher Advektion erster Ordnung verschwinden turbulente Wirbel, und das Fluid wirkt zu glatt und monoton
  • Eine höhere Auflösung kann das abmildern, doch bei Echtzeitsimulationen sind die Rechenressourcen begrenzt
  • Vorticity confinement sucht in jedem Schritt nach verschwindenden kleinen Details und verstärkt sie
    • Das Verfahren ist nicht vollständig realistisch, bewahrt Details kleiner Skalen aber meist an physikalisch plausiblen Positionen
    • Ursprünglich wurde es entwickelt, um komplexe Strömungsfelder um Hubschrauberblätter in technischen Simulationen zu behandeln
  • An jedem Gitterpunkt wird die vorticity über den Curl gemessen; anschließend wird die Richtung berechnet, in der die vorticity in der Umgebung höher ist, und dem Geschwindigkeitsfeld wird eine durch die confinement-Konstante ε > 0 gesteuerte Rotationskraft hinzugefügt
    • Schon niedrige confinement-Werte von etwa 0–15 können einen großen Unterschied machen
    • Höhere Werte können stilisierte, aufquellende Strömungen erzeugen

Synthese von Turbulenz mit Curl Noise

  • Curl noise misst und verstärkt nicht die vorticity des vorhandenen Geschwindigkeitsfelds, sondern erzeugt mit einer Rauschfunktion ein neues skalares vorticity-Feld
  • Mathematisch wird ein zufälliges vorticity-Feld φ = rand * z synthetisiert und anschließend zur vorhandenen vorticity ω addiert, sodass die finale vorticity ω* = ω + φ entsteht
  • Schnell bewegte, stark turbulente Fluide wie Rauch und Feuer werden stark von vorticity confinement und curl noise beeinflusst
  • Das tatsächliche curl-noise-Feld φ verändert sich über die Zeit und wird gemeinsam mit der Fluidströmung advehiert

Für Feuer werden Brennstoff und Temperatur hinzugefügt

  • Mit der grundlegenden Fluidroutine allein lassen sich rauchartige Strömungen erzeugen; für die Simulation von Feuer und Rauch sind einige zusätzliche Kanäle nötig
  • Das Verbrennungsmodell ergänzt Brennstoffdichte ρ und ein Temperaturfeld T
    • 0 ≤ ρ ≤ 1 ist die Brennstoffdichte
    • T > 0 ist die Temperatur an jeder Position
  • Hier wird angenommen, dass der Brennstoff im System bereits entzündet ist und kontinuierlich Wärme hinzufügt; das Problem nicht entzündeten Brennstoffs wird nicht behandelt
  • In jedem Zeitschritt erhöht der Brennstoff die Temperatur entsprechend der festgelegten Verbrennungstemperatur
    • Die Temperatur wird in der Form T' = max(T, ρ * T_burn) aktualisiert
  • Wärme diffundiert von heißen zu kalten Bereichen, und auch die großräumige Fluidströmung transportiert Wärme
    • In der Simulation wird das Temperaturfeld mit dem Geschwindigkeitsfeld advehiert
    • Da die reagierenden Moleküle ebenfalls mit dem Fluid wandern, wird auch das Brennstofffeld advehiert
  • Heiße Moleküle geben gemäß dem Stefan-Boltzmann Law ihre Temperatur als Licht ab
    • Eine physikalisch exakte Simulation würde die Stefan-Boltzmann-Konstante verwenden
    • In einer Grafiksimulation ist es nützlich, wenn Artists die Abkühlrate σ_cool steuern können
  • Der Brennstoff nimmt in jedem Zeitschritt entsprechend der Verbrennungsrate γ_fuel ab

Thermischer Auftrieb lässt heißes Fluid nach oben steigen

  • Wird nur das Temperaturfeld berechnet, hat es noch keinen Einfluss auf die Fluidströmung; daher muss der Effekt ergänzt werden, dass heiße Luft aufsteigt und kalte Luft absinkt
  • Thermal buoyancy fügt dem Geschwindigkeitsfeld eine nach oben gerichtete Kraft hinzu, die proportional zur Temperatur ist
    • Da eine inkompressible Strömung angenommen wird, wird die tatsächliche Ausdehnung der Luft nicht behandelt
    • Das Geschwindigkeitsfeld wird in der Form u' = u + (β T Δt) j aktualisiert
    • β ist eine positive Auftriebskonstante und j der nach oben gerichtete Einheitsvektor
  • Durch Verbrennungsmodell und thermischen Auftrieb entsteht ein Fluid, das wie Feuer aussieht
    • Mit passenden Werten für Auftrieb und Abkühlung lassen sich große, anschwellende Materialsäulen erzeugen
    • Das Ergebnis dieser Phase ähnelt eher Rauch als exakten Flammen
  • Die gesamte Schleife besteht aus Selbstadvektion der Geschwindigkeit, Verbrennung, vorticity confinement, thermischem Auftrieb, Druckprojektion sowie Advektion von Dichte, Temperatur und Brennstoff

Flammenfarben mit Schwarzkörperstrahlung rendern

  • Feuer ist ein participating medium und emittiert Licht durch Schwarzkörperstrahlung
  • Die orangefarbenen und roten Farbtöne von Feuer entstehen durch Schwarzkörperstrahlung; rendert man die Simulation brennenden Brennstoffs mit der richtigen Formel, kann der Übergang von Rauch zu Feuer erreicht werden
  • Planck’s Law beschreibt die spektrale Dichte des Lichts, das ein Schwarzkörper bei einer bestimmten Temperatur T emittiert
  • Implementiert man das Schwarzkörper-Rendering in einem Fragment Shader, entsteht auf Basis von Fluid-, Verbrennungs- und Auftriebsmodell eine vollständige Feuersimulation
  • Es bleiben weitere Erweiterungsthemen, die hier nicht behandelt wurden
    • Nicht gitterbasierte Verfahren zum Lösen von Simulationen in einem festen Volumen
    • Probleme mit variabler Domäne, bei denen Fluide unterschiedliche Bereiche im Gitter einnehmen, etwa Wasser in einer halb gefüllten Tasse
    • Dynamische Hindernisse
    • Rendering-Verbesserungen wie genauere Schwarzkörperstrahlung, Lichtstreuung und Postprocessing-Effekte

1 Kommentare

 
GN⁺ 2023-12-20
Hacker-News-Kommentare
  • Ich habe in CFD promoviert, aber Vorticity Confinement und Curl-Noise-Turbulenz waren mir neu.
    In Bereichen mit höheren Reynolds-Zahlen wie in industrieller CFD will man einen Ansatz, der die künstliche Dissipation numerischer Verfahren mit Rauschen ausgleicht, normalerweise nicht.
    Im Gegenteil: Um Simulationen mit hoher Reynolds-Zahl zu stabilisieren, will man oft gerade künstliche Dissipation, und in der Computergrafik scheint plausibel aussehend wichtiger zu sein als physikalisch korrekt.

  • Ich habe vor einiger Zeit irgendwo einen Artikel gelesen und dann in C eine extrem einfache Flammen-Simulation auf Spielzeugniveau gebaut.
    Man setzt die Helligkeit jedes Pixels einfach auf die durchschnittliche Helligkeit der direkt benachbarten Pixel und berechnet von unten nach oben.
    Wenn man unten nur ein paar seitlich wandernde „heiße“ Pixel hinzufügt, entstehen sofort Flammen — mit sehr wenig Code, ohne Differential- und Integralrechnung, und es sieht ziemlich gut aus.

    • Das ist der Laplace-Operator.
      In einer Dimension ist das einfach die zweite Ableitung, also die Krümmung: Je schärfer ein Gipfel, desto negativer, je schärfer ein Tal, desto positiver.
      Wenn man Werte entsprechend anpasst, ergibt das einen glättenden Effekt, und in diskretisierter Form ist es buchstäblich Mittelwertbildung.
      Eigentlich hast du die ganze Zeit Differentialrechnung betrieben.
      Den Weg zu kennen und ihn zu gehen sind zwei verschiedene Dinge.
      Dazu gibt es auch ein 3Blue1Brown-Video mit anschaulicher grafischer Erklärung: https://youtube.com/watch?v=ToIXSwZ1pJU
    • „Die Helligkeit jedes Pixels auf die durchschnittliche Helligkeit der direkt benachbarten Pixel setzen“ klingt nach Faltung.
  • Es geht hier um Feuer- und Rauchsimulation für Spiele und um Fluidsimulation auf der GPU, aber wenn solche Effekte im Spiel laufen, fragt man sich doch, ob die GPU nicht ohnehin schon ausgelastet ist.
    Ein CFD-Problem zu rechnen und gleichzeitig zu rendern wirkt wie eine ziemlich große Last.
    Ich frage mich auch, ob man so etwas auf der iGPU laufen lassen kann, während die dGPU das Rendering übernimmt, oder ob die iGPU dafür zu schwach ist und man besser gleich auf die CPU zurückfällt.

    • Die kurze Antwort ist: Die GPU ist nicht „schon ausgelastet“.
      Moderne GPUs sind extrem leistungsfähig und können Physik, aufwendige Render-Passes, Fluidsimulation und „Game-AI“-Dinge wie Unit-Pathfinding mit über 100 FPS verarbeiten.
      Etwas ausführlicher: Die Zeit zwischen den Frames einer sehr schnellen „Diashow“ mit 60+ FPS ist das Frame-Budget, und normalerweise müssen innerhalb von 5 bis 30 ms alle Berechnungen für den Zustand des nächsten Frames und dessen Rendering erledigt werden.
      Dazu können Bewegungen von Einheiten auf der Karte, Flammenphysik, das Kopieren von Terrain-Texturen und das Rendern von Vertices mit Materialien gehören, und in vielen Game-Engines führt die GPU pro Frame dutzende solcher separaten Berechnungen aus.
      Eine GPU ist im Grunde ein Nebencomputer, der am Hauptrechner hängt: Man wirft ihr pro Frame mehrere Jobs zu, sie liefert Ergebnisse zurück, und diese werden so zusammengesetzt, dass es wie ein Spiel aussieht.
      iGPUs nutzt so gut wie niemand.
      Im Vergleich zur primären dGPU sind sie meist völlig nutzlos und werden ignoriert.
    • Jetzt laufen auch LLMs auf GPUs, also werden künftige GPUs ihre Ressourcen zwischen Grafik, Physik und KI für NPCs aufteilen müssen.
      Die Zeit, in der man das austarieren muss, dürfte spannend werden, und wahrscheinlich werden sich lokale und entfernte Rechenressourcen die Last zunehmend teilen.
    • Früher ließ man PhysX-Berechnungen manchmal auf einer eigens dafür ausgewählten GPU laufen.
      Ich erinnere mich, dass ich diese Einstellung bei Red Faction entweder bewusst zugewiesen oder überhaupt erst bemerkt habe, während ich mir ständig weiter einstürzende Wände ansah.
      Fast wie Minecraft, nur auf dem Mars mit einem Raketenwerfer in der Hand.
  • Man muss nicht unbedingt ein Spiel spielen, um die GPU zu nutzen
    Heutzutage gibt es auch viele Rendering-Programme mit GPU-Modus
    Allerdings sind GPU-Algorithmen hochgradig parallelisiert und unterscheiden sich daher oft von CPU-Simulationsalgorithmen

  • EmberGen ist eine völlig verrückte Software, die Feuer und Rauch in Echtzeit auf Consumer-GPUs simuliert und außerdem einen node-basierten Workflow unterstützt, sodass sich neue Effekte leicht erstellen lassen
    Workflows, die früher Stunden gedauert haben, lassen sich jetzt in wenigen Minuten einrichten
    https://jangafx.com/software/embergen/
    Ich dachte, in diesem Artikel würde es um EmberGen gehen, und ehrlich gesagt finde ich es etwas schade, dass EmberGen auf HN nicht mehr Aufmerksamkeit bekommen hat: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
    Ich habe keine Verbindung zu EmberGen/JangaFX, sondern bin einfach nur ein zufriedener Kunde

  • Wenn man so etwas mag, ist auch Ten Minute Physics interessant
    Besonders Kapitel 17, „How to write an Eulerian Fluid Simulator with 200 lines of code“, ist gut
    https://matthias-research.github.io/pages/tenMinutePhysics/i...

  • Ich frage mich, welche Einstiegsmaterialien ihr jemandem empfehlen würdet, der von einem Mathematikstudium in die Softwareentwicklung gewechselt ist und jetzt in CFD-Simulation einsteigen möchte
    Das Thema ist wirklich faszinierend, aber mein Wissen in Vektoranalysis und partiellen Differentialgleichungen ist ziemlich eingerostet

    • Wenn dein Interesse eher bei physikalischer Simulation für die Forschung liegt, kann ich dir kaum helfen, aber für simulationsorientierte Unterhaltung ist SideFX Houdini nur schwer zu schlagen
      https://www.youtube.com/watch?v=zxiqA8_CiC4
      Die kostenlose nichtkommerzielle „Apprentice“-Version ist nur beim Rendering und bei Kollaborationsfunktionen eingeschränkt
      Allerdings ist es ein ziemlich tiefgehendes Werkzeug
      Wenn man aus der Softwarewelt in diese Branche wechselt, ist der Lern-Workflow für solche Tools völlig anders
      Viele sagen, Houdini sei eher mit einer IDE als mit einem 3D-Modellierungsprogramm vergleichbar, und dem stimme ich in vielerlei Hinsicht zu
      Statt visuelle Werkzeuge wie Blender zu benutzen, baut man fast ausschließlich Node-Netzwerke und verändert Attribute und Parameter
      Das meiste lässt sich in Python erledigen und ist sauberer als bei 3ds Max, aber da es nicht kompiliert wird, ist die Performance bei großen Simulationen schlecht
      Auch die hauseigene C-ähnliche Sprache VEX ist brauchbar, und es gibt zusätzlich ein feiner abgestuftes Node-System für detailliertere Arbeiten wie komplexere Mathematik
      Technisch ist das fast vollständig ein datenorientierter Workflow
      Wenn du allerdings der Typ bist, der „durch Lesen der Dokumentation lernt“, musst du Tutorials sehr schnell lieben lernen
      Es ist völlig anders als jede Umgebung oder jedes Paradigma, mit dem ich bisher gearbeitet habe, und die Community ist im Allgemeinen freundlich, leidet aber ziemlich stark unter dem Fluch des Wissens
    • Man könnte sich auch einfach bei etwas wie StarCCM bewerben und in dem Bereich arbeiten
    • Ich habe das früher als NASA-Auftragnehmer gemacht
      Wenn du es wirklich willst, ist es sinnvoll, einen Job in dem Feld zu bekommen, und auf Bundes- oder Auftragnehmerseite wären Marshall Space Flight Center oder Ames einen Blick wert
      Ames verfügt laut Top500 über die Systeme Aitken [#85, 9.07 PFlops], Pleiades [#132, 5.95 PFlops] und Electra [#143, 5.44 PFlops]
      Auch GRC, LARC und JSC haben einiges
      Zumindest noch vor ein paar Jahren war die Integration von Auftragnehmern und Bundesangestellten ziemlich gut und abgesehen von der Mittelzuweisung fast transparent
      Innerhalb der NASA sind bei MSFC die Gruppen Propulsion Structural, Thermal & Fluid Analysis [2][3] und bei Ames die Entry Systems Group [4] recht bekannt
      Damals haben wir mit Overflow/LARC [5] oder Loci/Mississippi State University [6] Hybrid-RANS/LES-Simulationen im Maßstab von rund 100 Millionen Zellen für Fahrzeuge oder Fahrzeug-plus-Startturm durchgeführt, einschließlich bewegter überlappender Gitter, reaktiver Verbrennungschemie mit etwa 10 bis 20 Spezies und Lagrangescher Dynamik verdampfender Partikel
      Dabei wurden SSME und SRB gemeinsam gezündet, und auch das Wasserdämpfungssystem beim Start war enthalten
      Diese Informationen sind allerdings zehn Jahre alt, daher weiß ich nicht, was heute Stand der Technik ist; inzwischen dürfte man weiter sein
      Wenn du wissen willst, woran die Branche interessiert ist, ist die alte CFD Vision 2030 Study von 2014 als Einstieg trotzdem nicht schlecht [7]
      Es lohnt sich auch, ein Ticket für die Supercomputing-Konferenz zu besorgen und dort herumzulaufen
      Dieses Jahr fand sie in Denver statt [8]
      Der Fokus liegt allerdings eher auf den „großen“ Themen, sodass du vor allem riesige Wettersimulationen oder Nebeldynamik sehen wirst
      Ich mag die Konferenz selbst, aber ohne Skalierungserfolge in der Größenordnung #CPUs/#GPUs/#FPGAs++ bekommt man nur schwer Aufmerksamkeit
      Außerhalb der NASA auf Regierungsseite gibt es NIST (Gaithersburg), DOE (Oak Ridge, Sandia, Los Alamos), die Air Force (AF Research Lab) und Huntington Beach
      [1] NASA Advanced Supercomputing Division: https://en.wikipedia.org/wiki/NASA_Advanced_Supercomputing_D...
      [2] NASA, MSFC: https://www.nasa.gov/wp-content/uploads/2016/01/g-28367g_pst...

[3] Etwas ältere Beispiele: https://ntrs.nasa.gov/api/citations/20140016892/downloads/20...
[4] NASA Ames: https://www.nasa.gov/entry-systems-and-technology-division/
[5] OVERFLOW/NASA/LARC: https://overflow.larc.nasa.gov/
[6] Loci/MSU: https://simcenter.msstate.edu/
[7] CFD Vision 2030 Study: https://ntrs.nasa.gov/api/citations/20140003093/downloads/20...
[8] Supercomputing SC23: https://sc23.supercomputing.org/