Pesquisas em computação gráfica e processamento geométrico fornecem as ferramentas necessárias para simular fenômenos físicos como fogo e chamas, auxiliando na criação de efeitos visuais em videogames e filmes, bem como na fabricação de formas geométricas complexas usando ferramentas como impressão 3D.
Sob o capô, problemas matemáticos chamados equações diferenciais parciais (PDEs) modelam esses processos naturais. Entre as muitas PDEs usadas em física e computação gráfica, uma classe chamada PDEs parabólicas de segunda ordem explica como os fenômenos podem se tornar suaves ao longo do tempo. O exemplo mais famoso dessa classe é a equação do calor, que prevê como o calor se difunde ao longo de uma superfície ou em um quantity ao longo do tempo.
Pesquisadores em processamento de geometria projetaram vários algoritmos para resolver esses problemas em superfícies curvas, mas seus métodos geralmente se aplicam apenas a problemas lineares ou a uma única EDP. Uma abordagem mais geral por pesquisadores do Laboratório de Ciência da Computação e Inteligência Synthetic (CSAIL) do MIT aborda uma classe geral desses problemas potencialmente não lineares.
Em um artigo publicado recentemente no Transações em Gráficos revista e apresentados na conferência SIGGRAPH, eles descrevem um algoritmo que resolve diferentes PDEs parabólicas não lineares em malhas triangulares dividindo-as em três equações mais simples que podem ser resolvidas com técnicas que pesquisadores de gráficos já têm em seu equipment de ferramentas de software program. Esta estrutura pode ajudar a analisar melhor formas e modelar processos dinâmicos complexos.
“Nós fornecemos uma receita: se você quiser resolver numericamente uma PDE parabólica de segunda ordem, você pode seguir um conjunto de três etapas”, diz a autora principal Leticia Mattos Da Silva SM ’23, uma estudante de doutorado do MIT em engenharia elétrica e ciência da computação (EECS) e afiliada do CSAIL. “Para cada uma das etapas dessa abordagem, você está resolvendo um problema mais simples usando ferramentas mais simples de processamento de geometria, mas no ultimate, você obtém uma solução para a PDE parabólica de segunda ordem mais desafiadora.”
Para fazer isso, Da Silva e seus coautores usaram a divisão de Strang, uma técnica que permite que pesquisadores de processamento de geometria dividam a EDP em problemas que eles sabem como resolver de forma eficiente.
Primeiro, seu algoritmo avança uma solução no tempo resolvendo a equação do calor (também chamada de “equação de difusão”), que modela como o calor de uma fonte se espalha sobre uma forma. Think about usar um maçarico para aquecer uma placa de steel — esta equação descreve como o calor daquele ponto se difundiria sobre ela. Esta etapa pode ser concluída facilmente com álgebra linear.
Agora, think about que a EDP parabólica tem comportamentos não lineares adicionais que não são descritos pela propagação do calor. É aqui que entra o segundo passo do algoritmo: ele considera a parte não linear resolvendo uma equação de Hamilton-Jacobi (HJ), uma EDP não linear de primeira ordem.
Embora equações HJ genéricas possam ser difíceis de resolver, Mattos Da Silva e coautores provam que seu método de divisão aplicado a muitas EDPs importantes produz uma equação HJ que pode ser resolvida por meio de algoritmos de otimização convexa. A otimização convexa é uma ferramenta padrão para a qual pesquisadores em processamento de geometria já têm software program eficiente e confiável. Na etapa ultimate, o algoritmo avança uma solução para frente no tempo usando a equação de calor novamente para avançar a EDP parabólica de segunda ordem mais complexa para frente no tempo.
Entre outras aplicações, a estrutura pode ajudar a simular fogo e chamas de forma mais eficiente. “Há um pipeline enorme que cria um vídeo com chamas sendo simuladas, mas no centro dele está um solucionador de PDE”, diz Mattos Da Silva. Para esses pipelines, uma etapa essencial é resolver a equação G, uma PDE parabólica não linear que modela a propagação frontal da chama e pode ser resolvida usando a estrutura dos pesquisadores.
O algoritmo da equipe também pode resolver a equação de difusão no domínio logarítmico, onde se torna não linear. O autor sênior Justin Solomon, professor associado da EECS e líder do CSAIL Geometric Knowledge Processing Group, desenvolveu anteriormente uma técnica de última geração para transporte best que requer tomar o logaritmo do resultado da difusão de calor. A estrutura de Mattos Da Silva forneceu cálculos mais confiáveis ao fazer a difusão diretamente no domínio logarítmico. Isso permitiu uma maneira mais estável de, por exemplo, encontrar uma noção geométrica de média entre distribuições em malhas de superfície como um modelo de um coala.
Embora sua estrutura se concentre em problemas gerais e não lineares, ela também pode ser usada para resolver PDE linear. Por exemplo, o método resolve a equação de Fokker-Planck, onde o calor se difunde de forma linear, mas há termos adicionais que derivam na mesma direção em que o calor está se espalhando. Em uma aplicação direta, a abordagem modelou como os redemoinhos evoluiriam sobre a superfície de uma esfera triangulada. O resultado se assemelha à arte latte roxa e marrom.
Os pesquisadores observam que este projeto é um ponto de partida para lidar com a não linearidade em outras PDEs que aparecem em gráficos e processamento de geometria de frente. Por exemplo, eles se concentraram em superfícies estáticas, mas gostariam de aplicar seu trabalho também às móveis. Além disso, sua estrutura resolve problemas envolvendo uma única PDE parabólica, mas a equipe também gostaria de lidar com problemas envolvendo PDE parabólica acoplada. Esses tipos de problemas surgem em biologia e química, onde a equação que descreve a evolução de cada agente em uma mistura, por exemplo, é vinculada às equações dos outros.
Mattos Da Silva e Solomon escreveram o artigo com Oded Stein, professor assistente na Viterbi College of Engineering da College of Southern California. O trabalho deles foi apoiado, em parte, por uma MIT Schwarzman School of Computing Fellowship financiada pelo Google, uma MathWorks Fellowship, a Swiss Nationwide Science Basis, o US Military Analysis Workplace, o US Air Drive Workplace of Scientific Analysis, a US Nationwide Science Basis, o MIT-IBM Watson AI Lab, o Toyota-CSAIL Joint Analysis Heart, a Adobe Techniques e o Google Analysis.