- L’algorithme GJK est une méthode permettant de vérifier si deux formes se chevauchent.
- Pour vérifier si la forme A et la forme B se chevauchent, il suffit de déterminer si au moins un point de chacune des deux formes coïncide.
Différence de Minkowski
- On soustrait tous les points des deux formes pour créer un nouvel ensemble.
- Si l’origine est incluse dans ce nouvel ensemble, cela signifie que les deux formes se chevauchent.
- Cet ensemble est appelé différence de Minkowski.
Idée de base de l’algorithme
- On vérifie si la différence de Minkowski de A et B contient l’origine.
- Si la différence contient l’origine, les deux formes se chevauchent.
Étapes de l’algorithme
- Initialisation : on définit un vecteur de direction arbitraire
det on trouve le premier pointp. - Recherche du point : on calcule le produit scalaire de
detp; s’il est positif, on continue, s’il est négatif, on s’arrête. - Ajout d’un nouveau point : on cherche un nouveau point depuis
pen direction de l’origine. - Simplification : on ajoute un nouveau point en prenant comme base les deux premiers points afin de simplifier la forme.
- Vérification de l’inclusion de l’origine : on vérifie si la forme simplifiée contient l’origine.
- Répétition : on répète jusqu’à ce que l’origine soit incluse, ou jusqu’à trouver une preuve qu’elle ne l’est pas.
Avis de GN⁺
- Point intéressant : l’algorithme GJK est un bon exemple de résolution d’un problème complexe grâce à une transformation mathématique simple.
- Pourquoi c’est utile : il est très utilisé dans les graphismes temps réel, notamment pour la détection de collisions.
- Regard critique : l’implémentation de l’algorithme peut être complexe et nécessite une compréhension précise.
- Technologies associées : parmi les autres algorithmes de détection de collisions, on trouve notamment SAT (Separating Axis Theorem).
- Points à considérer : lors de l’utilisation de l’algorithme GJK, il faut prendre en compte la complexité des formes et le coût de calcul.
1 commentaires
Commentaires Hacker News
J’ai galéré presque un an à cause de GJK dans les années 1990
C’est utile pour la détection de collisions 3D, et on peut aussi s’en servir comme algorithme de points les plus proches. L’idée de base est facile à comprendre. Étant donnés deux solides convexes, on choisit un point arbitraire sur chacun, on calcule la distance entre les deux points, puis on essaie de se déplacer depuis le point courant le long de chaque arête pour améliorer cette distance, et on répète en choisissant le nouveau point le plus proche
Mais dès que le point le plus proche n’est plus un sommet, cette approche casse, et c’est là qu’il faut introduire la notion de simplexe. Les combinaisons de points les plus proches se répartissent en sommet-sommet, sommet-arête, sommet-face, arête-arête, arête-face (pas de solution unique), face-face (pas de solution unique), et le traitement des simplexes revient en pratique à analyser ces cas
En réalité, beaucoup de problèmes apparaissent. Dans les moteurs physiques, les objets se stabilisent souvent en contact face-face, et un modèle de collision à point unique peut produire des oscillations ou des mouvements erronés. De plus, lorsque la position converge vers un contact face-face, GJK se met à manipuler de petites différences entre de grandes valeurs, ce qui peut faire perdre complètement les chiffres significatifs en virgule flottante. Les conditions d’arrêt peuvent aussi provoquer des boucles infinies
Théoriquement, c’est élégant, mais en pratique c’est un problème difficile d’analyse numérique. Cela dit, c’est probablement l’approche la plus rapide pour ce problème. Dans le cas général, c’est en O(log N), et si l’on utilise la dernière solution comme point de départ lorsque la situation est proche de la position précédente, on se rapproche de O(1)
Le regretté professeur Steven Cameron, d’Oxford, a beaucoup travaillé à faire fonctionner GJK correctement, et l’a utilisé à la fin des années 1990 dans « Falling Bodies », le premier système commercial de ragdoll 3D
Les obtenir est encore pire numériquement. On part du simplexe produit par GJK, on l’étend vers l’extérieur, et au passage il faut faire de la triangulation. L’implémenter avec de bonnes performances est quasiment un cauchemar
Je me demande si le brevet a maintenant expiré, et s’ils envisagent de publier le code. Ce serait un document historiquement important et intéressant, un peu comme lire le code source de Doom
Je ne trouvais pas d’article expliquant intuitivement l’algorithme de détection de collisions GJK, alors j’ai passé l’après-midi à en écrire un moi-même
Si vous voyez des façons de le rendre plus clair et plus efficace, dites-le-moi. Évidemment, gardez en tête que c’est un texte sur des maths écrit par un lycéen de première
C’est déjà bon, mais pour le rendre encore plus complet, j’ajouterais quelques éléments : une courte explication de la complexité temporelle dans le pire cas, une section séparée sur les conditions d’arrêt, et du pseudocode au fil de l’explication
L’approche actuelle, qui explique les choses sous un angle mathématique, fonctionne bien et mérite d’être conservée. Mais après chaque étape, en définissant des fonctions auxiliaires comme
S(•), ajouter un court pseudocode indiquant où en est l’algorithme rendrait le tout encore meilleurJ’ai aussi aimé l’article sur le modèle caché d’OpenAI. Le temps passé à regarder ce qu’a fait d’autre quelqu’un qui produit des résultats impressionnants est presque toujours bien investi
Le titre devrait être « as simply as possible ». Je ne connaissais pas l’algorithme GJK, mais si j’enseignais Calculus III en ce moment, j’aurais cherché un moyen d’intégrer ce contenu au cours. L’explication est aussi bonne que ça
Dans l’exemple du rectangle aux coins doucement arrondis à la fin de l’article, je ne vois pas ce qui empêche de se rapprocher de plus en plus de la réponse sans jamais l’atteindre réellement. Bien sûr, je comprends qu’en calcul réel il n’y a pas de raison de continuer au-delà d’une limite de précision pratique
Au début, j’ai compris qu’on appliquait une transformation à A et B pour obtenir la forme A-B. Après plusieurs relectures, il me semble que A-B ne désigne pas les deux ensembles à gauche, mais l’intersection d’autres A et B, et que le point important est que cette intersection recouvre l’origine, ou 0,0. Est-ce bien ça ?
Une présentation vidéo sur le même algorithme : https://www.youtube.com/watch?v=ajv46BSqcK4
Il y a à la fin une démo interactive qui montre la différence de Minkowski
L’article est très clair et intéressant
Une autre façon de vérifier si deux ensembles convexes s’intersectent consiste à résoudre un problème d’optimisation convexe qui minimise la norme de la différence entre un point appartenant au premier ensemble convexe et un point appartenant au second. Si la valeur optimale est 0, les deux ensembles s’intersectent
Il serait intéressant de comparer l’algorithme GJK et l’optimisation convexe. Je ne sais pas vraiment lequel des deux est le plus avantageux
La première image montre l’intersection de formes non convexes, alors que le fait que l’algorithme ne fonctionne que pour des formes convexes n’apparaît que beaucoup plus loin, ce qui peut être un peu trompeur
J’utilise depuis un moment la fonction Minkowski dans openSCAD, et je suis content de comprendre enfin ce que c’est réellement
Vu que ça suscite bien plus d’intérêt que prévu, je devrais préciser que mon site personnel est en fait une collection élaborée de private jokes
Si vous voulez me contacter ou s’il y a quelque chose à faire, vous pouvez répondre ici
J’ai implémenté GJK il y a presque 10 ans à partir de l’excellente explication de Casey : https://www.youtube.com/watch?v=Qupqu1xe7Io
J’ai déjà écrit un article lié à la géométrie de Minkowski : https://nickp.svbtle.com/asteroid-intersections