Détection de collision

(Learn how and when to remove this message)

La détection de collision est le problème informatique consistant à détecter une intersection de deux ou plusieurs objets dans un espace virtuel. Plus précisément, elle traite des questions de savoir si , quand et où deux ou plusieurs objets se croisent. La détection de collision est un problème classique de géométrie computationnelle avec des applications en infographie , simulation physique , jeux vidéo , robotique (y compris la conduite autonome ) et physique computationnelle . Les algorithmes de détection de collision peuvent être divisés en opérant sur des objets spatiaux 2D ou 3D.

Aperçu

La détection de collision est étroitement liée au calcul de la distance entre les objets, car deux objets (ou plus) se croisent lorsque la distance entre eux atteint zéro ou devient même négative. Une distance négative indique qu'un objet a pénétré un autre. La détection de collision nécessite plus de contexte que la simple distance entre les objets.

L'identification précise des points de contact sur les surfaces des deux objets est également essentielle pour le calcul d'une réponse de collision physiquement précise . La complexité de cette tâche augmente avec le niveau de détail des représentations des objets : plus le modèle est complexe, plus le coût de calcul est élevé.

La détection de collision implique souvent des objets dynamiques, ce qui ajoute une dimension temporelle aux calculs de distance. Au lieu de simplement mesurer la distance entre des objets statiques, les algorithmes de détection de collision visent souvent à déterminer si le mouvement des objets les amènera à un moment où leur distance sera nulle, une opération qui ajoute une charge de calcul importante.

Dans la détection de collisions impliquant plusieurs objets, une approche naïve nécessiterait de détecter les collisions pour toutes les combinaisons d'objets par paires. À mesure que le nombre d'objets augmente, le nombre de comparaisons requises augmente rapidement : pour les objets, des tests d'intersection sont nécessaires avec une approche naïve. Cette croissance quadratique rend une telle approche coûteuse en termes de calcul à mesure qu'elle augmente.

En raison de la complexité mentionnée ci-dessus, la détection de collision est un processus à forte intensité de calcul. Néanmoins, elle est essentielle pour les applications interactives telles que les jeux vidéo, la robotique et les moteurs physiques en temps réel. Pour gérer ces exigences de calcul, des efforts considérables ont été déployés pour optimiser les algorithmes de détection de collision.

Une approche couramment utilisée pour accélérer les calculs requis consiste à diviser le processus en deux phases : la phase large et la phase étroite . La phase large vise à répondre à la question de savoir si les objets pourraient entrer en collision, en utilisant une approche conservatrice mais efficace pour exclure les paires qui ne se croisent clairement pas, évitant ainsi des calculs inutiles.

Les objets qui ne peuvent pas être définitivement séparés dans la phase large sont transférés vers la phase étroite. Ici, des algorithmes plus précis déterminent si ces objets se croisent réellement. Si tel est le cas, la phase étroite calcule souvent l'heure et le lieu exacts de l'intersection.

Phase large

Cette phase vise à trouver rapidement des objets ou des parties d'objets pour lesquels il peut être rapidement déterminé qu'aucun autre test de collision n'est nécessaire. Une propriété utile de cette approche est qu'elle est sensible à la sortie . Dans le contexte de la détection de collision, cela signifie que la complexité temporelle de la détection de collision est proportionnelle au nombre d'objets proches les uns des autres. Un exemple précoce de cela est l'I-COLLIDE où le nombre de tests de collision en phase étroite requis était où est le nombre d'objets et est le nombre d'objets à proximité. Il s'agit d'une amélioration significative par rapport à la complexité quadratique de l'approche naïve.

Partitionnement spatial

Plusieurs approches peuvent être regroupées sous le terme générique de partitionnement spatial , qui comprend les octrees (pour la 3D), les quadtrees (pour la 2D), le partitionnement de l'espace binaire (ou arbres BSP) et d'autres approches similaires. Si l'on divise l'espace en un certain nombre de cellules simples et si l'on peut montrer que deux objets ne se trouvent pas dans la même cellule, il n'est pas nécessaire de vérifier leur intersection. Les scènes dynamiques et les objets déformables nécessitent une mise à jour du partitionnement, ce qui peut entraîner des frais supplémentaires.

Hiérarchie des volumes englobants

Hiérarchie des volumes englobants (BVH) : structure arborescente sur un ensemble de volumes englobants. La collision est déterminée en effectuant un parcours d'arbre à partir de la racine. Si le volume englobant de la racine ne croise pas l'objet d'intérêt, le parcours peut être arrêté. Si, toutefois, il y a une intersection, le parcours se poursuit et vérifie les branches pour chaque intersection. Les branches pour lesquelles il n'y a pas d'intersection avec le volume englobant peuvent être éliminées d'un test d'intersection ultérieur. Par conséquent, plusieurs objets peuvent être déterminés comme ne se croisant pas en même temps. BVH peut être utilisé avec des objets déformables tels que des tissus ou des corps mous, mais la hiérarchie des volumes doit être ajustée lorsque la forme se déforme. Pour les objets déformables, nous devons nous préoccuper des auto-collisions ou des auto-intersections. BVH peut également être utilisé à cette fin. La collision entre deux objets est calculée en calculant l'intersection entre les volumes englobants de la racine de l'arbre. Lorsqu'il y a une collision, nous plongeons dans les sous-arbres qui se croisent. Les collisions exactes entre les objets réels ou leurs parties (souvent des triangles d'un maillage triangulaire ) doivent être calculées uniquement entre les feuilles qui se croisent. La ​​même approche fonctionne pour les collisions par paires et les auto-collisions.

Exploiter la cohérence temporelle

Pendant la phase large, lorsque les objets du monde se déplacent ou se déforment, les structures de données utilisées pour éliminer les collisions doivent être mises à jour. Dans les cas où les changements entre deux images ou pas de temps sont faibles et où les objets peuvent être bien approximés avec des cadres de délimitation alignés sur les axes, l' algorithme de balayage et d'élagage peut être une approche appropriée.

Plusieurs observations clés rendent l'implémentation efficace : deux boîtes englobantes se croisent si, et seulement si , il y a chevauchement le long des trois axes ; le chevauchement peut être déterminé, pour chaque axe séparément, en triant les intervalles pour toutes les boîtes ; et enfin, entre deux trames, les mises à jour sont généralement faibles (ce qui rend les algorithmes de tri optimisés pour les listes presque triées adaptés à cette application). L'algorithme garde la trace des boîtes qui se croisent actuellement et, à mesure que les objets se déplacent, le nouveau tri des intervalles permet de suivre l'état.

Taille par paires

(Learn how and when to remove this message)

Une fois que nous avons sélectionné une paire de corps physiques pour une étude plus approfondie, nous devons vérifier plus attentivement les collisions. Cependant, dans de nombreuses applications, les objets individuels (s'ils ne sont pas trop déformables) sont décrits par un ensemble de primitives plus petites, principalement des triangles. Nous avons donc maintenant deux ensembles de triangles, et (pour simplifier, nous supposerons que chaque ensemble a le même nombre de triangles).

La chose évidente à faire est de vérifier tous les triangles par rapport à tous les triangles pour détecter les collisions, mais cela implique des comparaisons, ce qui est très inefficace. Si possible, il est souhaitable d'utiliser un algorithme d'élagage pour réduire le nombre de paires de triangles que nous devons vérifier.

La famille d'algorithmes la plus utilisée est connue sous le nom de méthode des volumes englobants hiérarchiques . En tant qu'étape de prétraitement, pour chaque objet (dans notre exemple, et ), nous calculerons une hiérarchie de volumes englobants . Ensuite, à chaque pas de temps, lorsque nous devons vérifier les collisions entre et , les volumes englobants hiérarchiques sont utilisés pour réduire le nombre de paires de triangles considérées. Pour plus de simplicité, nous donnerons un exemple utilisant des sphères englobantes, bien qu'il ait été noté que les sphères ne sont pas souhaitables dans de nombreux cas.

Si est un ensemble de triangles, nous pouvons précalculer une sphère englobante . Il existe de nombreuses façons de choisir , nous supposons seulement que est une sphère qui contient complètement et qui est aussi petite que possible.

À l'avance, nous pouvons calculer et . De toute évidence, si ces deux sphères ne se croisent pas (et c'est très facile à tester), alors et . Ce n'est cependant pas beaucoup mieux qu'un algorithme d'élagage à n corps.

Si est un ensemble de triangles, alors nous pouvons le diviser en deux moitiés et . Nous pouvons le faire pour et , et nous pouvons calculer (à l'avance) les sphères englobantes et . L'espoir ici est que ces sphères englobantes soient beaucoup plus petites que et . Et, si, par exemple, et ne se coupent pas, alors il n'y a aucun sens à comparer un triangle de avec un triangle de .

En guise de précalcul , nous pouvons prendre chaque corps physique (représenté par un ensemble de triangles) et le décomposer de manière récursive en un arbre binaire , où chaque nœud représente un ensemble de triangles et ses deux enfants représentent et . À chaque nœud de l'arbre, nous pouvons précalculer la sphère englobante .

Lorsque vient le moment de tester une paire d'objets pour une collision, leur arbre de sphères englobantes peut être utilisé pour éliminer de nombreuses paires de triangles.

De nombreuses variantes de ces algorithmes sont obtenues en choisissant autre chose qu'une sphère pour . Si l'on choisit des boîtes englobantes alignées sur les axes , on obtient des AABBTrees. Les arbres à boîtes englobantes orientées sont appelés OBBTrees. Certains arbres sont plus faciles à mettre à jour si l'objet sous-jacent change. Certains arbres peuvent accueillir des primitives d'ordre supérieur telles que des splines au lieu de simples triangles.

Les objets qui ne peuvent pas être définitivement séparés dans la phase large sont transférés vers la phase étroite. Dans cette phase, les objets considérés sont relativement proches les uns des autres. Néanmoins, des tentatives visant à déterminer rapidement si une intersection complète est nécessaire sont d'abord utilisées. Cette étape est parfois appelée phase intermédiaire. Une fois ces tests réussis (par exemple, la paire d'objets peut entrer en collision), des algorithmes plus précis déterminent si ces objets se croisent réellement. Si tel est le cas, la phase étroite calcule souvent l'heure et l'emplacement exacts de l'intersection.

Un moyen rapide d'éviter un calcul coûteux et inutile consiste à vérifier si le volume englobant qui entoure les deux objets se croise. Si ce n'est pas le cas, il n'est pas nécessaire de vérifier les objets réels. Cependant, si le volume englobant se croise, le calcul le plus coûteux doit être effectué. Pour que le test du volume englobant apporte une valeur ajoutée, deux propriétés doivent être équilibrées : a) le coût de l'intersection du volume englobant doit être faible et b) le volume englobant doit être suffisamment serré pour que le nombre d'intersections « faussement positives » soit faible. Une intersection faussement positive dans ce cas signifie que le volume englobant se croise mais que les objets réels ne le font pas. Différents types de volumes englobants offrent différents compromis pour ces propriétés.

Les boîtes englobantes alignées sur les axes (AABB) et les cuboïdes sont populaires en raison de leur simplicité et de leurs tests d'intersection rapides. Les volumes englobants tels que les boîtes englobantes orientées (OBB) , les K-DOP et les coques convexes offrent une approximation plus étroite de la forme fermée au détriment d'un test d'intersection plus élaboré.

Les volumes englobants sont généralement utilisés au stade précoce (élagage) de la détection de collision, de sorte que seuls les objets avec des volumes englobants qui se chevauchent doivent être comparés en détail. Le calcul de collision ou de chevauchement entre les volumes englobants implique des calculs supplémentaires. Par conséquent, pour que cela soit bénéfique, nous avons besoin que le volume englobant soit relativement serré et que la surcharge de calcul due aux collisions soit faible.

Les objets pour lesquels les approches d’élagage n’ont pas pu exclure la possibilité d’une collision doivent subir un calcul de détection de collision exact.

Selon le théorème des plans séparateurs , pour deux objets convexes disjoints , il existe un plan tel que l'un des objets se trouve entièrement sur un côté de ce plan et l'autre objet sur le côté opposé de ce plan. Cette propriété permet le développement d'algorithmes efficaces de détection de collision entre objets convexes. Plusieurs algorithmes sont disponibles pour trouver les points les plus proches sur la surface de deux objets polyédriques convexes - et déterminer la collision. Les premiers travaux de Ming C. Lin qui utilisaient une variante de l' algorithme du simplexe de la programmation linéaire et l' algorithme de distance Gilbert-Johnson-Keerthi en sont deux exemples. Ces algorithmes s'approchent du temps constant lorsqu'ils sont appliqués de manière répétée à des paires d'objets stationnaires ou lents, et chaque étape est initialisée à partir de la vérification de collision précédente .

Le résultat de tout ce travail algorithmique est que la détection de collision peut être effectuée efficacement pour des milliers d’objets en mouvement en temps réel sur des ordinateurs personnels et des consoles de jeu classiques.

Lorsque la plupart des objets impliqués sont fixes, comme c'est le cas dans les jeux vidéo, des méthodes a priori utilisant le précalcul peuvent être utilisées pour accélérer l'exécution.

L'élagage est également souhaitable ici, à la fois l'élagage à n corps et l'élagage par paires, mais les algorithmes doivent prendre en compte le temps et les types de mouvements utilisés dans le système physique sous-jacent.

En ce qui concerne la détection exacte des collisions par paires, cela dépend fortement de la trajectoire et il faut presque utiliser un algorithme de recherche de racine numérique pour calculer l'instant de l'impact.

A titre d'exemple, considérons deux triangles se déplaçant dans le temps et . A tout moment, les deux triangles peuvent être vérifiés pour l'intersection en utilisant les vingt plans mentionnés précédemment. Cependant, nous pouvons faire mieux, puisque ces vingt plans peuvent tous être suivis dans le temps. Si le plan passe par des points dans alors il y a vingt plans à suivre. Chaque plan doit être suivi par rapport à trois sommets, ce qui donne soixante valeurs à suivre. L'utilisation d'un chercheur de racines sur ces soixante fonctions produit les temps de collision exacts pour les deux triangles donnés et les deux trajectoires données. Nous notons ici que si les trajectoires des sommets sont supposées être des polynômes linéaires dans alors les soixante fonctions finales sont en fait des polynômes cubiques, et dans ce cas exceptionnel, il est possible de localiser le temps de collision exact en utilisant la formule des racines du cubique. Certains analystes numériques suggèrent que l'utilisation de la formule des racines du cubique n'est pas aussi stable numériquement que l'utilisation d'un chercheur de racines pour les polynômes.

Un objet maillé triangulaire est couramment utilisé dans la modélisation de corps 3D. Normalement, la fonction de collision est une interception triangle-triangle ou une forme de délimitation associée au maillage. Un centroïde triangulaire est un emplacement de centre de masse tel qu'il serait en équilibre sur la pointe d'un crayon. La simulation n'a besoin que d'ajouter une dimension de centroïde aux paramètres physiques. Étant donné les points centroïdes de l'objet et de la cible, il est possible de définir le segment de ligne reliant ces deux points.

Le vecteur de position du centre de gravité d'un triangle est la moyenne des vecteurs de position de ses sommets. Ainsi, si ses sommets ont des coordonnées cartésiennes , alors le centre de gravité est .

Voici la fonction pour une distance de segment de ligne entre deux points 3D.

Ici, la longueur/distance du segment est un critère de « réussite » ajustable. Au fur et à mesure que les objets s'approchent, la longueur diminue jusqu'à la valeur seuil. Une sphère triangulaire devient le test de géométrie efficace. Une sphère centrée sur le centroïde peut être dimensionnée pour englober tous les sommets du triangle.

Les simulateurs physiques diffèrent dans la façon dont ils réagissent à une collision. Certains utilisent la souplesse du matériau pour calculer une force, qui résoudra la collision dans les pas de temps suivants comme dans la réalité. Cela demande beaucoup de ressources CPU pour les matériaux à faible souplesse. Certains simulateurs estiment le moment de la collision par interpolation linéaire , annulent la simulation et calculent la collision par les méthodes plus abstraites des lois de conservation .

Certains utilisent l'interpolation linéaire ( méthode de Newton ) pour calculer le moment de la collision avec une précision bien supérieure à celle du reste de la simulation. La détection de collision utilise la cohérence temporelle pour permettre des pas de temps encore plus fins sans augmenter considérablement la demande de CPU, comme dans le contrôle aérien .

Après une collision inélastique, des états spéciaux de glissement et de repos peuvent se produire et, par exemple, Open Dynamics Engine utilise des contraintes pour les simuler. Les contraintes évitent l'inertie et donc l'instabilité. La mise en œuvre du repos au moyen d'un graphe de scène évite la dérive.

En d'autres termes, les simulateurs physiques fonctionnent généralement de deux manières : la collision est détectée a posteriori (après la collision) ou a priori (avant la collision). Outre la distinction a posteriori et a priori , presque tous les algorithmes modernes de détection de collision sont divisés en une hiérarchie d'algorithmes. On utilise souvent les termes « discret » et « continu » plutôt que a posteriori et a priori .

Dans le cas a posteriori , la simulation physique est avancée d'un petit pas, puis vérifiée pour voir si des objets se croisent ou sont visiblement considérés comme se croisant. À chaque étape de simulation, une liste de tous les corps qui se croisent est créée, et les positions et trajectoires de ces objets sont « fixées » pour tenir compte de la collision. Cette méthode est appelée a posteriori car elle omet généralement l'instant réel de la collision et ne détecte la collision qu'après qu'elle se soit réellement produite.

Dans les méthodes a priori , il existe un algorithme de détection de collision qui va pouvoir prédire très précisément les trajectoires des corps physiques. Les instants de collision sont calculés avec une grande précision, et les corps physiques ne s'interpénètrent jamais réellement. On parle de méthode a priori car l'algorithme de détection de collision calcule les instants de collision avant de mettre à jour la configuration des corps physiques.

Les principaux avantages des méthodes a posteriori sont les suivants. Dans ce cas, l'algorithme de détection de collision n'a pas besoin de connaître la myriade de variables physiques ; une simple liste de corps physiques est fournie à l'algorithme et le programme renvoie une liste de corps qui se croisent. L'algorithme de détection de collision n'a pas besoin de comprendre le frottement, les collisions élastiques ou, pire, les collisions non élastiques et les corps déformables. De plus, les algorithmes a posteriori sont en effet plus simples d'une dimension que les algorithmes a priori . Un algorithme a priori doit gérer la variable temps, qui est absente du problème a posteriori .

En revanche, les algorithmes a posteriori posent des problèmes lors de l'étape de "fixation", où il faut corriger les intersections (qui ne sont pas physiquement correctes). De plus, si l'étape discrète est trop grande, la collision pourrait passer inaperçue, ce qui se traduirait par un objet qui en traverserait un autre s'il était suffisamment rapide ou petit.

Les avantages des algorithmes a priori sont une fidélité et une stabilité accrues. Il est difficile (mais pas complètement impossible) de séparer la simulation physique de l'algorithme de détection de collision. Cependant, dans tous les cas, sauf les plus simples, le problème de déterminer à l'avance le moment où deux corps entreront en collision (à partir de certaines données initiales) n'a pas de solution sous forme fermée : un outil de recherche de racines numériques est généralement utilisé.

Certains objets sont en contact de repos , c'est-à-dire en collision, mais sans rebondir ni s'interpénétrer, comme un vase posé sur une table. Dans tous les cas, le contact de repos nécessite un traitement particulier : si deux objets entrent en collision ( a posteriori ) ou glissent ( a priori ) et que leur mouvement relatif est inférieur à un seuil, le frottement devient stiction et les deux objets sont disposés dans la même branche du graphe de scène .

Les jeux vidéo doivent répartir leur temps de calcul très limité entre plusieurs tâches. Malgré cette limitation des ressources et l'utilisation d'algorithmes de détection de collision relativement primitifs, les programmeurs ont pu créer des systèmes crédibles, bien qu'inexacts, destinés aux jeux.

Pendant longtemps, les jeux vidéo avaient un nombre très limité d'objets à traiter, et vérifier toutes les paires n'était donc pas un problème. Dans les jeux en deux dimensions, dans certains cas, le matériel était capable de détecter et de signaler efficacement les pixels superposés entre les sprites à l'écran. Dans d'autres cas, le simple fait de carreler l'écran et de lier chaque sprite aux tuiles qu'il chevauche permet un élagage suffisant, et pour les vérifications par paires, des rectangles ou des cercles de délimitation appelés hitboxes sont utilisés et jugés suffisamment précis.

Les jeux en trois dimensions ont utilisé des méthodes de partitionnement spatial pour l'élagage des corps et ont longtemps utilisé une ou quelques sphères par objet 3D réel pour les vérifications par paires. Les vérifications exactes sont très rares, sauf dans les jeux qui tentent de simuler la réalité de près. Même dans ce cas, les vérifications exactes ne sont pas nécessairement utilisées dans tous les cas.

Comme les jeux n'ont pas besoin de reproduire la physique réelle, la stabilité n'est pas un problème majeur. Presque tous les jeux utilisent une détection de collision a posteriori, et les collisions sont souvent résolues à l'aide de règles très simples. Par exemple, si un personnage se retrouve coincé dans un mur, il peut être simplement ramené à son dernier bon emplacement connu. Certains jeux calculent la distance que le personnage peut parcourir avant de se retrouver coincé dans un mur, et ne l'autorisent à se déplacer que sur cette distance.

Dans de nombreux cas de jeux vidéo, l'approximation des personnages par un point est suffisante pour détecter les collisions avec l'environnement. Dans ce cas, les arbres de partitionnement de l'espace binaire fournissent un algorithme viable, efficace et simple pour vérifier si un point est intégré dans le décor ou non. Une telle structure de données peut également être utilisée pour gérer avec élégance la situation de « position de repos » lorsqu'un personnage court au sol. Les collisions entre personnages et les collisions avec des projectiles et des obstacles sont traitées séparément.

Un simulateur robuste est un simulateur qui réagit de manière raisonnable à toute entrée. Par exemple, si nous imaginons un jeu vidéo de course automobile à grande vitesse , d'une étape de simulation à l'autre, il est concevable que les voitures avancent sur une distance substantielle le long de la piste de course. S'il y a un obstacle peu profond sur la piste (comme un mur de briques), il n'est pas totalement improbable que la voiture le franchisse complètement, ce qui est très indésirable. Dans d'autres cas, la « réparation » requise par les algorithmes a posteriori n'est pas implémentée correctement, ce qui entraîne des bugs qui peuvent piéger les personnages dans les murs ou leur permettre de les traverser et de tomber dans un vide sans fin où il peut y avoir ou non un gouffre mortel sans fond , parfois appelé « enfer noir », « enfer bleu » ou « enfer vert », selon la couleur prédominante. Ce sont les signes distinctifs d'un système de détection de collision et de simulation physique défaillant. Big Rigs: Over the Road Racing est un exemple tristement célèbre de jeu dont le système de détection de collision est défaillant ou peut-être manquant.

Une hitbox est une forme invisible couramment utilisée dans les jeux vidéo pour la détection de collision en temps réel ; c'est un type de boîte englobante. Il s'agit souvent d'un rectangle (dans les jeux 2D) ou d'un cuboïde (en 3D) qui est attaché à un point sur un objet visible (comme un modèle ou un sprite) et qui le suit. Les formes circulaires ou sphéroïdales sont également courantes, bien qu'elles soient encore le plus souvent appelées « boîtes ». Il est courant que les objets animés aient des hitbox attachées à chaque partie mobile pour garantir la précision pendant le mouvement.

Les hitboxes sont utilisées pour détecter les collisions « à sens unique », comme lorsqu'un personnage est touché par un coup de poing ou une balle. Elles ne sont pas adaptées à la détection de collisions avec retour d'information (par exemple, se cogner contre un mur) en raison de la difficulté rencontrée par les humains et l'IA à gérer les emplacements en constante évolution d'une hitbox ; ces types de collisions sont généralement gérés à l'aide de boîtes englobantes alignées sur des axes beaucoup plus simples . Les joueurs peuvent utiliser le terme « hitbox » pour désigner ces types d'interactions, quoi qu'il en soit.

Une hitbox est une hitbox utilisée pour détecter les sources de dégâts entrantes. Dans ce contexte, le terme hitbox est généralement réservé à celles qui infligent des dégâts. Par exemple, une attaque ne peut réussir que si la hitbox autour du coup de poing d'un attaquant entre en contact avec l'une des hitboxes de l'adversaire sur son corps, tandis que les hitboxes adverses qui entrent en collision peuvent entraîner des échanges ou des annulations de coups entre les joueurs, et les hurtboxes adverses n'interagissent pas entre elles. Le terme n'est pas standardisé dans l'industrie ; certains jeux inversent leurs définitions de hitbox et de hurtbox , tandis que d'autres n'utilisent « hitbox » que pour les deux côtés.