Research in computer graphics and geometry processing provides the tools needed to simulate physical phenomena such as fire and flames, facilitating the creation of visual effects in video games and movies, as well as the manufacturing of complex geometric shapes using tools such as 3D printing.
In the background, 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 across a surface or in a volume over time.
Researchers in the field of geometric processing have designed numerous algorithms to solve these problems on curved surfaces, but their methods typically apply only to linear problems or to a single partial differential equation. A more general approach developed by researchers at MIT's Computer Science and artificial intelligence Laboratory (CSAIL) addresses a general class of these potentially nonlinear problems.
In a Article recently published in the Chart Transactions In a paper published in the journal and presented at the SIGGRAPH conference, they describe an algorithm that solves different nonlinear parabolic partial differential equations on triangle meshes by breaking them down into three simpler equations that can be solved with techniques that graphics researchers already have in their software toolkit. This framework can help better analyze shapes and model complex dynamic processes.
“We offer a recipe: If you want to solve a second-order parabolic partial differential equation numerically, you can follow a set of three steps,” says lead author Leticia Mattos Da Silva SM ’23, an MIT PhD student in electrical engineering and computer science (EECS) and affiliated with CSAIL. “At each step of this approach, you’re solving a simpler problem using simpler geometry processing tools, but in the end, you get a solution to the more challenging second-order parabolic partial differential equation.”
To accomplish this, Da Silva and his co-authors used Strang partitioning, a technique that allows geometric processing researchers to break down the PDE into problems they know how to solve efficiently.
First, their algorithm advances a solution in time by solving the heat equation (also called the “diffusion equation”), which models how heat from a source spreads over a shape. Imagine using a blowtorch to heat a metal plate: this equation describes how heat from that point would spread over it. This step can easily be completed with linear algebra.
Now, let us imagine that the parabolic partial differential equation has additional nonlinear behaviors that are not described by heat propagation. This is where the second step of the algorithm comes into play: it takes into account the nonlinear part by solving a Hamilton-Jacobi (HJ) equation, a first-order nonlinear partial differential equation.
While generic HJ equations can be difficult to solve, Mattos Da Silva and coauthors demonstrate that their splitting method applied to many important PDEs yields an HJ equation that can be solved by convex optimization algorithms. Convex optimization is a standard tool for which geometry processing researchers already have efficient and reliable software. In the final step, the algorithm advances a solution forward in time by again using the heat equation to advance the more complex second-order parabolic PDEs forward in time.
Among other applications, the framework could help simulate fires and flames more efficiently. “There is a huge process that creates a video with simulated flames, but at the heart of all this is a partial differential equation solver,” says Mattos Da Silva. For these processes, an essential step is solving the G equation, a nonlinear parabolic partial differential equation that models the frontal spread of the 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. Senior author Justin Solomon, an EECS associate professor and leader of CSAIL’s Geometric Data Processing Group, previously developed a cutting-edge technique for optimal transport that requires taking the logarithm of the heat diffusion result. Mattos Da Silva’s framework provided more reliable calculations by performing diffusion directly in the logarithmic domain. This allowed for a more stable way to, for example, find a geometric notion of averaging across distributions on surface meshes such as a model of a koala.
Although its framework focuses on general nonlinear problems, it can also be used to solve linear partial differential equations. For example, the method solves the Fokker-Planck equation, in which heat diffuses linearly, but there are additional terms that travel in the same direction as the heat is propagating. In a simple application, the approach modeled how eddies would develop on the surface of a triangulated sphere. The result resembles purple and brown latte art.
The researchers note that this project is a starting point for directly addressing nonlinearity in other partial differential equations that appear in graphics processing and geometry. For example, they focused on static surfaces, but would like to apply their work to moving ones as well. Furthermore, their framework solves problems involving a single parabolic partial differential equation, but the team would also like to tackle problems involving coupled parabolic partial differential equations. These types of problems arise in biology and chemistry, where the equation describing the evolution of each agent in a mixture, for example, is linked to the equations of the others.
Mattos Da Silva and Solomon co-wrote the paper with Oded Stein, an assistant professor at the University of Southern California’s Viterbi School of Engineering. Their work was supported, in part, by a Google-funded MIT Schwarzman College of Computing fellowship, a MathWorks fellowship, the Swiss National Science Foundation, the U.S. Army Research Office, the U.S. Air Force Office of Scientific Research, the U.S. National Science Foundation, the MIT-IBM Watson ai Lab, the Toyota-CSAIL Joint Research Center, Adobe Systems, and Google Research.
