Der GJK-Algorithmus: Eine einfache Aufgabe auf seltsame und schöne Weise lösen

 (computerwebsite.net)
2 Punkte von GN⁺ 2024-06-13 | 1 Kommentare | Auf WhatsApp teilen
  • Der GJK-Algorithmus ist eine Methode, um zu prüfen, ob sich zwei Formen überlappen.
  • Um zu prüfen, ob Form A und Form B sich überlappen, muss man feststellen, ob sich irgendein Punkt der beiden Formen überschneidet.

Minkowski-Differenz

  • Es wird eine neue Menge gebildet, indem alle Punkte der beiden Formen voneinander subtrahiert werden.
  • Wenn diese neue Menge den Ursprung enthält, bedeutet das, dass sich die beiden Formen überlappen.
  • Dies wird als Minkowski-Differenz bezeichnet.

Grundidee des Algorithmus

  • Es wird geprüft, ob die Minkowski-Differenz von A und B den Ursprung enthält.
  • Wenn die Differenzmenge den Ursprung enthält, überlappen sich die Formen.

Schritte des Algorithmus

  1. Initialisierung: Ein beliebiger Richtungsvektor d wird festgelegt und der erste Punkt p gesucht.
  2. Punktsuche: Das Skalarprodukt von d und p wird berechnet; ist es positiv, geht es weiter, ist es negativ, wird beendet.
  3. Neuen Punkt hinzufügen: Von p aus wird in Richtung des Ursprungs ein neuer Punkt gesucht.
  4. Vereinfachung: Ausgehend von den ersten beiden Punkten wird ein neuer Punkt hinzugefügt, um zu vereinfachen.
  5. Prüfen, ob der Ursprung enthalten ist: Es wird geprüft, ob die vereinfachte Form den Ursprung enthält.
  6. Wiederholung: Der Vorgang wird wiederholt, bis der Ursprung enthalten ist oder ein Beweis dafür gefunden wird, dass er nicht enthalten ist.

Meinung von GN⁺

  • Interessanter Punkt: Der GJK-Algorithmus ist ein gutes Beispiel dafür, wie sich ein komplexes Problem durch eine einfache mathematische Transformation lösen lässt.
  • Warum hilfreich: Er ist in Echtzeitgrafik, etwa bei der Kollisionserkennung, sehr nützlich.
  • Kritische Sicht: Die Implementierung des Algorithmus kann komplex sein und erfordert ein genaues Verständnis.
  • Verwandte Technologien: Weitere Algorithmen zur Kollisionserkennung sind etwa SAT (Separating Axis Theorem).
  • Zu beachten: Beim Einsatz des GJK-Algorithmus sollten die Komplexität der Formen und die Rechenkosten berücksichtigt werden.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-06-13
Hacker-News-Kommentare

  • In den 1990ern habe ich mich wegen GJK fast ein Jahr lang herumgequält.
    Es ist nützlich für 3D-Kollisionserkennung und lässt sich auch als Algorithmus für den nächstgelegenen Punkt verwenden. Die Grundidee ist leicht zu verstehen: Hat man zwei konvexe Körper, wählt man auf jedem Körper je einen beliebigen Punkt, berechnet den Abstand zwischen den beiden Punkten und versucht dann, vom aktuellen Punkt aus entlang jeder Kante den Abstand zu verbessern; anschließend wählt man den neuen nächstgelegenen Punkt und wiederholt das Ganze.
    Sobald der nächstgelegene Punkt aber kein Scheitelpunkt mehr ist, bricht diese Methode zusammen, und dann braucht man das Konzept eines Simplex. Die Kombinationen für den nächstgelegenen Punkt lassen sich in Scheitelpunkt–Scheitelpunkt, Scheitelpunkt–Kante, Scheitelpunkt–Fläche, Kante–Kante, Kante–Fläche (keine eindeutige Lösung) und Fläche–Fläche (keine eindeutige Lösung) einteilen; die Simplex-Behandlung läuft im Grunde darauf hinaus, diese Fälle zu analysieren.
    In der Praxis treten viele Probleme auf. In Physik-Engines stabilisieren sich Objekte häufig in einem Fläche-zu-Fläche-Kontakt, und ein Kollisionsmodell mit nur einem einzelnen Punkt kann Schwingungen oder falsche Bewegungen erzeugen. Wenn sich die Position einem Fläche-zu-Fläche-Kontakt annähert, hantiert GJK außerdem mit kleinen Differenzen zwischen großen Werten, wodurch die signifikanten Stellen der Gleitkommazahlen vollständig verloren gehen können. Auch Abbruchbedingungen können Endlosschleifen verursachen.
    Theoretisch ist es elegant, praktisch aber ein schwieriges Problem der numerischen Analyse. Trotzdem ist es vermutlich der schnellste Ansatz für dieses Problem. Im allgemeinen Fall ist es O(log N), und wenn man in einer Situation nahe der vorherigen Position die letzte Lösung als Startpunkt verwendet, kommt es O(1) nahe.
    Der verstorbene Professor Steven Cameron aus Oxford hat viel Arbeit investiert, um GJK zuverlässig zum Laufen zu bringen, und GJK wurde Ende der 1990er in „Falling Bodies“, dem ersten kommerziellen 3D-Ragdoll-System, verwendet.

    • Nachdem man einen Kontakt gefunden hat, muss man fast zwangsläufig irgendetwas damit machen, und für die meisten nützlichen Verarbeitungen braucht man die tatsächliche Überlappungsinformation.
      Diese zu berechnen ist numerisch noch schlimmer. Man startet mit dem von GJK erzeugten Simplex, erweitert ihn nach außen und muss dabei eine Triangulierung vornehmen. Das performant zu implementieren ist ein ziemlicher Albtraum.
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      Ich frage mich, ob das Patent inzwischen abgelaufen ist und ob es Pläne gibt, den Code zu veröffentlichen. Das wäre historisch bedeutsam und vermutlich ein spannendes Material, ähnlich wie den Doom-Quellcode zu lesen.

  • Ich habe keinen Artikel gefunden, der den GJK-Kollisionserkennungsalgorithmus intuitiv erklärt, also habe ich mir einen Nachmittag genommen und selbst eine Zusammenfassung geschrieben.
    Wenn es Möglichkeiten gibt, ihn klarer und effizienter zu machen, würde ich mich über Hinweise freuen. Natürlich bitte mit etwas Nachsicht dafür, dass es ein Text ist, in dem ein Schüler der 11. Klasse mathematische Inhalte erklärt.

    • Der Text ist sehr klar. Wenn du solche Arbeit weiter machst, sieht man genug Talent, dass du eines Tages ein hervorragendes Lehrbuch schreiben könntest.
      Er ist bereits gut, aber um ihn noch vollständiger zu machen, könnte man ein paar Dinge ergänzen: eine kurze Erklärung zur Zeitkomplexität im Worst Case, einen eigenen Abschnitt zu Abbruchbedingungen und zwischendurch Pseudocode.
      Die Erklärung aus mathematischer Perspektive passt gut und ist es wert, beibehalten zu werden. Es wäre aber noch besser, nach jedem Schritt kurze Pseudocode-Blöcke einzufügen, die Hilfsfunktionen wie S(•) definieren und zeigen, wie weit der Algorithmus gerade fortgeschritten ist.
      Auch der Artikel über das versteckte Modell von OpenAI war gut. Die Zeit, die man damit verbringt nachzusehen, was jemand sonst noch gemacht hat, nachdem er etwas Beeindruckendes geschaffen hat, lohnt sich fast immer.
    • Aus Sicht eines Mathematikers wäre meine schlimmste Kritik, dass ich ein paar Formulierungen ganz leicht anders gewählt hätte, wenn der Text an mathematische Leser gerichtet wäre.
      Der Titel sollte „as simply as possible“ lauten. Ich kannte den GJK-Algorithmus nicht, aber wenn ich gerade Calculus III unterrichten würde, hätte ich wohl versucht, einen Weg zu finden, das in den Unterricht einzubauen. So gut ist die Erklärung.
    • Ich frage mich, ob bei diesem Algorithmus die Terminierung garantiert ist.
      Beim Beispiel mit dem weich abgerundeten Rechteck am Ende des Artikels ist mir nicht klar, was verhindert, dass man sich der Antwort nur immer weiter annähert, ohne sie tatsächlich zu erreichen. Natürlich weiß ich, dass es beim praktischen Rechnen keinen Grund gibt, nach einer sinnvollen Genauigkeitsgrenze weiterzumachen.
    • Die drei Mengen A, B, A-B in der zweiten Abbildung verwirren mich.
      Zuerst habe ich es so verstanden, dass auf A und B eine Transformation angewendet wird und dadurch die Form A-B entsteht. Nach mehrmaligem Lesen scheint A-B aber nicht die beiden Mengen links zu meinen, sondern die Schnittmenge eines anderen A und B darzustellen; wichtig scheint zu sein, dass diese Schnittmenge den Ursprung bzw. 0,0 überlappt. Stimmt das?

  • Ein Videovortrag zum selben Algorithmus: https://www.youtube.com/watch?v=ajv46BSqcK4

  • Der Artikel ist sehr klar und interessant.
    Eine andere Möglichkeit, die Schnittmenge zweier konvexer Mengen zu prüfen, besteht darin, ein Problem der konvexen Optimierung zu lösen: Man minimiert die Norm der Differenz zwischen einem Punkt aus der ersten konvexen Menge und einem Punkt aus der zweiten konvexen Menge. Wenn der optimale Wert 0 ist, schneiden sich die beiden Mengen.
    Es wäre interessant, den GJK-Algorithmus mit konvexer Optimierung zu vergleichen. Ich bin mir nicht sicher, welcher Ansatz vorteilhafter ist.

    • Interessante Frage. Wenn die Überlappung groß genug ist, könnte eine Innere-Punkte-Methode möglicherweise schnell terminieren. Man könnte wohl auch clevere Abbruchbedingungen für ein frühes Beenden hinzufügen.

  • Das erste Bild zeigt die Überschneidung nichtkonvexer Formen, aber dass der Algorithmus nur für konvexe Formen funktioniert, kommt erst deutlich später vor; das könnte etwas irreführend sein.

    • Es wird erklärt, dass nichtkonvexe Formen in konvexe Formen zerlegt und so behandelt werden.

  • Ich habe die Minkowski-Funktion in openSCAD eine Weile verwendet, und es ist schön zu erfahren, was sie tatsächlich ist.

  • Da das hier mehr Aufmerksamkeit bekommen hat als erwartet, sollte ich wohl erwähnen, dass meine persönliche Website im Grunde eine ausgefeilte Sammlung von Insiderwitzen ist.
    Wenn ihr Kontakt aufnehmen wollt oder etwas ansteht, könnt ihr einfach antworten.

    • Wenn du Interesse an Mentoring für Forschungsprojekte hast, kannst du mir eine Mail schicken: bersub@cmu.edu
    • Die Website ist gut und du wirkst wie eine coole Person. Mach weiter coole Sachen.

  • Vor fast 10 Jahren habe ich GJK auf Basis von Caseys hervorragender Erklärung implementiert: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • Ich habe einmal einen Artikel über Minkowski-Geometrie geschrieben: https://nickp.svbtle.com/asteroid-intersections