Métodos Analíticos para Simulação
Dinâmica de Corpos Rígidos Nãopenetrantes
–Autor: David Baraff
–Fonte:SIGGRAPH 1989
–Web:http://www.pixar.com/companyinfo/research/deb/
César Candido Xavier - Aluno
Mestrado CG
1
Objetivo
 Apresentar
de maneira sucinta Método
Heurístico utilizado por David Baraff,
para Simulação Dinâmica de Corpos
Rígidos Não-penetrantes.
César Candido Xavier - Aluno Mestrado CG
2
Heurístico ?
 Do
grego heuristike: achado, descoberta;
 Relacionado
a heurística, ie, uma
hipótese
de
trabalho
adotada
provisoriamente como idéia diretriz na
pesquisa de fatos;
 Método Heurístico: Técnicas (ex: autoeducação) que servem como ajuda na
solução de um problema para o
aprimoramento da performance.
César Candido Xavier - Aluno Mestrado CG
3
Roteiro
 Introdução
 Motivação
 Revisão
alguns conceitos físicos
 Simulação utilizando Métodos Analíticos
 Modelando Contatos
 Calculando Dinamicamente forças de
contato corretamente
 Solução Heurística
 Restrições Adicionais
 Conclusão
César Candido Xavier - Aluno Mestrado CG
4
Introdução
 Muitos
trabalhos utilizam as leis
dinâmica Newtoniana para simular
sistemas de corpos rígidos (CR);
 Toda simulação realística de corpos
rígidos exige que não haja interpenetração de dois quaisquer corpos;
 Foco do “Paper”: Dado um número de
corpos rígidos poliédricos, calcular as
forças que naturalmente surgem para
prevenir a interpenetração.
César Candido Xavier - Aluno Mestrado CG
5
Motivação
Moore e Hahn fizeram os primeiros trabalhos
(1988) utilizando métodos analíticos p/ cálculo
de forças (impulso) entre CR;
 O método utilizado p/ corpos em repouso,
entretanto, era não analítico. Modelo Utilizado
p/ corpos em repouso: série de colisões
ocorrendo freqüentemente.  Modelo Analítico
de forças que não é válido;
 Platt e Barr utilizaram “Penalty Forces”; e
 Moore e Wilhelms utilizaram forças elásticas.

César Candido Xavier - Aluno Mestrado CG
6
Motivação (continuação)
Métodos Errôneos
Vantagens:

-
fácil de implementar;
pouco complexidade; e
extensível p/ corpos não rígidos.
Desvantagens:

-
as simulações apresentam resultados aproximados;
a correção da simulação é difícil de se verificar em alguns
casos; e
requer ajustes para condições diferentes na simulação.
César Candido Xavier - Aluno Mestrado CG
7
Motivação (continuação)
Métodos Analíticos

Vantagens:
- dão respostas exatas;
- produzem E.D.O. que requerem bem menos passos no tempo
durante simulação; e
- a correção da simulação é fácil de se verificar (baseadas
diretamente da dinâmica Newtoniana).

Desvantagens:
-são muito mais complexos de derivar e implementar.
César Candido Xavier - Aluno Mestrado CG
8
Revisão

Centro de Massa:

Momento Linear:

Força:

Torque:

Momento Angular:

mx
my
mz



x 
;y 
;z 
;
i
cm
i
M
i
cm
i
M
i
cm
i
M
p  m  v;
F  dp dt ;
  rx F (  rFsen(Θ));
Momento de Inércia:
César Candido Xavier - Aluno Mestrado CG
l  r x p;
I   mi ri
2
9
Simulação via Métodos Analíticos

Tratamento diferenciado entre forças de colisão e
forças de contato em repouso.

Forças de colisão:
- forças descontínuas (impulsivas);
- dimensão mv; e
- causam descontinuidades na velocidade do CR.

Forças de contato:
- são contínuas em algum intervalo não-nulo;
- dimensão ma; e
- não causam descontinuidades na velocidade do CR.
César Candido Xavier - Aluno Mestrado CG
10




Simulador interage na solução de um par de EDO
acopladas, via uso do método numérico de RungeKutta de 4º Ordem ou Adams-Moulton;
Ao integrador é passado todas condições iniciais dos
corpos;
Métodos Analíticos introduzem descontinuidades nas
velocidades dos corpos quando há colisão. Não
teremos boa solução se integrarmos sobre estes
intervalos...
Solução:
– Devemos descobrir o tempo no qual uma colisão ocorrerá!!!

Foi utilizado o método descrito por Moore e
Wilhelms.
César Candido Xavier - Aluno Mestrado CG
11

Resolvendo uma Colisão:
- uma vez determinado o tempo da colisão, o
integrador é parado;
- faz-se o cálculo das novas forças;
- calcula-se as novas velocidades dos corpos em colisão
(novas condições iniciais); e
- reinicializa-se o integrador.
César Candido Xavier - Aluno Mestrado CG
12
Modelando Contatos
 Contato:colidindo
ou em repouso;
 Dois corpos A e B se tocam em um
número finito de contatos (pontos de
contato);
 pa(to):posição de um ponto de contato de
um CR A no instante t0;
 Sejam dois pontos ‘a’ e ‘b’ dos CR A e B
que estão em contato:
pa (t0)=p=pb (t0)
César Candido Xavier - Aluno Mestrado CG
13
Características pa(to) e pb(to) :

-
Variáveis no tempo;
-
Variam de acordo com os movimentos
independentemente dos CR A e B
respectivamente; e
-
indica:
(t )  p (t )
i. pcolisão;
ii. repouso; ou
iii. separando-se,
.
.
a
0
b
0
César Candido Xavier - Aluno Mestrado CG
14

Associado a cada ponto de contato:
F
– Força
(possivelmente nula); e
– Um vetor unitário normal a superfície .

Contatos tipo Vértice-Plano
– Corpo A: vértice; e
– Corpo B: plano com normal

n
em
n pb.
Contatos tipo Aresta-Aresta
– Um corpo é definido como Corpo A arbitrariamente.
– N é mutuamente perpendicular as arestas em contato e
direcionado se afastando de B.
Obs.: na ausência de atrito
César Candido Xavier - Aluno Mestrado CG
F
é colinear com
.
n
15
César Candido Xavier - Aluno Mestrado CG
16

Pontos de Contato Degenerados
Obs:
usualmente
estes
casos
existem
apenas
instantaneamente, e a escolha para n tem pouco efeito na
simulação.
César Candido Xavier - Aluno Mestrado CG
17
Pontos de Contato Degenerados
Cálculo da intensidade F nestes casos é um
problema NP-completo (teorema de Palmer);
Solução: extensão de um plano local em B, e dáse o tratamento de contatos tipo Vértice-Plano.


Restrição dos Pontos de Contato
–
–
–
Pontos extremos;
Vértices do segmento de reta; e
Polígono de contato das regiões.
César Candido Xavier - Aluno Mestrado CG
18
Restrição Pontos de Contato




n: número de pontos de contato;
n :i vetor normal a superfície do iésimo ponto de contato;
f i :intensidade da força do iésimo ponto de contato;
Fi  f i n;
César Candido Xavier - Aluno Mestrado CG
19
Calculando dinamicamente forças de
contato corretamente

Um vetor F é uma força de contato de
magnitude correta se:
1. não permite que os corpos interpenetrem-se;
2. a força de contato “empurra” mas não “puxa”;
3. forças de contato ocorrem apenas nos pontos de
contato; e
4. visto como uma função do tempo, as forças de
contato são contínuas.
César Candido Xavier - Aluno Mestrado CG
20
Restrições p/ Não-Penetrações


É suficiente examinar o movimento relativo dos
corpos em cada ponto de contato;
Seja a função característica:
i (t )  ni  ( p
César Candido Xavier - Aluno Mestrado CG
a
(to )  p b (to ))
21
.

..
Quem seriam  i (t ) e i (t ) ?
 i (t )  ni  ( p



a
 i (t )  ni  ( p
 
 
(to )  p b (to ))  ni  ( p a (to )  p b (to ));

a



(to )  p b (to ))  2 ni  ( p a (to )  p b (to )) 


ni  ( p (t )  p (t ))
a
o
b
o
Seja. to o instante no qual há o choque entre os CR A e B.
-  i (t )  0 :
 A e B estão colidindo (nunca acontecerá)
.
 i (t )  0 :
.
0
-
0
 i (t )  0 :
 A e B estão se separando (fi=0)
0
-
 se χ”i (to) <0, χi está diminuindo em to e uma
interpenetração é eminente,..e portanto devemos ter:
 i (t )0
0
César Candido Xavier - Aluno Mestrado CG
22

Exemplo 1:
César Candido Xavier - Aluno Mestrado CG
23

Exemplo 2:
César Candido Xavier - Aluno Mestrado CG
24
Matriz formulação das condições (1) e (2)
 i (t0 )  a1i f1  a2i f 2  ...  a,nipara
f 1≤
b i 0≤ n
n i
 

(não há inter-penetração);

fi ≥ 0, para 1≤ i ≤ n (forcas somente “empurram”);
César Candido Xavier - Aluno Mestrado CG
25

Podemos escrever a representação matricial,
portanto, da seguinte forma:
–
i ( f )  (A f ) b ;
 
i
– A f  b0
–
ou equivalentemente, A f b; e
f 0.
César Candido Xavier - Aluno Mestrado CG
26
Programação Linear (PL)





Encontrar um vetor
que satisfaz: Mx ≥ c (M é matriz
e c é um vetor) que minimiza uma função linear z(x) é
um exemplo de um problema típico de PL;
x.
Se existem x que satisfazem todas as restrições dizemos
que o sistema é realizável e cada x é uma solução
realizável;
Se x é uma solução realizável que minimiza z, são ditos
sistemas limitados e x uma solução ótima.
PL é um problema polinomial no tempo;
x.
Se, entretanto, é explorado o fato de A ser
tipicamente
uma matriz esparsa, a solução é O(n);
César Candido Xavier - Aluno Mestrado CG
27
Formulação das condições (3) e (4)

Uma f que atenda aA f
correta!!!
b e f 0
, não será necessariamente
– Exemplo 1: f=mgcos(θ) é a única solução correta, porém
f=2mgcos(θ) é solução realizável que previne a inter-penetração,
porém acelera incorretamente, afastando o CR A de B.
César Candido Xavier - Aluno Mestrado CG
28
Sabemos que se para o i-ésimo ponto de contato, se
 i ( f )0,
 
então  i é estritamente crescente e os CR A e B estão se
 
separando.
Para atendermos (3) devemos ter:
f  i ( f )  0.
i
 
César Candido Xavier - Aluno Mestrado CG
29
Para 1≤ i ≤ n, nossas restrições passam a ser escritas como:
Ou:
César Candido Xavier - Aluno Mestrado CG
30





T
O termo que envolve a forma f A f é quadrático em
fi;
Programação Quadrática, diferentemente de PL é
um problema NP-difícil de um modo geral;
Modelando contatos sem atrito A é positivamente
semidefinida (PSD), e programas quadráticos
podem teoricamente ser resolvidos em tempo
polinomial (não existe tal algoritmo...)
Não há porque acreditar que com atrito A
continuará sendo PSD...
SOLUÇÃO: desenvolvimento de um algoritmo
heurístico para este problema...
César Candido Xavier - Aluno Mestrado CG
31
Solução Heurística
Uma determinada configuração de corpos
tem apenas uma configuração de
movimentos corretos.
Seja V e C os conjuntos de pontos que estão
deixando de existir e não estão deixando de
existir, ou seja:
V={j | ponto de contato que está sumindo}
C={k | ponto de contato que não está sumindo}
César Candido Xavier - Aluno Mestrado CG
32
Sabemos que para qualquer solução
–
–
f :
correta
se j V  f  0; e
j

se k  C   k ( f )  0.
Podemos escrever:
César Candido Xavier - Aluno Mestrado CG
33
Exemplo: Seja um sistema quadrático com restrições em
quatro pontos de contato, com V={1,3} e C={2,4}
César Candido Xavier - Aluno Mestrado CG
34
Como achar V ?
César Candido Xavier - Aluno Mestrado CG
35
1) Solução mais simples: V=Ø
Não existem pontos de contato que estão deixando
de existir, e f está sujeito às seguintes restrições:
A f  b e f 0
Através de diversas simulações constatou-se que a
solução V=Ø é correta para a grande maioria dos
casos.
César Candido Xavier - Aluno Mestrado CG
36
2) Predizendo um conjunto não-vazio de V
Se for encontrado uma configuração com pontos de contatos
que estão deixando de existir, a adivinhação de que V=Ø
resultará em um sistema indeterminado.
Solução: encontrar uma solução aproximada fa que satisfaça às
restrições:

 i ( f a )0 e f a 0.
Seja
ro vetor residual:
César Candido Xavier - Aluno Mestrado CG
37
Se fa for uma solução correta, para todos pontos j,
que estão deixando de existir,
e para todos os outros pontos k,
r
j


 j, ( f a )0
r 
k

 k. ( f a )  0
2.1) Encontrando fa Aproximadas
A heurística utilizada para encontrar a solução aproximada
é: escolha fa que minimiza a seguinte função:
,
sujeita às seguintes restrições:
César Candido Xavier - Aluno Mestrado CG
38
2.2) Tratando com Predições Incorretas
-Tendo n pontos de contatos, deveríamos testar
todas as 2n possibilidades ?
- A implementação desenvolvida leva em
consideração que pontos deixando de existir
ocorrem com pouquíssima freqüência...
- Energia é adicionada ao sistema, produzindo
resultados incorretos...
César Candido Xavier - Aluno Mestrado CG
39
- ... porém o (d)efeito é mascarado pelo fato de que
estas configurações são singulares, ou seja f a é
aplicado apenas por um período pequeno no
tempo.
- Descobriu-se que, no pequeno intervalo de tempo
na qual f aé aplicado, levando-se em conta que f a é
usualmente uma boa aproximação da solução
correta produziu resultados satisfatórios.
César Candido Xavier - Aluno Mestrado CG
40
Restrições Adicionais
Restrições Holonômicas (figuras articuladas)
podem ser adicionadas de uma maneira
consistente;
 Barzel e Barr mantiveram restrições holonômicas
pela introdução de forças de restrição que
satisfaziam ao sistema linear


Todo o sistema é resolvido conforme descrito
anteriormente , à exceção do somatório mínimo
das forças, o qual levará em consideração tão
somente as restrições não holonômicas das forças.
César Candido Xavier - Aluno Mestrado CG
41
É
consistente com a formulação proposta,
uma vez que programação linear permite
restrições com igualdades;
 Não estão sujeitos as condições (2);
 Todo o sistema é resolvido conforme
metodologia apresentada, à exceção do
somatório mínimo de forças, o qual levará
em questão apenas as forças de restrições
não-holonômicas; e
 Utilizado pacote de PL esparsa p/ resolver
em O(n).
César Candido Xavier - Aluno Mestrado CG
42
Exemplos
César Candido Xavier - Aluno Mestrado CG
43
César Candido Xavier - Aluno Mestrado CG
44
César Candido Xavier - Aluno Mestrado CG
45
Conclusão




A solução proposta para encontrar as forças de contato
entre corpos poliédricos, foi baseada em uma
heurística, cuja solução é encontrada via uso de
técnicas de Programação Linear;
A solução proposta permite trabalhar com restrições
holonômicas;
O grande esforço computacional do algoritmo é
voltado na solução de um sistema linear de
desigualdades; e
O algoritmo heurístico utilizado ocasionalmente
falhará e uma solução aproximada é utilizada. Isto
adiciona energia a simulação mas não resulta em
nenhum efeito visual insatisfatório.
César Candido Xavier - Aluno Mestrado CG
46