- 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
d et on trouve le premier point p.
- Recherche du point : on calcule le produit scalaire de
d et p ; 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
p en 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
Avis Hacker News
Algorithme GJK : Dans les années 1990, j’ai passé un an à essayer de comprendre l’algorithme GJK. Il est utile pour la détection de collision et la recherche des points les plus proches. L’idée de base est facile à comprendre. On part de deux solides convexes, on choisit des points arbitraires et on essaie d’améliorer la distance entre ces points. On sélectionne les points les plus proches et on répète. Quand les points les plus proches ne sont plus des sommets, la notion de « simplex » devient nécessaire. Il s’agit alors d’analyser plusieurs cas. Dans les moteurs physiques, des problèmes apparaissent lorsque des objets se stabilisent en contact face contre face. En théorie, c’est une solution élégante, mais en pratique, c’est un problème difficile d’analyse numérique. Cela reste probablement l’approche la plus rapide. En général, c’est en O(log N), et en O(1) quand on est proche de la position précédente. Le regretté professeur Stephen Cameron d’Oxford a mené beaucoup de recherches pour implémenter correctement GJK. GJK a été utilisé à la fin des années 1990 dans le système commercial de ragdoll 3D « Falling Bodies ».
Rédaction d’une explication de GJK : Ne trouvant pas d’explication intuitive de l’algorithme de détection de collision GJK, j’en ai rédigé une moi-même. Si quelqu’un voit comment la rendre plus claire ou plus efficace, je suis preneur. Comme il s’agit d’une explication mathématique faite par un lycéen, il faut l’aborder avec une dose raisonnable de scepticisme.
Vidéo sur l’algorithme GJK : Partage d’une présentation vidéo sur le même algorithme. Lien vers la vidéo
Éloge de l’article : Excellent article. Très clair et intéressant.
Comparaison avec l’optimisation convexe : Une autre façon de vérifier l’intersection entre deux ensembles convexes consiste à résoudre un problème d’optimisation convexe qui minimise la norme de la différence entre deux points. Si la valeur optimale est 0, alors les ensembles ont un point d’intersection. J’aimerais voir une comparaison entre l’algorithme GJK et cette approche par optimisation convexe. Je ne sais pas lequel est le meilleur.
Éloge de l’article et malentendu : Excellent article. En revanche, la première image montre une intersection de formes non convexes, alors que l’algorithme ne fonctionne que sur des formes convexes, ce qui n’est précisé que plus tard.
Découverte de l’algorithme GJK : C’est la première fois que j’entends parler de l’algorithme GJK.
Article de blog connexe : J’ai écrit un billet de blog lié à la géométrie de Minkowski. Lien du blog
Site personnel : Vu l’attention inattendue, je précise que mon site personnel est rempli de plaisanteries. Si vous voulez me contacter, dites-le-moi en réponse.
Utilisation de la fonction Minkowski : J’utilisais la fonction Minkowski dans openSCAD, et je suis heureux de découvrir ce que c’est réellement.
Éloge de l’algorithme : Un algorithme remarquable.