Détection de collisions entre N solides : méthode discrète

1. Introduction

On s'intéresse à une simulation dynamique de N solides indéformables pouvant entrer en collision. Ce problème se pose dans la programmation des jeux vidéos, mais aussi dans certaines simulations physiques, par exemple celle du modèle des sphères dures.

Pour détecter les collisions entre les solides, il y a deux méthodes ([1]):

• Méthode continue (détection a priori) : à chaque étape, les trajectoires des solides sont calculées exactement pour déterminer, pour chaque paire, l'instant précis de la collision.
• Méthode discrète (détection a posterori) : le mouvement des solides est calculé de manière discrète, avec un pas de temps assez petit. À chaque pas, on recherche les intersections entre solides. Lorsqu'une intersection est trouvée, on remonte le temps pour en déduire la collision correspondante.

La première méthode est sans doute la meilleure (plus rapide et plus robuste) lorsque les solides n'exercent pas de forces entre eux (en dehors des collisions), ce qui rend la prévision a priori de la collision de deux solides faisables. C'est la méthode à utiliser pour le modèle des sphères dures.

Lorsqu'il y a des interactions entre solides, ou lorsque leur forme complexe rend trop difficile la détection a priori, ont doit utiliser la seconde méthode, à laquelle on s'intéresse dans ce document. On voit immédiatement une faiblesse de cette méthode : si le pas de temps n'est pas assez petit, certains objets peuvent se traverser sans que leur collision ne soit détectée.

À chaque pas de temps de la simulation, il faut détecter les intersections entre objets puis calculer l'instant de contact pour les objets ayant une intersection, afin d'en déduire leur position au moment du contact. Une détection de collision qui explorerait systématiquement toutes les paires d'objets aurait une complexité en N², très pénalisante lorsque N est grand. Il faut donc utiliser une méthode d'accélération qui permette d'éliminer rapidement le cas des objets assez éloignés pour ne pas entrer en collision. Ce document montre comment implémenter une méthode d'accélération dans laquelle le domaine d'espace simulé est découpé en cellules parallélépipédiques (pavage d'espace). Chaque objet est représenté par une boîte contenante parallélépipédique dont les faces sont parallèles à celles du pavage d'espace.

Le code python décrit ci-dessous est dans le fichier CollisionsGrille.py.

2. Objets et boîtes contenantes

Les objets solides de la simulation sont dotés d'une position sous forme d'une liste de trois coordonnées, qui est par exemple la position du centre de masse. La boîte contenante est un parallélépipède dont les faces sont parallèles aux axes de coordonnées, qui englobe tous les points de l'objet. Cette boîte est définie par des bornes min et max sous forme d'une liste de 3 valeurs. Chaque objet contient aussi l'ensemble des cellules de l'espace (voir paragraphe suivant) avec lesquelles sa boîte contenante a une intersection. La détection des collisions se fera seulement avec les autres objets qui sont dans ces mêmes cellules.

Les objets de la simulation seront placés dans une liste globale liste_objets. Chaque objet sera référencé par son indice dans cette liste (et non par une référence python). L'indice est mémorisé dans l'objet.

Voici la classe mère des objets solides :

from math import floor,sqrt

class ObjetSolide:
    def __init__(self,indice):
        self.indice = indice
        self.position = [0,0,0]
        self.min = [-0.5,-0.5,-0.5]
        self.max = [0.5,0.5,0.5]
        self.cellules_coupees = set()
    def set_position(self,p):
        for k in range(3):
            tr = p[k]-self.position[k]
            self.min[k] += tr
            self.max[k] += tr
            self.position[k] = p[k] 
    def set_boite_contenante(self,min,max):
        self.min = min
        self.max = max
    def bornes_cellules(self,delta):
        return [int(floor(self.min[0]/delta[0])),int(floor(self.max[0]/delta[0])),int(floor(self.min[1]/delta[1])),int(floor(self.max[1]/delta[1])),int(floor(self.min[2]/delta[2])),int(floor(self.max[2]/delta[2]))]
    def get_cellules_coupees(self):
        return self.cellules_coupees
    def set_cellules_coupees(self,cellules_coupees):
        self.cellules_coupees = cellules_coupees
    def set_position_collision(self,p,tau):
        self.position_collision = p
        self.instant_collision = tau 
    def valider_position_collision(self):
        self.set_position(self.position_collision)
    def print_cellules_coupees(self):
        for c in self.cellules_coupees:
            print(c)
        

3. Pavage de l'espace

L'espace est divisé en cellules parallélépipédiques de côtés Δx, Δy et Δz. Une cellule est référencée par trois indices (i,j,k), éventuellement négatifs. L'intérieur de la cellule est défini par les inégalités suivantes :

$$\begin{array}{cc}\hfill & i\Delta x<x<(i+1)\Delta x\hfill \\ \hfill & j\Delta y<y<(j+1)\Delta y\hfill \\ \hfill & k\Delta z<z<(k+1)\Delta z\hfill \end{array}$$

Les indices i des cellules qui ont une intersection avec la boîte contenante d'un objet sont :

$$\begin{array}{cc}\hfill & E\left(\frac{xmin}{\Delta x}\right)\le i\le E\left(\frac{xmax}{\Delta x}\right)\hfill \end{array}$$

où E(x) est le plus petit entier inférieur ou égal à x. On procède de même pour les indices j et k.

La classe Cellule contient les trois indices et la liste des objets qui ont une intersection avec elle.

class Cellule:
    def __init__(self,indices):
        self.indices = indices
        self.objets_coupes = set()
    def ajouter_objet(self,indice_objet):
        self.objets_coupes.add(indice_objet)
        return len(self.objets_coupes)
    def enlever_objet(self,indice_objet):
        self.objets_coupes.remove(indice_objet)
        return len(self.objets_coupes)
    def print_objets(self):
        for o in self.objets_coupes:
            print(o)
             

Dans chaque direction d'espace (X,Y ou Z), le pavage peut être soit non borné, soit borné. Dans le premier cas, les indices des cellules sont seulement limités par la plus grande valeur entière. Dans le second cas, une longueur i_max est introduite pour la coordonnée bornée avec par convention $0\le i<i_{max}$. La condition limite sur les deux bords de la coordonnée bornée peut être périodique.

La pavage est représenté par la classe Pavage. Il contient les cellules qui ont au moins un object coupé, c'est-à-dire dont la boîte contenante a une intersection avec la cellule. Ces cellules sont stockées sous forme d'une table associative (dictionnaire python) dont les clés sont les indices sous forme d'un triplet.

Les données de cette classe sont :

• liste_objets : liste globale des objets de la simulation.
• delta : liste de 3 flottants. delta[k] est la largeur des cellules selon l'axe k.
• bords : liste de 3 booléens. bords[k] est égal à True si la coordonnée k est limitée par des bords.
• longueurs : liste de 3 entiers. longueurs[k] est l'indice maximal, utilisé si la coordonnée k est limitée par des bords.
• periodiques : liste de 3 booléens. periodiques[k] est égal à True si la coordonnée k est limitée par des bords avec des conditions limites périodiques.
• dict_cellules : dictionnaire des cellules coupées par au moins un objet. Les clés sont des triplets (i,j,k).

class Pavage:
    def __init__(self,liste_objets,delta,bords,longueurs,periodiques):
        self.liste_objets = liste_objets
        self.delta = delta
        self.bords = bords
        self.periodiques = periodiques
        self.longueurs = longueurs
        self.dict_cellules = {}
            

La fonction suivante place un object dans une cellule.

    def placer_objet_cellule(self,indice_objet,indices_cellule):
        if indices_cellule in self.dict_cellules:
            cellule = self.dict_cellules[indices_cellule]
            cellule.ajouter_objet(indice_objet)
        else:
            cellule = Cellule(indices_cellule)
            self.dict_cellules[indices_cellule] = cellule
            cellule.ajouter_objet(indice_objet)
            
              

La fonction suivante enlève un objet d'une cellule. Si l'objet est le dernier de la cellule, celle-ci est enlevée de la table des cellules.

    def enlever_objet_cellule(self,indice_objet,indices_cellules):
        if indices_cellules in self.dict_cellules:
            cellule = self.dict_cellules[indices_cellules]
            if cellule.enlever_objet(indice_objet)==0:
                del self.dict_cellules[indices_cellules]
              

La fonction suivante affiche toutes les cellules avec les objets qu'elles contiennent (pour débogage) :

    def print_cellules(self):
        for i in self.dict_cellules:
            indices = self.dict_cellules[i].indices
            print("Cellule (%d,%d,%d)"%(indices[0],indices[1],indices[2]))
            self.dict_cellules[i].print_objets()
              

La fonction suivante déplace un objet vers une nouvelle position définie par 3 coordonnées. La liste des cellules coupées par l'objet (par sa boîte contenante) est mise à jour. L'objet est ajouté dans les nouvelles cellules coupées et enlevé des cellules quittées.

    def deplacer_objet(self,indice_objet,position):
        objet = self.liste_objets[indice_objet]
        anciennes_cellules_coupees = objet.get_cellules_coupees()
        objet.set_position(position)
        cellules_coupees = set()
        bornes = objet.bornes_cellules(self.delta)
        i = [0,0,0]
        pos = position
        for i[0] in range(bornes[0],bornes[1]+1):
            for i[1] in range(bornes[2],bornes[3]+1):
                for i[2] in range(bornes[4],bornes[5]+1):
                    for axe in range(3):
                        if self.bords[axe]:
                            if self.periodiques[axe]:
                                if i[axe] < 0:
                                    i[axe] = self.longueurs[axe]-1
                                    pos[axe] += self.delta*self.longueurs[axe]
                                elif i[axe] > self.longueurs[axe]:
                                    i[axe] = 0
                                    pos[axe] -= self.delta*self.longueurs[axe]
                    cellules_coupees.add((i[0],i[1],i[2]))
        objet.set_position(pos)
        objet.set_cellules_coupees(cellules_coupees)
        nouvelles_cellules = cellules_coupees.difference(anciennes_cellules_coupees)
        for c in nouvelles_cellules:
            self.placer_objet_cellule(indice_objet,c)
        cellules_quittees = anciennes_cellules_coupees.difference(cellules_coupees)
        for c in cellules_quittees:
            self.enlever_objet_cellule(indice_objet,c)
                    
              

Le programme de simulation (non implémenté ici), se charge de déplacer tous les objets en intégrant les équations du mouvement du solide. Partant de la configuration du système à l'instant t_n, le programme détermine la configuration à l'instant t_n+1=t_n+Δt sans se préoccuper d'éventuelles collisions entre objets. À l'instant t_n+1, il faut déterminer les objets entrés en collision sur l'intervalle [t_n,t_n+1].

La détection de collision entre deux objets se fait avec une fonction dont le prototype est :

detecter_collision(objet1,objet2,parametres)

Cette fonction effectue les opérations suivantes :

• Détection d'intersection entre les boîtes contenantes des deux objets.
• Le cas échéant, détection d'intersection entre les deux objets.
• Le cas échéant, détermination de l'instant t_n+τ de collision en faisant une interpolation linéaire du mouvement entre les instants t_n et t_n+1.
• Mémorisation des positions de collision et du temps τ en appelant la fonction set_position_collision de chaque objet.
• Renvoi de la valeur de τ s'il y a collision, -1 sinon.

La fonction suivante de la classe Pavage appelle la fonction de détection de collision pour les paires d'objets qui peuvent présenter une intersection, c'est-à-dire dont les boîtes contenantes ont une intersection avec au moins une cellule en commun. Pour cela, la fonction commence par établir la liste des paires d'objets vérifiant cette propriété. Pour ces paires, la fonction de détection de collision est appelée. Si une collision est détectée, la paire est ajoutée à une liste de paires en collision, classées par instant croissant. La liste des paires en collisions est parcourue de manière à ne retenir, pour chaque objet, que la première collision. La fonction renvoit la liste des objets (liste d'indices) subissant une collision et la liste des collisions sous forme de paires d'indices d'objets avec l'instant de collision, rangée par temps croissant.

    def chercher_collisions(self,detecter_collision,parametres):
        paires_objets = []
        for cellule in self.dict_cellules.values():
            for i1 in cellule.objets_coupes:
                for i2 in cellule.objets_coupes:
                    if i1!=i2:
                        if ((i1,i2) not in paires_objets) and ((i2,i1) not in paires_objets):
                            paires_objets.append((i1,i2))
        collisions = []
        n = 0
        for paire in paires_objets:
            tau = detecter_collision(self.liste_objets[paire[0]],self.liste_objets[paire[1]],parametres)
            if tau >= 0:
                if n==0:
                    collisions.append([paire,tau])
                    n+=1
                else:
                    k1=0
                    k2=n
                    while k1!=k2:
                        k=int((k1+k2)/2)
                        tau0 = collisions[k][1]
                        if tau>tau0:
                            k1 = k
                        else:
                            k2 = k
                    collisions.insert(k2,[paire,tau])
                    n+=1
        liste_collisions = []
        liste_objets_collision = []
        for col in collisions:
            i1 = col[0][0]
            i2 = col[0][1]
            if (not i1 in liste_objets_collision) and (not i2 in liste_objets_collision):
                liste_objets_collision.append(i1)
                liste_objets_collision.append(i2)
                liste_collisions.append(col)
        return [liste_objets_collision,liste_collisions]     
              

Le programme de simulation devra effectuer la boucle constituée des opérations suivantes :

• Placer les objets subissant une collision dans leur position de collision, en appelant la fonction valider_position_collision de l'objet.
• Calculer les collisions pour les objets concernés, c.a.d. calculer les vitesses juste après la collision.
• Pour chaque objet ayant subi une collision, calculer la nouvelle trajectoire entre les instants t_n+τ et t_n+1.
• Déplacer ces objets dans le pavage d'espace en appelant la fonction deplacer_objet du pavage.
• Effectuer la recherche de collision en appelant la fonction chercher_collisions du pavage.
• Reprendre la première étape tant qu'il reste des collisions à résoudre.

Pour éviter les cas de multiples collisions sans fin, un nombre maximal d'itération devra être prévu pour la boucle précédente.

4. Test

from CollisionsGrille import *            
            
o1=ObjetSolide(0)
o2=ObjetSolide(1)
o3=ObjetSolide(2)
pavage = Pavage([o1,o2,o3],[1,1,1],[False,False,False],[1,1,1],[False,False,False])
pavage.deplacer_objet(0,[5.5,5.5,0.5])
pavage.deplacer_objet(1,[10.5,0.5,0.5])
pavage.deplacer_objet(2,[5,5,0])
print("Cellules coupees par l'objet 0")
o1.print_cellules_coupees()
print("Cellules coupees par l'objet 1")
o2.print_cellules_coupees()
print("Cellules du pavage et objets contenus")
pavage.print_cellules()
pavage.deplacer_objet(1,[5.7,5.2,0.3])
print("Cellules du pavage et objets contenus")
pavage.print_cellules()
            

Comme exemple de fonction de détection de collision, on considère le cas de deux sphères. Pour simplifier, on teste directement l'intersection des deux sphères sans passer par celle des boîtes contenantes. L'instant de collision renvoyé est nul.

def detecter_collision(objet1,objet2,parametres):
    p1 = objet1.position
    p2 = objet2.position
    dx = p2[0]-p1[0]
    dy = p2[1]-p1[1]
    dz = p2[2]-p1[2]
    d = sqrt(dx*dx+dy*dy+dz*dz)
    if d>objet1.rayon+objet2.rayon:
        return -1
    return 0
            

o1.rayon = 0.5
o2.rayon = 0.5
o3.rayon = 0.5
result = pavage.chercher_collisions(detecter_collision,[])
print(result)
pavage.deplacer_objet(0,[5.5,5.2,0.5])
pavage.deplacer_objet(1,[5.5,5.2,0.5])
pavage.deplacer_objet(2,[5.3,5.6,0.2])
result = pavage.chercher_collisions(detecter_collision,[])
print(result)