SIMULATION D'UN BILLARD

Commentaire de Urgo le 30/08/2005 23:00:45

J'ai les boules que tu n'utilises pas le mot "bille".

Commentaire de JCDjcd le 31/08/2005 13:29:20

pas besoin de cours de physique, il n'y a que une seul calcul :
comment calculer les rebonds (les chocs).
Il y a deux quantités qui se conservent :
* l'énergie
* la quantité de mouvement

On a ainsi deux équations.
On se place dans le repere (u,v) avec u unitaire et dirige selon les deux centres des boules, et v l'orthogonal direct et

unitaire de u.
Dans ce repere on va changer les vitesses des deux boules pour simuler le rebond. Seul les vitesses selon u change, les

composantes selon v restent inchangees.
On a :
delta(mA.vA² + mB.vB²) = 0
delta(mA.vA + mB.vB) = 0

la solution est (il suffit de verifier) :
vA(apres) = 2.vG - vA(avant)
vB(apres) = 2.vG - vB(avant)
avec vG la vitesse du centre de gravité

voila les seules equations utilisees

(pour ce qui est de la resolution, physiquement parlant : dans un repere se deplacant a la vitesse du centre de gravité, les

vitesses changent seulement de signes, d'ou le resultat car :
v(apres) = [-(v(avant)-vG)] + vG = 2.vG - v(avant)

Un truc amusant a faire est de mettre 500 boules dans un billards, et cela donne l'effet d'un gaz (analogie non-fortuite) ou

a des abeilles, et je trouve ca beau a voir, essayez donc.

Commentaire de Patrice99 le 01/09/2005 08:45:54

As-tu prévu le cas ou plusieurs boules entrent en collision au meme moment ? j'ai fait un simulateur de gravité dans l'espace, et je n'ai jamais réussit à simuler des chocs parfaits, complètement réalistes : il y a toujours eu des défauts. Je vais regarder ton code.

Commentaire de Patrice99 le 01/09/2005 15:58:23

Oui, je fais la même chose, mais le résultat est décevant dans mon cas, car je simule des orbites parfaitement symétriques : au moindre écart, la symétrie se perd.

Commentaire de Kirua le 03/09/2005 01:32:35

Patrice, tes erreurs proviennent probablement de l'utilisateur de ce qu'on appelle l' "intégreur (ou interpolateur) d'Euler". Tu as sans doute fait un truc du style:

F = ma
A = F/m
v dt = F/m dt

et donc on a qq ch dans le goût de:

nouvelle vitesse = ancienne vitesse + (F/m) * delta temps

avec un delta temps équivalent à l'écart entre deux frames. c'est easy à coder, suffisament précis quand il s'agit de faire du "eye candy" (des jolis effets), mais pour faire une simulation physique, c'est complètement nul :/ tu fais une erreur de l'ordre de delta temps élevé au carré. pour réduire drastiquement l'erreur (due à la discrétisation du temps), tu peux utiliser l'interpolateur de runge-kutta, qui réduit l'erreur à l'ordre de delta temps exposant 5, ce qui est sérieusement plus petit!

Sinon, c'est cool pour la simu de collisions. Perso quand j'ai codé la mienne (ça fait un moment, mais je m'en souviens encore très bien, c'était génial ^^), je n'ai utilisé que des opérations vectorielles, complètement empiriques ("observé" sur des schémas de ma conception), et ça s'est révélé correct (juste pour mentionner le fait que c'est possible, et qu'il ne fait pas forcément faire un changement de repère, ce qui peut être non trivial).

Commentaire de JCDjcd le 03/09/2005 09:55:53

Une seule remarque : ici il n'y a pas de forces, car les boules se deplacent grace a l'intertie : l'acceleration est nulle en dehors des chocs. Pour ce qui est des chocs, il ne faut pas les resourdre avec des equations diferentielles, car le chocs est brutal, donc un force infini sur un temps infinitesimal. Il faut mieux resonner en termes de quantite conservee, et de resourdre le probleme directement au lieu de passer pas des Equa. Diff. ou les erreurs de calculs numeriques seront enormes.

Commentaire de JCDjcd le 03/09/2005 13:21:49

Pour revenir a la detection des collisions :la distance entre deux boules est une fonction quadratique du temps (ou temps les cas degeneres un fonction lineaire). Il suffit de resoudre "distance=somme des deux rayons"
Les erreurs de la resolution interviennent evidemment.
Mais cela n'est pas suffisant, comme tu le faisais remarquer Kirua, il est  aussi preferable de calculer le signe du produit scalaire entre les vitesses et les positions (qui est en fait le coefficient lineaire de l'equation) pour voir si les boules se rapprochent ou s'eloignent. Le probleme est que si la solution est dans le passe, il n'y a pas de collision, par contre dans le futur aucun probleme, mais si elle est exactement au present (i.e. t(chocs) = t(courant) alors il y a un chocs que si les deux boules se rapprochent, i.e. si la derivee est negative, i.e. voir le signe de la quantite du dessus.

Donc la resolution des collisions est en soi pas complique, mais il faut bien faire les calculs sur papier, et surtout prendre en compte le cas t(chocs) = t(courant) car sinon l'algo. se plante, les cas pathologiques sont faciles a trouves.

Commentaire de JCDjcd le 03/09/2005 13:54:40

Tout d'abord je n'utilise pas de pas "dt", en fait j'ai en memoire toutes les collisions possibles (on peut les afficher dans le programme). Je ne garde en memoire que les collisions qui vont se produire dans le present ou dans le futur, ensuite je veux passer par exemple de t=0s a t=10s, alors je prends la premiere collision qui arrivera dans le temps (je prends le minimum dans l'arbre des collisions d'ou l'interet d'avoir une recherche en log(n)) ensuite j'effectue la collision et je recommence jusqu'a temps que j'atteigne 10s.
Mais la difficulte provient du test des collisions : la definition d'une collision est lorsque la distance entre deux boules vaut la somme des deux rayons et que la collision se produise a t>=0, car la resolution de l'equation en t peut avoir comme solution des temps negatifs, donc je ne prends que les cas t>=0, de plus il y a un autre probleme : c'est le cas t=0, car prenons le cas ou deux boules sont initialement collees sans vitesse initiale, alors la resolution donne t=0 car a t=0 la distance vaut bien la somme des deux rayons ! Mais pourtant physiquement il n'y a pas de collision. Il faut etre plus rigoureux sur la definition d'un chocs, il y a chocs que si la distance vaut la somme des deux rayons et que cela se produise a t>=0 ET que la distance diminue, i.e. sa derivee strictement negative. Donc le point crucial est ici. Il faut que ces DEUX conditions soient verifiees pour qu'il est chocs, le cas echeant la collision est enregistree dans l'arbre.

Un cas pathologique est par exemple : plusieurs boules collees et alignees sans vitesse initiale, et on envoie une boule dans l'alignement (comme le celebre jeu des 5 boules dont on lache que celle de l'extremite et seule la boule a l'autre extremite bouge). Alors la on est en plein dans le cas du dessus, et la distinction entre "se rapprochent" et "s'eloigne" est importante.



le fonction pour resoudre une collision est :
//----------------------------------------------------------
// calcul l'eventuelle collision entre deux boules
static BOOL foreseeBetweenTypeCrash(double *pTime,P_BALL B1,P_BALL B2)
{
// somme des deux rayons
double    R;
// difference des deux vitesse
VECT2D    dv;
// difference des deux position
VECT2D    dp0;
// pour la resolution de l'equation
double    a,    // coefficient
          b,    // coefficient
          c;    // coefficient

AssertPointer(pTime);
AssertPointer(B1);
AssertPointer(B2);

// on calcule l'equation
SubVect2D(&dp0,&B2->p0,&B1->p0);
SubVect2D(&dv,&B2->v,&B1->v);
R = B1->r + B2->r;
a = Norm2Vect2D(&dv);
b = 2.*DotProductVect2D(&dp0,&dv);
c = Norm2Vect2D(&dp0) - R*R;
c = max(0.,c); // pour les erreurs de calculs
// on resout l'equation
// * ceci distingue le contact entre deux boules, et le rebond
//   car il peut y avoir contact sans rebond, il n'y a rebond
//   que si les deux boules se rapproche, i.e. la distance diminue
//   i.e. sa derivee est strictement negatif, <b> a le signe
//   de cette derivee
if(b >= 0.)
  return FALSE;
else
// * il y a rebond (pas forcement dans le futur)
  {
  double T1,T2;
  if(resolve(&T1,&T2,a,b,c))
    {
    // si les deux racines sont negatives
    if((T1 < 0.) && (T2 < 0.))
      return FALSE;
    // si les deux racines sont positives
    else if((T1 >= 0.) && (T2 >= 0.))
      return (*pTime = min(T1,T2),TRUE);
    // si les deux racines sont de signes opposes
    else
      return (*pTime = max(T1,T2),TRUE);
    }
  else
    return FALSE;
  }
} // foreseeBetweenTypeCrash()

Commentaire de JCDjcd le 03/09/2005 14:45:41

Effectivement je test toutes les collisions, mais l'algorithme est lineaire car je n'ai que 2.n calculs a faire, en memoire en revanche j'en ai O(n²), mais en realite c'est beaucoup plus petit que cela. L'idee de ne s'interesse qu'au voisinage pour le calcul des chocs est jolie, mais le probleme c'est que mathematiquement, rien ne me dit qu'il n'y aura aucun rebond avec une boule lointaine, car il y a des configurations pathologiques qui existent.
Donc pour le moment je calculs les eventuelles collisions avec TOUTES les autres boules, mais en revanche j'utilise des arbres pour rechecher le minimum.
Donc c'est un logique telle que :
recalculer : O(n)
memoire : O(n²)
minimum : O(log(n))
tout cela dans le pire des cas

Commentaire de gagah1 le 04/09/2005 11:28:06

J'arrive pas à compiler la source ( j'utilise DevC++) , tu pourrais mettre l'exe comme dit Patrice99 en renommant l'extension. Pour voir exactement comment cela donne, et peut etre pour adapter à mon vieux jeu de billard que j'ai programmé il y a si longtemps. Merci

Commentaire de Patrice99 le 04/09/2005 12:59:31

Ça à l'air d'être parfait, il faudrait que je teste le code source avec mon simulateur de gravité qui est chaotique : la moindre erreur de calcul sera amplifiée au bout d'un moment. Tu n'aurais pas envie de faire une version en C# ? Comme ça je pourrais mélanger du VB.Net et du C#...