Chocs entre N particules



Théorie des chocs :

Afin de détecter un choc, un algorithme simple a tout d'abord été utilisé. Il consiste à faire avancer les billes en utilisant un schéma d'Euler, c'est à dire que les billes avancent par « tics » de V*dt à chaque pas de temps, puis à tester toutes les billes 2 à 2 afin de savoir s'il faut traiter un choc ou pas. Seulement, 2 problèmes ont été rencontrés en utilisant cet algorithme :
les billes avançant par « tics », elles se chevauchent régulièrement lors de la détection et de la résolution du choc, introduisant ainsi un biais quasi-systématique sur cette dernière.
La complexité de cet algorithme de détection étant importante (N²), les ordinateurs n'étaient pas capables de résoudre le problème (sans ralentissements) pour plus d'une vingtaine de billes, ce qui est insuffisant pour faire des statistiques.



Afin de contourner ce problème, un algorithme optimisé et également plus précis de détection des chocs à été mis en place. Le premier problème cité ci-dessus a été contourné de la manière suivante :
soit la distance entre 2 billes R et S :

On sait que X(t) = X(0) + Vt.
En injectant ceci, et en posant que :


on obtient alors le système suivant :


avec sa solution :


pour




ainsi, on peut calculer la position exacte des billes avant de résoudre le choc, et donc s'affranchir de la première difficulté citée ci-dessus.

D'autre part, à la place de tester les billes 2 à 2 comme précédemment, on divise l'espace en une sorte de matrice, et on ne teste les collisions que sur les plus proches voisins (voir figure ci-dessous) :

FIGURE

on réduit de cette manière énormément la complexité de l'algorithme de détection, et on peut passer de 20 billes à 1000 billes, ce qui est un progrès colossal, permettant maintenant de faire des statistiques. Voici quelques détails sur cet algorithme :
On divise l'espace en sous-espaces de dimensions DmaxX, dMaxY, avec :
et .

Ces grandeurs ne sont pas déterminées au hasard, elles représentent respectivement la distance maximale que peut parcourir une bille sur l'axe x et sur l'axe y.
On tient ensuite à jour, dans chaque sous espace, un tableau contenant toutes les billes qui s'y trouvent. On ne teste alors ensuite que les sous-espaces voisins de la bille considérée, économisant alors une quantité de test énorme dès lors que le nombre de billes grandit.




Résolution des chocs :

on cherche dans cette partie à déterminer la vitesse des 2 billes après un choc, en fonction de celle-ci avant ce même choc. Pour ce faire, on utilise la conservation de l'énergie cinétique, ainsi que la conservation de la quantité de mouvement sur l'axe n reliant le centre des 2 billes (voir figure ci-dessous) :

En déroulant les calculs, on obtient finalement les relations suivantes (dans le repère du laboratoire) :



.