Mouvements de cercles

Bonjour,
Comme le laisse entendre le titre de ce post, mon problème est comment concevoir "logiquement" le mouvements de cercles "solides", c'est à dire ne pouvant se supersposer, dans un espace 2D.
Tester une intersection de deux cercles est simple a réaliser étant donné qu'il faut juste tester que la distance entre les centres des deux cercles considérés ne soit pas inferieur à la somme des deux rayons.
Mon problème n'est pas de calculer si il y a intersection mais plutot de comprendre comment cela rentre dans un algorithme de mouvement.
Je possede des cercles Ci caracterisés par leur deplacement tour-à-tour di, je calcule les di en fonction des contraintes que je souhaite mais après cela bloque... Le methode la plus simple serait de déplacerles cercles "un par un", en considerant que un seul bouge alors que les autres sont fixes... Cela est en effet plus simple à coder et ne doit pas etre visible si on prends des di suffisement petits mais c'est moins proches de la réalité. Ainsi j'aimerais deplacer chaque cercle en considerant que tous les autres bouges mais la je n'arrive pas à concevoir comment il faut faire..., il faudrait decomposer mes di en "ddi", puis avancer ddi par ddi en utilisant la première methode. :?
Mon problème est du au fait des collisions mais di risquent de changer... Comment cela est programmé généralement?

On pourrait aussi ne pas modifier les di mais en gros tester a chaque tour :
si collisions ->di du au rebond
sinon di normal sans post-test de collisions...
Cependant cette methode implique que mes cercles sont parfois collisés et si jamais mes di deviennent trop grand il se pourrait que des cercles se traversent sans problème...

En fait ce que je voudrais c'est éviter de devoir faire le test pour chaque cercle avec tous les autres cercles (soit n² tests) mais je ne vois pas comment faire autrement.

J'imagine que si on est habitué à gérer le déplacement d'objet mon problème doit etre trivial, mais moi je seche...
Si quelqu'un peut peut me donner des éléments de reponse, un debut de résolution ou des conseils, je lui en serait res reconnaissant. :D
D'avance merci

En connaissant les vecteurs vitesses et les positions courants, il est facile de calculer la date de la prochaine collision: tu calcules les dates des collisions éventuelles entre chaque paire de disque et tu prends la plus petite en O(n²).

Donc tu peux faire les mouvements jusqu'à cet instant sans aucun test.
Au moment de la collision, tu mets à jour les vecteurs vitesse des deux disques qui se rencontrent et tu calcules la date de la prochaine collision.

Pour cela, tu peux soit refaire le calcul complet en O(n²) soit stocker pour chaque disque la date de sa prochaine collision. En utilisant ces informations stockées, tu as juste à mettre à jour la date des collisions des deux disques qui viennent de se rencontrer, ce qui se fait en O(n).

Une fois, la date de la prochaine collision calculée, tu peux encore faire l'animation jusqu'à cette date sans aucun test.

Les positions courantes, je les ai cela est sur. En ce qui concerne les vecteurs vitesses, cela est moins evident. Je n'ai pas enocre codé leur calculs mais elles pourraient etre la résultante d'une acceleration, de forces et de variables plus ou moins aléatoires, dont notamment les rebonds qui introduiraient une nouvelle force. (Et l'utilisateut qui pourrait bouger mes cercles à la souris, ou au moins rajouter une force non négligeable.) Ainsi je dispose du vecteur vitesse à l'instant de ma boucle mais pas plus loin...

Citation:

---

il est facile de calculer la date de la prochaine collision

---

J'avoue que je ne sais pas comment... Faire ddi par ddi et tester à chaque fois d>r1+r2? Il n'y a pas mieux?

Sinon je comprends ta logique qui est pas mal :

Je dispose de n cercles notés Ci (0<=i<n), leurs vecteurs vitesses étant Di. Di me permet de connaitre la droite de propagation de mon cercle Ci, calculer l'intersection des droites ne devrait pas poser de problèmes mais en considerant à la fois le temps (les droites peuvent se croiser mais cela ne signifie pas que les cercles se rencontrent) et le rayon des cercles, je ne sais pas. A la fain de ce calcul, pour un cercler Ci je dispose de n Tij, temps avant la collision avec un autre cercle Cj, je dois donc prendre le plus petit de ceux ci que je nomerais Ti, et de meme je prend le min des Ti et j'obtiens la temps d'animation sans collisions. J'anime j'usqu'à ce moment la puis seulement les vecteurs vitesse des 2 atomes qui se rencontre changent. Il me reste donc à recalculer les l'ensemble des Tij i etant une des valeurs definissant le couple des cercles qui se sont rencontrés. Et je recommence à chercher le min(min(Tij)) et ainsi de suite...

Mais c'est vrai que si mon vecteur vitesse varie en fonction du temps, je ne vois pas comment faire...
Remarque : à part le calcul que je n'ai pas compris dans cette methode, cette methode parait très bien pour simuler une application type billard.

On m'a parlé d'utilisation de graphe mais vu que je ne sais pas ce que c'est, je ne sais pas non plus en quoi cela pourrait m'aider... Enfin... Si quelqu'un a une idée pour limiter de meme les tests, avec ceci ou une autre methode, il est le bienvenu. :D

Citation:

---

Envoyé par TabrisLeFol

Citation:

---

il est facile de calculer la date de la prochaine collision

---

J'avoue que je ne sais pas comment... Faire ddi par ddi et tester à chaque fois d>r1+r2? Il n'y a pas mieux?

---

Eh oui... J'avais supposé que les vecteurs vitesse sont constant, ce qui permet d'aboutir à une équation du second degré.
Si tu ne peux pas mettre en équation ton mouvement, c'est effectivement plus difficile et on risque effectivement d'être obligé de faire de la simulation numérique en avançant par petits ddi... Tout va donc dépendre de ce que tu peux obtenir pour estimer ton mouvement. Et là c'est de la mécanique!

Citation:

---

Envoyé par TabrisLeFol

On m'a parlé d'utilisation de graphe mais vu que je ne sais pas ce que c'est, je ne sais pas non plus en quoi cela pourrait m'aider... Enfin... Si quelqu'un a une idée pour limiter de meme les tests, avec ceci ou une autre methode, il est le bienvenu. :D

---

Je ne suis pas convaincu que les graphes puissent t'aider. Tu pourrais peut-être regarder du côté de la géométrie algorithmique mais il s'agit de résultats déjà avancés (qu'on trouve dans les revues scientifiques mais pas dans les bouquins d'introduction en français).

Si je comprends bien , il ne s'agit pas d'un simple billard (où les boules se déplacent grosso modo en ligne droite, encore qu'avec les effets qu'on peut leur donner...). Tu envisages donc que les accélérations des cercles soient donnés d'une façon assez générale (loi de la mécanique, frottements, actions de l'utilisateur, redynamisation lors du rebond comme dans un flipper ...)

Je crois qu'il faut considérer l'ensemble de tous les cercles comme un seul système physique. Si tu traites les cercles un par un tu vas probablement faire quelquechose de foireux sur le plan de la physique. Comme on l'a discuté dans l'autre fil 'Euler/Runge-Kutta' sur ce même forum, il semble raisonnable d'utiliser RK4. La position du système (pour n cercles) est définie par 2n coordonnées. Il faut donc pour abaisser le degré de l'équation différentielle à 1 et pouvoir utiliser RK4 utiliser 4n coordonnées (espace + vitesse). Tu auras donc une équation différentielle d'ordre 1 dont la fonction inconnue est à valeurs dans R^(4n).

L'avantage (comme déjà expliqué dans l'autre fil) c'est que cette méthode te donne aussi les vitesses, et te permet donc de calculer les rebonds. Il me semble difficile de prévoir les collisions. Il faut simplement les attendre, et tester à chaque pas de RK4. Si le nombre de cercles est raisonnable, ça devrait aller.

Ok, merci. Je vais par commencer par tester une sorte de billard (Choc de particules sans pertes d'energies), en utilisant pour cela Somme(F) = ma. Puis je complexifierais et je vous ferais part de mes resultats...