Intégration de Runge-Kutta (RK4) pour la physique des jeux

Gaffer on Games a un excellent article sur l’utilisation de l’ intégration RK4 pour améliorer la physique des jeux. La mise en œuvre est simple, mais les maths derrière cela me déconcerte. Je comprends les dérivés et les intégrales au niveau conceptuel, mais je n’ai pas manipulé les équations depuis longtemps.

Voici les conséquences de la mise en œuvre de Gaffer:

void integrate(State &state, float t, float dt) { Derivative a = evaluate(state, t, 0.0f, Derivative()); Derivative b = evaluate(state, t+dt*0.5f, dt*0.5f, a); Derivative c = evaluate(state, t+dt*0.5f, dt*0.5f, b); Derivative d = evaluate(state, t+dt, dt, c); const float dxdt = 1.0f/6.0f * (a.dx + 2.0f*(b.dx + c.dx) + d.dx); const float dvdt = 1.0f/6.0f * (a.dv + 2.0f*(b.dv + c.dv) + d.dv) state.x = state.x + dxdt * dt; state.v = state.v + dvdt * dt; }

Quelqu’un peut-il expliquer en termes simples comment RK4 fonctionne? Plus précisément, pourquoi faisons-nous la moyenne des dérivés à 0.0f , 0.0f , 1.0f? et 1.0f? En quoi la moyenne des dérivées jusqu’au 4ème ordre diffère-t-elle d’une simple intégration euler avec un timestep plus petit?

Après avoir lu la réponse acceptée ci-dessous et plusieurs autres articles, je sais comment fonctionne RK4. Pour répondre à mes propres questions:

Quelqu’un peut-il expliquer en termes simples comment RK4 fonctionne?

RK4 tire parti du fait que nous pouvons obtenir une meilleure approximation d’une fonction si nous utilisons ses dérivées d’ordre supérieur plutôt que la dérivée première ou seconde. C’est pourquoi la série de Taylor converge beaucoup plus rapidement que les approximations d’Euler. (regardez l’animation à droite de cette page)

Plus précisément, pourquoi faisons-nous la moyenne des dérivés à 0.0f , 0.0f , 1.0f et 1.0f ?

La méthode de Runge-Kutta est une approximation d’une fonction qui échantillonne des dérivées de plusieurs points dans un temps, contrairement à la série de Taylor qui échantillonne uniquement les dérivées d’un seul point. Après avoir échantillonné ces dérivés, nous devons savoir comment peser chaque échantillon pour obtenir l’approximation la plus proche possible. Une manière simple de le faire est de sélectionner des constantes qui coïncident avec la série de Taylor, ce qui permet de déterminer les constantes d’une équation de Runge-Kutta.

Cet article l’a rendu plus clair pour moi. Remarquez comment (15) est l’expansion de la série de Taylor alors que (17) est la dérivation de Runge-Kutta.

En quoi la moyenne des dérivées jusqu’au 4ème ordre diffère-t-elle d’une simple intégration euler avec un timestep plus petit?

Mathématiquement, il converge beaucoup plus rapidement que de nombreuses approximations d’Euler. Bien sûr, avec suffisamment d’approximations d’Euler, nous pouvons obtenir une précision égale à RK4, mais la puissance de calcul nécessaire ne justifie pas l’utilisation d’Euler.

Cela peut être un peu trop simplifié en ce qui concerne les mathématiques réelles, mais signifie un guide intuitif de l’intégration de Runge Kutta .

Étant donné une certaine quantité à un moment t1 , nous voulons connaître la quantité à un autre moment t2 . Avec une équation différentielle du premier ordre, on peut connaître le taux de variation de cette quantité à t1 . Il n’y a rien d’autre que nous pouvons savoir avec certitude; le rest devine.

L’intégration d’Euler est la manière la plus simple de deviner: extrapoler linéairement de t1 à t2, en utilisant le taux de variation précisément connu à t1 . Cela donne généralement une mauvaise réponse. Si t2 est loin de t1, cette extrapolation linéaire ne correspondra à aucune courbure dans la réponse idéale. Si nous prenons beaucoup de petits pas de t1 à t2 , nous aurons le problème de la soustraction de valeurs similaires. Les erreurs de roundoffs vont ruiner le résultat.

Nous affinons donc notre proposition. Une façon consiste à aller de l’avant et à faire cette extrapolation linéaire de toute façon, en espérant que ce n’est pas trop loin de la vérité, utilisez l’équation différentielle pour calculer une estimation du taux de variation à t2 . Ceci, moyenné avec le taux de variation (précis) à t1 , représente mieux la pente typique de la réponse vraie entre t1 et t2 . Nous l’utilisons pour effectuer une nouvelle extrapolation linéaire de t1 à t2 . Il n’est pas évident de prendre la moyenne simple ou de donner plus de poids au taux t1 sans faire le calcul pour estimer les erreurs, mais il y a un choix ici. En tout cas, c’est une meilleure réponse qu’Euler donne.

Peut-être mieux, faites notre extrapolation linéaire initiale à un point dans le temps à mi-chemin entre t1 et t2 , et utilisez l’équation différentielle pour calculer le taux de changement. Cela donne une réponse à peu près aussi bonne que la moyenne que nous venons de décrire. Ensuite, utilisez ceci pour une extrapolation linéaire de t1 à t2 , puisque notre but est de trouver la quantité à t2 . C’est l’algorithme du point milieu.

Vous pouvez imaginer, en utilisant l’estimation à mi-parcours du taux de variation, pour effectuer une autre extrapolation linéaire de la quantité de t1 au point médian. Avec l’équation différentielle, on obtient une meilleure estimation de la pente. En utilisant ceci, nous terminons en extrapolant de t1 à t2 où nous voulons une réponse. C’est l’algorithme de Runge Kutta .

Pouvons-nous faire une troisième extrapolation au point médian? Bien sûr, ce n’est pas illégal, mais une parsing détaillée montre une amélioration décroissante, de sorte que d’autres sources d’erreur dominent le résultat final.

Runge Kutta applique l’équation différentielle au point initial t1, deux fois au milieu et une fois au dernier point t2. Les points intermédiaires sont une question de choix. Il est possible d’utiliser d’autres points entre t1 et t2 pour effectuer ces estimations améliorées de la pente. Par exemple, on pourrait utiliser t1 , un point au tiers vers t2, un autre 2/3 vers t2 et à t2 . Les poids pour la moyenne des quatre dérivés seront différents. En pratique, cela n’aide pas vraiment, mais pourrait avoir une place dans les tests, car il devrait donner la même réponse, mais fournir un ensemble différent d’erreurs d’arrondi.

Pour ce qui est de votre question, pourquoi: je me souviens avoir écrit un simulateur de tissu où le tissu était une série de ressorts reliés entre eux par des nœuds. Dans le simulateur, la force exercée par le ressort est proportionnelle à l’étendue du ressort. La force provoque une accélération au niveau du nœud, ce qui provoque une vitesse qui déplace le nœud qui s’étend au spring. Il y a deux intégrales (intégrant l’accélération pour obtenir la vitesse et intégrant la vitesse pour obtenir la position) et si elles sont inexactes, les erreurs font boule de neige: trop d’accélération entraîne trop de vélocité, ce qui provoque encore plus d’accélération instable.

Il est difficile à expliquer sans graphiques, mais je vais essayer: Disons que vous avez f (t), où f (0) = 10, f (1) = 20 et f (2) = 30.

Une intégration correcte de f (t) sur l’intervalle 0

L’intégration de la règle rectangle se rapproche de cette surface avec un rectangle où la largeur est le delta dans le temps et la longueur est la nouvelle valeur de f (t), donc dans l’intervalle 0

Maintenant, si vous deviez tracer ces points et tracer une ligne à travers eux, vous verrez qu’il est réellement sortingangular, avec une surface de 30 (unités), et donc l’intégration d’Euler est inadéquate.

Pour obtenir une estimation plus précise de la surface (intégrale), vous pouvez prendre de plus petits intervalles de t, en évaluant par exemple f (0), f (0.5), f (1), f (1.5) et f (2).

Si vous me suivez toujours, la méthode RK4 est alors simplement un moyen d’estimer les valeurs de f (t) pour t0

(mais comme d’autres l’ont dit, lisez l’article de Wikipedia pour une explication plus détaillée. RK4 est dans la catégorie de l’intégration numérique )

RK4, au sens le plus simple, fait une fonction d’approximation basée sur 4 dérivées et un point pour chaque pas de temps: votre condition initiale au sharepoint départ A, une première pente approximée B basée sur le sharepoint données A à votre pas / 2 pente de A, une troisième approximation C, qui a une valeur de correction pour la pente en B pour refléter les changements de forme de votre fonction, et enfin une pente finale basée sur la pente corrigée au point C.

Donc, fondamentalement, cette méthode vous permet de calculer en utilisant un sharepoint départ, un point milieu moyenné qui a des corrections intégrées aux deux parties pour ajuster la forme et un point final doublement corrigé. Cela fait la consortingbution effective de chaque sharepoint données 1/6 1/3 1/3 et 1/6, donc la plupart de votre réponse est basée sur vos corrections pour la forme de votre fonction.

Il s’avère que l’ordre d’approximation RK (Euler est considéré comme un RK1) correspond à la façon dont sa précision s’échelonne avec des pas de temps plus petits.

La relation entre les approximations RK1 est linéaire, donc pour 10 fois plus de précision, la convergence est environ 10 fois supérieure.

Pour RK4, 10 fois la précision, vous obtenez environ 10 ^ 4 fois plus de convergence. Ainsi, alors que votre temps de calcul augmente linéairement dans RK4, cela augmente votre précision polynomiale.