Ich nahm das Studium der Kollisionserkennungsprozesse auf und führte mich zum Gilbert-Johnson-Keerthi (GJK) -Algorithmus.

Alle Codebeispiele im Beitrag sind in TypeScript geschrieben. In den Beispielen werden die von mir erstellten Strukturen verwendet, die im Beitrag nicht ausführlich behandelt werden. Sie sind einfach und können im GitHub-Repository angezeigt werden:

• Vector
• IShape
• Collision

Der gesamte Code aus dem Beitrag wird im GitHub-Repository gespeichert:

https://github.com/jthomperoo/gjk-ts-implementation

Der Beitrag wurde basierend auf diesem Artikel und dem darin empfohlenen Video geschrieben:

• http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
• http://mollyrocket.com/849

Einleitung

GJK ist ein Algorithmus zur Bestimmung des Schnittpunkts zweier konvexer Formen. Es ist einfach und wird mithilfe einer verallgemeinerten „Hilfsfunktion“ implementiert, mit der Sie einen allgemeineren Ansatz verwenden können. Auf die gleiche Weise können Sie Polygone und Formen verarbeiten, die aus Kurven bestehen, z. B. Ellipsen.

Erforderliche Informationen

Minkowski-Summe

GJK verwendet ein Konzept namens Minkowski-Summe. SM wird berechnet, indem alle Punkte zweier Zahlen addiert werden. Nehmen Sie zum Beispiel die beiden folgenden Abbildungen:


Abbildung A (grün):


Abbildung B (lila):


Aus den Werten von Abbildung A und Abbildung B können wir die Minkowski-Summe berechnen:

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

Wenn wir diese Werte nehmen und daraus ein Diagramm erstellen, werden wir sehen, welche Zahl das Ergebnis sein wird.

Minkowski-Summe für die Abbildungen A und B:

Beachten Sie, dass AD in Tabelle und Grafik A + D entspricht



Um die Minkowski-Summe besser zu verstehen, können wir uns vorstellen, dass wir eine Zahl A nehmen und sie mit dem Umriss eines B umgehen. Die resultierende Zahl ist die Minkowski-Summe.

Minkowski Unterschied

GJK verwendet eine Variation der Minkowski-Summe, in der nicht A + B, sondern A - B verwendet wird. In den von mir gelesenen Quellen wird dies als „Minkowski-Differenz“ bezeichnet. Der Minkowski-Unterschied hat eine interessante Eigenschaft: Wenn sich zwei Figuren überlappen / schneiden, enthält der resultierende Minkowski-Unterschied den Ursprung. Und das ist die Basis des GJK-Algorithmus.

Aus den Werten der Abbildungen A und B können wir die Minkowski-Differenz berechnen:

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

Wenn wir diese Werte nehmen und in die Grafik einfügen, sehen wir die resultierende Zahl.

Minkowski-Unterschied für die Abbildungen A und B:

Beachten Sie, dass sich AD in Tabelle und Grafik auf A - D bezieht

Algorithmus

Basierend auf diesen Konzepten optimiert der GJK-Algorithmus sie. Die Berechnung der Minkowski-Summe kann viel Zeit in Anspruch nehmen, insbesondere wenn Sie den Schnittpunkt zweier aus vielen Punkten bestehender Zahlen überprüfen. Um dies zu vermeiden, verwendet GJK zwei Schlüsselkonzepte: Hilfsfunktionen und Simplexe.

Hilfsfunktionen

Hilfsfunktionen sind eine Möglichkeit, einen Punkt am Rand der Minkowski-Differenz abzutasten, ohne die gesamte Figur zu konstruieren. Die Hilfsfunktion erhält zwei verglichene Zahlen und die Richtung, die überprüft werden muss. Dann empfängt die Hilfsfunktion von jeder Figur einen Punkt, der von zwei entgegengesetzten Richtungen am weitesten entfernt ist. Mit diesen beiden am weitesten entfernten Punkten können Sie den Hilfspunkt auf der Zahl der Minkowski-Differenz berechnen. Wir nehmen Punkte aus entgegengesetzten Richtungen, weil wir einen Punkt auf der Minkowski-Differenz erhalten, der uns die größte Fläche gibt, dh es besteht eine höhere Wahrscheinlichkeit, dass wir den Ursprung in die Abbildung aufnehmen. Da die Minkowski-Differenz der a - b das Vorhandensein des Punktes der Figur b, der aus der entgegengesetzten Richtung abgetastet wurde, einen Hilfspunkt, der so weit wie möglich in dieser Richtung liegt.

Die Implementierung der Hilfsfunktion ist recht einfach:

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

Einer der Vorteile von GJK ist, dass FarthestPointInDirection abstrahiert und auf Polygone und Kurven angewendet werden kann. Hier ist die Implementierung von FarthestPointInDirection für ein Polygon.

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } } 

Wenn Sie sehen möchten, wie andere Formen implementiert werden, lesen Sie das Git-Repository dieses Beitrags , in dem die Implementierung für Circle .

So wird der Hilfspunkt in (1,0) -Richtung für die Abbildungen A und B berechnet:

1. Nehmen Sie den entferntesten Punkt von der Figur A; es stellt sich heraus, Punkt B (1, -1) zu sein . (Sie können es wie den oben gezeigten Algorithmus berechnen oder es einfach anhand des Diagramms anzeigen.)
2. Nehmen Sie den entferntesten Punkt von Abbildung B; es stellt sich heraus, dass es der Punkt F (-1, 1) ist .
3. Berechnen Sie B - F ; es stellt sich heraus, dass es der Punkt BF (2, -2) ist - es wird ein Hilfspunkt sein.

Simplexe

Ein Simplex ist eine Stichprobe von Punkten entlang der Minkowski-Differenzzahl. Simplexe können bis zu drei Punkte enthalten. GJK verwendet sie und versucht, ein Dreieck um den Ursprung zu konstruieren, um das Auftreten einer Kollision zu bestimmen.

Simplex-Konstruktion

Simplexe werden iterativ konstruiert, indem Hilfspunkte in verschiedene Richtungen hinzugefügt werden. Jeder Hilfspunkt sollte in eine neue Richtung zeigen, damit wir so schnell wie möglich einen Simplex mit einem Ursprungspunkt erstellen können. Die Schwierigkeit liegt in der Wahl der Richtung, in die der nächste Hilfspunkt gelangen soll.

Kollisionserkennung und Richtungsauswahl

Der Basisalgorithmus erstellt einfach mithilfe einer Hilfsfunktion einen Simplex und versucht, einen Ursprungspunkt in die Abbildung einzuschließen. Wir können verstehen, dass es keine Kollision / Schnittmenge gibt, indem wir prüfen, ob der berechnete Hilfspunkt den Ursprung erreicht, und wenn dies nicht der Fall ist, muss der Ursprung außerhalb der Minkowski-Differenz liegen. Daher können wir sagen, dass es keine Kollision / Kreuzung gibt.

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); } 

Die gesamte Komplexität und interne Funktionsweise des Algorithmus erfolgt in simplex.CalculateDirection . Diese Funktion bestimmt, ob sich der Ursprung im aktuellen Simplex befindet. In diesem Fall wird undefined . Andernfalls wird eine neue Richtung zurückgegeben, um einen Hilfspunkt zu erhalten, der dem Simplex hinzugefügt werden muss.

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } } 

Sie fragen sich vielleicht: Warum überprüfen wir nicht das BC-Segment? Weil wir bedingungslos ausschließen können, dass der Ursprung entlang seiner Senkrechten liegt. Da sich die Punkte B und C bereits im Simplex befinden und nicht nur hinzugefügt wurden, wissen wir, dass sie in der vorherigen Iteration überprüft wurden. Sie können entweder als Teil eines Dreiecks oder als Segment der ersten beiden Punkte in einem Simplex überprüft werden - das spielt keine Rolle. Daher können wir die BC-Segmentprüfung sicher überspringen.

Detaillierte Erklärung

Wir haben viel Code und es sieht verwirrend aus. Im Folgenden werde ich die Schritte des Algorithmus für die oben gezeigten Abbildungen A und B analysieren.

Punkte der Figuren A und B:

1. Vorbereitung des Algorithmus; wir nehmen (0,1) als Anfangsrichtung.
   
   

    // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); 

   
   
2. Wir bekommen den ersten Hilfspunkt.
   
   

     // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); 

   
   Wir erhalten den am weitesten entfernten Punkt von Punkt A in Richtung (0,1) und von Punkt B in Richtung (0,-1) .
   
   aFar: (0,1) und bFar: (0,-1)
   
   Verwenden Sie diese Werte, um den Hilfspunkt zu erhalten.
   
   Unterstützung: aFar-bFar = (0,2)
   
   

     function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

   
   
3. Wir drehen die Richtung für den nächsten Hilfspunkt um und beginnen mit der Iteration, wobei wir einen neuen Hilfspunkt berechnen.
   
   Unterstützung: (0,-3)
   
   

     // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); 

4. Überprüfen Sie, ob der Hilfspunkt den Ursprung erreicht hat. Wenn nicht, sollte es keine Kreuzung geben. Wenn sie den Ursprung erreicht hat, fügen Sie den Punkt dem Simplex hinzu.
   
   In diesem Fall hat der Hilfspunkt den Ursprung erreicht.
   
   Richtung: (0,-1)
   
   Unterstützung: (0,-3)
   
   supportPoint.Dot (Richtung): 3
   
   

     // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); 

   
   
5. Zu diesem Zeitpunkt ist der Simplex ein Segment, sodass er keinen Ursprungspunkt enthalten kann. Definieren Sie eine neue Richtung, in die nach dem Hilfspunkt gesucht werden soll.
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. Wir nehmen den letzten Punkt, der dem Simplex hinzugefügt wurde, und bestimmen die Richtung zum Ursprung. Dies ist der Kehrwert dieses Punktes.
      
      a: (0,-3) ao: (0,3)
      
      

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { 

   2. Da der Simplex ein Segment und kein Dreieck ist, nehmen wir den zweiten Punkt des Segments und berechnen das Segment des Simplex.
      
      b: (0,2) ab: (0,5)
      
      

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); 

   3. Wir berechnen die Senkrechte zu diesem Segment und überprüfen, ob es auf den Ursprung gerichtet ist. Dies ist die neue Richtung für den nächsten Hilfspunkt.
      
      abPerp: (5, 0)
      
      abPerp.Dot (ao) 0
      
      abPerp: (-5, 0)
      
      
      
      
      

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; 

6. Jetzt haben wir eine Richtung, um nach dem nächsten Hilfspunkt zu suchen. Wir kehren zum Beginn des Zyklus zurück und verlassen ihn nicht, denn während wir eine Richtung haben und die Kreuzung noch nicht gefunden wurde.
   
   Richtung: (-5, 0)
   
   Unterstützung: (-2,-2)
   
   supportPoint.Dot (Richtung): 10
   
   Der Hilfspunkt hat den Ursprung erreicht, daher können wir nicht sagen, dass es keinen Schnittpunkt gibt.
   
   

     while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } 

7. Fügen Sie dem Simplex einen neuen Hilfspunkt hinzu und erstellen Sie ein Dreieck. Dieses Dreieck kann den Ursprung enthalten. Wenn dies der Fall ist, gibt der Simplex undefined und keine neue Richtung für die Suche.
   
   

     // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); 

   
   
   1. Nehmen Sie die Punkte des Simplex des Dreiecks.
      a: (-2,-2) b: (0,-3) c: (0,2) ao: (2,2)
      
      

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; 

   2. Nehmen Sie die Segmente ab und ac.
      
      ab: (2,-1) ac: (2,4)
      
      

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); 

   3. Wir berechnen die Senkrechte zum Segment ab, die vom Simplex gerichtet ist.
      
      abperp: (-1,-2)
      
      

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } 

   4. Wir bestimmen, ob der Ursprung außerhalb des Simplex jenseits von ab liegt.
      
      abPerp.Dot (ao): -6
      
      Der Ursprung liegt nicht außerhalb des Simplex jenseits von ab.
      
      
      
      
      

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } 

   5. Wir berechnen die Senkrechte zu dem vom Simplex gerichteten Segment ac.
      
      acPerp: (-4,2)
      
      

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } 

   6. Bestimmen Sie, ob der Ursprung außerhalb des Simplex jenseits von Wechselstrom liegt.
      
      acPerp.Dot (ao): -4
      
      Der Ursprung liegt nicht außerhalb des Simplex jenseits von ab.
      
      
      
      
      

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } 

   7. Da AB und AC in dieser Iteration überprüft wurden und wir wissen, dass BC in der vorherigen Iteration überprüft wurde, muss der Ursprung im Simplex liegen, sodass eine Kollision / Kreuzung erkannt wurde. Wenn Sie darüber informiert werden, wird die Funktion undefined .
      
      
      
8. Da eine Kollision erkannt wurde, wird die Schleife verlassen und Collision über die Kollision zwischen den beiden Figuren werden zurückgegeben.
   
   

     direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); 

Fazit

Ich hoffe, dieser Artikel hilft Ihnen, den GJK-Algorithmus zu verstehen. Der Algorithmus gibt eine Ja / Nein-Antwort auf das Vorhandensein eines Konflikts zwischen den beiden Figuren. Ein Arbeitsbeispiel mit Polygonen und Kreisen kann im Repository für diesen Beitrag angezeigt werden. Sie können diesen Code mit zusätzlichen Algorithmen und Techniken erweitern, indem Sie versuchen, die Durchdringungsentfernung zwischen den beiden Figuren, der Kollisionsnormalen und dem Kontaktpunkt zu ermitteln. Der dyn4j-Beitrag enthält Links zu guten Ressourcen zu verschiedenen Kollisions- / Antworterkennungsalgorithmen. Wenn Sie GJK erweitern möchten, sollten Sie sie studieren.