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 Pc Science and Synthetic Intelligence Laboratory (CSAIL) des MIT befasst sich mit einer allgemeinen Klasse dieser potenziell nichtlinearen Probleme.
In einem kürzlich erschienener Artikel im 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 program-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 SM ’23, eine MIT-Doktorandin in Elektrotechnik und Informatik (EECS) und CSAIL-Mitarbeiterin. „Bei jedem Schritt dieses Ansatzes lösen Sie ein einfacheres Downside 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 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 in die Zukunft, indem er die Wärmegleichung (auch „Diffusionsgleichung“ genannt) löst, die modelliert, wie sich Wärme von einer Quelle über eine Kind 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 mit konvexen Optimierungsalgorithmen gelöst werden kann. Konvexe Optimierung ist ein Standardwerkzeug, für das Forscher in der Geometrieverarbeitung bereits über effiziente und zuverlässige Software program 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-Solver“, 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 Groups kann die Diffusionsgleichung auch im logarithmischen Bereich lösen, wo sie nichtlinear wird. Seniorautor Justin Solomon, außerordentlicher Professor der EECS und Leiter der CSAIL Geometric Information Processing Group, entwickelte zuvor eine hochmoderne Technik für optimalen Transport, bei der das Ergebnis der Wärmediffusion logarithmiert werden muss. Mattos Da Silvas Framework lieferte zuverlässigere Berechnungen, indem es die Diffusion direkt im logarithmischen Bereich durchführte. Dies ermöglichte eine stabilere Methode, um beispielsweise 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 Artwork.
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 Staff möchte jedoch auch Probleme mit gekoppelten parabolischen PDEs angehen. Diese Artwork 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 gemeinsam mit Oded Stein verfasst, einem Assistenzprofessor an der Viterbi Faculty of Engineering der College of Southern California. Ihre Arbeit wurde unter anderem durch ein von Google finanziertes MIT Schwarzman School of Computing Fellowship, ein MathWorks Fellowship, den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung, das US Military Analysis Workplace, das US Air Drive Workplace of Scientific Analysis, die US Nationwide Science Basis, das MIT-IBM Watson AI Lab, das Toyota-CSAIL Joint Analysis Middle, Adobe Techniques und Google Analysis unterstützt.