Rahmen für die Lösung parabolischer partieller Differentialgleichungen könnte als Leitfaden für Computergrafik und Geometrieverarbeitung dienen

Die Forschung im Bereich Computergrafik und Geometrieverarbeitung liefert die notwendigen Werkzeuge zur Simulation physikalischer Phänomene wie Feuer und Flammen und unterstützt die Erstellung visueller Effekte in Videospielen und Filmen sowie die Herstellung komplexer geometrischer Formen mit Werkzeugen wie dem 3D-Drucker.

Im Grunde werden diese natürlichen Prozesse durch mathematische Probleme modelliert, die als partielle Differentialgleichungen (PDEs) bezeichnet werden. Unter den vielen PDEs, die in der Physik und Computergrafik verwendet werden, erklärt eine Klasse namens parabolische PDEs zweiter Ordnung, wie Phänomene mit der Zeit glatt werden können. Das bekannteste Beispiel in dieser Klasse ist die Wärmeleitungsgleichung, die vorhersagt, wie sich Wärme im Laufe der Zeit entlang einer Oberfläche oder in einem Volumen ausbreitet.

Forscher im Bereich der Geometrieverarbeitung haben zahlreiche Algorithmen entwickelt, um diese Probleme auf gekrümmten Oberflächen zu lösen, aber ihre Methoden sind oft nur auf lineare Probleme oder auf eine einzelne PDE anwendbar. Ein allgemeinerer Ansatz von Forschern des Computer Science and Artificial Intelligence Laboratory (CSAIL) des MIT befasst sich mit einer allgemeinen Klasse dieser potenziell nichtlinearen Probleme.

In einem kürzlich erschienenen Artikel veröffentlicht im ACM-Transaktionen zu Grafiken Sie wurden in der Zeitschrift „The 4000“ veröffentlicht und auf der SIGGRAPH-Konferenz vorgestellt. Sie beschreiben einen Algorithmus, der verschiedene nichtlineare parabolische Differentialgleichungen auf Dreiecksnetzen löst, indem er sie in drei einfachere Gleichungen aufspaltet, die mit Techniken gelöst werden können, die Grafikforscher bereits in ihrem Software-Toolkit haben. Dieses Framework kann dabei helfen, Formen besser zu analysieren und komplexe dynamische Prozesse zu modellieren.

„Wir bieten ein Rezept: Wenn Sie eine parabolische PDE zweiter Ordnung numerisch lösen möchten, können Sie drei Schritte befolgen“, sagt die Hauptautorin Leticia Mattos Da Silva, eine MIT-Doktorandin in Elektrotechnik und Informatik (EECS) und CSAIL-Mitarbeiterin. „Bei jedem Schritt dieses Ansatzes lösen Sie ein einfacheres Problem mit einfacheren Werkzeugen aus der Geometrieverarbeitung, aber am Ende erhalten Sie eine Lösung für die anspruchsvollere parabolische PDE zweiter Ordnung.“

Um dies zu erreichen, verwendeten Mattos Da Silva und ihre Co-Autoren die Strang-Aufteilung, eine Technik, die es Forschern im Bereich der Geometrieverarbeitung ermöglicht, die PDE in Probleme zu zerlegen, von denen sie wissen, wie sie diese effizient lösen können.

Zunächst entwickelt ihr Algorithmus eine Lösung zeitlich weiter, indem er die Wärmegleichung (auch „Diffusionsgleichung“ genannt) löst, die modelliert, wie sich Wärme von einer Quelle über eine Form ausbreitet. Stellen Sie sich vor, Sie erwärmen eine Metallplatte mit einem Lötbrenner – diese Gleichung beschreibt, wie sich Wärme von dieser Stelle über sie ausbreiten würde. Dieser Schritt lässt sich mithilfe linearer Algebra leicht durchführen.

Stellen Sie sich nun vor, dass die parabolische PDE zusätzliche nichtlineare Verhaltensweisen aufweist, die nicht durch die Wärmeausbreitung beschrieben werden. Hier kommt der zweite Schritt des Algorithmus ins Spiel: Er berücksichtigt den nichtlinearen Teil, indem er eine Hamilton-Jacobi-Gleichung (HJ) löst, eine nichtlineare PDE erster Ordnung.

Während generische HJ-Gleichungen schwer zu lösen sein können, beweisen Mattos Da Silva und Co-Autoren, dass ihre auf viele wichtige PDEs angewandte Aufteilungsmethode eine HJ-Gleichung ergibt, die über konvexe Optimierungsalgorithmen gelöst werden kann. Konvexe Optimierung ist ein Standardwerkzeug, für das Forscher in der Geometrieverarbeitung bereits über effiziente und zuverlässige Software verfügen. Im letzten Schritt entwickelt der Algorithmus eine Lösung zeitlich weiter, indem er erneut die Wärmegleichung verwendet, um die komplexere parabolische PDE zweiter Ordnung zeitlich weiterzuentwickeln.

Unter anderem könnte das Framework dabei helfen, Feuer und Flammen effizienter zu simulieren. „Es gibt eine riesige Pipeline, die ein Video mit simulierten Flammen erstellt, aber das Herzstück davon ist ein PDE-Löser“, sagt Mattos Da Silva. Ein wesentlicher Schritt für diese Pipelines ist die Lösung der G-Gleichung, einer nichtlinearen parabolischen PDE, die die Frontausbreitung der Flamme modelliert und mit dem Framework der Forscher gelöst werden kann.

Der Algorithmus des Teams kann die Diffusionsgleichung auch im logarithmischen Bereich lösen, wo sie nichtlinear wird. Der leitende Autor Justin Solomon, außerordentlicher Professor der EECS und Leiter der CSAIL Geometric Data Processing Group, hatte zuvor eine hochmoderne Technik für optimalen Transport entwickelt, bei der der Logarithmus des Ergebnisses der Wärmediffusion erforderlich ist.

Das Framework von Mattos Da Silva ermöglichte zuverlässigere Berechnungen, indem es die Diffusion direkt im logarithmischen Bereich durchführte. Dies ermöglichte beispielsweise eine stabilere Methode, um einen geometrischen Mittelwert unter Verteilungen auf Oberflächennetzen wie einem Koalamodell zu finden.

Obwohl sich ihr Rahmen auf allgemeine, nichtlineare Probleme konzentriert, kann er auch zur Lösung linearer partieller Differentialgleichungen verwendet werden. Beispielsweise löst die Methode die Fokker-Planck-Gleichung, bei der sich Wärme linear ausbreitet, es aber zusätzliche Terme gibt, die in dieselbe Richtung driften, in die sich die Wärme ausbreitet. In einer einfachen Anwendung modellierte der Ansatz, wie sich Wirbel über die Oberfläche einer dreieckigen Kugel entwickeln würden. Das Ergebnis ähnelt lila-brauner Latte Art.

Die Forscher weisen darauf hin, dass dieses Projekt ein Ausgangspunkt ist, um die Nichtlinearität anderer PDEs, die in der Grafik- und Geometrieverarbeitung auftreten, direkt anzugehen. Sie konzentrierten sich beispielsweise auf statische Oberflächen, möchten ihre Arbeit jedoch auch auf bewegte anwenden. Darüber hinaus löst ihr Rahmen Probleme mit einer einzelnen parabolischen PDE, das Team möchte jedoch auch Probleme mit gekoppelten parabolischen PDEs angehen. Diese Art von Problemen tritt in der Biologie und Chemie auf, wo beispielsweise die Gleichung, die die Entwicklung jedes Wirkstoffs in einer Mischung beschreibt, mit den Gleichungen der anderen verknüpft ist.

Mattos Da Silva und Solomon haben die Arbeit zusammen mit Oded Stein, Assistenzprofessor an der Viterbi School of Engineering der University of Southern California, verfasst.

Diese Geschichte wird mit freundlicher Genehmigung von MIT News erneut veröffentlicht (web.mit.edu/newsoffice/), eine beliebte Site mit Neuigkeiten zu Forschung, Innovation und Lehre am MIT.