La détection de collision est-elle toujours O (n ^ 2)?

14

Le moteur physique est-il capable de réduire cette complexité, par exemple en regroupant des objets proches les uns des autres et en vérifiant les collisions à l'intérieur de ce groupe plutôt que contre tous les objets? (par exemple, des objets éloignés peuvent être supprimés d'un groupe en regardant sa vitesse et sa distance par rapport à d'autres objets).

Sinon, cela rend-il la collision triviale pour les sphères (en 3D) ou les disques (en 2D)? Dois-je faire une double boucle ou créer un tableau de paires à la place?

EDIT: Pour un moteur physique comme bullet et box2d, la détection de collision est-elle toujours O (N ^ 2)?

jokoon
la source
12
Deux mots: partitionnement spatial
MichaelHouse
1
Tu paries. Je crois que les deux ont des implémentations de SAP ( Sweep and Prune ) (entre autres) qui est un algorithme O (n log (n)). Recherchez «Détection de collision à large phase» pour en savoir plus.
MichaelHouse
2
@ Byte56 Sweep and Prune a la complexité O (n log (n)) uniquement si vous devez trier chaque fois que vous testez. Vous voulez garder une liste triée d'objets et chaque fois que vous en ajoutez un, il vous suffit de la trier au bon endroit O (log (n)) donc vous obtenez O (log (n) + n) = O (n). Cela devient très compliqué quand les objets commencent à bouger!
MartinTeeVarga
1
@ SM4, si les mouvements est limité, quelques passes de tri à bulles peuvent prendre soin de cette (marquer seulement les objets déplacés et de les déplacer vers l' avant ou vers l' arrière dans le tableau jusqu'à ce qu'ils soient triés juste regarder pour d' autres objets de mouvement.
cliquet monstre

Réponses:

14

La division spatiale est toujours O (N ^ 2) dans le pire des cas et c'est à cela que sert la complexité de l'informatique.

Cependant il existe des algorithmes qui fonctionnent en temps linéaire O (N) . Tous sont basés sur une sorte de ligne de balayage.

Fondamentalement, vous devez trier vos objets selon une seule coordonnée. Disons X. Si vous effectuez le tri à chaque fois avant la détection de collision, la complexité sera O (N * logN). L'astuce consiste à trier uniquement lorsque vous ajoutez des objets à la scène et plus tard lorsque quelque chose change dans la scène. Le tri après mouvement n'est pas anodin. Voir l'article lié ci-dessous pour un algorithme qui prend en mouvement et fonctionne toujours en temps linéaire.

Ensuite, vous balayez de gauche à droite. Chaque fois que votre ligne de balayage traverse le début d'un objet, vous le placez dans une liste temporaire. Chaque fois que votre ligne de balayage quitte l'objet, vous le retirez de la liste. Vous ne considérez les collisions qu'à l'intérieur de cette liste temporaire.

La ligne de balayage naïf est également O (N ^ 2) dans le pire des cas (vous faites en sorte que tous les objets s'étendent sur toute la carte de gauche à droite), mais vous pouvez la rendre O (N) en la rendant plus intelligente (voir le lien ci-dessous). Un très bon algorithme sera assez complexe.

Voici un schéma simple du fonctionnement de la ligne de balayage:

Algorithme de ligne de balayage

La ligne passe de gauche à droite. Les objets sont triés par coordonnée X.

  • Premier cas: les deux premiers objets sont vérifiés. Rien d'autre ne compte.
  • Deuxième cas: le premier objet a été vérifié et a disparu de la liste. Deux et trois sont vérifiés.
  • Troisième cas: même si cet objet EST en collision, nous ne vérifions pas.
  • Cas quatre: Parce que nous vérifions dans ce cas!

De tels algorithmes ont une complexité O (C * N) = O (N).

Source: Deux ans de cours de géométrie computationnelle.

Dans la détection de collision, cela est généralement appelé balayage et élagage , mais la famille d'algortithmes de lignes de balayage est utile dans de nombreux autres domaines.

Lecture supplémentaire recommandée qui, selon moi, est hors de portée de cette question, mais néanmoins intéressante: Méthodes efficaces de balayage et d'élagage à grande échelle avec insertion et retrait AABB - Cet article présente un algorithme amélioré de balayage et d'élagage qui utilise des boîtes de délimitation alignées sur l'axe (AABB ) avec un tri prenant en compte les mouvements. Algorigthm présenté dans les travaux papier en temps linéaire.


Notez maintenant que c'est le meilleur algorithme en théorie . Cela ne signifie pas qu'il est utilisé. En pratique, l'algorithme O (N ^ 2) avec division spatiale aura de meilleures performances en termes de vitesse dans un cas typique (proche de O (N)) et un besoin supplémentaire de mémoire. En effet, la constante C dans O (C * N) peut être très élevée! Comme nous avons généralement suffisamment de mémoire et que les cas typiques ont des objets répartis uniformément dans l'espace - un tel algorithme fonctionnera mieux. Mais O (N) est la réponse à la question d'origine.

MartinTeeVarga
la source
box2d / bullet l'utilise-t-il?
jokoon
3
"Balayer et tailler" est ce que l'on appelle normalement la physique. Une bonne chose est que vous pouvez garder le tri mis à jour à mesure que la simulation avance. De plus, la ligne de balayage dans votre graphique est un peu décalée en termes d'implémentation (bien que pour la théorie) - vous ne feriez qu'itérer les débuts / fins de la boîte, donc vous ne vérifieriez que les collisions potentielles réelles. Vu cette méthode utilisée pour générer des arbres de partitionnement spatial plus capables plutôt qu'utilisée directement aussi.
Sean Middleditch
3
Comme techniquement, il peut en fait y avoir O (N ^ 2) collisions par paires, il n'est pas tout à fait vrai de dire que le balayage et le pruneau sont toujours O (N). Au contraire, la complexité de base de l'algorithme est O (N + c), où c est le nombre de collisions trouvées par l'algorithme - il est sensible à la sortie , tout comme de nombreux algorithmes de coque convexes. (Référence: en.wikipedia.org/wiki/Output-sensitive_algorithm )
Steven Stadnicki
1
Vous devez étayer vos revendications avec certaines publications ou au moins des noms d'algorithmes.
sam hocevar
1
@SamHocevar J'ai ajouté un lien vers un algorithme de balayage et d'élagage vraiment avancé qui fonctionne en temps linéaire avec une ventilation détaillée des constantes. Le fait que les algorithmes soient appelés "Sweep and Prune" était nouveau pour moi, car je n'ai jamais travaillé avec. J'ai utilisé ces algorithmes dans la sélection de cartes (ce qui est une sorte de collision de 1 point avec d'autres objets), donc je viens d'appliquer les connaissances.
MartinTeeVarga
8

Non. La détection de collision n'est pas toujours O (N ^ 2).

Par exemple, disons que nous avons un espace de 100x100 avec des objets de taille 10x10. Nous pourrions diviser cet espace en cellules de 10x10 avec une grille.

Chaque objet peut se trouver dans jusqu'à 4 cellules de la grille (il peut s'insérer directement dans un bloc ou être «entre» les cellules). Nous pourrions garder une liste d'objets dans chaque cellule.

Nous avons seulement besoin de vérifier les collisions dans ces cellules. S'il y a un nombre maximum d'objets par cellule de grille (par exemple, il n'y a jamais plus de 4 objets dans le même bloc), la détection de collision pour chaque objet est O (1) et la détection de collision pour tous les objets est O (N).

Ce n'est pas le seul moyen d'éviter la complexité O (N ^ 2). Il existe d'autres méthodes, plus adaptées à d'autres cas d'utilisation - utilisant souvent des structures de données basées sur des arbres.

L'algorithme que j'ai décrit est un type de partitionnement d'espace , mais il existe d'autres algorithmes de partitionnement d'espace. Voir Types de structures de données de partitionnement d'espace pour plus d'algorithmes qui évitent la complexité temporelle O (N ^ 2).

Les mécanismes de prise en charge Box2D et Bullet réduisent le nombre de paires vérifiées.

Du manuel , section 4.15:

Le traitement des collisions dans une étape physique peut être divisé en phase étroite et phase large. Dans la phase étroite, nous calculons les points de contact entre des paires de formes. Imaginez que nous ayons N formes. En utilisant la force brute, nous aurions besoin d'effectuer la phase étroite pour N * N / 2 paires.

La classe b2BroadPhase réduit cette charge en utilisant une arborescence dynamique pour la gestion des paires. Cela réduit considérablement le nombre d'appels en phase étroite.

Normalement, vous n'interagissez pas directement avec la phase large. Au lieu de cela, Box2D crée et gère une large phase en interne. De plus, b2BroadPhase est conçu avec la boucle de simulation de Box2D à l'esprit, il n'est donc probablement pas adapté à d'autres cas d'utilisation.

Du Bullet Wiki :

Il existe différents types d'algorithmes à large phase qui améliorent l'algorithme naïf O (n ^ 2) qui renvoie simplement la liste complète des paires. Ces larges séquences optimisées introduisent parfois encore plus de paires sans collision, mais cela est compensé par leur temps d'exécution généralement amélioré. Ils ont des caractéristiques de performance différentes et aucune ne surpasse les autres dans toutes les situations.

Arbre AABB dynamique

Ceci est implémenté par la btDbvtBroadphase dans Bullet.

Comme son nom l'indique, il s'agit d'un arbre AABB dynamique . Une caractéristique utile de cette large phase est que la structure s'adapte dynamiquement aux dimensions du monde et de son contenu. Il est très bien optimisé et une très bonne large portée générale. Il gère des mondes dynamiques où de nombreux objets sont en mouvement, et l'ajout et la suppression d'objets sont plus rapides que SAP.

Balayer et tailler (SAP)

Dans Bullet, il s'agit de la gamme de classes AxisSweep. Il s'agit également d'une bonne large portée à usage général, avec une limitation qui nécessite une taille mondiale fixe, connue à l'avance. Cette phase large a les meilleures performances pour les mondes dynamiques typiques, où la plupart des objets ont peu ou pas de mouvement. BtAxisSweep3 et bt32AxisSweep3 quantifient les points de début et de fin pour chaque axe sous forme d'entiers au lieu de nombres à virgule flottante, pour améliorer les performances.

Le lien suivant est une introduction générale à la large bande et également une description de l'algorithme de balayage et d'élagage (bien qu'il l'appelle "Trier et balayer"):

http://www.ziggyware.com/readarticle.php?article_id=128

Jetez également un œil à la page wikipedia:

http://en.wikipedia.org/wiki/Sweep_and_prune

luiscubal
la source
Certains liens vers des questions similaires et des ressources externes en feraient une excellente réponse.
MichaelHouse
3
C'est faux. Vous obtenez toujours O (N ^ 2). Ce sera beaucoup plus rapide, quelque chose comme N ^ 2/100, mais toujours N ^ 2. Pour preuve, considérez simplement que tous les objets se trouvent dans une seule cellule.
MartinTeeVarga
4
@ sm4 C'est le pire des cas O (N ^ 2), ce qui est en effet ce qui se passe si tous les objets sont dans une cellule. Cependant, dans un moteur physique, les objets ne seront généralement pas dans une seule cellule. Dans mon exemple, aucun objet ne peut jamais partager la même cellule avec plus de 3 autres objets. Ce serait ce qui se passe dans un moteur physique pour des objets "normaux" (et par "normal" je veux dire "pas seulement un capteur").
luiscubal
Je pense que votre algorithme nécessiterait de vérifier les 8 cellules autour, pas seulement les 4 cellules.
jokoon
6
@luiscubal La complexité est toujours le «pire des cas». En théorie, vous recherchez une complexité "garantie". C'est la même chose avec quicksort, qui est O (N ^ 2) et mergesort, qui est O (N * logN). Quicksort fonctionne mieux sur des données réelles et a une exigence spatiale moindre. Mais mergesort a garanti une meilleure complexité. Si vous devez vérifier quelque chose, utilisez mergesort. Si vous devez trier quelque chose, utilisez le tri rapide.
MartinTeeVarga
2

O (N ^ 2) fait référence au fait que si vous avez N objets, déterminer ce qui entre en collision avec ce qui est, dans le pire des cas , N ^ 2 calculs de collision. Disons que vous avez 3 objets. Pour trouver "qui frappe qui", vous devez trouver:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

C'est 6 contrôles pour les collisions, ou N * (N-1) contrôles. En analyse asymptotique, nous élargirions le polynôme et nous approcherions comme O (N ^ 2). Si vous aviez 100 objets, ce serait 100 * 99, ce qui est assez proche de 100 * 100.

Donc, si vous partitionnez l'espace en utilisant un octree par exemple, le nombre moyen de comparaisons entre les corps est réduit. S'il est possible que tous les objets se rassemblent dans une très petite zone (par exemple, si vous faites une sorte de simulation de flux de particules, où les particules peuvent se rassembler dans la même zone), alors l'O (N ^ 2) peut toujours se produire à points dans la simulation (à quels points vous verrez un ralentissement).

Donc, le point entier de O (N ^ 2) est dû à la nature de chaque corps vérifiant tous les autres corps de la scène. C'est juste la nature du calcul. Beaucoup de choses peuvent aider à rendre cela moins cher. Même un graphique de scène (par exemple, la détection entre des objets dans la même pièce uniquement) réduira considérablement le nombre de calculs de collision à effectuer, mais ce sera toujours O (M ^ 2) (où M est le nombre d'objets dans la pièce à contre laquelle une collision a été détectée). Les volumes englobants sphériques rendent la vérification initiale très rapide ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS), donc même si la détection de collision est O (N ^ 2), les calculs de la sphère englobante sont susceptibles de se produire très rapidement.

bobobobo
la source
Il n'est pas nécessaire de prendre la vérification de la force brute comme référence: indépendamment des algorithmes intelligents, N objets peuvent chacun entrer en collision avec tous les autres objets, ce qui donne O (N ^ 2) collisions qui nécessitent un travail O (N ^ 2) pour être traité. Les bons algorithmes ne peuvent faire mieux que lorsqu'il y a moins de collisions.
Lorenzo Gatti