Animação de Tecido

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Animação de Tecido
Implementação, otimização, e correção do modelo
Animação de Tecido
Implementação, otimização, e correção do modelo
Apresentação para a disciplina MATA65 - Computação Gráfica, da Universidade Federal da Bahia.
Professor: Antonio L. Apolinario Jr.
Alunos: Fernando Nascimento e Marcio Bouças
Motivação
Dinâmica de Corpo Flexível (soft-body physics) abrange diversas áreas da computação visual, como softwares médicos, jogos eletrônicos e simulações para a industria da moda.
Muitos materiais do mundo real não são completamente sólidos. Simulá-los é computacionalmente complexo.
Focando em tecidos, como implementá-los? 
De que forma a simulação de tecidos pode ser otimizada?
Como tornar o tecido virtual coerente com tecidos reais?
Introdução
Apresentaremos como representar tecidos computacionalmente, de forma a simular tecidos reais.
Mostraremos uma forma de otimização baseada em CUDA e OpenGL
Mostraremos uma simulação de exemplo, no Three.js
Depois, mostraremos uma forma de representar tecidos mais realisticamente, usando procedimentos de dinâmica inversa
Simulação de Tecidos
Exemplos:
Simulação de Tecidos
Exemplos:
Simulação de Tecidos
Exemplos:
Simulação de Tecidos
P: Como simular tecidos de maneira fiel?
R: Tentando simular a malha de tecido computacionalmente
Um pouco de física.
Modelo Massa-Mola
Dentre os modelos de representação de tecido, o massa-mola é um dos mais comuns.
Lembrem da aula de física (é, eu sei. Mas não façam essa cara…). Consiste de massas interligadas por molas.
Modelo Massa-Mola
Podemos fazer uma malha complexa de massas interligadas por molas:
Modelo Massa-Mola
Mais especificamente, no nosso modelo, uma malha poligonal será considerada uma coleção de pontos-massa, onde cada vértice atua como uma massa, e atuaram restrições (constraints), que equivalerão à molas.
Modelo Massa-Mola
As molas atuarão de forma diferente dependendo da posição das massas que ela liga, com relação à malha
Considerando uma malha de M x N massas virtuais:
Molas ligando massas [i,j] com [i, j+1], ou [i,j] com [i+1, j], serão chamadas “structural springs” (molas estruturais)
Molas ligando massas [i,j] com [i+1, j+1], ou [i+1,j] com [i, j+1], serão chamadas “shear springs” (molas de tosa (?), molas de corte)
Molas ligando massas [i,j] com [i, j+2], ou [i, j] com [i+2, j], serão chamadas “flexion springs” (molas de flexão)
Modelo Massa-Mola
As molas estruturais agem sob a tensão de compressão ou de tração (esticar)
As molas de corte agem sob a tensão de corte (tensões diagonais, ou tensões em direções opostas)
As molas de flexão agem sob tensão de flexão (dobrar)
Modelo Massa-Mola
Espera-se que o “tecido” seja suscetível tanto a interações com outros objetos geométricos (ex: esferas virtuais, ou o corpo de um personagem renderizado), como com aceleração (ex: gravidade), ou força externa (ex: vento virtual)
As massas são afetadas por essas interações, e seu movimento é propagado pela malha através da resolução das constraints
Resolver uma interação entre massas pode afetar a interação entre outras mas, com o relaxamento, ou seja, com a continuidade de interações, essas diferenças vão sendo corrigidas com o tempo.
Agora é MUITA física...
Dinâmica e Forças
Considerando uma malha de M x N massas, cada massa estará posicionada, no momento t, no ponto Pi,j(t)
A evolução do sistema se dá por
Fi,j = mai,j
Onde m é a massa de cada ponto Pi,j
ai,j é a aceleração causada pela
Força Fi,j, que pode ser dividida em:
Dinâmica e Forças
Força interna
É resultante das tensões das molas ligando Pi,j aos seus vizinhos, descrita por: 
Onde:
R é o conjunto todos os pares (k, l), tal que Pk,l está ligado a Pi,j (todas as massas adjacentes a Pi,j)
li,j,k,l é o vetor entre Pi,j e Pk,l,
l0i,j,k,lé o tamanho original da mola ligando Pi,j e Pk,l
ki,j,k,l é a rigidez (stiffness) da mola ligando Pi,j e Pk,l
Dinâmica e Forças
Força externa
Tem várias naturezas, de acordo com o que o modelo for exposto. 
Gravidade, amortecimento viscoelástico (viscous damping) e interação viscoelástica (viscous interaction) com ar/vento estarão sempre presentes
Sendo g a aceleração da gravidade, o peso de Pi,j é dado por :
Dinâmica e Forças
Força externa
Amortecimento viscoelástico é dado por:
Onde:
Cdis é o coeficiente de amortecimento
vi,j é a velocidade de Pi,j
O papel do amortecimento viscoelástico é a dissipação da energia mecânica do modelo.
É introduzido por forças externas, mas pode ser considerada uma força interna também.
Dinâmica e Forças
Força externa (cont.)
Por fim, a movimentação fluida viscoelástica (viscous fluid moving) na velocidade uniforme ufluid exerce, na superfície de um corpo se movendo na velocidade v, uma força Fvi = Cvi[ni,j (ufluid - v)]n, onde n é a normal da superfície. Para o nosso modelo:
Onde ni,j é a normal da superficie no ponto Pi,j
Dinâmica e Forças
Integração
Com base nas equações anteriores, conseguimos calcular a força Fi,j(t) aplicada no ponto Pi,j para qualquer momento t
A Equação Fundamental da Dinâmica pode ser integrada explicitamente pelo método de Euler:
Onde delta t é um dado momento do tempo / passo da execução do algoritmo
Dinâmica e Forças
Nem todos os movimentos do objeto tecido são computáveis analiticamente. Isso acontece para TODOS os problemas de contato.
Exemplo: cortina pendurada
Todo ponto preso está sujeito à força da gravidade
Porém, os pontos presos sofrem uma força contrária que não é diretamente computável em função da posição e da velocidade dos vértices da malha. 
Esse deslocamento pode ser determinada indiretamente, de maneira inversa
O deslocamento do ponto preso é conhecido. 0.
Também podemos calcular a velocidade e força resultante aplicadas a ele. Também é 0.
Em resumo, não levamos em conta a integração anterior para pontos presos.
Ou, independente do resultado, ele receberá um valor conhecido anteriormente.
A esse procedimento inverso chamamos de Procedimentos de Dinâmica Inversa (Dynamic Inverse Procedures)
Dinâmica e Forças
Procedimentos de Dinâmica Inversa podem ser usados para lidar com a colisão do objeto-tecido com outros objetos, ou até com o próprio tecido.
Porém, estes não serão abordados nesta apresentação (já temos bastante coisa, sério!) 
Ainda temos tempo?
Se sim, vamos continuar daqui
Se não, pulamos para o slide 38
Otimização
Heath (2015) demonstra preocupação com a renderização de tecidos em computadores domésticos. Isso seria de grande aplicação em jogos, ou em simuladores, por exemplo.
Para isso, ele utiliza CUDA, OpenGL, e o próprio computador
CUDA, sigla para Compute Unified Device Architecture, é uma extensão para a linguagem de programação C, a qual possibilita o uso de computação paralela. A ideia por trás disso tudo é que programadores possam usar os poderes da unidade de processamento gráfico (GPU) para realizar algumas operações mais rapidamente
O OpenGL (Open Graphics Library) é uma API livre utilizada na computação gráfica, para desenvolvimento de aplicativos gráficos, ambientes 3D, jogos, entre outros. A OpenGL foi produzida com C e C++ em mente, mas pode ser utilizada para diversas outras com um alto nível de eficiência. WebGL é baseado no OpenGL ES 2.0. O Three.js é baseado em WebGL
O computador utilizado foi um processador i5 3570k (3.43.8 Ghz), 4GB de RAM, e uma NVIDIA GTX 980. 
Otimização - Threads?
A idéia inicial era paralelizar o processo de satisfação de restrições
Foi criada uma pilha de blocos com 32 threads cada um (pois é o número de processos simultâneos que a placa gráfica processa)
O resultado foi:
Otimização - Threads?
Falha completa.
Otimização - Threads?
O motivo é óbvio: cada massa da malha participa de muitos cálculos de restrições (cada massa é ligada por muitas outras massas através das molas virtuais).
Usando threads, um ponto de massa pode ser necessário na execução de mais de uma thread ao mesmo tempo, gerando uma
condição de corrida (race condition)
Tão ruim quanto, uma thread pode reposicionar um ponto de massa que já teve sua posição resolvida por uma thread anterior.
Pensou-se em usar travas (locks) para que uma thread não atrapalhasse outra, mas isso poderia fazer com que uma delas bloqueasse muitas outras, por vezes desnecessariamente.
Threads não são uma boa ideia. O algoritmo sequencial precisa ser revisto, para que nenhum ponto fosse utilizado por threads diferentes simultaneamente.
Otimização - buckets
A ideia, para evitar locks e race conditions é criar grupos (ou baldes, buckets) de restrições (molas) sem pontos em comum. 
Logo, o problema se torna como agrupar as restrições de modo que todas possam ser resolvidas em paralelo, e sem interferência
Foram criados 16 buckets diferentes:
Um para as molas veticais pares, e outro para as ímpares
Um para as horizontais pares, outra para as ímpares
Quatro, para as diagonais pares e ímpares, e para as anti-diagonais pares e ímpares
Foram feitos buckets análogos para molas de flexão (que não ligam massas adjacentes)
Otimização - buckets
Exemplo de uma malha 10 x 10, demonstrando as molas “primarias” (structurals e shear). Para molas “secundárias” (flexion), o processo é análogo.
Otimização - buckets
Uma vez que cada constraint consiste de dois ponteiros no array de pontos de massa, eles podem ser gerados e armazenados na memória global da GPU antes do começo da simulação
Colisão e comandos de OpenGL ainda são responsabilidade da CPU, logo as massas precisam ser copiadas pra GPU antes de resolver as interações, e devolver pra RAM quando terminar.
A GTX980 pode resolver 512 constraint ao mesmo tempo (32threads / warp * 16 núcleos SMX).
Logo, para uma malha com no máximo de 512 molas, a simulação é executada, essencialmente, em tempo linear, limitada pelo envio de dados para a GPU, e a recuperação destes. 
Otimização - buckets
Resultados
Comparemos o uso da GPU com paralelismo para a resolução das constraints, e da CPU usando apenas um núcleo.
Vamos analisar a taxa de frames por segundo (FPS), ao usar os dois métodos acima, para malhas de resolução (quantidade de pontos) diferentes.
Abaixo: GPU(esquerda) contra CPU (direita), numa malha de resolução de 80 x 80
Otimização - buckets
Resultados:
Para malhas de 40 x 40, a CPU “vence”
Para todas as outras, a GPU leva a melhor
Otimização - buckets
Resultados:
Analisando o aumento relativo de performance, temos o gráfico ao lado
Podemos perceber uma tendência: Não só a GPU supera, rapidamente, a CPU, como tende a melhorar com o aumento da resolução da malha
Otimização - buckets
Resultados:
Indo mais a fundo, podemos perceber que o tempo de resolução de constraints na GPU (antes de 160 x 160) é praticamente nulo! Enquanto isso, na CPU esse tempo cresce de forma (praticamente) linear.
O tempo de copiar os dados para a GPU (GPU Data Copy) é praticamente constante.
O que também explica a “vitória” da CPU em 40 x 40: o GPU Data Copy leva quase tanto tempo quanto a simulação da CPU
Resultados:
Fica claro que, o que realmente pesa, na renderização pela GPU, é o GPU Data Copy, e o Tempo de Desenho (Drawing Time). 
Este último é responsabilidade do OpenGL, que é processado na CPU (como já explicamos)
Assim, utlizando o método de paralelismo com Buckets, e um motor OpenGL otimizado, pode-se obter um resultado impressionante
Otimização - buckets
Demonstração com o Three.js
http://threejs.org/examples/webgl_animation_cloth.html
Relembrando...
Lembra disso? Vamos precisar
Efeito Super-Elástico
Notaram, no exemplo, como o tecido se estica? Na verdade, é ótimo que tenham usado uma textura de rede, pois poucos tecidos se comportam daquela forma sem se rasgar antes.
Provot (1995) notou o mesmo problema, mostrando como a deformação nas pontas presas é muito maior que a do resto do tecido. 
As “molas” responsáveis pelas massas presas se deformavam em mais de 100%!
Efeito Super-Elástico
Neste exemplo, ele usa uma malha de 17 x 17 para demonstrar a deformação, após 200 interações do algoritmo
Efeito Super-Elástico
Tal efeito, na física de polimeros, é conhecido como super-elasticidade, que ocorre com materiais com taxas de deformação muito altas
… O que não deveria acontecer com tecidos. A elasticidade destes é não linear e, a medida que a taxa de deformação aumenta, sua rigidez (stiffness) também aumenta. Essa taxa costuma ser muito reduzida e, quando uma força grande é aplicada, ocorre uma ruptura antes que tal deformação ocorra
Ou seja, ele “rasga”. Mas não vamos trabalhar com rasgos e cortes. Nossa ideia é limitar essa deformação exagerada. Também queremos evitar a oscilação exagerada dos tecidos (que também pode ser vista no exemplo)
Podemos pensar em aumentar o coeficiente de amortecimento cdis, mas isso geraria um efeito falso, como se o tecido estivesse embebido em óleo.
Efeito Super-Elástico
A ideia é alterar o modelo, aumentando a rigidez das molas. É um resultado alcançável, mas não de forma simples.
Dado um intervalo de tempo delta-t, e uma massa m, existe um valor de rigidez máximo, Kc, além do qual a resolução numérica do sistema diverge.
Isso ocorre se delta-t for maior que o período inicial do sistema, dado por
Efeito Super-Elástico
Teriamos que fazer com que delta-t fosse menor que T0, aumentando o número de interações para um mesmo tempo de animação, tornando o algoritmo custoso.
Vamos tentar outra abordagem, então.
Dinâmica Inversa
Vamos aplicar um procedimento simples a cada mola, para evitar os super alongamentos
Cada mola/constraint terá sua deformação calculada pela equação que já vimos
Se uma certa mola se deformar mais que um certo valor 𝜏c, um procedimento dinâmico inverso será aplicado às duas pontas da mola, até que sua deformação seja igual a 𝜏c
Exemplo: se 𝜏c=0,1, a molá não deformará mais que 10%
Dinâmica Inversa
O cálculo que o algoritmo faz, inicialmente, posiciona as masas na direção correta. Mas não deforma as molas no comprimento correto. Vamos fazer com que a distância entre os pontos nunca passe de 𝜏c
Para isso, temos agora 3 tipos de mola: presas nas duas pontas, presa em só uma ponta, e solta (não fixada) nas duas pontas
Se:
Dinâmica Inversa
Se ambas as pontas estiverem “soltas”, elas serão aproximadas (mantendo a direção) até que sua distância seja igual a 𝜏c
Se apenas uma ponta estiver solta, esta será aproximada da ponta fixa, até que a distância entre ambas seja 𝜏c
Se as duas pontas estiverem presas, nada precisa ser feito.
Dinâmica Inversa
Importante: esse método será aplicado às molas “primarias” (estrutural, e de corte). Não há necessidade de aplicá-lo à molas de flexão.
Molas estruturais lidam com deformações (esticar e comprimir). Molas de flexão lidam com dobras. E dificilmente um tecido é resistente à dobra. Logo, esse tipo de mola não precisa ser restringida.
Dinâmica Inversa
“Mas isso não pode modificar a posição de massas já corrigidas?”
Pode. Na verdade, vai. Mas a vantagem do método empregado é que as deformações se propagam pela estrutura da malha.
Dinâmica Inversa
Resultados
Melhoria no aspecto visual dos objetos-tecido
Menor deformação das malhas
Utilizando o algoritmo Massa-mola tradicional
Utilizando a dinâmica reversa nas molas estruturais
Utilizando dinâmica reversa nas molas estruturais e de corte
Dinâmica Inversa
Resultados
Novo algoritmo tem custo computacional 15% maior
Para alcançar resultados semelhantes, o algoritmo antigo precisa aumentar a rigidez e o tempo amostral.
O que faz com que o novo algoritmo seja 90% mais rápido que o clássico.
Esquerda: Modelo calculado da forma antiga em 9 minutos. 
Direita: Modelo usando o algoritmo proposto. 1 minuto.
Dinâmica Inversa
Resultados
Aplicando o método numa bandeira, e com vento forte 
O movimento do método antigo é bastante caótico (lembrem do exemplo do three.js) (abaixo)
Já com a DI, o resultado é bastante realista (acima)
Dinâmica Inversa
Resultados
Com mesmas velocidade do vento,
tempo de execução, e rigidêz das molas, o modelo antigo se torna caótico (abaixo)
Dinâmica Inversa
Resultados
O método pode ser aplicado com tecidos presos em pontos diferentes - como nesse barco a vela, por exemplo
Conclusão
Modelagem de tecido é importante para o aumento de realismo de simulações, jogos, e filmes.
Porém, sua computação é custosa.
Mostramos uma forma de paralelismo feita de maneira ingênua, e seu resultado desastroso.
Na sequencia, mostramos um paralelismo feito em momentos distintos, de tempo de execução O(n), numa placa gráfica doméstica.
Vimos que o modelo comumente utilizado para representar tecidos tem duas falhas, super-elasticidade e alta instabilidade
Por fim, mostramos um método pouco eficaz para resolver esse problema (aumento do tempo de amostragem), e outro mais simples e eficiente (dinâmica reversa)
Obrigado!
Podem acordar, já encerramos!
Referências
HEATH, Ian. Accelerating Cloth Simulation with CUDA. http://www.andrew.cmu.edu/user/iheath/418/cloth/CUDAClothSimulatorFinalReport.html
Provot, Xavier. Deformation constraints in a mass-spring model to describe rigid cloth behaviour. Graphics interface. Canadian Information Processing Society, 1995. http://kucg.korea.ac.kr/education/2005/CSCE352/paper/provot95.pdf
Esta apresentação pode ser acessada em: https://docs.google.com/presentation/d/1Hi-19SGBBpJ82hjoKNPJWuKMctvdjNGww2PttHDwCjY/edit?usp=sharing