The study of computer graphics and geometric processing provides the tools needed to simulate physical phenomena such as fire and flames, helps create visual effects in video games and movies, and helps produce 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 describes how phenomena can smooth out over time. The most famous example of this class is the heat equation, which predicts how heat spreads over a surface or volume over time.
Geometric processing researchers have designed numerous algorithms to solve these problems on curved surfaces, but their methods often apply only to linear problems or to single PDEs. A more general approach presented by researchers at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) addresses a general class of these potentially nonlinear problems.
In a recently published paper, graphic trading Published in the journal and presented at the SIGGRAPH conference, the algorithm describes an algorithm that solves a variety of nonlinear parabolic PDEs on triangular meshes by decomposing them into three simpler equations that can be solved using techniques that graphics researchers already have in their software toolkits. The framework can help to better analyze shapes and model complex dynamic processes.
“We provide a recipe: If you want to solve a second-order parabolic PDE numerically, you follow three steps,” says lead author Leticia Mattos Da Silva SM ’23, a PhD student in MIT’s Department of Electrical Engineering and Computer Science (EECS) and a CSAIL affiliate. “At each step of the approach, you solve a simpler problem using simpler tools of geometric processing, but ultimately you arrive at a solution to the more difficult second-order parabolic PDE.”
To achieve this, da Silva and her co-authors used Strang partitioning, a technique that allows geometric process researchers to break down partial differential equations into problems that they know how to solve efficiently.
First, their algorithm advances the solution forward in time by solving the heat equation (aka the “diffusion equation”), which models how heat from a heat source spreads through a shape. Imagine using a torch to heat a metal plate. This equation describes how heat from that point spreads. This step can be easily done with linear algebra.
Now imagine that the parabolic PDE has additional nonlinear behavior that is not explained by heat diffusion. This is where the second step of the algorithm comes in. We solve the Hamilton-Jacobi (HJ) equations, which are first-order nonlinear PDEs, to account for the nonlinear part.
The general HJ equation can be difficult to solve, but Mattos Da Silva and co-authors have shown that the partitioning method applied to many important PDEs produces HJ equations that can be solved by a convex optimization algorithm. Convex optimization is a standard tool for which geometric processing researchers already have efficient and reliable software. In the final step, the algorithm reuses the heat equation to advance the solution in time by advancing …
Among other applications, the framework could help simulate fires and flames more efficiently. “There are huge pipelines that create videos that simulate flames, but at the heart of them are PDE solvers,” says Mattos Da Silva. For these pipelines, a crucial step is solving the G equation, a nonlinear parabolic PDE that models the flame front propagation, which can be solved using the researchers’ framework.
The team’s algorithm can also solve diffusion equations in the algebraic domain, where they become nonlinear. Lead author Justin Solomon, an associate professor in EECS and leader of the CSAIL Geometric Data Processing Group, previously developed a state-of-the-art technique for optimal transport that required the logarithm of the heat diffusion result. Mattos Da Silva’s framework performed diffusion directly in the algebraic domain, providing more robust computations. This allowed for a more robust way to find geometric notions of the mean in the distribution of surface meshes, such as the koala model, for example.
Their framework focuses on general, nonlinear problems, but can also be used to solve linear partial differential equations. For example, the method solves the Fokker-Planck equation, where heat spreads linearly but has an additional term that drifts in the same direction as the heat spreads. In a simple application, the approach modeled how vortices evolve on the surface of a triangular sphere. The result is a purple and brown latte art.
The researchers point out that this project is a starting point for solving nonlinearities in other PDEs that are directly relevant to graphics and geometric processing. For example, they focused on static surfaces, but they would like to apply the work to moving surfaces as well. Furthermore, while their framework solves problems involving single parabolic PDEs, the team would also like to solve problems involving coupled parabolic PDEs. This type of problem arises, for example, in biology and chemistry, where the equations describing the evolution of each agent in a mixture are coupled with other equations.
Mattos Da Silva and Solomon wrote the paper with Oded Stein, an assistant professor at the Viterbi School of Engineering at the University of Southern California. Their research was supported by the MIT Schwarzman College of Computing Fellowship funded by Google, the MathWorks Fellowship, the Swiss National Science Foundation, the US Army Research Office, the US Air Force Office of Scientific Research, the US National Science Foundation, the MIT-IBM Watson AI Lab, the Toyota-CSAIL Joint Research Center, Adobe Systems, and Google Research.
