Tutoriel de physique du jeu vidéo - Partie II : Détection de collision pour les objets solides

Ceci est la deuxième partie de notre série en trois parties sur la physique des jeux vidéo. Pour le reste de cette série, voir :

Partie I : Une introduction à la dynamique des corps rigides
Partie III : Simulation de corps rigide contraint

Dans la première partie de cette série, nous avons exploré les corps rigides et leurs mouvements. Dans cette discussion, cependant, les objets n'ont pas interagi les uns avec les autres. Sans un travail supplémentaire, les corps rigides simulés peuvent se traverser de part en part, ou « s'interpénétrer », ce qui n'est pas souhaitable dans la majorité des cas.

Afin de simuler de manière plus réaliste le comportement des objets solides, nous devons vérifier s'ils entrent en collision les uns avec les autres à chaque fois qu'ils se déplacent, et s'ils le font, nous devons faire quelque chose à ce sujet, comme appliquer des forces qui modifient leurs vitesses, donc qu'ils se déplaceront dans la direction opposée. C'est là que comprendre la physique des collisions est particulièrement important pour les développeurs de jeux.

Dans la partie II, nous couvrirons l'étape de détection de collision, qui consiste à trouver des paires de corps qui entrent en collision parmi un nombre éventuellement important de corps dispersés dans un monde 2D ou 3D. Dans le prochain et dernier épisode, nous parlerons davantage de la « résolution » de ces collisions pour éliminer les interpénétrations.

Pour un examen des concepts d'algèbre linéaire mentionnés dans cet article, vous pouvez vous référer au cours intensif d'algèbre linéaire dans la partie I.

Physique des collisions dans les jeux vidéo

Dans le contexte des simulations de corps rigides, une collision se produit lorsque les formes de deux corps rigides se croisent ou lorsque la distance entre ces formes tombe en dessous d'une petite tolérance.

Si nous avons n corps dans notre simulation, la complexité de calcul de la détection des collisions avec des tests par paires est O ( n 2 ) , un nombre qui fait grincer des dents aux informaticiens. Le nombre de tests par paires augmente de manière quadratique avec le nombre de corps, et déterminer si deux formes, dans des positions et des orientations arbitraires, entrent en collision n'est déjà pas bon marché. Afin d'optimiser le processus de détection de collision, nous le divisons généralement en deux phases : une phase large et une phase étroite .

La phase large est chargée de trouver des paires de corps rigides qui entrent potentiellement en collision et d'exclure les paires qui n'entrent certainement pas en collision, parmi l'ensemble des corps qui se trouvent dans la simulation. Cette étape doit pouvoir très bien s'adapter au nombre de corps rigides pour s'assurer que nous restons bien en dessous de la complexité temporelle O ( n 2 ) . Pour y parvenir, cette phase utilise généralement un partitionnement spatial couplé à des volumes englobants qui établissent une limite supérieure de collision.

La phase étroite opère sur les paires de corps rigides trouvées par la phase large qui pourraient entrer en collision. C'est une étape de raffinement où nous déterminons si les collisions se produisent réellement, et pour chaque collision trouvée, nous calculons les points de contact qui seront utilisés pour résoudre les collisions plus tard.

Dans les sections suivantes, nous parlerons de certains algorithmes pouvant être utilisés dans la phase large et la phase étroite.

Phase large

Dans la vaste phase de la physique des collisions pour les jeux vidéo, nous devons identifier les paires de corps rigides susceptibles d'entrer en collision. Ces corps peuvent avoir des formes complexes comme des polygones et des polyèdres, et ce que nous pouvons faire pour accélérer cela est d'utiliser une forme plus simple pour englober l'objet. Si ces volumes englobants ne se croisent pas, les formes réelles ne se croisent pas non plus. S'ils se croisent, les formes réelles peuvent se croiser.

Certains types populaires de volumes englobants sont les boîtes englobantes orientées (OBB), les cercles en 2D et les sphères en 3D. Examinons l'un des volumes englobants les plus simples : les boîtes englobantes alignées sur l'axe (AABB) .

Les AABB sont très appréciés des programmeurs en physique car ils sont simples et offrent de bons compromis. Un AABB bidimensionnel peut être représenté par une structure comme celle-ci en langage C :

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

Le champ min représente l'emplacement du coin inférieur gauche de la boîte et le champ max représente le coin supérieur droit.

Pour tester si deux AABB se croisent, il suffit de savoir si leurs projections se croisent sur tous les axes de coordonnées :

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

Ce code a la même logique que la fonction b2TestOverlap du moteur Box2D (version 2.3.0). Il calcule la différence entre le min et le max des deux AABB, dans les deux axes, dans les deux ordres. Si l'une de ces valeurs est supérieure à zéro, les AABB ne se croisent pas.

Même si un test de chevauchement AABB est bon marché, cela n'aidera pas beaucoup si nous continuons à faire des tests par paires pour chaque paire possible puisque nous avons toujours la complexité temporelle indésirable O ( n 2 ) . Pour minimiser le nombre de tests de chevauchement AABB, nous pouvons utiliser une sorte de partitionnement d'espace , qui fonctionne sur les mêmes principes que les index de base de données qui accélèrent les requêtes. (Les bases de données géographiques, telles que PostGIS, utilisent en fait des structures de données et des algorithmes similaires pour leurs index spatiaux.) Dans ce cas, cependant, les AABB se déplaceront constamment, donc généralement, nous devons recréer des index après chaque étape de la simulation.

De nombreux algorithmes de partitionnement d'espace et structures de données peuvent être utilisés à cette fin, tels que des grilles uniformes, des quadtrees en 2D, des octrees en 3D et le hachage spatial. Examinons de plus près deux algorithmes de partitionnement spatial populaires : le tri et le balayage, et les hiérarchies de volumes englobants (BVH).

L'algorithme de tri et de balayage

La méthode de tri et de balayage (également connue sous le nom de balayage et d'élagage ) est l'un des choix préférés des programmeurs en physique pour une utilisation dans la simulation de corps rigides. Le moteur Bullet Physics, par exemple, a une implémentation de cette méthode dans la classe btAxisSweep3 .

La projection d'un AABB sur un seul axe de coordonnées est essentiellement un intervalle [ b , e ] (c'est-à-dire début et fin). Dans notre simulation, nous aurons de nombreux corps rigides, et donc de nombreux AABB, et cela signifie de nombreux intervalles. Nous voulons savoir quels intervalles se croisent.

Dans l'algorithme de tri et de balayage, nous insérons toutes les valeurs b et e dans une seule liste et la trions par ordre croissant de leurs valeurs scalaires. Ensuite, nous balayons ou parcourons la liste. Chaque fois qu'une valeur b est rencontrée, son intervalle correspondant est stocké dans une liste séparée d' intervalles actifs , et chaque fois qu'une valeur e est rencontrée, son intervalle correspondant est supprimé de la liste des intervalles actifs. A tout instant, tous les intervalles actifs se croisent. (Consultez la thèse de doctorat de David Baraff, p. 52 pour plus de détails. Je suggère d'utiliser cet outil en ligne pour afficher le fichier postscript.) La liste des intervalles peut être réutilisée à chaque étape de la simulation, où nous pouvons trier efficacement cette liste en utilisant le tri par insertion, qui est efficace pour trier des listes presque triées.

En deux et trois dimensions, l'exécution du tri et du balayage, comme décrit ci-dessus, sur un seul axe de coordonnées réduira le nombre de tests d'intersection AABB directs qui doivent être effectués, mais le gain peut être meilleur sur un axe de coordonnées qu'un autre. Par conséquent, des variantes plus sophistiquées de l'algorithme de tri et de balayage sont mises en œuvre. Dans son livre Real-Time Collision Detection (page 336), Christer Ericson présente une variante efficace où il stocke tous les AABB dans un seul tableau, et pour chaque exécution du tri et du balayage, un axe de coordonnées est choisi et le tableau est trié par la valeur min des AABB dans l'axe choisi, en utilisant le tri rapide. Ensuite, le réseau est traversé et des tests de chevauchement AABB sont effectués. Pour déterminer l'axe suivant qui doit être utilisé pour le tri, la variance du centre des AABB est calculée et l'axe avec la plus grande variance est choisi pour l'étape suivante.

Arbres de volumes englobants dynamiques

Une autre méthode de partitionnement spatial utile est l' arbre de volume englobant dynamique , également connu sous le nom de Dbvt . Il s'agit d'un type de hiérarchie de volumes englobants .

Le Dbvt est un arbre binaire dans lequel chaque nœud a un AABB qui délimite tous les AABB de ses enfants. Les AABB des corps rigides eux-mêmes sont situés dans les nœuds feuilles. Typiquement, un Dbvt est « interrogé » en donnant l'AABB pour lequel on souhaite détecter des intersections. Cette opération est efficace car les enfants des nœuds qui ne croisent pas l'AABB interrogé n'ont pas besoin d'être testés pour le chevauchement. En tant que telle, une requête de collision AABB commence à partir de la racine et continue de manière récursive à travers l'arborescence uniquement pour les nœuds AABB qui se croisent avec l'AABB interrogé. L'arbre peut être équilibré par des rotations d'arbres, comme dans un arbre AVL.

Box2D a une implémentation sophistiquée de Dbvt dans la classe b2DynamicTree . La classe b2BroadPhase est responsable de l'exécution de la phase large et utilise une instance de b2DynamicTree pour effectuer des requêtes AABB.

Phase étroite

Après la phase large de la physique des collisions dans les jeux vidéo, nous avons un ensemble de paires de corps rigides qui entrent potentiellement en collision. Ainsi, pour chaque paire, compte tenu de la forme, de la position et de l'orientation des deux corps, nous devons savoir s'ils sont, en fait, en collision ; s'ils se croisent ou si leur distance est inférieure à une petite valeur de tolérance. Nous devons également savoir quels sont les points de contact entre les corps en collision, car cela est nécessaire pour résoudre les collisions plus tard.

Formes convexes et concaves

En règle générale de la physique des jeux vidéo, il n'est pas trivial de déterminer si deux formes arbitraires se croisent, ou de calculer la distance qui les sépare. Cependant, une propriété qui est d'une importance cruciale pour déterminer à quel point c'est dur, c'est la convexité de la forme. Les formes peuvent être convexes ou concaves et les formes concaves sont plus difficiles à travailler, nous avons donc besoin de stratégies pour les gérer.

Dans une forme convexe, un segment de ligne entre deux points quelconques de la forme tombe toujours complètement à l'intérieur de la forme. Cependant, pour une forme concave (ou "non convexe"), il n'en va pas de même pour tous les segments de ligne possibles reliant les points de la forme. Si vous pouvez trouver au moins un segment de ligne qui tombe en dehors de la forme, la forme est concave.

D'un point de vue informatique, il est souhaitable que toutes les formes soient convexes dans une simulation, car nous disposons de nombreux algorithmes de test de distance et d'intersection puissants qui fonctionnent avec des formes convexes. Cependant, tous les objets ne seront pas convexes, et nous les contournons généralement de deux manières : coque convexe et décomposition convexe.

L' enveloppe convexe d'une forme est la plus petite forme convexe qui la contient entièrement. Pour un polygone concave en deux dimensions, ce serait comme marteler un clou sur chaque sommet et enrouler un élastique autour de tous les clous. Pour calculer l'enveloppe convexe d'un polygone ou d'un polyèdre, ou plus généralement, d'un ensemble de points, un bon algorithme à utiliser est l'algorithme quickhull , qui a une complexité temporelle moyenne de O ( n log n ) .

Évidemment, si nous utilisons une coque convexe pour représenter un objet concave, elle perdra ses propriétés concaves. Des comportements indésirables, tels que des collisions "fantômes", peuvent devenir apparents, car l'objet aura toujours une représentation graphique concave. Par exemple, une voiture a généralement une forme concave, et si nous utilisons une coque convexe pour la représenter physiquement et que nous plaçons ensuite une boîte dessus, la boîte peut sembler flotter dans l'espace au-dessus.

En général, les coques convexes sont souvent assez bonnes pour représenter des objets concaves, soit parce que les collisions irréalistes ne sont pas très perceptibles, soit parce que leurs propriétés concaves ne sont pas essentielles pour tout ce qui est simulé. Dans certains cas, cependant, nous pourrions souhaiter que l'objet concave se comporte physiquement comme une forme concave. Par exemple, si nous utilisons une coque convexe pour représenter physiquement un bol, nous ne pourrons rien mettre à l'intérieur. Les objets flotteront juste dessus. Dans ce cas, on peut utiliser une décomposition convexe de la forme concave.

Les algorithmes de décomposition convexe reçoivent une forme concave et renvoient un ensemble de formes convexes dont l'union est identique à la forme concave d'origine. Certaines formes concaves ne peuvent être représentées que par un grand nombre de formes convexes, et celles-ci peuvent devenir extrêmement coûteuses à calculer et à utiliser. Cependant, une approximation est souvent suffisante, et ainsi, des algorithmes tels que V-HACD produisent un petit ensemble de polyèdres convexes à partir d'un polyèdre concave.

Dans de nombreux cas de physique des collisions, cependant, la décomposition convexe peut être faite à la main, par un artiste. Cela élimine le besoin de taxer les performances avec des algorithmes de décomposition. Les performances étant l'un des aspects les plus importants des simulations en temps réel, il est généralement judicieux de créer des représentations physiques très simples pour des objets graphiques complexes. L'image ci-dessous montre une décomposition convexe possible d'une voiture 2D en utilisant neuf formes convexes.

Test des intersections - Théorème de l'axe de séparation

Le théorème de l'axe de séparation (SAT) stipule que deux formes convexes ne se coupent pas si et seulement s'il existe au moins un axe où les projections orthogonales des formes sur cet axe ne se coupent pas.

Il est généralement plus intuitif visuellement de trouver une ligne en 2D ou un plan en 3D qui sépare les deux formes, ce qui est en fait le même principe. Un vecteur orthogonal à la droite en 2D, ou le vecteur normal du plan en 3D, peut être utilisé comme « axe de séparation ».

Les moteurs physiques de jeu ont un certain nombre de classes de formes différentes, telles que les cercles (sphères en 3D), les arêtes (un seul segment de ligne) et les polygones convexes (polyèdres en 3D). Pour chaque paire de type de forme, ils ont un algorithme de détection de collision spécifique. Le plus simple d'entre eux est probablement l'algorithme cercle-cercle :

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

Même si le SAT s'applique aux cercles, il est beaucoup plus simple de vérifier si la distance entre leurs centres est inférieure à la somme de leurs rayons. Pour cette raison, le SAT est utilisé dans l'algorithme de détection de collision pour des paires spécifiques de classes de forme, telles que polygone convexe contre polygone convexe (ou polyèdres en 3D).

Pour toute paire de formes, il existe un nombre infini d'axes que nous pouvons tester pour la séparation. Ainsi, déterminer quel axe tester en premier est crucial pour une implémentation SAT efficace. Heureusement, lors du test de collision d'une paire de polygones convexes, nous pouvons utiliser les normales des bords comme axes de séparation potentiels. Le vecteur normal n d'une arête est perpendiculaire au vecteur d'arête et pointe à l'extérieur du polygone. Pour chaque arête de chaque polygone, il suffit de savoir si tous les sommets de l'autre polygone sont devant l'arête.

Si un test réussit - c'est-à-dire si, pour n'importe quelle arête, tous les sommets de l'autre polygone sont devant lui - alors les polygones ne se croisent pas. L'algèbre linéaire fournit une formule simple pour ce test : étant donné une arête sur la première forme avec des sommets a et b et un sommet v sur l'autre forme, si ( v - a ) · n est supérieur à zéro, alors le sommet est devant du bord.

Pour les polyèdres, nous pouvons utiliser les normales des faces ainsi que le produit croisé de toutes les combinaisons d'arêtes de chaque forme. Cela ressemble à beaucoup de choses à tester; cependant, pour accélérer les choses, nous pouvons mettre en cache le dernier axe de séparation que nous avons utilisé et essayer de l'utiliser à nouveau dans les prochaines étapes de la simulation. Si l'axe de séparation mis en cache ne sépare plus les formes, nous pouvons rechercher un nouvel axe à partir de faces ou d'arêtes adjacentes à la face ou à l'arête précédente. Cela fonctionne parce que les corps ne bougent ou ne tournent pas beaucoup entre les étapes.

Box2D utilise SAT pour tester si deux polygones convexes se croisent dans son algorithme de détection de collision polygone-polygone dans b2CollidePolygon.cpp.

Calcul de la distance - L'algorithme de Gilbert-Johnson-Keerthi

Dans de nombreux cas de physique des collisions, nous voulons considérer que des objets entrent en collision non seulement s'ils se croisent réellement, mais aussi s'ils sont très proches les uns des autres, ce qui nous oblige à connaître la distance qui les sépare. L'algorithme de Gilbert-Johnson-Keerthi (GJK) calcule la distance entre deux formes convexes ainsi que leurs points les plus proches. Il s'agit d'un algorithme élégant qui fonctionne avec une représentation implicite des formes convexes via des fonctions de support, des sommes de Minkowski et des simplexes, comme expliqué ci-dessous.

Fonctions de soutien

Une fonction de support s A ( d ) renvoie un point sur la frontière de la forme A qui a la projection la plus élevée sur le vecteur d . Mathématiquement, il a le produit scalaire le plus élevé avec d . C'est ce qu'on appelle un point de support , et cette opération est également connue sous le nom de mappage de support . Géométriquement, ce point est le point le plus éloigné de la forme dans la direction de d .

Trouver un point d'appui sur un polygone est relativement facile. Pour un point support pour le vecteur d , il vous suffit de parcourir ses sommets et de trouver celui qui a le produit scalaire le plus élevé avec d , comme ceci :

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

Cependant, la véritable puissance d'une fonction de support est qu'elle facilite le travail avec des formes telles que des cônes, des cylindres et des ellipses, entre autres. Il est plutôt difficile de calculer directement la distance entre de telles formes, et sans un algorithme comme GJK, vous devriez généralement les discrétiser en un polygone ou un polyèdre pour simplifier les choses. Cependant, cela pourrait entraîner d'autres problèmes car la surface d'un polyèdre n'est pas aussi lisse que la surface d'une sphère, par exemple, à moins que le polyèdre ne soit très détaillé, ce qui peut entraîner de mauvaises performances lors de la détection de collision. D'autres effets secondaires indésirables peuvent également apparaître ; par exemple, une sphère "polyédrique" peut ne pas rouler en douceur.

Pour obtenir un point d'appui pour une sphère centrée sur l'origine, il suffit de normaliser d (c'est-à-dire de calculer d / || d || , qui est un vecteur de longueur 1 (unité de longueur) qui pointe toujours dans la même direction de d ) puis nous le multiplions par le rayon de la sphère.

Consultez l'article de Gino van den Bergen pour trouver plus d'exemples de fonctions de support pour les cylindres et les cônes, entre autres formes.

Nos objets seront, bien sûr, déplacés et tournés depuis l'origine dans l'espace de simulation, nous devons donc pouvoir calculer des points d'appui pour une forme transformée. Nous utilisons une transformation affine T ( x ) = R x + c pour déplacer et faire pivoter nos objets, où c est le vecteur de déplacement et R est la matrice de rotation . Cette transformation fait d'abord pivoter l'objet autour de l'origine, puis le translate. La fonction de support d'une forme transformée A est :

Sommes de Minkowski

La somme de Minkowski de deux formes A et B est définie comme :

Cela signifie que nous calculons la somme de tous les points contenus dans A et B . Le résultat est comme gonfler A avec B .

De même, nous définissons la différence de Minkowski comme :

que l'on peut aussi écrire comme la somme de Minkowski de A avec -B :

Pour les convexes A et B , A⊕B est aussi convexe.

Une propriété utile de la différence de Minkowski est que si elle contient l'origine de l'espace, les formes se croisent, comme on peut le voir sur l'image précédente. Pourquoi donc? Parce que si deux formes se croisent, elles ont au moins un point en commun, qui se trouve au même endroit dans l'espace, et leur différence est le vecteur zéro, qui est en fait l'origine.

Une autre caractéristique intéressante de la différence de Minkowski est que si elle ne contient pas l'origine, la distance minimale entre l'origine et la différence de Minkowski est la distance entre les formes.

La distance entre deux formes est définie par :

En d'autres termes, la distance entre A et B est la longueur du vecteur le plus court qui va de A à B . Ce vecteur est contenu dans A⊖B et c'est celui qui a la plus petite longueur, qui par conséquent est le plus proche de l'origine.

Il n'est généralement pas simple de construire explicitement la somme de Minkowski de deux formes. Heureusement, nous pouvons également utiliser le mappage de support ici, car :

Simplexes

L'algorithme GJK recherche itérativement le point sur la différence de Minkowski le plus proche de l'origine. Pour ce faire, il construit une série de simplexes plus proches de l'origine à chaque itération. Un simplexe - ou plus précisément, un k-simplex pour un entier k - est l'enveloppe convexe de k + 1 points affinement indépendants dans un espace à k dimensions. Autrement dit, si pour deux points, ils ne doivent pas coïncider, pour trois points, ils ne doivent pas non plus se trouver sur la même ligne, et si nous avons quatre points, ils ne doivent pas non plus se trouver sur le même plan. Par conséquent, le 0-simplex est un point, le 1-simplex est un segment de droite, le 2-simplex est un triangle et le 3-simplex est un tétraèdre. Si nous supprimons un point d'un simplexe, nous décrémentons sa dimensionnalité de un, et si nous ajoutons un point à un simplexe, nous incrémentons sa dimensionnalité de un.

GJK en action

Mettons tout cela ensemble pour voir comment GJK fonctionne. Pour déterminer la distance entre deux formes A et B , on commence par prendre leur différence de Minkowski A⊖B . Nous recherchons le point le plus proche de l'origine sur la forme résultante, puisque la distance à ce point est la distance entre les deux formes d'origine. Nous choisissons un point v dans A⊖B , qui sera notre approximation de distance. Nous définissons également un ensemble de points vide W , qui contiendra les points du simplexe de test courant.

Ensuite, nous entrons dans une boucle. On commence par prendre le point support w = s A⊖B (- v ) , le point sur A⊖B dont la projection sur v est la plus proche de l'origine.

Si || w || n'est pas très différent de || v || et l'angle entre eux n'a pas beaucoup changé (selon certaines tolérances prédéfinies), cela signifie que l'algorithme a convergé et nous pouvons retourner || v || comme la distance.

Sinon, nous ajoutons w à W . Si l'enveloppe convexe de W (c'est-à-dire le simplexe) contient l'origine, les formes se croisent, et cela signifie également que nous avons terminé. Sinon, nous trouvons le point du simplexe le plus proche de l'origine, puis nous réinitialisons v pour qu'il soit cette nouvelle approximation la plus proche. Enfin, nous supprimons tous les points de W qui ne contribuent pas au calcul du point le plus proche. (Par exemple, si nous avons un triangle et que le point le plus proche de l'origine se trouve dans l'une de ses arêtes, nous pouvons supprimer le point de W qui n'est pas un sommet de cette arête.) Ensuite, nous répétons ces mêmes étapes jusqu'à ce que l'algorithme converge.

L'image suivante montre un exemple de quatre itérations de l'algorithme GJK. L'objet bleu représente la différence de Minkowski A⊖B et le vecteur vert est v . Vous pouvez voir ici comment v se concentre sur le point le plus proche de l'origine.

Pour une explication détaillée et approfondie de l'algorithme GJK, consultez l'article A Fast and Robust GJK Implementation for Collision Detection of Convex Objects , par Gino van den Bergen. Le blog du moteur physique dyn4j a également un excellent article sur GJK.

Box2D a une implémentation de l'algorithme GJK dans b2Distance.cpp, dans la fonction b2Distance . Il n'utilise GJK que pendant le calcul du temps d'impact dans son algorithme de détection de collision continue (un sujet dont nous parlerons plus loin).

Le moteur physique Chimpunk utilise GJK pour toutes les détections de collisions, et son implémentation se trouve dans cpCollision.c, dans la fonction GJK . Si l'algorithme GJK signale une intersection, il doit encore connaître les points de contact, ainsi que la profondeur de pénétration. Pour ce faire, il utilise l'algorithme Expanding Polytope, que nous explorerons ensuite.

Détermination de la profondeur de pénétration - L'algorithme du polytope en expansion

Comme indiqué ci-dessus, si les formes A et B sont sécantes, GJK générera un simplexe W qui contient l'origine, à l'intérieur de la différence de Minkowski A⊖B . À ce stade, nous savons seulement que les formes se croisent, mais dans la conception de nombreux systèmes de détection de collision, il est souhaitable de pouvoir calculer combien d'intersection nous avons et quels points nous pouvons utiliser comme points de contact, de sorte que nous gérons la collision de manière réaliste. L' algorithme Expanding Polytope (EPA) nous permet d'obtenir cette information, en commençant là où GJK s'est arrêté : avec un simplexe qui contient l'origine.

La profondeur de pénétration est la longueur du vecteur de translation minimum (MTV), qui est le plus petit vecteur le long duquel on peut translater une forme qui se croise pour la séparer de l'autre forme.

Lorsque deux formes se croisent, leur différence de Minkowski contient l'origine, et le point sur la frontière de la différence de Minkowski qui est le plus proche de l'origine est le MTV. L'algorithme EPA trouve ce point en développant le simplexe que GJK nous a donné en un polygone ; subdivisant successivement ses arêtes avec de nouveaux sommets.

Tout d'abord, nous trouvons l'arête du simplexe la plus proche de l'origine et calculons le point d'appui dans la différence de Minkowski dans une direction normale à l'arête (c'est-à-dire perpendiculaire à celle-ci et pointant à l'extérieur du polygone). Ensuite, nous divisons cette arête en y ajoutant ce point d'appui. Nous répétons ces étapes jusqu'à ce que la longueur et la direction du vecteur ne changent pas beaucoup. Une fois l'algorithme converge, nous avons le MTV et la profondeur de pénétration.

En utilisant GJK en combinaison avec EPA, nous obtenons une description détaillée de la collision, peu importe si les objets se croisent déjà, ou juste assez proches pour être considérés comme une collision.

L'algorithme EPA est décrit dans l'article Proximity Queries and Penetration Depth Computation on 3D Game Objects , également écrit par Gino van den Bergen. Le blog dyn4j a également un article sur l'EPA.

Détection continue des collisions

Les techniques de physique des jeux vidéo présentées jusqu'à présent effectuent une détection de collision pour un instantané statique de la simulation. C'est ce qu'on appelle la détection de collision discrète , et elle ignore ce qui se passe entre les étapes précédentes et actuelles. Pour cette raison, certaines collisions peuvent ne pas être détectées, en particulier pour les objets se déplaçant rapidement. Ce problème est connu sous le nom de tunnellisation .

Les techniques de détection de collision continue tentent de trouver quand deux corps sont entrés en collision entre l'étape précédente et l'étape actuelle de la simulation. Ils calculent le moment de l'impact , nous pouvons donc remonter dans le temps et traiter la collision à ce moment-là.

Le temps d'impact (ou temps de contact) t c est l'instant du temps où la distance entre deux corps est nulle. Si nous pouvons écrire une fonction pour la distance entre deux corps dans le temps, ce que nous voulons trouver est la plus petite racine de cette fonction. Ainsi, le temps de calcul de l'impact est un problème de recherche de racine .

Pour le calcul de l'instant d'impact, on considère l'état (position et orientation) du corps dans l'étape précédente à l'instant t i -1 , et dans l'étape courante à l'instant t i . Pour simplifier les choses, nous supposons un mouvement linéaire entre les étapes.

Simplifions le problème en supposant que les formes sont des cercles. Pour deux cercles C 1 et C 2 , de rayon r 1 et r 2 , où leur centre de masse x 1 et x 2 coïncident avec leur centre de gravité (c'est-à-dire qu'ils tournent naturellement autour de leur centre de masse), on peut écrire la fonction de distance comme:

En considérant le mouvement linéaire entre les étapes, nous pouvons écrire la fonction suivante pour la position de C 1 de t i -1 à t i

C'est une interpolation linéaire de x 1 ( t i -1 ) à x 1 ( t i ) . La même chose peut être faite pour x 2 . Pour cet intervalle, nous pouvons écrire une autre fonction de distance :

Réglez cette expression égale à zéro et vous obtenez une équation quadratique sur t . Les racines peuvent être trouvées directement en utilisant la formule quadratique. Si les cercles ne se croisent pas, la formule quadratique n'aura pas de solution. S'ils le font, cela pourrait entraîner une ou deux racines. S'il n'a qu'une seule racine, cette valeur est le moment de l'impact. S'il a deux racines, la plus petite est le moment de l'impact et l'autre est le moment où les cercles se séparent. Notez que le temps d'impact ici est un nombre de 0 à 1. Ce n'est pas un temps en secondes ; c'est juste un nombre que nous pouvons utiliser pour interpoler l'état des corps à l'endroit précis où la collision s'est produite.

Détection continue des collisions pour les non-cercles

L'écriture d'une fonction de distance pour d'autres types de formes est difficile, principalement parce que leur distance dépend de leurs orientations. Pour cette raison, nous utilisons généralement des algorithmes itératifs qui rapprochent de plus en plus les objets à chaque itération jusqu'à ce qu'ils soient suffisamment proches pour être considérés comme entrant en collision.

L'algorithme d' avancement conservateur déplace les corps vers l'avant (et les fait pivoter) de manière itérative. À chaque itération, il calcule une limite supérieure pour le déplacement. L'algorithme original est présenté dans la thèse de doctorat de Brian Mirtich (section 2.3.2), qui considère le mouvement balistique des corps. Cet article d'Erwin Coumans (l'auteur du Bullet Physics Engine) présente une version plus simple qui utilise des vitesses linéaires et angulaires constantes.

L'algorithme calcule les points les plus proches entre les formes A et B , dessine un vecteur d'un point à l'autre et projette la vitesse sur ce vecteur pour calculer une limite supérieure de mouvement. Il garantit qu'aucun point du corps ne dépassera cette projection. Ensuite, il fait avancer les corps de cette quantité et répète jusqu'à ce que la distance tombe sous une petite valeur de tolérance.

Cela peut prendre trop d'itérations pour converger dans certains cas, par exemple, lorsque la vitesse angulaire de l'un des corps est trop élevée.

Résolution des collisions

Une fois qu'une collision a été détectée, il est nécessaire de modifier les mouvements des objets en collision de manière réaliste, par exemple en les faisant rebondir les uns sur les autres. Dans le prochain et dernier épisode de ces théories, nous discuterons de certaines méthodes populaires pour résoudre les collisions dans les jeux vidéo.

Les références

Si vous souhaitez approfondir vos connaissances sur la physique des collisions, telles que les algorithmes et les techniques de détection des collisions, le livre Real-Time Collision Detection , de Christer Ericson, est un incontournable.

Étant donné que la détection de collision repose fortement sur la géométrie, l'article de Toptal Computational Geometry in Python: From Theory to Application est une excellente introduction au sujet.