- 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
- Initialisierung: Ein beliebiger Richtungsvektor
d wird festgelegt und der erste Punkt p gesucht.
- Punktsuche: Das Skalarprodukt von
d und p wird berechnet; ist es positiv, geht es weiter, ist es negativ, wird beendet.
- Neuen Punkt hinzufügen: Von
p aus wird in Richtung des Ursprungs ein neuer Punkt gesucht.
- Vereinfachung: Ausgehend von den ersten beiden Punkten wird ein neuer Punkt hinzugefügt, um zu vereinfachen.
- Prüfen, ob der Ursprung enthalten ist: Es wird geprüft, ob die vereinfachte Form den Ursprung enthält.
- 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.
1 Kommentare
Hacker-News-Kommentare
GJK-Algorithmus: Ich habe mich in den 1990er Jahren ein Jahr lang damit abgemüht, den GJK-Algorithmus zu verstehen. Er ist nützlich für Kollisionserkennung und das Finden der nächstgelegenen Punkte. Das Grundkonzept ist leicht zu verstehen. Man beginnt mit zwei konvexen Körpern, wählt zufällige Punkte und versucht, die Distanz zwischen ihnen zu verbessern. Man wählt die nächstgelegenen Punkte und wiederholt den Vorgang. Wenn die nächstgelegenen Punkte keine Ecken mehr sind, braucht man das Konzept des „Simplex“. Dabei analysiert man verschiedene Fälle. In Physik-Engines treten Probleme auf, wenn Objekte sich auf Flächen-zu-Flächen-Kontakt einpendeln. Theoretisch ist es eine elegante Lösung, in der Praxis aber ein schwieriges numerisches Problem. Trotzdem ist es wahrscheinlich der schnellste Ansatz. Im allgemeinen Fall O(log N), wenn die vorige Position nahe liegt O(1). Der verstorbene Professor Stephen Cameron aus Oxford hat viel Forschung betrieben, um GJK korrekt zu implementieren. In den späten 1990er Jahren wurde GJK im kommerziellen 3D-Ragdoll-System „Falling Bodies“ verwendet.
Eine Erklärung zu GJK geschrieben: Ich konnte keine intuitive Erklärung des GJK-Kollisionserkennungsalgorithmus finden und habe deshalb selbst eine geschrieben. Falls jemand weiß, wie man sie klarer oder effizienter machen kann, freue ich mich über Hinweise. Da es sich um eine mathematische Erklärung von einem Highschool-Schüler handelt, sollte man sie mit einer angemessenen Portion Skepsis lesen.
Video zum GJK-Algorithmus: Es wurde ein Link zu einer Videopräsentation über denselben Algorithmus geteilt. Videolink
Lob für den Artikel: Ein großartiger Artikel. Sehr klar und interessant.
Vergleich mit konvexer Optimierung: Eine andere Methode, um zu prüfen, ob zwei konvexe Mengen einen Schnittpunkt haben, ist das Lösen eines konvexen Optimierungsproblems, bei dem die Norm der Differenz zwischen zwei Punkten minimiert wird. Ist der optimale Wert 0, dann schneiden sich die Mengen. Ich würde gern einen Vergleich zwischen dem GJK-Algorithmus und dem Ansatz über konvexe Optimierung sehen. Ich bin nicht sicher, welcher besser ist.
Lob für den Artikel und Missverständnis: Ein großartiger Artikel. Allerdings zeigt das erste Bild den Schnittpunkt nichtkonvexer Formen, während sich erst später herausstellt, dass der Algorithmus nur für konvexe Formen funktioniert.
GJK-Algorithmus zum ersten Mal gesehen: Ich höre zum ersten Mal vom GJK-Algorithmus.
Verwandter Blogpost: Ich habe einen Blogpost zu Minkowski-Geometrie geschrieben. Bloglink
Persönliche Website: Unerwarteterweise bekommt das Ganze Aufmerksamkeit, daher der Hinweis, dass meine persönliche Website voller Scherze ist. Wenn jemand Kontakt aufnehmen möchte, sagt bitte per Antwort Bescheid.
Verwendung der Minkowski-Funktion: Ich habe in openSCAD die Minkowski-Funktion verwendet und freue mich, jetzt zu wissen, was sie tatsächlich ist.
Lob für den Algorithmus: Ein großartiger Algorithmus.