Voir la source de Détection de collision

Dans les simulations physiques, les [[jeu vidéo|jeux vidéo]] et la [[géométrie algorithmique]], la '''détection de collision''' implique l'utilisation d'algorithmes pour tester les [[collision]]s (intersection de solides donnés), pour calculer des trajectoires, les dates d'impact et des points d'impact dans une simulation physique.

== Vue d'ensemble ==
[[Fichier:Billiards balls.jpg|right|thumb|Des billes de billard s'entrechoquant est un exemple typique du domaine de la détection de collision.]]

Dans la simulation physique, on souhaite procéder à des expériences, comme jouer au [[billard]]. La [[physique]] des billes de billard est bien décrite, à l'aide de modèles de mouvement de [[corps rigide]] et de [[collision élastique]]. Une description initiale de la scène devrait être donnée, avec une description physique précise de la table de billard et des billes, de même que les positions initiales de toutes les billes. Étant donné une certaine impulsion initiale sur la bille blanche (résultant probablement d'un joueur tapant la bille à l'aide de sa queue), nous voulons calculer les trajectoires, les déplacements précis et les positions finales de toutes les billes avec un [[programme informatique]]. Un programme pour simuler ce jeu possèderait plusieurs parties, l'une d'elles serait responsable du calcul des impacts précis entre les billes de billard. Cet exemple en particulier se révèle être très sensible aux [[stabilité numérique|instabilités numériques]] : une petite erreur dans un calcul pourrait causer des changements importants dans les positions finales des billes.

Les jeux vidéo ont des besoins similaires, avec quelques différences cruciales. Alors que la simulation physique doit simuler la physique du monde réel aussi précisément que possible, les jeux vidéo peuvent le faire d'une manière seulement ''acceptable'', en {{page h'|temps réel}} et de manière robuste. Les compromis sont autorisés, tant que la simulation résultante est satisfaisante pour le joueur.

En géométrie algorithmique, on s'intéresse aux algorithmes permettant d'obtenir une détection précise des collisions (plus comme les simulateurs physiques). Cependant, il faut que ces algorithmes aient de bons temps d'exécution. Malheureusement, la plupart des algorithmes utilisés dans les simulations physiques et les jeux vidéo n'ont pas une [[Principe de localité (informatique)|complexité]] satisfaisante dans le pire des cas, du point de vue de la [[notation de Landau]], même s'il s'avère qu'en pratique ils fonctionnent très bien.

== Détection de collision dans une simulation physique ==
Les simulateurs physiques diffèrent dans la manière dont ils réagissent à une collision. Il y a un gouffre énorme entre une approche [[KISS-principe|KISS]] et une approche maligne. Certains utilisent la dureté de la matière pour calculer une force, ce qui résoudra la collision dans les étapes qui suivent d'une manière proche de la réalité. Ce calcul peut être très consommateur de CPU, selon la mollesse de l'objet. Certains simulateurs estiment la date de la collision via une interpolation linéaire, reviennent en arrière dans la simulation, et calculent la collision à l'aide de la méthode la plus abstraite des [[loi de conservation|lois de conservation]].

Certains itèrent sur l'[[interpolation linéaire]] ([[méthode de Newton]]) pour calculer la date de la collision avec une plus grande précision que le reste de la simulation. La détection de collisions utilise la cohérence du temps pour permettre des étapes de temps plus fines sans augmenter la charge du CPU (voir par exemple le [[Contrôle du trafic aérien]]).

Après une collision rigide, des états particuliers de glissement et d'immobilité peuvent apparaître. Par exemple, l'[[Open Dynamics Engine]] utilise des contraintes pour les simuler. Les contraintes évitent l'inertie, et par conséquent l'instabilité. L'implémentation de l'immobilité par un [[graphe de scène]] évite d'avoir des objets qui dérivent.

=== En d'autres mots ===
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.

=== ''A posteriori'' ou ''a priori'' ===
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 (physique)|adhérence]] et les deux objets sont arrangés dans le même [[graphe de scène]]. Cependant, {{Référence nécessaire|cela pourrait poser des problèmes dans les algorithmes ''a posteriori''}}.

== Optimisation ==
Les approches naïves de détection de collision parmi plusieurs objets sont très lentes. Tester chaque objet avec chaque autre fonctionnera mais est trop inefficace pour être utilisé quand le nombre d'objets est grand. Appliqué à des objets à la géométrie complexe, en testant chaque face avec chaque face de l'autre objet est en soi assez lent. Par conséquent, des recherches considérables ont été effectuées pour accélérer la résolution de ce problème.

=== Élagage à ''n'' corps ===
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 <math>n</math> objets, il y a <math>{n \choose 2} = n(n-1)/2</math> 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 <math>O(n^2)</math>. 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 (mathématiques)|droite]] (comme dans l'exemple du billard) qui sépare les objets en deux [[ensemble]]s sans [[intersection (mathématiques)|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 <math>n</math> objets occupent le même [[point (géométrie)|point]] de l'[[espace (notion)|espace]], alors il faudra tester <math>n(n-1)/2=O(n^2)</math> 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.

=== Exploiter la cohérence temporelle ===
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<ref>{{lien web |titre=Lin-Canny Closest Features Algorithm<!-- Vérifiez ce titre --> |url=http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html |site=berkeley.edu |consulté le=01-07-2023}}.</ref>, qui suggéra d'utiliser des [[volume englobant|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 <math>I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]</math>). On observe que deux boîtes <math>I_1 \times I_2 \times I_3</math> et <math>J_1 \times J_2 \times J_3</math> se croisent [[si et seulement si]] <math>I_1</math> croise <math>J_1</math>, <math>I_2</math> croise <math>J_2</math> et <math>I_3</math> croise <math>J_3</math>. On suppose que d'une étape de temps à la suivante, si <math>I_k</math> et <math>J_k</math> 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 <math>n</math> de boîtes englobantes). Dans chaque liste, chaque intervalle peut croiser tous les autres. Donc, pour chaque liste, nous avons une [[matrice (mathématiques)|matrice]] <math>M=(m_{ij})</math> de valeurs [[bit|binaire]]s et de taille <math>(n \times n)</math> : <math>m_{ij} = 1</math> si les intervalles <math>i</math> et <math>j</math> se croisent.

Par hypothèse, la matrice <math>M</math> 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 naturel|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 <math>M</math> 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êtement]]s, 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.

=== Élagage paire à paire ===
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, <math>S={S_1,S_2,...,S_n}</math> et <math>T={T_1,T_2,...,T_n}</math> (pour simplifier, nous supposerons que chaque ensemble a le même nombre de triangles).

La chose évidente à faire est d'examiner tous les triangles <math>S_j</math> face à tous les triangles  <math>T_k</math> pour les collisions, mais ceci implique des comparaisons de <math>n^2</math>, 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, <math>S</math> et <math>T</math>) nous calculerons une hiérarchie des volumes de frontière. Puis, à chaque temps de l'étape, quand nous devons vérifier les collisions entre <math>S</math> et <math>T</math>, 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 <math>E</math> est un ensemble de triangles, nous pouvons précalculer une sphère de frontière <math>B(E)</math>. Il y a beaucoup de manières de choisir <math>B(E)</math>, nous supposons seulement que <math>B(E)</math> est une sphère qui contient complètement <math>E</math> et qui est aussi petit que possible.

En avance, nous pouvons calculer <math>B(S)</math> et <math>B(T)</math>. 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 <math>S</math> et <math>T</math>. Ce n'est pas bien mieux qu'un algorithme de taillage de ''n''-corps.

Cependant, si <math>E={E_1,E_2,...,E_m}</math> est un ensemble de triangles, alors nous pouvons le couper en deux moitiés <math>L(E):={E_1,E_2,...,E_{m/2}}</math> et <math>R(E):={E_{m/2+1},...,E_{m-1},E_m}</math>. Nous pouvons faire ceci à <math>S</math> et à <math>T</math>, puis nous pouvons calculer (en avance) les sphères de frontière <math>B(L(S)),B(R(S))</math> et <math>B(L(T)),B(R(T))</math>. L'espoir ici est que ces sphères de frontière soient beaucoup plus petites que <math>B(S)</math> et <math>B(T)</math>. 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 <math>S</math> contre n'importe quel triangle en <math>L(T)</math>.

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 <math>N</math> représente un ensemble de triangles et ses deux enfants représentent <math>L(N)</math> et <math>R(N)</math>. À chaque nœud de l'arbre, en tant que nous précalculons la sphère de frontière <math>B(N)</math>.

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 <math>B(T)</math>. 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 [[Spline|cannelures]] au lieu des simples triangles.

=== Détection de collisions exactement appariées ===
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 [[ensemble convexe|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 <math>{v1,v2,v3}</math> et <math>{v4,v5,v6}</math>, où chaque <math>vj</math> est un vecteur dans <math>\mathbb R^3</math>, alors nous pouvons prendre trois sommets, <math>vi,vj,vk</math>, 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<ref>[ftp://ftp.cs.unc.edu/pub/users/manocha/PAPERS/COLLISION/thesis.pdf "Efficient Collision Detection for Animation and Robotics (thesis)" de Lin, Ming C de l'Université de Californie (Berkeley) publié en 1993]
</ref> ont employé une variation de l'[[algorithme du simplexe]] en [[optimisation linéaire]]. {{lien|lang=en|trad=Gilbert-Johnson-Keerthi distance algorithm|texte=L'algorithme de la distance de Gilbert-Johnson-Keerthi}} 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.

=== Elagage à priori ===
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 <math>{\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}</math> et <math>{\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}} </math>. 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 <math>{\displaystyle P(u,v,w)}</math> est le plan passant par les points <math>{\displaystyle u,v,w}</math> dans <math>{\displaystyle {\mathbb {R} }^{3}}</math>, il y a alors vingt plans <math>{\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}</math> à 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 <math>{\displaystyle t}</math>, 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.

=== Partitionnement spatial ===

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.

=== Boîtes englobantes ===

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.

=== Segments de centroïdes de triangles ===

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 <math>{\displaystyle (x_{1},y_{1},z_{1})}</math>, <math>{\displaystyle (x_{2},y_{2},z_{2})} </math> and <math>{\displaystyle (x_{3},y_{3},z_{3})}</math>, le centroïde sera <math>{\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)} </math>.

La distance entre deux points est <math>\mathrm{distance} = \sqrt{(z_2 - z_1)^2 + (x_2 - x_1)^2 + (y_2 - y_1)^2}</math>

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.

== Jeux vidéo ==
Les jeux vidéo doivent partager leur temps de calcul limité entre plusieurs tâches. En dépit de cette limitation des ressources et de l'utilisation d'algorithmes de détection de collision relativement primitifs, les programmeurs ont été capables de créer des systèmes crédibles, bien qu'inexacts, pour une utilisation dans des jeux.

Pendant longtemps, les jeux vidéo avaient un nombre limité d'objets à traiter. Ainsi, la vérification de toutes les paires n'était pas un problème. Dans les jeux bidimensionnels, dans certains cas, le matériel pouvait efficacement détecter et rapporter les [[pixel]]s de recouvrement entre les sprites sur l'écran. Dans d'autres cas, le pavage de l'écran et le [[binning]] de chaque sprite dans les tuiles qu'il recouvre suffit à fournir la taille suffisante, et, pour des contrôles par paires, des enveloppes rectangulaires ou circulaires sont employées et considérées comme suffisamment précises.

Les jeux tridimensionnels ont employé des méthodes de division spatiale pour l'élagage à n-corps, et ont pendant longtemps utilisé une ou quelques sphères par objet 3d réel pour le contrôle par paire. Les contrôles exacts sont très rares, à l'exception de quelques genres tels que la simulation. Mais même là, des contrôles exacts ne sont pas nécessairement employés dans tous les cas.

Puisque les jeux utilisent une physique simplifiée, la stabilité n'est pas indispensable. Presque tous les jeux emploient la détection de collision a posteriori, et les collisions sont souvent résolues en utilisant des règles très simples. Par exemple, si le protagoniste se retrouve de lui-même à l'intérieur d'un mur, il pourrait être simplement déplacé de nouveau à son dernier bon emplacement connu. Quelques jeux calculeront la distance que le protagoniste peut parcourir avant d'être à l'intérieur d'un mur, et lui permettront de se déplacer seulement jusque là.

Un effet légèrement plus sophistiqué et plus saisissant est le modèle physique de "[[Physique ragdoll|ragdoll]]". Si un personnage de jeu vidéo est mis hors d'action, au lieu de jouer une animation prédéfinie, un squelette simplifié du personnage est animé comme s'il s'agissait d'une poupée de chiffon. Cette poupée de chiffon tombe et peut heurter l'environnement, dans ce cas elle se comporte convenablement.

Dans beaucoup de jeux vidéo, ramener les protagonistes à un simple point est suffisant pour détecter les collisions avec l'environnement. Dans ce cas, les arbres binaires de partitionnement de l'espace fournissent un algorithme simple, efficace et viable pour vérifier si un point est inclus dans le paysage ou pas. Une telle [[structure de données]] peut également être employée pour manipuler la situation "de position de repos" avec élégance quand un protagoniste court le long d'une étendue. Des collisions entre les personnages, et les collisions avec des projectiles et les risques, sont traitées séparément.

Un simulateur sera robuste s'il réagit à n'importe quelle entrée d'une manière raisonnable. Par exemple, si nous imaginons un jeu vidéo de course de voitures à grande vitesse, d'une étape de simulation à l'autre, il est possible que les voitures avancent d'une distance substantielle le long du circuit de course. S'il y a un obstacle peu profond sur la voie (tel qu'un mur de brique), il n'est pas entièrement improbable que la voiture le sautera complètement, ce qui est un effet indésirable. Dans d'autres exemples, la "réparation" qu'à postériori les algorithmes exigent n'est pas mise en application correctement, et les personnages se retrouvent dans les murs, ou tombent au loin dans un vide profond de noir. Ce sont les marques d'une détection de collision et d'un système de simulation physique médiocres.

== Notes et références ==
{{Traduction/Référence|en|Collision detection|507480200}}
{{Références}}

== Voir aussi ==
=== Articles connexes ===
*[[Moteur physique]]
*[[Physique numérique]]
*[[OptiX]]

=== Liens externes ===
* [http://www.tsarevitch.org/ozcollide/ OZCollide] Librairie de détection de collision 3D libre, rapide et cross-platform.
* [http://www.game-corp.net/topic-722-0.html Collision glissante 2D en DarkBasic]

{{Portail|jeu vidéo|programmation informatique}}

[[Catégorie:Physique appliquée et interdisciplinaire]]
[[Catégorie:Développement de jeux vidéo]]