TD 6-7 : La théière et le lapin (suite)
Partie V - Détection de collisions entre plusieurs objets
Introduction
Nous allons maintenant examiner le cas de la détection de collisions entre objets multiples. Pour cela, modifiez la fonction main de la classe TD67 de la façon suivante : commentez la ligne InterfaceA.demarrer(); et enlevez les commentaires devant la ligne InterfaceB.demarrer();. En exécutant le programme TD67, la fenêtre suivante apparait (Figure 13).
Figure 13. Détection de collisions entre objets multiples.
Ce nouveau programme simule le mouvement de plusieurs objets mobiles. Parce que les fonctions de détection de collisions ne sont pas encore programmées, les objets sortent du cube, et ne rebondissent pas les uns sur les autres (cf Figure 13). Par la suite, nous allons programmer une méthode efficace de détection de collisions entre objets multiples, qui évite la complexité quadratique d'un algorithme naïf. Un algorithme de ce genre est souvent utilisé en premier lieu, afin de détecter rapidement les paires d'objets potentiellement en contact, avant de procéder à une détection de collisions plus précise entre les paires d'objets (par exemple à l'aide de l'algorithme de la question 14).
Dans ce programme, les objets sont donc de simples sphères (dans une application, ces sphères seraient les sphères englobantes des objets).
Question 15 - Droit dans le mur...
Afin que les sphères restent dans le cube, commencez par compléter la fonction detecterCollisionsAvecMurs(Sphere[] sphere, Vecteur3[] point, Vecteur3[] normale, ListePairesIndices listePairesIndices) de la classe TD67. Les six murs sont des demi-espaces décrits par les tableaux point et normale. Lorsque la sphère i pénètrera un mur, on insèrera la sphère dans la liste listePairesIndices de la façon suivante :
listePairesIndices.inserer(i,-1);.
|
Indice
Indice : On utilisera bien sûr une des fonctions écrites précédemment. |
Question 16 - Carré ment lent...
Complétez maintenant la fonction detecterCollisionsEntreSpheresQuadratique(ListePairesIndices listePairesIndices) de la classe TD67, en écrivant un algorithme de complexité quadratique pour détecter les collisions entre les sphères. Lorsque les sphères i et j seront en collision, on insèrera la paire de sphères dans la liste listePairesIndices de la façon suivante :
listePairesIndices.inserer(i,j);.
|
Indice 1
Indice 1 : On utilisera bien sûr une des fonctions écrites précédemment. |
|
Indice 2
Indice 2 : On évitera d'être "trop" quadratique, en ne testant que les paires telles que i soit strictement plus petit que j. |
On pourra observer le résultat et remarquer le temps nécessaire pour détecter les collisions (affiché dans l'application - Figure 14).
Figure 14. Algorithme quadratique.
Question 17 - Sweep and prune
L'algorithme Sweep and Prune que nous allons utiliser pour détecter rapidement des collisions entre les objets repose sur la réduction de la dimensionalité du problème. Concrètement, nous allons projeter les sphères suivant trois axes, Ox, Oy et Oz, et déterminer les recouvrements entre les projections suivant ces axes. Nous n'effectuerons alors un test de recouvrement entre deux sphères que lorsque les projections -suivant les trois axes- se recouvreront (notez que le recouvrement entre les projections des sphères est une condition nécessaire au recouvrement entre les sphères elles-mêmes, puisqu'il indique un recouvrement entre les boîtes englobant les sphères).
Parce que la projection d'une sphère selon un axe est un intervalle, nous allons utiliser une classe BorneIntervalle (fichier BorneIntervalle.java) pour décrire la position des bornes des intervalles sur un axe. Ainsi, la classe BorneIntervalle contient un champ borne, de type double, un champ debutIntervalle, de type boolean (qui vaut true lorsque la borne est la borne inférieure de l'intervalle), et un champ indice, de type int, qui contient l'indice de la sphère dont l'intervalle est la projection.
Les projections des sphères selon les axes Ox, Oy et Oz vont être stockées dans les tableaux statiques de bornes d'intervalles. Afin de détecter rapidement des recouvrements entre les intervalles, nous allons trier les bornes par ordre croissant dans les tableaux. A chaque pas de temps de simulation, les bornes vont être modifiées en raison du mouvement des objets. En théorie, le tri des tableaux à chaque pas de temps serait de complexité O(nlog(n)) (c.f. cours). Cependant, si les objets bougent seulement un peu d'un pas de temps à l'autre, les tableaux de bornes seront presque triés. Nous allons donc utiliser le tri par insertion pour trier les tableaux de bornes à chaque pas de temps. Bien que ce tri soit de complexité quadratique dans le cas le pire, il est de complexité quasi-linéaire lorsque les tableaux sont presque triés.
Commencez par compléter la fonction echangerBornes(BorneIntervalle a, BorneIntervalle b) de la classe TD67, qui échange le contenu des deux bornes référencées par a et b.
Question 18 - Tri par insertion
Complétez la fonction trierBornesParInsertion(BorneIntervalle[] borneIntervalle) de la classe TD67, qui trie les bornes du tableau borneIntervalle par insertion.
Rappel : le tri par insertion fonctionne de la manière suivante : pour chaque élément i du tableau, de 0 à borneIntervalle.length, on parcourt les éléments à gauche de i, vers la gauche (en utilisant un indice j qui varie de i-1 à 0), afin de déterminer à quel endroit la borne i doit s'insérer dans le tableau composé des éléments de 0 à i-1. Lors du parcours vers la gauche (i.e., lorsque j décroit), on échange les éléments d'indices j et j+1 lorsque les bornes correspondantes ne sont pas dans le bon ordre (i.e., lorsque borneIntervalle[j+1].borne est plus petit que borneIntervalle[j].borne). Puisque, lorsque l'on examine l'élément i, les éléments de 0 à i-1 sont déjà triés, on peut arrêter le parcours vers la gauche lorsque l'élément j est plus petit que l'élément j+1. Ainsi, lorsque le tableau est déjà trié, le tri par insertion a une complexité linéaire.
Question 19 - Intervalles...
Commencez par ajouter à la classe TD67 trois déclarations de tableaux de bornes d'intervalles (type BorneIntervalle[]) destinés à stocker les projections des sphères selon les axes Ox, Oy et Oz. On pourra par exemple appeler ces tableaux borneIntervalleX, borneIntervalleY et borneIntervalleZ.
Complétez la fonction initialiserIntervalles(Sphere[] sphere) de la classe TD67, qui initialise les trois tableaux de bornes d'intervalles borneIntervalleX, borneIntervalleY et borneIntervalleZ. Plus précisément, vous allouerez suffisamment de mémoire pour chaque tableau, pour pouvoir stocker les projections de toutes les sphères, puis vous remplirez ces tableaux avec les projections des sphères dans les trois directions. Enfin, vous trierez les tableaux grâce à la fonction précédente.
Question 20 - ...et matrices
Nous allons également mémoriser le statut de recouvrement (true ou false) des intervalles et des sphères à chaque étape. Pour cela, ajoutez à la classe TD67 un tableau tridimensionnel de booléens :
static boolean[][][] matriceCollisions;
Pour deux sphères i et j, l'état des recouvrements selon X, selon Y, selon Z, et global (i.e., selon X et Y et Z) sera stocké respectivement dans matriceCollisions[i][j][0], matriceCollisions[i][j][1], matriceCollisions[i][j][2] et matriceCollisions[i][j][3].
Ajoutez enfin une liste de paire de boîtes en collisions :
static ListePairesIndices listePairesBoitesEnCollision;
Cette liste sera mise à jour à chaque pas de simulation.
Maintenant que ces déclarations ont été ajoutées, complétez la fonction initialiserMatriceCollisionsEtListePairesBoitesEnCollision(Sphere[] sphere) de la classe TD67, qui initialise les matrices utilisées pour stocker l'état (true ou false) des recouvrements entre paires d'intervalles ou de boîtes (matriceCollisions), ainsi que la liste des paires de boîtes en collision (listePairesBoitesEnCollision). Comme précédemment, on allouera suffisamment de mémoire, et on initialisera le contenu de la matrice et de la liste en fonction du tableau de sphères fourni en paramètre.
|
Indice 1
Indice 1: l'allocation de la matrice pourra être faite de la manière suivante : matriceCollisions=new boolean[sphere.length][sphere.length][4]; |
|
Indice 2
Indice 2: il suffira de stocker les états pour j strictement plus grand que i. |
Question 21 - "Intervalles combien" ?
Complétez la fonction miseAJourIntervalles(Sphere[] sphere) de la classe TD67, qui met à jour les valeurs des bornes dans les tableaux borneIntervalleX, borneIntervalleY et borneIntervalleZ (sans les trier). Cette fonction sera appelée à chaque pas de simulation.
NB: les sphères ont bougé depuis l'initialisation des intervalles, mais on souhaite faire la mise à jour en temps linéaire.
Question 22 - Pas à pas...
L'algorithme Sweep and Prune repose sur le fait qu'il est possible de mettre à jour les matrices de collisions entre intervalles (matriceCollisions[][][0], matriceCollisions[][][1] et matriceCollisions[][][2]) de façon incrémentale, au cours du tri. En vous inspirant de la fonction trierBornesParInsertion(...), complétez la fonction triBornesEtMiseAjourMatriceSimultanes(BorneIntervalle[] borneIntervalle, int axe), qui trie le tableau borneIntervalle et met à jour la matrice de collisions correspondante.
Important : on fera en sorte que, lorsque le tableau est déjà trié, la fonction ait une complexité linéaire.
Question 23 - Suppression
Nous allons nous inspirer de la fonction précédente pour mettre à jour la liste des paires de boîtes englobantes en collision. Complétez la fonction supprimer(ListePairesIndices liste, int indiceA, int indiceB) de la classe TD67, qui supprime la paire d'indices (indiceA, indiceB) si elle fait partie de la liste liste (et renvoie true), ou renvoie false si la paire ne fait pas partie de la liste.
Question 24 - Sweep...
En vous inspirant de la fonction triBornesEtMiseAjourMatriceSimultanes(...), complétez la fonction miseAjourListePairesBoitesEnCollision(BorneIntervalle[] borneIntervalle, int axe) de la classe TD67, qui trie le tableau borneIntervalle tout en mettant à jour la matrice de collisions correspondante ainsi que la matrice de booléens de recouvrement des boîtes englobantes et la liste de paires de boîtes en collision.
Important : ici aussi on fera en sorte que, lorsque le tableau est déjà trié, la fonction ait une complexité linéaire.
Question 25 - ...and Prune
Utilisez les fonctions précédentes pour compléter la fonction detecterCollisionsEntreSpheresOptimise(Sphere[] sphere, ListePairesIndices listePairesIndices), qui détecte les collisions entre paires de sphères (et non les paires de boîtes!) en temps quasi-linéaire lorsque les objets se déplacent peu d'un pas de temps à l'autre (et en temps linéaire lorsque les sphères sont immobiles). On supposera que la liste listePairesIndices fournie en paramètre est vide, et qu'il faut y insérer les paires de sphères en collision.
On pourra observer la réduction significative du temps de calcul en sélectionnant l'option "Optimise" (Figure 15). Par ailleurs, on pourra tester la validité des algorithmes optimisés en sélectionnant l'option "Test", qui exécute les deux algorithmes (quadratique et optimisé) et compare les listes de paires de sphères en collision (et affiche les listes lorsqu'elles sont différentes).
Figure 15. Détection de collisions optimisée. Dans cet exemple, l'algorithme optimisé détecte les paires de sphères en collision en moins d'une milliseconde.
Partie VI - Détection de collisions entre plusieurs objets par table de hachage
Introduction
Comme nous l'avons vu, le problème de la méthode sweep-and-prune est que la complexité devient quadratique lorsque les objets se déplacent trop rapidement (complexité que l'on pourrait réduire à nlog(n) en changeant d'algorithme de tri). Nous allons maintenant faire une hypothèse supplémentaire sur les objets qui composent la scène, et utiliser une table de hachage pour détecter efficacement des collisions entre objets multiples rapides.
Ainsi, supposons maintenant que toutes les sphères ont à peu près le même rayon (borné par rMax, que l'on déduira du code de la fonction initialisationScene()), et imaginons que la scène est découpée en cellules cubiques de côté 2*rMax.
En supposant également que les recouvrements entre sphères sont détectés rapidement lorsqu'ils interviennent (et que les sphères ne peuvent donc jamais se recouvrir largement), un petit nombre de sphères occupe la même cellule cubique de la scène à un instant donné.
Question 26 - Une petite dernière...
Créez dans un fichier NoeudFileSpheres.java la classe NoeudFileSpheres, destinée à gérer une liste d'objets de type Sphere, et munissez la d'un constructeur qui permet d'ajouter un maillon en tête de liste. Cette liste sera utilisée pour prendre en compte les collisions dans la table de hachage.
Question 27 - Et tu caches, et tu caches... (Briche)
Créez dans un fichier TableDeSpheres.java la classe TableDeSpheres, qui implémente une table de hachage permettant d'insérer des sphères. Plus précisément, cette classe possèdera une référence à un tableau d'objets de type NoeudFileSpheres et implémentera notamment les fonctions int hashSphere(Sphere s) (pour obtenir un indice en fonction des coordonnées du centre de la sphere), void insererSphere(Sphere s) (pour insérer une sphère dans la table, et gérer d'éventuelles collisions), et void viderTable() (pour réinitialiser la table). On supposera que les sphères ne seront insérées qu'une seule fois. Il ne sera donc pas nécessaire de vérifier la présence d'une sphère dans la table avant de faire son insertion. Le nombre de cellules cubiques nCubesParCote sera une variable statique de la table de hachage, fourni en paramètre à un constructeur.
Question 28 - Hache que chat va vite!
Ajoutez une référence à une table de hachage dans le fichier TD67.java. On veillera à ce que la table soit construite lors de l'initialisation de la scène.
Proposez un algorithme efficace de détection de collisions entre objets multiples qui utilise la table de hachage. Vous implémenterez votre algorithme dans une fonction detecterCollisionsEntreSpheresParTableDeHachage(...) ajoutée au fichier TD67.java. Vous pourrez modifier la fonction avancerSimulation() de la classe InterfaceB pour vérifier le bon fonctionnement de votre algorithme.
Question 29 - Au pire...
Quelle est la complexité théorique dans le cas le pire de votre algorithme ? Donnez la réponse, et sa justification, dans un fichier complexite.txt.
Un petit mot pour la fin...
La conception de méthodes de recherche géométrique est un thème de recherche encore actif (objets complexes, objets déformables, détection de collisions continue, etc.), par exemple pour concevoir des méthodes de qualité utilisables dans les jeux vidéo, dans les logiciels de conception assistée par ordinateur, de simulation de dynamique moléculaire, etc. Ces TDs n'ont fait qu'aborder la question (tout en vous donnant une solide introduction au problème et aux méthodes employées). Si ce sujet vous intéresse, vous trouverez facilement plus d'informations en traînant sur Google.
Stéphane Redon - 2005-2012 - stephane.redon@inria.fr - http://nano-d.inrialpes.fr/~redon