Research in computer graphics and geometric processing provides the tools needed to simulate physical phenomena such as fire and flames, facilitating the creation of visual effects in video games and films as well as the fabrication of complex geometric shapes using tools such as 3D printing.
Under the hood, mathematical problems called partial differential equations (PDEs) model these natural processes. Among the many PDEs used in physics and computer graphics, a class called second-order parabolic PDEs explains how phenomena can become smooth over time. The most famous example of this class is the heat equation, which predicts how heat diffuses along a surface or in a volume over time.
Geometry researchers have designed many algorithms to solve these problems on curved surfaces, but their methods often apply only to linear problems or to a single PDE. A more general approach from researchers at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) tackles a general class of these potentially nonlinear problems.
In a recently published article in the ACM Transactions on Charts In a paper published in the journal and presented at the SIGGRAPH conference, they describe an algorithm that solves different nonlinear parabolic PDEs on triangular meshes by breaking them into three simpler equations that can be solved with techniques that graphics researchers already have in their software toolbox. This framework can help better analyze shapes and model complex dynamic processes.
“We propose a recipe: If you want to solve a second-order parabolic PDE numerically, you can follow a series of three steps,” says lead author Leticia Mattos Da Silva, a doctoral student in electrical and computer engineering at MIT (EECS) and affiliated with CSAIL. “For each of the steps in this approach, you solve a simpler problem using simpler geometric processing tools, but at the end you get a solution to the more complex second-order parabolic PDE.”
To achieve this, Mattos Da Silva and his co-authors used Strang division, a technique that allows geometric processing researchers to decompose the PDE into problems that they know how to solve efficiently.
First, their algorithm advances a solution forward in time by solving the heat equation (also called the “diffusion equation”), which models how heat from a source spreads across a shape. Imagine using a blowtorch to heat a metal plate: this equation describes how heat from that location would spread across it. This step can be done easily using linear algebra.
Now let us imagine that the parabolic PDE exhibits additional nonlinear behaviors that are not described by the heat propagation. This is where the second step of the algorithm comes in: it takes into account the nonlinear part by solving a Hamilton-Jacobi (HJ) equation, a first-order nonlinear PDE.
Although generic HJ equations can be difficult to solve, Mattos Da Silva and co-authors prove that their division method applied to many large PDEs produces an HJ equation that can be solved via convex optimization algorithms. Convex optimization is a standard tool for which geometry researchers already have efficient and reliable software. In the final step, the algorithm advances a solution in time by using the heat equation again to advance the more complex second-order parabolic PDE in time.
Among other possible applications, the framework could help simulate fire and flames more efficiently. “There’s a huge pipeline that creates a video with simulated flames, but at the heart of it is a partial differential equation solver,” says Mattos Da Silva. A key step for these pipelines is solving the G equation, a nonlinear parabolic partial differential equation that models the frontal propagation of flame and can be solved using the researchers’ framework.
The team’s algorithm can also solve the diffusion equation in the logarithmic domain, where it becomes nonlinear. Lead author Justin Solomon, an EECS associate professor and head of CSAIL’s Geometric Data Processing Group, had previously developed a state-of-the-art technique for optimal transport that requires taking the logarithm of the heat diffusion result.
Mattos Da Silva’s framework allowed for more reliable calculations by performing the diffusion directly in the logarithmic domain. This allowed for a more stable method, for example, to find a geometric notion of mean among distributions on surface meshes such as a koala model.
Although their framework focuses on general, nonlinear problems, it can also be used to solve linear PDEs. For example, the method solves the Fokker-Planck equation, where heat diffuses linearly, but there are additional terms that drift in the same direction as the heat propagates. In a simple application, the approach modeled how vortices would evolve on the surface of a triangular sphere. The result looks like purple and brown latte art.
The researchers point out that this project is a starting point for tackling head-on nonlinearity in other PDEs that arise in graphics and geometry processing. For example, they have focused on static surfaces, but would also like to apply their work to moving surfaces. Furthermore, their framework solves problems involving a single parabolic PDE, but the team would also like to tackle problems involving coupled parabolic PDEs. These types of problems arise in biology and chemistry, where the equation describing the evolution of each agent in a mixture, for example, is related to the equations of the others.
Mattos Da Silva and Solomon wrote the paper with Oded Stein, an assistant professor at the University of Southern California’s Viterbi School of Engineering.
More information:
Leticia Mattos Da Silva et al, A framework for solving parabolic partial differential equations on discrete domains, ACM Transactions on Charts (2024). DOI: 10.1145/3666087
Provided by the Massachusetts Institute of Technology
This article is republished with kind permission from MIT News (web.mit.edu/newsoffice/), a popular site covering the latest research, innovation, and teaching at MIT.
Quote:A framework for solving parabolic partial differential equations could guide computational processing of computer graphics and geometry (2024, August 28) retrieved August 29, 2024 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without written permission. The content is provided for informational purposes only.