Simulation 2D de collision de corps (détection de collision rapide pour un grand nombre de balles)

Question

Je veux écrire un programme pour simuler un mouvement de nombre élevé (N = 1000 - 10^5 et plus) de corps (cercles) sur 2D avion. Tous les corps ont une taille égale et la seule interaction entre eux est une collision élastique. Je veux obtenir quelque chose comme mais à plus grande échelle, avec plus de balles et de remplissage plus dense de l'avion (pas un modèle de gaz comme ici, mais comme un modèle d'eau bouillante).

Donc, je veux une méthode de détection rapide que le numéro de boule i ait une autre bille sur son chemin dans un rayon de 2 * rayon + distance V * delta_t. Je ne veux pas faire une recherche complète de collision avec N balles pour chacune des balles i. (Cette recherche sera N^2.)

PS Désolé pour GIF en boucle d'animation. Appuyez simplement sur Echap pour l'arrêter. (Ne fonctionnera pas dans Chrome).

Answer 1

Cette première étape de la simulation physique est la détection de collision en phase large. Il existe plusieurs approches décrites ici http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html mais les deux bases sont le partitionnement spatial, divisant les objets en une grille, ou tri-et-balayage, qui consiste à trier tous les objets le long de deux axes.

Answer 2

Évidemment, vous voulez éviter les vérifications (N1 -) * N pour les collisions avec chaque itération. Une approche simple consisterait à diviser la zone en une grille de cellules 2D, puis à faire un seul passage pour déterminer les cellules que chaque boule traverse dans l'itération en cours. Chaque balle ne vérifie ensuite que les collisions avec les balles traversant les cellules qu'elle traverse.

Je suis sûr qu'il existe des approches plus sophistiquées, mais cela pourrait être un bon début.

Answer 3

La largeur/longueur de la grille doit être supérieure ou égale à leur rayon et la recherche doit se faire sur les premiers voisins (8 + centre = 9 grilles). Avec une taille de grille minimale, il faut dix à quinze fois plus de calculs de nombre de particules.