Table des matières Python

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]):

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 N2, 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 :

iΔx<x<(i+1)ΔxjΔy<y<(j+1)ΔykΔz<z<(k+1)Δz

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

E(xminΔx)iE(xmaxΔx)

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 imax est introduite pour la coordonnée bornée avec par convention 0i<imax . 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 :

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 tn, le programme détermine la configuration à l'instant tn+1=tn+Δt sans se préoccuper d'éventuelles collisions entre objets. À l'instant tn+1, il faut déterminer les objets entrés en collision sur l'intervalle [tn,tn+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 :

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 :

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)
            
Références
[1]  M. G. Coutinho,  Guide to dynamic simulations of rigids bodies and particle systems,  (Springer, 2013)
Creative Commons LicenseTextes et figures sont mis à disposition sous contrat Creative Commons.