GJK, dix ans après : le débat a changé de place

En 2016, il fallait qu’un canapé s’arrête contre un mur.

Sur Kazaplan, on aménageait son logement en trois dimensions, et le mobilier traversait les cloisons. J’ai écrit une bibliothèque de détection de collisions pour Babylon.js, collision-gjk-epa, et je suis passé à autre chose.

J’y suis revenu cette année pour en tirer un lab. Le principe n’a pas pris une ride. Tout ce qu’il y a autour, si.

Le changement de question

GJK ne regarde pas deux formes. Il regarde leur différence de Minkowski : l’ensemble de tous les écarts a - b, pour a dans A et b dans B. Deux formes se touchent si et seulement si cet ensemble contient l’origine, parce qu’un écart nul veut dire qu’un point de A est aussi un point de B.

La question du recouvrement de deux formes devient donc celle de l’appartenance d’un point à une seule. C’est tout l’algorithme.

Ce qu’il a de remarquable, c’est qu’il ne construit jamais cette différence. Il n’en demande qu’une chose, le point le plus loin dans une direction donnée. Le panneau de droite ci-dessous la dessine quand même, mais uniquement pour qu’on voie ce que l’algorithme tâte à l’aveugle.

Poussez une forme à gauche : la différence se déforme à droite, et l’origine se retrouve dedans ou dehors. Le disque n’a aucun sommet, et rien ne le distingue des polygones, puisque GJK ne connaît d’une forme que son point extrême dans une direction.

Ce qui était difficile

Pas l’algorithme. À plat, le simplexe est un triangle et les cas à départager se comptent sur les doigts d’une main. En volume, c’est un tétraèdre : quatre faces, des arêtes à tester les unes contre les autres, et le code enfle. C’est le passage de la 2D à la 3D qui m’a demandé le plus de travail.

L’autre morceau, ce sont les cas limites. L’origine qui tombe exactement sur une arête, des vecteurs colinéaires à quelques décimales près. La géométrie devient ambiguë, le signe d’un produit vectoriel ne veut plus rien dire, et l’algorithme s’engage dans une branche qui n’a aucun sens.

C’est exactement sur ce point que GJK a changé depuis.

GJK n’est plus celui que j’ai écrit

En 2017, Montanari, Petrinic et Barbieri publient dans ACM TOG une refonte du sous-algorithme de distance. Ils remplacent l’algorithme de Johnson et sa procédure de secours par une méthode dite des volumes signés, qui évite de multiplier entre elles des quantités parfois infimes.

Le gain en temps de calcul est modeste : environ 10 % en moyenne, entre 5 et 25 % quand les objets sont au contact. Ce n’est pas là que ça se joue. Le sous-algorithme est exact à la précision machine, et il supprime la procédure de secours, c’est-à-dire la branche qui existait pour rattraper précisément les cas dont je parlais plus haut. Leur implémentation de référence est openGJK.

La deuxième évolution est plus spectaculaire. En 2022, Montaut, Le Lidec, Petrik, Sivic et Carpentier établissent que GJK est un cas particulier de l’algorithme de Frank-Wolfe en optimisation convexe. Une fois cette parenté posée, on peut lui appliquer les accélérations classiques du domaine : Polyak, Nesterov. Le résultat, publié sous le nom de GJK++ dans IEEE T-RO en 2024, va jusqu’à doubler la vitesse sur des millions de paires d’objets du quotidien. C’est implémenté dans Coal, l’ex-HPP-FCL renommé en 2024, qui embarque ses propres GJK et EPA sans passer par libccd.

Si vous avez appris GJK il y a quinze ans, ce n’est pas le même algorithme qui tourne aujourd’hui dans les bibliothèques sérieuses.

Le vrai débat de 2026 n’est pas l’algorithme

C’est là que je m’attendais à écrire qu’EPA est la pièce fragile qu’on remplace. La réalité est plus intéressante, et plus utile.

EPA reprend le simplexe final de GJK quand il y a contact et le gonfle jusqu’au bord de la différence de Minkowski, pour donner la profondeur de pénétration et la normale. Il est coûteux, il est numériquement fragile, et il ne donne qu’un point de contact là où un moteur a besoin de toute la surface par laquelle deux objets se touchent. Le reproche est constant.

Les moteurs ont donc cherché à ne jamais l’appeler. Mais ils sont partis dans deux directions opposées, et leur point de désaccord n’est pas EPA.

Jolt, celui de Horizon Forbidden West et Death Stranding 2, garde GJK/EPA et rétrécit chaque forme d’un « convex radius » avant de la regonfler. Les formes rétrécies ne s’interpénètrent presque jamais, donc EPA ne s’exécute quasiment plus. Le prix, c’est une marge : les objets reposent l’un sur l’autre à une distance non nulle.

Erin Catto, l’auteur de Box2D, refuse ce prix. Dans un billet de juillet 2026 consacré à Box3D, il explique préférer le test d’axe séparateur parce que les formes peuvent y reposer directement les unes sur les autres, sans marge et donc sans interstice visible. Il note au passage qu’EPA est numériquement fragile, et qu’il faut souvent prévoir une solution de repli derrière lui.

Sauf que le SAT en 3D est quadratique : il faut tester les faces contre les sommets, et les arêtes contre les arêtes. Pour un rocher à 32 points et 89 arêtes, cela fait 7 921 combinaisons d’arêtes à examiner, contre 144 pour une boîte. La réponse de Catto n’est pas de changer d’algorithme, c’est de payer cette facture en SIMD. Sur son banc d’essai de 5 120 objets, un AMD 7950X passe de 40 706 ms en scalaire à 15 762 ms en AVX2 sur un seul fil d’exécution, et de 5 292 à 2 277 ms sur huit.

Le débat ne porte donc pas sur GJK contre SAT. Il porte sur une marge de collision : l’acceptez-vous ou non. Répondez oui, vous prenez Jolt et EPA devient un filet de sécurité. Répondez non, vous prenez le SAT et vous devez financer son coût quadratique. Cette décision se répercute ensuite sur le solveur, sur le rendu, et sur ce que voit l’utilisateur.

Je n’avais pas ce débat en tête en 2016. Je voulais que le canapé s’arrête contre le mur.

Deux axes qui n’existaient pas

La différentiabilité. GJK et EPA sont discontinus, donc inutilisables dans une optimisation par gradient. D’où des reformulations complètes, comme DCOL (Tracy, Howell et Manchester, 2023), qui pose la collision comme un problème d’optimisation convexe : on y cherche le plus petit facteur d’échelle à appliquer aux formes avant qu’elles se touchent. Au-dessus de 1, elles sont séparées ; en dessous, elles s’interpénètrent. Cette valeur-là, elle, se dérive.

Le sujet est toujours vivant : un article de février 2026 propose iDCOL, avec des dérivées analytiques. Le problème qu’il attaque : les configurations dégénérées des formes à courbure nulle ou indéfinie. Dix ans plus tard, c’est toujours le même ennemi.

Le calcul par lots sur GPU. L’apprentissage par renforcement demande des milliers de paires en parallèle, et GJK s’y prête mal : il multiplie les branchements, et son nombre d’itérations varie d’une paire à l’autre. MuJoCo a pris une direction que je n’avais pas prévue, celle d’aller vers GJK/EPA, avec une implémentation maison qui remplace libccd et son MPR, au point que les options mpr_tolerance et mpr_iterations ont été renommées ccd_tolerance et ccd_iterations. Côté GPU en revanche, MJX déroule un nombre fixe d’itérations, ou bascule carrément sur un SAT sans branches.

Ce qui n’a pas bougé

Pour situer tout ça, il existe depuis cette année une revue d’état de l’art signée Mangoni, Fusai et Tasora, qui compare les algorithmes de détection fine et recense les questions encore ouvertes : le passage à l’échelle, les corps déformables, l’intégration aux flux CAO et au GPU.

Aucune de ces questions n’est « trouver mieux que GJK ». La fonction de support, cette idée qu’une forme peut se réduire à une boîte noire qui renvoie son point extrême dans une direction, reste ce qui permet de traiter un disque et un polyèdre du même geste. Elle est même devenue un goulot d’étranglement qu’on optimise pour lui-même : un article de septembre 2025 porte uniquement sur l’agencement mémoire des enveloppes convexes pour accélérer ces requêtes.

Ce qui a vieilli dans mon code de 2016, ce n’est donc pas l’idée. C’est la façon de descendre dans le simplexe, la tolérance aux cas limites, et surtout le fait d’ignorer le seul arbitrage qui compte vraiment quand on choisit un moteur.

Le code est toujours en ligne. Le lab plus haut en reprend le principe, à plat, pour qu’il se regarde.