Research in computer graphics and geometry processing offers the means to replicate real-world phenomena such as fire and flames, supporting the production of visual effects for video games and films as well as the construction of intricate geometric objects with the use of 3D printing technology.
These natural processes are modeled at the mathematical level using partial differential equations (PDEs). A type of PDE known as second-order parabolic PDEs, among the several PDEs utilized in physics and computer graphics, explains how events can eventually become smooth. The heat equation, which forecasts how heat diffuses over time along a surface or in a volume, is the most well-known example in this class.
Many algorithms have been developed by geometry processing researchers to handle these problems on curved surfaces; however, their approaches are frequently limited to solving linear problems or a single PDE. Researchers at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) have taken on a broader class of these potentially nonlinear issues with a more general approach.
They describe an algorithm that solves various nonlinear parabolic PDEs on triangle meshes by breaking them down into three simpler equations that can be solved using methods that graphics researchers already have in their software toolbox in a paper that was recently published in the Transactions on Graphics journal and presented at the SIGGRAPH conference. This framework can be used to simulate intricate dynamical processes and analyze shapes more effectively.
“We offer a recipe: To solve a second-order parabolic PDE numerically, you can adhere to a series of three actions,” explains lead author Leticia Mattos Da Silva SM ’23, an affiliate of CSAIL and an MIT PhD candidate in electrical engineering and computer science (EECS). “This approach involves solving a simpler problem for each step using simpler geometry processing tools, and the result is a solution to the more difficult second-order parabolic PDE.”
In order to do this, Da Silva and her coauthors employed a method known as strangling, which enables researchers studying geometry processing to decompose the PDE into simpler, more manageable problems.
Initially, their algorithm solves the heat equation, which is sometimes referred to as the “diffusion equation” and describes how heat from a source diffuses over a shape, moving a solution forward in time. Imagine heating up a metal plate with a blow torch; this equation explains how heat would spread over it.This is a simple step that can be finished with linear algebra.
Now suppose that there exist other nonlinear behaviors of the parabolic PDE that are not explained by the heat dissipation. This is where the algorithm’s second phase comes in: it solves a Hamilton-Jacobi (HJ) equation, a first-order nonlinear PDE, to account for the nonlinear component.
Although generic HJ equations are challenging to solve, Mattos Da Silva and colleagues demonstrate that by applying their splitting method to a number of significant PDEs, a HJ equation that can be solved using convex optimization algorithms is produced. Convex optimization is a common tool for which geometry processing researchers already have dependable and effective software. In the last stage, the algorithm uses the heat equation once more to move a solution ahead in time, solving the second-order parabolic PDE, which is more complicated.
The framework may find use in improving the accuracy of fire and flame simulations, among other things. “A PDE solver is at the core of a massive pipeline that creates a video with simulated flames,” explains Mattos Da Silva. The G-equation, a nonlinear parabolic PDE that simulates the front propagation of the flame and can be solved using the researchers’ framework, is a crucial step for these systems.
The diffusion problem can also be solved by the team’s approach in the logarithmic domain, where it turns nonlinear. The CSAIL Geometric Data Processing Group leader and senior author Justin Solomon, an associate professor of EECS, previously devised a cutting-edge method for optimal transport that involves taking the logarithm of the heat diffusion result. Because Mattos Da Silva’s architecture performed diffusion directly in the logarithmic domain, the computations were more dependable. This made it possible to obtain a geometric notion of average among distributions on surface meshes, such as a koala model, more steadily, for example.
Their framework is applicable to solving linear PDEs even if it concentrates on general, nonlinear issues. The technique, for example, solves the Fokker-Planck equation, in which heat diffuses linearly but with additional terms that also drift in the direction of heat diffusion. The method modeled the evolution of swirls over the surface of a triangulated sphere in a simple application. The outcome is similar to brown and purple latte art.
The initiative, according to the researchers, provides a beginning point for directly addressing the nonlinearity in other PDEs that arise in graphics and geometry processing. For instance, they concentrated on stationary surfaces but would also like to leverage their research on moving ones. Additionally, the team’s methodology addresses difficulties with a single parabolic PDE, but they would also wish to address coupled parabolic PDE problems. These kinds of issues occur in the fields of biology and chemistry, where, for example, the equation characterizing the evolution of each agent in a mixture is connected to the equations of the other agents.
Oded Stein, an assistant professor at the Viterbi School of Engineering at the University of Southern California, co-wrote the work with Mattos Da Silva and Solomon. The MIT-IBM Watson AI Lab, the Toyota-CSAIL Joint Research Center, Adobe Systems, Google Research, the Swiss National Science Foundation, the U.S. Army Research Office, the U.S. Air Force Office of Scientific Research, the MIT Schwarzman College of Computing Fellowship funded by Google, a MathWorks Fellowship, and the U.S. National Science Foundation all provided financial support for this work.
