Détection de collision

Les simulateurs physiques fonctionnent généralement de deux manières : a posteriori ou a priori. En plus de cette distinction, la plupart des algorithmes modernes de détection de collision sont divisés en une hiérarchie d'algorithmes.

Dans le cas a posteriori, on fait progresser la simulation physique pendant un petit intervalle de temps, puis on vérifie si des objets se rencontrent. À chaque étape de la simulation, une liste de tous les corps en collision est créée, et les positions et trajectoires de ces objets sont corrigées pour prendre en compte la collision. Nous disons que cette méthode est a posteriori parce qu'on manque typiquement le moment réel de la collision ; on ne la détecte que lorsqu'elle a effectivement eu lieu.

Dans les méthodes a priori, on écrit un algorithme de détection de collisions qui sera capable de prédire très précisément les trajectoires des corps physiques. Les instants des collisions sont calculés avec une grande précision, et les corps physiques ne se coupent jamais. On appelle cela a priori car on calcule les instants des collisions avant de mettre à jour la configuration des objets.

Les principaux avantages des méthodes a posteriori sont que, dans ce cas, l'algorithme de détection de collision n'a pas besoin de considérer une innombrable quantité de variables physiques ; une simple liste des objets est donnée à l'algorithme et le programme retourne une liste d'objets en collision. L'algorithme de détection de collision n'a pas besoin de gérer la friction, les collisions élastiques, ou pire, les collisions non élastiques et les corps déformables. De plus, les algorithmes a posteriori sont en pratique d'une dimension plus simple que les algorithmes a priori. En effet, un algorithme a priori doit gérer une variable de temps, qui est absente du problème a posteriori.

D'un autre côté, les algorithmes a posteriori posent des problèmes à l'étape de correction, où les intersections (qui ne sont pas physiquement correctes) doivent être corrigées. En fait, un tel algorithme est parfois considéré comme intrinsèquement imparfait et instable.

Les avantages des algorithmes a priori augmentent la fidélité et la stabilité. Il est difficile (mais pas complètement impossible) de séparer la simulation physique de l'algorithme de détection de collision. Cependant, dans les cas non simples, le problème de déterminer en avance la date de collision de deux objets (étant donné quelques données initiales) n'a pas de solution bien définie—un algorithme de recherche d'un zéro d'une fonction est en général nécessaire.

Étant donné qu'il est impossible d'obtenir les valeurs exactes, on peut aussi utiliser un simple algorithme a posteriori puis utiliser une recherche dichotomique pour tenter de calculer le moment initial d'une collision, s'il y en a. Cependant, en dehors du fait que cette méthode peut rater certaines collisions, la recherche dichotomique est connue pour être relativement inefficace comparée à d'autres méthodes de recherche de zéro, telle que la méthode de Newton.

Certains objets restent en contact, c'est-à-dire en collision mais sans rebondir ni s'interpénétrer, tel un vase posé sur une table. Dans tous les cas, la situation de contact requiert un traitement spécial: si deux objets sont en collision (a posteriori) ou glissent (a priori) et que le leur mouvement relatif est en dessous d'un seuil, le frottement devient adhérence et les deux objets sont arrangés dans le même graphe de scène. Cependant, cela pourrait poser des problèmes dans les algorithmes a posteriori.

Pour les problèmes où plusieurs corps bougent simultanément (comme des boules de billard) une étape de pré-sélection permet de réduire le nombre de paires d'objets que l'on doit considérer dans la collision.

Avec ${\displaystyle n}$ objets, il y a ${\displaystyle {n \choose 2}=n(n-1)/2}$ paires d'objets qui peuvent éventuellement entrer en collision (voir Coefficient binomial). Itérer parmi toutes les paires donnerait un algorithme avec une complexité temporelle en ${\displaystyle O(n^{2})}$. Dans l'exemple du billard, avec treize billes sur la table, soixante-dix-huit paires seront testées. Cependant, s'il n'y a que sept billes dans la moitié nord de la table et six dans la partie sud, alors on peut se limiter à tester les billes de la partie nord entre elles, de même pour celles de la partie sud. Dans ce cas, seulement trente-six paires de billes seront testées.

Le problème est que pour de gros objets très proches les uns des autres, il n'est pas toujours facile de trouver une droite (comme dans l'exemple du billard) qui sépare les objets en deux ensembles sans intersection. Cela peut être corrigé à l'aide d'un algorithme récursif ; on obtient alors un programme qui semble fonctionner plus rapidement que l'approche naïve en général.

Du point de vue du comportement dans le pire des cas, on remarque que si tous les ${\displaystyle n}$ objets occupent le même point de l'espace, alors il faudra tester ${\displaystyle n(n-1)/2=O(n^{2})}$ paires. C'est pour cela qu'on s'intéresse plutôt à des algorithmes dont la complexité temporelle s'exprime en fonction de la taille de leur sortie. Dans notre cas, ces algorithmes s'exécuteront plus rapidement si le nombre de collisions est petit.

Dans beaucoup d'applications, la disposition des corps physiques change très peu d'une étape de temps à une autre. Certains objets ne bougent même pas. Des algorithmes ont été créés pour que les calculs faits dans une étape précédente puissent être réutilisés à l'étape courante.

D'un point de vue macroscopique, l'objectif de la détection de collision est de trouver des paires d'objets qui peuvent éventuellement se croiser. Ces paires nécessiteront un traitement ultérieur. Un algorithme performant pour effectuer cela a été développé par M. C. Lin de l'université de Berkley[1], qui suggéra d'utiliser des boîtes englobantes pour tous les objets de la scène.

En trois dimensions, chaque boîte est représentée par le produit cartésien de trois intervalles (une boîte serait ${\displaystyle I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]}$). On observe que deux boîtes ${\displaystyle I_{1}\times I_{2}\times I_{3}}$ et ${\displaystyle J_{1}\times J_{2}\times J_{3}}$ se croisent si et seulement si ${\displaystyle I_{1}}$ croise ${\displaystyle J_{1}}$, ${\displaystyle I_{2}}$ croise ${\displaystyle J_{2}}$ et ${\displaystyle I_{3}}$ croise ${\displaystyle J_{3}}$. On suppose que d'une étape de temps à la suivante, si ${\displaystyle I_{k}}$ et ${\displaystyle J_{k}}$ se croisent, alors il est fort probable qu'ils soient toujours croisés à l'étape suivante. De même, s'ils ne se croisent pas à l'étape précédente, il est fort probable qu'ils ne se croisent toujours pas à l'étape suivante.

Ainsi nous réduisons le problème à celui de suivre, d'une étape à l'autre, quels intervalles se croisent. Nous avons une liste d'intervalles (une pour chaque axe), toutes de même longueur (égale au nombre ${\displaystyle n}$ de boîtes englobantes). Dans chaque liste, chaque intervalle peut croiser tous les autres. Donc, pour chaque liste, nous avons une matrice ${\displaystyle M=(m_{ij})}$ de valeurs binaires et de taille ${\displaystyle (n\times n)}$ : ${\displaystyle m_{ij}=1}$ si les intervalles ${\displaystyle i}$ et ${\displaystyle j}$ se croisent.

Par hypothèse, la matrice ${\displaystyle M}$ associée à une liste d'intervalles sera quasiment inchangée d'une étape à une autre. Pour exploiter cela, la liste d'intervalles est implémentée avec une liste des bornes d'intervalle. À chaque élément de la liste on associe les coordonnées des bornes de fin d'intervalle, ainsi qu'un identifiant entier unique représentant cet intervalle. Puis, un algorithme de tri est appliqué pour trier la liste par coordonnée et mettre à jour la matrice ${\displaystyle M}$ dans la foulée. Il n'est pas difficile de voir que cet algorithme sera relativement rapide si, en effet, la disposition des boîtes ne change pas significativement d'une étape à l'autre.

Dans le cas de corps déformables, tels que des vêtements, il se peut qu'un tel algorithme ne soit pas applicable et qu'un algorithme n-body pruning soit le meilleur.

Si la vitesse des objets est bornée supérieurement, alors les paires d'objets peuvent être filtrées selon la distance les séparant et la durée d'une étape de temps.

Une fois que nous avons choisi une paire de corps physiques pour davantage de recherches, nous devons vérifier les collisions plus soigneusement. Cependant, dans beaucoup d'applications, différents objets (s'ils ne sont pas trop déformables) sont décrits par un ensemble de plus petites primitives, principalement des triangles. Aussi maintenant, nous avons deux ensembles de triangles, ${\displaystyle S={S_{1},S_{2},...,S_{n}}}$ et ${\displaystyle T={T_{1},T_{2},...,T_{n}}}$ (pour simplifier, nous supposerons que chaque ensemble a le même nombre de triangles).

La chose évidente à faire est d'examiner tous les triangles ${\displaystyle S_{j}}$ face à tous les triangles ${\displaystyle T_{k}}$ pour les collisions, mais ceci implique des comparaisons de ${\displaystyle n^{2}}$, lesquelles sont déplaisantes. Si possible, il est souhaitable d'employer un algorithme de taille pour réduire le nombre de paires de triangles que nous devons vérifier.

La famille la plus largement répandue des algorithmes est connue comme méthode de frontière hiérarchique de volumes. Comme étape de prétraitement, pour chaque objet (dans notre exemple, ${\displaystyle S}$ et ${\displaystyle T}$) nous calculerons une hiérarchie des volumes de frontière. Puis, à chaque temps de l'étape, quand nous devons vérifier les collisions entre ${\displaystyle S}$ et ${\displaystyle T}$, les volumes de frontières hiérarchiques sont employées pour réduire le nombre de paires de triangles à étudier. Au nom de la simplicité, nous donnerons un exemple en utilisant les sphères de frontière, bien qu'on l'ait noté que les sphères sont indésirables dans beaucoup de cas.

Si ${\displaystyle E}$ est un ensemble de triangles, nous pouvons précalculer une sphère de frontière ${\displaystyle B(E)}$. Il y a beaucoup de manières de choisir ${\displaystyle B(E)}$, nous supposons seulement que ${\displaystyle B(E)}$ est une sphère qui contient complètement ${\displaystyle E}$ et qui est aussi petit que possible.

En avance, nous pouvons calculer ${\displaystyle B(S)}$ et ${\displaystyle B(T)}$. Clairement, si ces deux sphères n'ont pas d'intersection (et c'est très facile à tester), alors ni l'un ni l'autre font ${\displaystyle S}$ et ${\displaystyle T}$. Ce n'est pas bien mieux qu'un algorithme de taillage de n-corps.

Cependant, si ${\displaystyle E={E_{1},E_{2},...,E_{m}}}$ est un ensemble de triangles, alors nous pouvons le couper en deux moitiés ${\displaystyle L(E):={E_{1},E_{2},...,E_{m/2}}}$ et ${\displaystyle R(E):={E_{m/2+1},...,E_{m-1},E_{m}}}$. Nous pouvons faire ceci à ${\displaystyle S}$ et à ${\displaystyle T}$, puis nous pouvons calculer (en avance) les sphères de frontière ${\displaystyle B(L(S)),B(R(S))}$ et ${\displaystyle B(L(T)),B(R(T))}$. L'espoir ici est que ces sphères de frontière soient beaucoup plus petites que ${\displaystyle B(S)}$ et ${\displaystyle B(T)}$. Et, si, par exemple, B(s) et B(L(t)) n'ont pas d'intersection, alors il n'y a aucun sens à tester n'importe quel triangle dans ${\displaystyle S}$ contre n'importe quel triangle en ${\displaystyle L(T)}$.

Comme précalcul, nous pouvons prendre chaque corps physique (représenté par un ensemble de triangles) et le décomposer récursivement dans un arbre binaire, où chaque nœud ${\displaystyle N}$ représente un ensemble de triangles et ses deux enfants représentent ${\displaystyle L(N)}$ et ${\displaystyle R(N)}$. À chaque nœud de l'arbre, en tant que nous précalculons la sphère de frontière ${\displaystyle B(N)}$.

Quand le moment vient pour tester une paire d'objets pour la collision, leur arbre de sphère frontière peut être employé pour éliminer beaucoup de paires de triangles.

Beaucoup de variantes des algorithmes sont obtenues en choisissant quelque chose autre qu'une sphère pour ${\displaystyle B(T)}$. Si on choisit les boîtes de frontière axe-alignées, on obtient des arbres AABB. Des arbres de bondissement orientés boîte s'appellent ArbresOBB. Il est plus facile mettre à jour quelques arbres si l'objet fondamental change. Quelques arbres peuvent s'adapter à des primitives d'ordre plus supérieures tels que des cannelures au lieu des simples triangles.

Une fois procédé à l'élagage, il subsiste un certain nombre de paires, candidates au contrôle de détection des collisions exactes.

Une observation de base est que pour toute paire d'objets convexes quelconques disjoints, il existe dans l'espace un plan tel qu'un des objets se trouve entièrement d'un côté de cette surface et l'autre objet du côté opposé. Ceci autorise le développement d'algorithmes très rapides de détection de collision pour les objets convexes.

Les premiers travaux dans ce secteur ont impliqué des méthodes de "séparation des convexes". Deux triangles se heurtent essentiellement seulement quand ils ne peuvent pas être séparés par une surface plane passant par les trois sommets. C'est-à-dire que si les triangles sont ${\displaystyle {v1,v2,v3}}$ et ${\displaystyle {v4,v5,v6}}$, où chaque ${\displaystyle vj}$ est un vecteur dans ${\displaystyle \mathbb {R} ^{3}}$, alors nous pouvons prendre trois sommets, ${\displaystyle vi,vj,vk}$, trouver une surface plane passant par chacun des trois sommets et vérifier si c'est une surface plane de séparation. Si une telle surface plane est un plan de séparation, alors les triangles sont considérées comme disjoints. D'autre part, si l'un quelconque de ces plans est un plan de séparation, alors les triangles sont considérés comme en intersection. Il existe vingt de ces plans.

Si les triangles sont coplanaires, ce test n'est pas entièrement réussi. On peut aussi ajouter quelques surfaces planes supplémentaires, par exemple, des surfaces planes qui sont perpendiculaires aux bords de triangle, pour régler le problème entièrement. Dans d'autres cas, les objets qui se rassemblent face à plat doivent nécessairement également se réunir sous un angle quelque part, par conséquent la détection de collision globale sera capable de trouver la collision.

De meilleures méthodes ont été depuis développées. Des algorithmes très rapides sont disponibles pour trouver les points les plus près sur la surface de deux objets polyédriques convexes. Les premiers travaux par M. C. Lin[2] ont employé une variation de l'algorithme du simplexe en optimisation linéaire. L'algorithme de la distance de Gilbert-Johnson-Keerthi (en) a remplacé cette approche. Ces algorithmes approchent en temps constant où est appliqué à plusieurs reprises aux paires stationnaires ou aux objets bougeant lentement, une fois utilisés avec ces points de départ à partir du précédent contrôle de collision.

À la suite de tout ce travail algorithmique, la détection de collision peut être réalisée efficacement pour des milliers d'objets mobiles en temps réel sur des PCs conventionnels et sur des consoles de jeu.

Lorsque la plupart des objets impliqués sont fixes, comme c'est souvent le cas des jeux vidéo, on peut utiliser des méthodes à priori utilisant un pré-calcul pour une exécution plus rapide.

L'élagage est également souhaitable dans ce cas, aussi bien l'élagage n-corps que paire-à-paire, mais les algorithmes doivent prendre en considération le temps et les types de déplacements utilisés dans le système physique sous-jacent.

La détection de collision exacte par paire dépend fortement des trajectoires, et on doit souvent utiliser un algorithme numérique de recherche de racines pour calculer l'instant d'impact.

Considérons l'exemple de deux triangles se déplaçant ${\displaystyle {\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}}$ et ${\displaystyle {\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}}$. A tout moment, on peut vérifier l'intersection des deux triangles en utilisant les vingt plans mentionnés précédemment. On peut cependant faire mieux, car on peut suivre ces vingt plans dans le temps. Si ${\displaystyle {\displaystyle P(u,v,w)}}$ est le plan passant par les points ${\displaystyle {\displaystyle u,v,w}}$ dans ${\displaystyle {\displaystyle {\mathbb {R} }^{3}}}$, il y a alors vingt plans ${\displaystyle {\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}}$ à suivre. Il faut suivre chaque plan par rapport à trois sommets, ce qui donne soixante valeurs à suivre. L'utilisation d'une résolution de racines pour ces soixante fonctions produit les temps de collision exacts pour les deux triangles données, et les deux trajectoires données. Notons ici que si les trajectoires des sommets sont supposées polynômiales linéaires en ${\displaystyle {\displaystyle t}}$, les soixante fonctions finales sont en fait polynomiales cubiques, et, dans ce cas exceptionnel, il est possible de situer le temps de collision exact en utilisant la formule des racines des polynômes cubiques. Certains spécialistes en analyse numérique suggèrent qu'utiliser la formule des racines des polynômes cubiques pour les polynômes n'est pas aussi stable que l'utilisation d'une résolution de racines.

D'autres algorithmes sont regroupés sous la catégorie de partitionnement spatial, qui inclut les "octree", le partitionnement d'espace binaire (ou arbres BSP), et d'autres approches similaires. Si l'espace est découpé en un certain nombre de cellules simples, et si on peut montrer que deux objets ne sont pas dans la même cellule, il ne faut alors pas vérifier s'ils se croisent. Comme il est possible de pré-calculer les arbres BSP, cette approche est bien adaptée à la gestion des murs et des obstacles fixes dans les jeux. Ces algorithmes sont généralement plus anciens que les algorithmes décrits plus haut.

Les boîtes englobantes (ou volumes englobants) sont la plupart du temps des rectangles 2D ou des cuboïdes 3D, mais d'autres formes sont possibles. On a essayé le diamant englobant, le parallélogramme englobant minimum, l'enveloppe convexe, le cercle englobant ou la balle englobante, et l'ellipse englobante, mais les boîtes englobantes restent les plus populaires grâce à leur simplicité. [3] boîtes englobantes sont généralement utilisées lors de l'étape initiale (élagage) de la détection de collision, pour n'avoir à comparer en détail que les objets dont les boîtes englobantes se recouvrent.

Un objet à mailles triangulaires est souvent utilisé dans la modélisation 3D. Normalement, la fonction de collision est une rencontre triangle-triangle ou une forme englobante associée à la maille. On appelle centroïde du triangle l'emplacement du centre de masse (tel qu'il serait en équilibre sur une pointe de crayon). La simulation doit seulement ajouter une dimension de centroïde aux paramètres physiques. Etant donné des points centroïdes aussi bien pour l'objet que pour la cible, il est possible de déterminer le segment joignant ces deux points.

Le vecteur de position du centroïde d'un triangle est la moyenne des vecteurs de positions de ses sommets. Ainsi, si les sommets possèdent les coordonnées cartésiennes ${\displaystyle {\displaystyle (x_{1},y_{1},z_{1})}}$, ${\displaystyle {\displaystyle (x_{2},y_{2},z_{2})}}$ and ${\displaystyle {\displaystyle (x_{3},y_{3},z_{3})}}$, le centroïde sera ${\displaystyle {\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}}$.

La distance entre deux points est ${\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}$

La longueur du segment est ainsi un critère de contact ajustable. Lorsque les objets approchent, la longueur diminue jusqu'à une valeur seuil. Une sphère centrée sur le centroïde pour être dimensionnée pour englober tous les sommets des triangles.

• Moteur physique
• Physique numérique
• OptiX

• OZCollide Librairie de détection de collision 3D libre, rapide et cross-platform.
• Collision glissante 2D en DarkBasic