Research in computer graphics and geometry processing provides the needed tools to simulate physical phenomena similar to fire and flames and supports the creation of visual effects in video games and movies in addition to the production of complex geometric shapes using tools similar to 3D printing.
Basically, these natural processes are modeled by mathematical problems called partial differential equations (PDEs). Among the various PDEs utilized in physics and computer graphics, a category called second-order parabolic PDEs explains how phenomena can grow to be smooth over time. The most famous example on this class is the warmth conduction equation, which predicts how heat spreads along a surface or in a volume over time.
Researchers in geometry processing have developed quite a few algorithms to resolve these problems on curved surfaces, but their methods are sometimes only applicable to linear problems or to a single PDE. A more general approach by researchers at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) addresses a general class of those potentially nonlinear problems.
In a recently published article in Published within the journal The 4000 and presented on the SIGGRAPH conference, they describe an algorithm that solves various nonlinear parabolic differential equations on triangular meshes by splitting them into three simpler equations that might be solved using techniques that graphics researchers have already got of their software toolkit. This framework can assist higher analyze shapes and model complex dynamic processes.
“We offer a recipe: If you wish to solve a second-order parabolic PDE numerically, you possibly can follow three steps,” says lead writer Leticia Mattos Da Silva SM '23, an MIT doctoral student in electrical engineering and computer science (EECS) and CSAIL collaborator. “At each step of this approach, you solve a less complicated problem using simpler tools from geometry processing, but in the long run you get an answer to the tougher second-order parabolic PDE.”
To achieve this, Da Silva and her co-authors used strand partitioning, a way that enables researchers in geometry processing to decompose the PDE into problems that they know easy methods to solve efficiently.
First, their algorithm evolves an answer in time by solving the warmth equation (also called the “diffusion equation”), which models how heat spreads from a source through a shape. Imagine heating a metal plate with a blowtorch – this equation describes how heat would spread from that location through it. This step is simple to do using linear algebra.
Now imagine that the parabolic PDE has additional nonlinear behaviors that aren’t described by the warmth propagation. This is where the second step of the algorithm comes into play: it takes the nonlinear part into consideration by solving a Hamilton-Jacobi (HJ) equation, a first-order nonlinear PDE.
While generic HJ equations might be difficult to resolve, Mattos Da Silva and co-authors prove that their partitioning method applied to many essential PDEs yields an HJ equation that might be solved using convex optimization algorithms. Convex optimization is an ordinary tool for which researchers in geometry processing have already got efficient and reliable software. In the ultimate step, the algorithm evolves an answer in time by again using the warmth equation to time evolve the more complex second-order parabolic PDE.
Among other things, the framework could help simulate fire and flames more efficiently. “There is a large pipeline that creates a video with simulated flames, but the center of it’s a PDE solver,” says Mattos Da Silva. A key step for these pipelines is solving the G equation, a nonlinear parabolic PDE that models the frontal propagation of the flame and might be solved with the researchers' framework.
The team's algorithm can even solve the diffusion equation within the logarithmic domain, where it becomes nonlinear. Senior writer Justin Solomon, associate professor of EECS and head of the CSAIL Geometric Data Processing Group, previously developed a state-of-the-art technique for optimal transport that requires taking the logarithm of the results of heat diffusion. Mattos Da Silva's framework provided more reliable calculations by performing diffusion directly within the logarithmic domain. This enabled a more robust method for, for instance, finding a geometrical mean amongst distributions on surface meshes similar to a koala model.
Although their framework focuses on general, nonlinear problems, it may well even be used to resolve linear partial differential equations. For example, the tactic solves the Fokker-Planck equation, where heat propagates linearly, but there are additional terms that drift in the identical direction that the warmth propagates. In a straightforward application, the approach modeled how vortices would develop across the surface of a triangular sphere. The result resembles purple-brown latte art.
The researchers indicate that this project is a place to begin to directly address the nonlinearity of other PDEs that arise in graphics and geometry processing. For example, they focused on static surfaces, but would love to use their work to moving ones as well. In addition, their framework solves problems with a single parabolic PDE, however the team also desires to tackle problems with coupled parabolic PDEs. These kinds of problems arise in biology and chemistry, where, for instance, the equation describing the evolution of every energetic ingredient in a mix is linked to the equations of the others.
Mattos Da Silva and Solomon co-authored the paper with Oded Stein, an assistant professor on the University of Southern California's Viterbi School of Engineering. Their work was supported 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, amongst others.
