Prós e contras de diferentes integradores [fechado]

29

Ao criar coisas como física em jogos, você precisa de um integrador. Eu já vi a integração da Verlet mencionada em vários lugares como uma ótima alternativa à integração do Euler. Por exemplo, no famoso documento de Thomas Jakobsen . No entanto, neste artigo Glenn Fiedler escreve:

Em vez de apresentar a vasta gama de diferentes integradores que existem, vou direto ao assunto e vou direto ao melhor. Esse integrador é chamado de integrador de ordem 4 da Runge Kutta, também conhecido como RK4.

Então, aparentemente, não há bala de prata. Quais são os prós e os contras dos diferentes integradores? Em relação à simplicidade, velocidade, precisão, estabilidade, etc. Quais integradores são mais adequados para quais tipos de jogos? Quando você usaria o Verlet, o RK4 ou outros? Você deveria usar o Euler?

paldepind
fonte
Há uma resposta para que você pode fantasia stackoverflow.com/questions/2769466/...
teodron
Obrigado pelo link. Já estou ciente disso.
paldepind

Respostas:

27

Prós e contras de ambos os métodos:

Prós RK4:

  1. precisão (graças à sua melhor série de aproximações, produz uma precissão de 4ª ordem)
  2. o amortecimento artificial / inerentemente induzido (um pouco como os métodos implícitos o fazem) adiciona estabilidade (ao passo que um simples passo de Euler não - ele faz o oposto, introduzindo energia fantasma que se acumula e pode mergulhar o sistema no caos)

Contras RK4:

  1. despesa de computação: embora não seja tão exigente em comparação com métodos implícitos ou híbridos IMEX, o RK4 é 4 vezes mais caro que o Euler explícito, pois exige muito mais avaliações de funções. Isso é mostrado ao apontar para o limite da otimização.
  2. ainda instável: dependendo dos tipos de forças envolvidas, o RK4 pode ser tão instável quanto Euler. Em média, o RK4 é um pouco mais estável e tende a tirar esse benefício de suas "habilidades" de amortecimento.
  3. Não simplético: o amortecimento numérico tem um custo - você não pode simular sistemas onde energia / volume / etc. a perda não deve aplicar um efeito visível ao longo do tempo (por exemplo, Dinâmica Molecular, forças derivadas de campos potenciais, problemas variacionais)

Verlet Pros:

  1. uma ou duas vezes a complexidade de uma etapa de Euler (dependendo do seu sabor de Verlet: posição ou velocidade).
  2. simplético: economiza energia interna
  3. precisão de segunda ordem: muitos jogos não exigem resultados de ponto flutuante de alta precisão e a segunda ordem é mais do que agradável aos olhos em um cenário de jogo (mais: foi usada em uma simulação de cenário que não é de jogo quando foi "descoberta", portanto não é tão ruim)

Contras Verlet:

  1. estável, mas ainda assim: provavelmente o melhor método explícito em termos de estabilidade. Tende a ganhar vantagem quando restrições rígidas são adicionadas ao sistema, permitindo menos dores de cabeça ao implementar restrições projetadas em motores de dinâmica baseados em posição. Ele dispara para o infinito se o sistema for perturbado por grandes forças externas e nenhum amortecimento / atrito for adicionado. Mesmo assim, existem certos limites impostos numericamente ao tamanho das forças internas (mola), mas elas são mais altas, em média, do que o RK4 pode fazer
  2. menor precisão: não é útil se você deseja estimativas de alta precissão
  3. requer, em média, intervalos de tempo menores que o RK4 para algumas simulações (o RK4 se beneficia da precisão e do amortecimento interno)

Usar um sobre o outro depende do cenário. Se rigidez e grandes forças externas e energias virtuais forem um problema, considere outros métodos com a palavra "implícita" em sua descrição / título.


Observe que alguns autores / livros usam o termo Euler semi-implícito para um integrador Euler explícito real chamado método simplético de Euler (ou Euler Cromer) do qual Verlet é realmente derivado. Verlet também é chamado por algumas pessoas de "método de salto". O Velocity Verlet e o método do ponto médio são bastante semelhantes, pois uma estimativa em um intervalo de tempo det + 0.5*dté necessário para uma etapa do tipo preditor-corretor. Os métodos IMEX (implícito-explícito) também são usados ​​para nomear duas abordagens semelhantes, mas não idênticas: separar os cálculos em partes rígidas e não rígidas e usar diferentes integradores (o explícito para não rígido, implícito para rígido) OU resolver a velocidade com uma etapa de atualização implícita e atualize a posição de maneira explícita (este é um método híbrido semi-implícito que se enquadra na classe de métodos IMEX, porque as partes rígidas afetam mais o cálculo da aceleração). Os métodos implícitos são mais complicados e exigem a solução de um sistema de equações não lineares simultâneas para toda a configuração. Métodos implícitos são usados ​​para corpos deformáveis ​​e geralmente não são usados ​​para corpos rígidos dissociados.

Conforme declarado em um dos comentários, se você puder, não use Euler. Use o método do ponto médio, o Euler semi-implícito ou, à mesma despesa, a posição-Verlet. Todos eles têm precisão um pouco mais alta e sensivelmente mais estabilidade do que o integrador explícito Euler.

Leitura de mini-comparação recomendada :

http://wiki.vdrift.net/Numerical_Integration

Gabriel Conrad
fonte
Uma observação: as duas variantes do Verlet podem ser codificadas para avaliar a aceleração apenas uma vez por atualização de quadro.
Teodron 8/08
1
Obrigado pela resposta! Praticamente o que eu estava procurando.
paldepind
3

As implementações de Euler tendem a ser muito rápidas, mas muito menos estáveis ​​que as alternativas. Runge Kutta é mais lento que Euler, mas muito mais preciso e estável.

Eu não sou muito conhecedor da integração do Verlet, então não tenho idéia de como ele se compara ao Euler e Runge Kutta.

Se você precisa que suas simulações sejam mais exatas, ou mesmo prova numericamente, o Runge Kutta é o melhor dos dois.

Se você precisa de física rápida e de baixo custo para um jogo simples, Euler é a melhor escolha.

Timothy Groote
fonte
2
Runge Kutta é de longe não mais estável que o EULER. É ainda Euler, feito 8 vezes por quadro em vez de 1 (com um pouco de previsão e correção, mas ainda ..) forums.evilmana.com/game-programming-theory/...
teodron
2
Depende do que você precisa para ser 'estável'. talvez eu devesse ter elaborado, runge kutta é numericamente mais estável que euler. farside.ph.utexas.edu/teaching/329/lectures/node35.html
Timothy Groote
3
Tanto quanto posso descobrir, não há razão para que Verlet seja mais lento que Euler. Então, comparado ao Verlet Euler não tem vantagem de velocidade e ainda é muito mais preciso e mais estável. Por isso, acho que sua afirmação de que Euler é melhor para uma física rápida e simples está incorreta.
paldepind
4
Aqui é um blogpost mostrando a grande diferença na precisão: kahrstrom.com/gamephysics/2011/08/03/euler-vs-verlet
paldepind
2
No último nível de Transformers (PS2, 2004), o modelo de voo que implementei utilizou um integrador Euler que atualizei 2000 vezes por quadro. (Claro, era um modelo de vôo bastante realista sendo acelerado para velocidades supersônicas e colocado dentro de um campo de gravidade curvo, de modo que seus requisitos de estabilidade eram bastante intensos. E não havia muito mais intensivo em CPU nesse nível, então Eu fui capaz de me safar). Lançar iterações extras no Euler geralmente é muito mais fácil do que mudar para um iterador diferente.
Trevor Powell
1

Em primeiro lugar, acho que você deve usar o Euler até ter uma necessidade direta de usar um esquema de integração mais avançado. É rápido e fácil de implementar.

Se você tiver problemas de estabilidade, como sistemas de molas que nunca param, ou se sua simulação exigir um alto nível de precisão, comece a experimentar com os outros.

Um que eu não vi mencionado acima é o método do ponto médio, que é muito fácil de implementar e requer apenas uma etapa extra de integração.

Mikael Högström
fonte
1
Acho Verlet é apenas um simples e fácil de implementar
paldepind
Eu nunca o usei, mas pelo que entendi, você provavelmente está correto.
Mikael Högström 09/08/12