Dans les simulations physiques, les jeux vidéo et la géométrie algorithmique, la détection de collision implique l'utilisation d'algorithmes pour tester les collisions (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 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 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 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 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. On ne peut donc pas garantir que le programme ne rencontrera jamais de collision dont le temps de détection est trop élevé pour que le jeu reste fluide.
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 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 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 et les deux objets sont arrangés dans le même graphe de scène. Cependant, .
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 objets, il y a 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 . 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 objets occupent le même point de l'espace, alors il faudra tester 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., 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 ). On observe que deux boîtes et se croisent si et seulement si croise , croise et croise . On suppose que d'une étape de temps à la suivante, si et 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 de boîtes englobantes). Dans chaque liste, chaque intervalle peut croiser tous les autres. Donc, pour chaque liste, nous avons une matrice de valeurs binaires et de taille : si les intervalles et se croisent.
Par hypothèse, la matrice 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 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.