Tri, balayage, élagage : algorithmes de détection de collision (2023)

 (leanrada.com)
3 points par GN⁺ 2024-08-15 | 1 commentaires | Partager sur WhatsApp
  • En physique de jeu, l’article explique la progression d’optimisation qui mène de la vérification de toutes les paires à la méthode sweep-and-prune, à partir d’une simulation de balles pour illustrer la détection de collision répétée
  • L’approche simple appelle intersects() sur toutes les paires candidates parmi n objets, soit environ (n*(n-1))/2 tests, ce qui croît rapidement en O(n²)
  • Un test d’intersection AABB se compose de plusieurs inégalités reliées par && ; en exploitant l’évaluation paresseuse et la transitivité des inégalités, on peut écarter tôt les candidats qui ne peuvent pas entrer en collision
  • Après avoir trié les objets selon leur x minimum, c’est-à-dire leur bord gauche, on peut faire un break dans la boucle interne dès que ball2.left > ball1.right, ce qui élimine d’un coup tous les candidats suivants
  • En ajoutant un coût de tri en O(n log n) puis un coût de boucle proportionnel au nombre de recouvrements sur l’axe x, m, on obtient en moyenne un comportement en O(n log n + m), avec beaucoup moins d’appels inutiles à intersects()

Point de départ : la détection de collision dans les jeux

  • La détection de collision est un prérequis pour de nombreux comportements en programmation de jeux vidéo
    • empêcher les personnages de se traverser
    • faire changer de direction un Goomba lorsqu’il heurte un autre objet
    • dans agar.io, permettre à une grande cellule de manger une plus petite cellule au contact
    • gérer la physique de jeu de manière générale
  • L’exemple compare plusieurs approches de détection de collision à l’aide d’une simulation de balles rigides
  • Le périmètre va de l’approche la plus simple jusqu’à sweep-and-prune, sans inclure le partitionnement spatial ni les raffinements par arbres spatiaux

L’approche naïve : tester toutes les paires

  • La méthode la plus directe consiste à considérer chaque paire d’objets comme candidate
    • la boucle externe parcourt chaque balle
    • la boucle interne commence à i + 1 pour éviter les paires dupliquées comme A-B et B-A
    • pour chaque paire candidate, on appelle intersects(ball1, ball2) et, si le résultat est vrai, on exécute bounce(ball1, ball2)
  • Ce test est répété à chaque pas de temps, de sorte que les balles rebondissent au moment où elles entrent en collision
  • Cela suffit quand le nombre d’objets est faible, mais le volume de tests devient vite un goulet d’étranglement quand ce nombre augmente

La limite imposée par O(n²)

  • L’algorithme naïf s’exécute en O(n²) selon la notation Big O
  • Pour n balles, le nombre de paires à tester est d’environ (n*(n-1))/2, soit 0.5n² - 0.5n
    • n = 5 donne 10 paires
    • n = 10 donne 45 paires
    • n = 15 donne 105 paires
    • n = 20 donne 190 paires
  • Dans le pire cas, si tous les objets se recouvrent en même temps, il est difficile pour n’importe quel algorithme de détection de collision d’éviter un traitement en O(n²) des collisions
  • En pratique, les cas moyen et meilleur sont toutefois plus utiles que le pire cas pour comparer les approches
  • L’approche naïve reste toujours en Θ(n²), indépendamment du nombre réel de collisions, ce qui laisse une large marge d’amélioration

Le travail répété à l’intérieur de intersects()

  • Le point de départ de l’optimisation est la fonction intersects(), appelée pour chaque paire candidate
  • Un test d’intersection AABB classique se compose de plusieurs comparaisons d’inégalités entre les bornes dans chaque direction
function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}
  • Ce test se décompose en quatre conditions
    • object1.left < object2.right
    • object1.right > object2.left
    • object1.top < object2.bottom
    • object1.bottom > object2.top
  • Grâce à l’évaluation paresseuse de &&, si une seule condition est fausse, tout le test d’intersection devient immédiatement faux
  • Si l’on généralise, sur plusieurs tests, l’idée qu’“au moins une condition est fausse”, on peut réduire le nombre même d’appels à intersects()
  • Cela rejoint l’idée du théorème de l’axe séparateur : si les projections ne se recouvrent pas sur un axe, les deux objets ne peuvent pas entrer en collision

Écarter des candidats grâce à la transitivité des inégalités

  • Rien qu’en regardant la condition object1.right > object2.left, on voit déjà une possibilité d’optimisation
  • Si trois objets A, B et C sont disposés horizontalement dans l’ordre A-B-C, les tests suivants peuvent tous être faux
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
  • Si A > B est faux et B > C est faux, alors, par transitivité des inégalités, on sait aussi que A > C est faux
  • Il devient donc possible de conclure que les deux objets n’entrent pas en collision sans appeler intersects(A, C)
  • Cette omission ne s’applique que lorsque les objets sont dans un certain ordre, mais comme leurs étiquettes sont arbitraires, il suffit de désigner l’objet de gauche comme A, celui du milieu comme B et celui de droite comme C
  • Le fait de placer les objets dans cet ordre logique correspond justement au tri

Tri selon le minimum sur l’axe x

  • Une liste triée permet d’appliquer la transitivité des inégalités à plusieurs candidats d’un seul coup
  • Un algorithme de tri rapide classique s’exécute en O(n log n), inférieur à O(n²)
  • Les objets n’étant pas des points mais des intervalles sur l’axe x, on trie selon leur position x à partir de leur bord gauche, le x minimum
  • Deux changements suffisent dans le code naïf en O(n²)
    • avant les boucles, sortByLeft(balls) trie les balles selon la coordonnée x de leur bord gauche
    • dans la boucle interne, on fait break si ball2.left > ball1.right
// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • La fonction de tri ordonne le tableau selon la différence entre les bords gauches
function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

Pourquoi break est sûr

  • Si la liste est triée, la relation suivante vaut pour tout entier positif arbitraire c
balls[j + c].left >= balls[j].left
  • Si le candidat courant vérifie la condition suivante, alors la paire courante ne se recouvre pas sur l’axe x
balls[j].left > ball1.right
  • En combinant les deux inégalités, on obtient la relation suivante
balls[j + c].left >= balls[j].left > ball1.right
  • Par transitivité, balls[j + c].left > ball1.right est donc aussi vrai, ce qui signifie qu’aucun des candidats suivants ne recouvre non plus ball1 sur l’axe x
  • Dès que l’objet courant ball2 ne recouvre plus ball1, on peut interrompre la boucle interne sans tester les autres candidats
  • Cette optimisation limite les appels réels à intersects() aux seules paires qui se recouvrent sur l’axe x

Complexité temporelle améliorée

  • Le coût du tri ajoute un terme en O(n log n) si l’on utilise un tri rapide comme mergesort ou quicksort
  • La double boucle avec arrêt anticipé peut être vue en moyenne comme O(n + m)
    • m est le nombre total de recouvrements sur l’axe x
    • dans le meilleur cas, s’il n’y a aucun recouvrement, le traitement inutile est presque nul et on se rapproche de O(n)
    • dans le pire cas, cela peut toujours se dégrader jusqu’à O(n²)
  • Le cas moyen suppose en général que les objets sont répartis de façon assez uniforme et que chaque objet n’a que quelques collisions
  • La complexité totale devient O(n log n + m) en combinant le tri et les boucles
  • L’amélioration par rapport à l’approche naïve vient de deux points
    • n log n est inférieur à n²
    • le coût dépend en partie du nombre de recouvrements m, au lieu de traiter systématiquement plus que nécessaire

Coût d’implémentation et suite

  • Cette approche fondée sur le tri offre un bon compromis, avec peu de changements de code pour un gain net en temps d’exécution
  • Dans la démo comparative, le test de paires basé sur le tri réduit visiblement le nombre de tests intersects() par frame par rapport à une vérification globale de toutes les paires
  • Le coût du tri n’apparaît pas dans la visualisation comparative, qui part de l’hypothèse que les tests d’intersection sont suffisamment coûteux
  • Les approches plus avancées et le code final se poursuivent dans Part 2

À lire aussi

1 commentaires

 
GN⁺ 2024-08-15
Commentaires sur Hacker News

  • Ce qui est intéressant dans cette approche, c’est que l’auteur suggère d’utiliser des algorithmes de tri « rapides » comme le tri fusion/tri rapide pour obtenir les meilleures performances.
    Mais en pratique, un algorithme de tri « pire », le tri par insertion, peut être plus rapide.
    Dans un système de détection de collisions, les objets ne bougent généralement que très peu d’une frame à l’autre ; on peut donc conserver la liste presque triée de la frame précédente.
    Sur ce type de liste, le tri par insertion se rapproche de O(n), tandis que le tri rapide peut se rapprocher de O(n^2).

    • L’auteur aborde presque exactement ce point dans la partie 2.
      Il explique en substance que « l’étape de tri est le goulot d’étranglement dans l’analyse, mais la plupart du temps le tri ne fait rien. La liste est presque toujours déjà triée depuis la frame précédente. Même quand l’ordre est perturbé, quelques échanges suffisent généralement à le rétablir. Voici un exemple de fonctionnement du tri par insertion ».
    • Au lieu de trier à chaque étape, on peut aussi rendre la structure d’indexation un peu plus lâche afin de capturer les candidats à la collision quand un objet s’est déplacé de moins qu’epsilon.
      Par exemple, on peut augmenter le rayon des sphères de epsilon.
      Tant qu’une sphère ne s’est pas déplacée de epsilon, il n’est pas nécessaire de recalculer l’index.
      Pour éviter un pic de latence au moment où il faut le recalculer, on peut trier 10 % par frame afin de produire un index en retard.
      Au bout de 10 frames, on obtient un index valide tant que la position est à moins de epsilon de celle d’il y a 10 frames.
    • Sur une liste presque triée, le tri rapide ne devient O(n^2) que si l’on choisit un très mauvais pivot.
      En choisissant le pivot aléatoirement, on obtient O(n log n), et si la liste est déjà presque triée, on peut aussi choisir l’élément du milieu comme pivot.
      Cela dit, même avec un pivot optimal, le tri rapide reste O(n log n) dans le meilleur cas.
      Il existe des variantes simples du tri fusion qui se comportent en O(n log k), où k est le nombre de runs croissants/décroissants dans les données.
      Le sort par défaut de la bibliothèque standard de Haskell utilise un tel algorithme, et Python le fait probablement aussi.

  • L’article était très bien structuré.
    Je fais du développement de jeux sous une forme ou une autre depuis la fin des années 90, et même si aujourd’hui la majeure partie de tout cela est abstraite par les moteurs, ce genre de contenu est essentiel pour comprendre comment fonctionnent les simulations de systèmes complexes.
    Merci à l’auteur d’avoir rendu le sujet accessible.

  • Pour la détection continue de collisions, j’ai toujours trouvé ce document très bon : https://github.com/bepu/bepuphysics2/blob/master/Documentati...
    La bibliothèque elle-même est aussi excellente en termes de performances.
    Elle est toutefois assez fortement optimisée, ce qui la rend un peu délicate à intégrer.

  • Je me demande si l’affirmation « cet algorithme naïf s’exécute en O(n2) selon la notation grand O » est correcte.
    La boucle externe i tourne n - 1 fois, et la boucle interne j commence à i + 1, donc il me semble qu’elle tourne de moins en moins, et toujours moins que n - 1.
    N’étant pas spécialiste, je me demande si, quand n est grand, on considère que c’est à peu près équivalent à O(n2), ou si c’est réellement plus petit comme cela en a l’air.

    • Ce n’est pas exactement n^2.
      Pour le iᵉ élément, on effectue (n - i - 1) comparaisons ; avec une indexation à partir de 0, le nombre total de comparaisons est (n - 1) * n / 2.
      Voir https://en.wikipedia.org/wiki/Triangular_number.
      Au final, cela ne change rien dans l’analyse en grand O.
      Le grand O décrit le comportement quand n tend vers l’infini, et dans ce cas le terme quadratique domine.
    • L’« optimisation » consistant à faire commencer la boucle interne à j = i + 1 sert à éviter de tester deux fois chaque paire d’objets.
      Elle évite aussi de tester un objet avec lui-même.
      Comme chaque paire est testée une fois, l’algorithme est en O(n^2).
    • Le grand O n’est qu’une classification de complexité décrivant comment le nombre d’opérations abstraites croît avec la taille de l’entrée, c’est-à-dire la longueur de la liste d’entrée.
      En général, si l’on peut exprimer analytiquement le nombre d’opérations comme une fonction de la taille de l’entrée, le grand O ne conserve que le terme dominant et ignore tous les coefficients.
      Il ne décrit pas forcément les performances réelles d’un algorithme.
      20n2^+5n et 2n^2 + 9001n sont tous deux en O(n^2).
    • C’est la somme de 1 à n, donc n(n+1)/2.
      En notation grand O, on ignore tous les coefficients et les termes qui croissent plus lentement, ce qui se réduit donc à une complexité quadratique.
    • On peut aussi comprendre le grand O comme quelque chose d’analogue au calcul de limites en analyse.

  • J’ai aimé l’utilisation des illustrations, et elle m’a semblé appropriée.
    Parfois, les articles avec des illustrations interactives donnent l’impression de n’être qu’un prétexte pour empiler des démos spectaculaires, un peu comme certaines conférences TED où l’habillage prend plus de place que le fond.
    Mais dans cet article, les illustrations n’écrasaient pas le contenu.

  • Partie 2 : https://leanrada.com/notes/sweep-and-prune-2/
    Il y a aussi d’autres bons articles à lire : https://leanrada.com/

  • Il y a longtemps, j’avais fait quelque chose de similaire : au lieu de trier, je maintenais des listes d’index pour chaque direction, et les objets se réordonnaient eux-mêmes.
    Par exemple, il y avait quatre listes du type objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge.
    Quand un objet se déplaçait horizontalement, il mettait à jour son propre index dans les tableaux leftEdge et rightEdge.
    Même en cas de déplacement, il suffisait généralement d’échanger seulement 1 ou 2 index.

    • Cette approche semble utile surtout pour des scènes majoritairement statiques.
      Plus il y a d’éléments dynamiques, plus une approche consistant à reconstruire le graphe paraît préférable.

  • Je découvre cette approche ; n’est-ce pas similaire à l’utilisation d’un quadtree ou autre pour réduire le nombre de collisionneurs potentiels ?

    • Oui.
      Cela dit, on voit plus souvent des structures comme les k-d trees en rendu hors ligne qu’en rendu temps réel.

  • Le passage disant que l’article ne traitera pas « d’autres approches comme le partitionnement spatial ou la subdivision par arbres spatiaux » m’intrigue.
    Quelqu’un sait-il si l’algorithme de l’article est généralement plus rapide que le partitionnement spatial/la subdivision par arbres spatiaux ?
    Il y a longtemps, j’avais utilisé une approche de type arbre spatial et, naïvement, cela me paraissait plutôt bon, mais c’était dans les années 80, avant Internet, donc je n’ai jamais étudié ni comparé les algorithmes utilisés par d’autres.

    • La complexité liée au maintien d’un partitionnement spatial, d’une subdivision en arbre, etc., peut devenir un gros fardeau, surtout quand on a énormément d’objets en mouvement.
      Gérer une seule liste d’entités, ou une grille de cellules 256x256 contenant chacune une liste d’entités, est beaucoup plus simple à écrire, déboguer et optimiser qu’une structure de partitionnement complexe où il faut maintenir tous les invariants de l’arbre à chaque déplacement d’objet.
      À l’époque de DOOM ou Quake, les performances de ces systèmes de base comptaient bien plus qu’aujourd’hui, donc il était plus logique pour les auteurs de moteurs de créer des systèmes de partitionnement très complexes.
      Les CPU actuels sont très forts pour parcourir des tableaux triés, et à cause du pipeline, suivre des listes chaînées ou des arbres est relativement moins avantageux qu’autrefois.
      Le temps CPU est davantage consommé par l’IA, le rendu et autres, plutôt que par la gestion des listes d’entités.