Détection des collisions entre un grand nombre de cercles

Question

Quelle est la meilleure façon de vérifier la collision d'un grand nombre de cercles ?
Il est très facile de détecter une collision entre deux cercles, mais si l'on vérifie chaque combinaison, c'est O(n 2 ) ce qui n'est certainement pas une solution optimale.

Nous pouvons supposer que l'objet cercle a les propriétés suivantes :

• Coordonnées
• Rayon
• Vélocité
• Direction

La vitesse est constante, mais la direction peut changer.

J'ai proposé deux solutions, mais il en existe peut-être de meilleures.

Solution 1
Divisez l'espace entier en carrés qui se chevauchent et vérifiez la collision uniquement avec les cercles qui se trouvent dans le même carré. Les carrés doivent se chevaucher pour qu'il n'y ait pas de problème lorsqu'un cercle se déplace d'un carré à l'autre.

Solution 2
Au début, les distances entre chaque paire de cercles doivent être calculées.
Si la distance est faible, ces paires sont stockées dans une liste, et nous devons vérifier la collision à chaque mise à jour.
Si la distance est grande, nous stockons après quelle mise à jour il peut y avoir une collision (elle peut être calculée car nous connaissons la distance et les vitesses). Cela doit être stocké dans une sorte de file d'attente prioritaire. Après le nombre de mises à jour calculé précédemment, la distance doit être vérifiée à nouveau, puis nous procédons de la même manière : nous la plaçons sur la liste ou dans la file d'attente prioritaire.

Réponses aux questions de Mark Byers

1. C'est pour un jeu ?
   Il s'agit d'une simulation, mais elle peut également être traitée comme un jeu.
2. Voulez-vous recalculer la nouvelle position toutes les n millisecondes, et vérifier également les collisions à ce moment-là ?
   Oui, le temps entre les mises à jour est constant.
3. Voulez-vous trouver l'heure à laquelle la première/toutes les collisions se produisent ?
   Non, je veux trouver chaque collision et faire "quelque chose" quand elle se produit.
4. Quelle est l'importance de la précision ?
   Cela dépend de ce que vous entendez par précision. Je dois détecter toutes les collisions.
5. Est-ce un gros problème si de très petits cercles en mouvement rapide peuvent se croiser occasionnellement ?
   On peut supposer que la vitesse est si faible qu'elle ne se produira pas.

Answer 1

Il y a " indice spatial Les structures de données "Quadtree", "r-tree" et "kd-tree" sont des exemples de structures de données permettant de stocker vos cercles pour une comparaison rapide ultérieure.

La solution 1 semble être un index spatial, et la solution 2 bénéficierait d'un index spatial chaque fois que vous recalculez vos paires.

Pour compliquer les choses, vos objets sont en mouvement - ils ont une vitesse.

Il est normal d'utiliser des index spatiaux pour les objets dans les jeux et les simulations, mais surtout pour les objets stationnaires, et généralement les objets qui ne réagissent pas à une collision en se déplaçant.

Il est normal dans les jeux et tels que vous calculez tout à des intervalles de temps définis (discrets), il se peut donc que deux objets se croisent mais que vous ne le remarquiez pas parce qu'ils se sont déplacés très rapidement. En fait, de nombreux jeux n'évaluent même pas les collisions dans un ordre chronologique strict. Ils ont un index spatial pour les objets stationnaires, par exemple les murs, et des listes pour tous les objets en mouvement qu'ils vérifient de manière exhaustive (bien qu'avec des vérifications discrètes relaxées comme je l'ai souligné).

La détection précise des collisions en continu et de la réaction des objets aux collisions dans les simulations est généralement beaucoup plus exigeante.

L'approche par paire que vous avez décrite semble prometteuse. Vous pourriez conserver les paires triées par collision suivante, et les réinsérer lorsqu'elles sont entrées en collision dans les nouvelles positions appropriées. Il suffit de trier la nouvelle liste de collisions générée (O(n lg n)) pour les deux objets, puis de fusionner deux listes (les nouvelles collisions pour chaque objet, et la liste de collisions existante ; en insérant les nouvelles collisions, en supprimant les collisions périmées qui listaient les deux objets qui sont entrés en collision), ce qui est O(n).

Une autre solution consiste à adapter votre index spatial pour stocker les objets non pas strictement dans un secteur, mais dans chacun de ceux qu'ils ont traversés depuis le dernier calcul, et à faire les choses de manière discrète. Cela implique de stocker les objets en mouvement rapide dans votre structure spatiale, et vous devrez l'optimiser pour ce cas.

Rappelez-vous que les listes liées ou les listes de pointeurs sont très mauvais pour la mise en cache sur les processeurs modernes. Je vous conseille de stocker des copies de vos cercles - leurs propriétés importantes pour la détection des collisions en tout cas - dans un tableau (mémoire séquentielle) dans chaque secteur de n'importe quel index spatial, ou dans les paires que vous avez décrites ci-dessus.

Comme Mark le dit dans les commentaires, il pourrait être assez simple de paralléliser les calculs.

Answer 2

Je suppose que vous faites une simple simulation de dynamique moléculaire sur une sphère dure, n'est-ce pas ? J'ai rencontré le même problème à plusieurs reprises lors de simulations Monte Carlo et de simulations de dynamique moléculaire. Vos deux solutions sont très souvent mentionnées dans la littérature sur les simulations. Personnellement, je préfère solution 1 mais légèrement modifié.

Solution 1
Divisez votre espace en cellules rectangulaires qui ne se chevauchent pas. Ainsi, lorsque vous vérifiez la collision d'un cercle, vous recherchez tous les cercles à l'intérieur d'une cellule où se trouve votre premier cercle, et vous recherchez X cellules dans chaque direction autour. J'ai essayé plusieurs valeurs de X et j'ai trouvé que X=1 est la solution la plus rapide. Vous devez donc diviser l'espace en cellules de taille égale dans chaque direction :

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

Le diviseur doit être supérieur à 3, sinon il provoquera des erreurs (s'il est trop petit, vous devez agrandir votre boîte de simulation).
Alors votre algorithme ressemblera à ceci :

1. Placez tous les cercles à l'intérieur de la boîte
2. Créer une structure cellulaire et stocker des index ou des pointeurs vers des cercles à l'intérieur d'une cellule (sur un tableau ou sur une liste).
3. Faites un pas dans le temps (déplacez tout) et mettez à jour les positions des cercles dans les cellules.
4. Cherchez la collision autour de chaque cercle. Vous devez vérifier une cellule autour dans chaque direction
5. S'il y a une collision - faites quelque chose
6. Allez à 3.

Si tu l'écris correctement, alors tu auras quelque chose sur O(N) complexité, car le nombre maximal de cercles à l'intérieur de 9 cellules (en 2D) ou de 27 cellules (en 3D) est constant pour tout nombre total de cercles.

Solution 2
Habituellement, cela se fait de la manière suivante :

1. Pour chaque cercle, créez une liste des cercles qui sont à distance R < R_max , calculer le temps après lequel nous devrions mettre à jour les listes (quelque chose au sujet de T_update = R_max / V_max ; où V_max est la vitesse maximale du courant)
2. Faire un pas dans le temps
3. Vérifier la distance de chaque cercle avec les cercles de sa liste
4. S'il y a une collision - faites quelque chose
5. Si le temps actuel est plus grand, alors T_update passez à 1.
6. Sinon, passez au point 2.

Cette solution avec des listes est très souvent améliorée en ajoutant une autre liste avec R_max_2 > R_max et avec sa propre T_2 le temps d'expiration. Dans cette solution, cette deuxième liste est utilisée pour mettre à jour la première liste. Bien sûr, après T_2 vous devez mettre à jour toutes les listes, ce qui est O(N^2) . Soyez également prudent avec ceci T y T_2 car si la collision peut changer la vitesse, ces temps changeront. De même, si vous introduisez des forces dans votre système, cela entraînera également un changement de vitesse.

Solution 1+2 Vous pouvez utiliser des listes pour la détection des collisions et des cellules pour la mise à jour des listes. Dans un livre, il est écrit que c'est la meilleure solution, mais je pense que si vous créez de petites cellules (comme dans mon exemple) alors solution 1 est meilleur. Mais c'est mon opinion.

Autre chose
Vous pouvez également faire d'autres choses pour améliorer la vitesse de la simulation :

1. Quand vous calculez la distance r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) vous n'avez pas besoin de faire l'opération racine carrée. Vous pouvez comparer r^2 à une certaine valeur - c'est bon. Vous n'avez pas non plus à faire tout (x1-x2)*(x1-x2) (je veux dire, pour toutes les dimentions), car si x*x est plus grande que certains r_collision^2 alors tous les autres y*y et ainsi de suite, résumées, seraient plus grandes.
2. La méthode de dynamique moléculaire est très facile à paralléliser. Vous pouvez le faire avec des threads ou même sur GPU. Vous pouvez calculer chaque distance dans différents threads. Sur GPU, vous pouvez facilement créer des milliers de threads presque sans coût.

Pour les sphères dures, il existe également un algorithme efficace qui ne fait pas de pas dans le temps, mais qui recherche la collision la plus proche dans le temps et saute à ce moment-là pour mettre à jour toutes les positions. Cela peut être intéressant pour les systèmes peu denses où les collisions ne sont pas très probables.

Answer 3

Une technique possible est d'utiliser le triangulation de Delaunay au centre de vos cercles.

considérez le centre de chaque cercle et appliquez la triangulation delaunay. cela va tesseler votre surface en triangles. cela vous permet de construire une graphique où chaque nœud stocke le centre d'un triangle, et chaque arête se connecte au centre d'un cercle voisin. La tesselation opérée ci-dessus limitera le nombre de voisins à une valeur raisonnable (6 voisins en moyenne).

maintenant, lorsqu'un cercle se déplace, vous avez un ensemble limité de cercles à prendre en compte pour la collision. vous devez alors appliquer à nouveau la tesselation à l'ensemble des cercles qui sont touchés par le déplacement, mais cette opération n'implique qu'un très petit sous-ensemble de cercles (les voisins du cercle qui se déplace, et certains voisins des voisins).

la partie critique est la première tesselation, qui prendra un certain temps à réaliser, les tesselations ultérieures ne sont pas un problème. et bien sûr vous avez besoin d'une implémentation efficace d'un graphe en terme de temps et d'espace...

Answer 4

Subdivisez votre espace en régions et tenez une liste des cercles qui sont centrés dans chaque région.

Même si vous utilisez un schéma très simple, comme placer tous les cercles dans une liste, triés par centre.x, vous pouvez accélérer les choses massivement. Pour tester un cercle donné, il suffit de le tester par rapport aux cercles situés de part et d'autre de lui dans la liste, jusqu'à ce que vous en atteigniez un dont la coordonnée x est supérieure à rayon loin.

Answer 5

Vous pourriez créer une version 2D d'un "arbre à sphères", qui est un cas particulier (et très facile à mettre en œuvre) de l'"indice spatial" proposé par Will. L'idée est de "combiner" des cercles dans un cercle "contenant" jusqu'à obtenir un seul cercle qui "contient" le "grand nombre de cercles".

Juste pour montrer la simplicité du calcul d'un "cercle contenant" (au sommet de ma tête) : 1) Additionner les centres des deux cercles (sous forme de vecteurs) et les mettre à l'échelle 1/2, ce qui donne le centre du cercle contenant. 2) Soustraire les centres des deux cercles (sous forme de vecteurs), ajouter les rayons et les mettre à l'échelle par 1/2, c'est le rayon du cercle contenant.