Ein Objekt hat eine Position und einen Geschwindigkeitsvektor. Normalerweise wird nur die Position verwendet, um zu überprüfen, ob zwei Objekte kollidieren. Dies ist problematisch für sich sehr schnell bewegende Objekte, da es passieren kann, dass sich das Objekt bei der ersten Kollisionsprüfung so schnell bewegt, dass es sich vor dem ersten Objekt und dahinter befindet die zweite Kollisionsprüfung.

Jetzt gibt es auch linienbasierte Kollisionsprüfungen, bei denen Sie nur prüfen, ob der Bewegungsvektor jedes Objekts den Begrenzungsrahmen des anderen schneidet. Dies kann als Erweiterung eines Punktes angesehen werden. Dies funktioniert jedoch nur, wenn das sich schnell bewegende Objekt wirklich klein ist.

Meine Idee ist also, anstatt einen Punkt zu erweitern, ein Rechteck zu erweitern. Dies ergibt ein Sechseck.

Nun, soweit so gut. Aber wie überprüfe ich eigentlich, ob sich zwei Sechsecke dieser Art kreuzen? Beachten Sie, dass dies sehr spezifische Sechsecke sind.

Bonusfrage : Ist es möglich zu berechnen, wo genau (bzw. nach wie viel Zeit) die Kollision stattgefunden hat? Dies kann sehr nützlich sein, um festzustellen, was wirklich passiert ist, wie wo und mit wie viel Leistung und um zu simulieren, wie sie sich in der Zeit zwischen der Kollision und dem Ende des Rahmens bewegt haben.

Die Lösung ist tatsächlich einfacher als erwartet. Der Trick besteht darin, die Minkowski-Subtraktion vor der Hexagon-Technik anzuwenden.

Hier sind deine Rechtecke A und B mit ihren Geschwindigkeiten vAund vB. Beachten Sie, dass vAund vBsind nicht wirklich Geschwindigkeiten, sie sind der Abstand während eines Rahmens gereist.

Ersetzen Sie nun das Rechteck B durch einen Punkt P und das Rechteck A durch das Rechteck C = A + (- B), dessen Dimensionen die Summe der Dimensionen von A und B sind. Die Minkowski-Additionseigenschaften geben an, dass eine Kollision zwischen dem Punkt und dem neuen Rechteck auftritt genau dann, wenn eine Kollision zwischen den beiden ursprünglichen Rechtecken auftritt:

Wenn sich jedoch das Rechteck C entlang des Vektors bewegt vAund der Punkt P entlang des Vektors vB, sagt uns eine einfache Änderung des Referenzrahmens, dass dies dasselbe ist, als wäre das Rechteck C noch und der Punkt P entlang des Vektors bewegt vB-vA:

Anschließend können Sie mithilfe einer einfachen Box-Segment-Schnittformel feststellen, wo die Kollision im neuen Referenzrahmen auftritt.

Der letzte Schritt ist, zum richtigen Referenzrahmen zurückzukehren. Teilen Sie einfach die zurückgelegte Strecke durch den Punkt bis zum eingekreisten Schnittpunkt durch die Länge des Vektors vB-vAund Sie erhalten einen ssolchen Wert 0 < s < 1. Die Kollision findet zu einem Zeitpunkt statt, an s * Tdem Tsich die Dauer Ihres Frames befindet.

Kommentar von madshogo :
Ein RIESIGER Vorteil dieser Technik gegenüber der in Mr Beasts eigener Antwort ist, dass, wenn es keine Rotation gibt, die "Minkowski-Subtraktion" A + (- B) für alle nachfolgenden Zeitschritte einmal berechnet werden kann !

Der einzige Algorithmus, der dabei Zeit in Anspruch nimmt (Minkowski-Summe, Komplexität O (mn), wobei m die Anzahl der Scheitelpunkte in A und n die Anzahl der Scheitelpunkte in B ist ), kann also nur einmal verwendet werden. Zeitproblem!

Später können Sie die Summe wegwerfen, sobald Sie sicher sind, dass sich A und B in verschiedenen Teilen Ihrer Szene (Ihres Quadtree?) Befinden und nicht mehr kollidieren.

Im Gegensatz dazu erfordert die Methode von Mr Beast bei jedem Zeitschritt eine ganze Reihe von Berechnungen.

Für achsenausgerichtete Rechtecke kann A + (- B) auch viel einfacher berechnet werden, als indem tatsächlich alle Summen Scheitelpunkt für Scheitelpunkt berechnet werden. Erweitern Sie einfach A, indem Sie die Höhe von B zu seiner Höhe und die Breite von B zu seiner Breite addieren (eine Hälfte auf jeder Seite).

Das alles funktioniert aber nur, wenn weder A noch B rotieren und beide konvex sind. Wenn es eine Drehung gibt oder wenn Sie konkave Formen verwenden, müssen Sie überstrichene Volumina / Bereiche verwenden.
Ende des Kommentars

Erstens ist die Antwort von Kevin Reid bei achsenausgerichteten Rechtecken die beste und der Algorithmus die schnellste.

Verwenden Sie zweitens für einfache Formen die Relativgeschwindigkeit (siehe unten) und den Satz der Trennachse für die Kollisionserkennung. Es wird Ihnen sagen , ob eine Kollision im Fall der linearen Bewegung geschieht (keine Rotation). Und wenn es eine Rotation gibt, brauchen Sie einen kleinen Zeitschritt, um genau zu sein. Nun zur Beantwortung der Frage:

Wie erkennt man im allgemeinen Fall, ob sich zwei konvexe Formen schneiden?

Ich gebe Ihnen einen Algorithmus, der für alle konvexen Formen und nicht nur für Sechsecke funktioniert.

Angenommen, X und Y sind zwei konvexe Formen. Sie kreuzen sich genau dann, wenn sie einen Punkt gemeinsam haben, dh es gibt einen Punkt x ∈ X und einen Punkt y ∈ Y, so dass x = y . Betrachtet man den Raum als Vektorraum, so bedeutet dies x - y = 0 . Und jetzt kommen wir zu diesem Minkowski-Geschäft:

Die Minkowski-Summe von X und Y ist die Menge von allem x + y für x ∈ X und y ∈ Y .

Ein Beispiel für X und Y

X, Y und ihre Minkowski-Summe, X + Y

Angenommen, (-Y) ist die Menge aller -y für y ∈ Y , dann gegeben den vorherigen Absatz, X und Y schneiden sich genau dann, wenn X + (-Y) 0 enthält , dh den Ursprung .

Nebenbemerkung: Warum schreibe ich X + (-Y) anstelle von X - Y ? Nun, weil es in der Mathematik eine Operation namens Minkowski-Differenz von A und B gibt, die manchmal mit X - Y geschrieben wird, aber nichts mit der Menge von allem zu tun hat x - y für x ∈ X und y ∈ Y (der echte Minkowski Unterschied ist etwas komplexer).

Wir möchten also die Minkowski-Summe von X und -Y berechnen und herausfinden, ob sie den Ursprung enthält. Der Ursprung ist im Vergleich zu anderen Punkten nicht besonders. Um festzustellen, ob sich der Ursprung innerhalb einer bestimmten Domäne befindet, verwenden wir einen Algorithmus, der uns mitteilen kann, ob ein bestimmter Punkt zu dieser Domäne gehört.

Die Minkowski-Summe von X und Y hat eine coole Eigenschaft: Wenn X und Y konvex sind, dann X + Y auch. Und festzustellen, ob ein Punkt zu einer konvexen Menge gehört, ist viel einfacher, als wenn diese Menge nicht konvex wäre.

Wir können unmöglich das gesamte x - y für x ∈ X und y ∈ Y berechnen, da es unendlich viele solcher Punkte x und y gibt. Da X , Y und X + Y also hoffentlich konvex sind, können wir einfach verwenden Die "äußersten" Punkte definieren die Formen X und Y , die ihre Eckpunkte sind, und wir erhalten die äußersten Punkte von X + Y und einige weitere.

Diese zusätzlichen Punkte sind von den äußersten Punkten von X + Y "umgeben", so dass sie nicht zur Definition der neu erhaltenen konvexen Form beitragen. Wir sagen, dass sie nicht die " konvexe Hülle " der Punktmenge definieren. Was wir also tun, ist, dass wir sie loswerden, um uns auf den endgültigen Algorithmus vorzubereiten, der uns sagt, ob der Ursprung innerhalb der konvexen Hülle liegt.

Der konvexe Rumpf von X + Y. Wir haben die "inneren" Eckpunkte entfernt.

Wir bekommen also

Ein erster, naiver Algorithmus

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Die Schleifen haben offensichtlich die Komplexität O (mn), wobei m und n die Anzahl der Eckpunkte jeder Form sind. Die minkoswkiMenge enthält höchstens mn Elemente. Der convexHullAlgorithmus hat eine Komplexität, die von dem von Ihnen verwendeten Algorithmus abhängt , und Sie können O (k log (k)) anstreben, wobei k die Größe der Menge von Punkten ist. In unserem Fall erhalten wir also O (mn log (mn) ) . Der containsAlgorithmus hat eine Komplexität, die linear mit der Anzahl der Kanten (in 2D) oder Flächen (in 3D) der konvexen Hülle ist. Dies hängt also wirklich von Ihren Ausgangsformen ab, ist jedoch nicht größer als O (mn) .

Ich lasse Sie nach dem containsAlgorithmus für konvexe Formen googeln , er ist ziemlich häufig. Ich kann es hier setzen, wenn ich die Zeit habe.

Aber es ist die Kollisionserkennung, die wir machen, damit wir das viel optimieren können

Wir hatten ursprünglich zwei Körper A und B, die sich während eines Zeitschritts dt ohne Drehung bewegten (was ich anhand Ihrer Bilder erkennen kann). Nennen wir v _A und v _B die jeweiligen Geschwindigkeiten von A und B , die während unseres Zeitschritts der Dauer dt konstant sind . Wir bekommen folgendes:

Und, wie Sie in Ihren Bildern hervorheben, streichen diese Körper in 3D durch Bereiche (oder Volumen), während sie sich bewegen:

und sie enden als A ' und B' nach dem Zeitschritt.

Um unseren naiven Algorithmus hier anzuwenden, müssten wir nur die überstrichenen Volumina berechnen. Aber das machen wir nicht.

In dem Bezugssystem B , B bewegt sich nicht (duh!). Und A hat eine bestimmte Geschwindigkeit in Bezug auf B , die Sie durch Berechnen von v _A - v _{B erhalten} (Sie können das Gegenteil tun , indem Sie die relative Geschwindigkeit von B im Bezugssystem von A berechnen ).

Von links nach rechts: Geschwindigkeiten im Basisbezugsrahmen; relative Geschwindigkeiten; Berechnung der relativen Geschwindigkeiten.

Wenn Sie B als unbeweglich in einem eigenen Referenzrahmen betrachten, müssen Sie nur das Volumen berechnen, das A durchläuft, wenn es sich während dt mit seiner relativen Geschwindigkeit v _A - v _B bewegt .

Dies verringert die Anzahl der Eckpunkte, die bei der Minkowski-Summenberechnung verwendet werden sollen (manchmal sehr).

Eine weitere mögliche Optimierung ist der Punkt, an dem Sie das Volumen berechnen, das von einem der Körper überstrichen wird, z. B. A. Sie müssen nicht alle Scheitelpunkte verschieben, aus denen A besteht. Nur diejenigen, die zu Kanten gehören (Flächen in 3D), deren äußere normale "Gesicht" die Richtung der Kehren. Sicherlich haben Sie das schon bemerkt, als Sie Ihre überstrichenen Flächen für die Quadrate berechnet haben. Anhand des Skalarprodukts mit der Abtastrichtung, die positiv sein muss, können Sie erkennen, ob eine Normale in die Abtastrichtung zeigt.

Die letzte Optimierung, die nichts mit Ihrer Frage nach Kreuzungen zu tun hat, ist in unserem Fall wirklich nützlich. Dabei werden die erwähnten Relativgeschwindigkeiten und die sogenannte Trennachsenmethode verwendet. Sicher weißt du es schon.

Angenommen, Sie kennen die Radien von A und B in Bezug auf ihre Massenschwerpunkte (dh den Abstand zwischen dem Massenschwerpunkt und dem am weitesten davon entfernten Scheitelpunkt) wie folgt:

Eine Kollision kann nur auftreten, wenn der Begrenzungskreis von A mit dem von B übereinstimmt . Wir sehen hier, dass dies nicht der Fall ist, und wie Sie dem Computer mitteilen, dass die Entfernung von C _B zu I wie im folgenden Bild berechnet werden soll, und sicherstellen, dass sie größer als die Summe der Radien von A und B ist . Wenn es größer ist, keine Kollision. Wenn es kleiner ist, dann Kollision.

Dies funktioniert nicht sehr gut mit Formen, die ziemlich lang sind, aber im Fall von Quadraten oder anderen derartigen Formen ist es eine sehr gute Heuristik , Kollisionen auszuschließen .

Der auf B angewendete Trennachsensatz und das von A überstrichene Volumen zeigen jedoch an, ob die Kollision auftritt. Die Komplexität des zugeordneten Algorithmus ist linear mit der Summe der Anzahl der Eckpunkte jeder konvexen Form, aber es ist weniger magisch, wann der Zeitpunkt kommt, um die Kollision tatsächlich zu handhaben.

Unser neuer, besserer Algorithmus, der Schnittpunkte zur Erkennung von Kollisionen verwendet, aber immer noch nicht so gut ist wie der Satz der Trennachse, um tatsächlich zu sagen, ob eine Kollision auftritt

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

Ich denke nicht, dass die Verwendung des Sechsecks hilfreich ist. Hier ist eine Skizze eines Weges, um genaue Kollisionen für achsenausgerichtete Rechtecke zu erhalten:

Zwei achsenausgerichtete Rechtecke überlappen sich genau dann, wenn sich ihre X-Koordinatenbereiche und ihre Y-Koordinatenbereiche überlappen. (Dies kann als Sonderfall des Satzes der Trennachse angesehen werden.) Wenn Sie also die Rechtecke auf die X- und Y-Achse projizieren, haben Sie das Problem auf zwei Schnittpunkte von Linie zu Linie reduziert.

Berechnen Sie das Zeitintervall, in dem sich die beiden Linien auf einer Achse schneiden (z. B. beginnt es zur Zeit (aktuelle Trennung von Objekten / relative Annäherungsgeschwindigkeit von Objekten)) und machen Sie dasselbe für die andere Achse. Überlappen sich diese Zeitintervalle, so ist der früheste Zeitpunkt innerhalb der Überlappung der Zeitpunkt der Kollision.

Ich glaube nicht, dass es einfach ist, die Kollision von Polygonen mit mehr Seiten als einem Rechteck zu berechnen. Ich würde es in primitive Formen wie Linien und Quadrate zerlegen:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Beachten Sie, wie ich den Startstatus jedes Objekts ignoriere, da dies bei der vorherigen Berechnung hätte überprüft werden müssen.

Separater Achsensatz

Die Seperate Achse Satz sagt : „Wenn wir eine Achse , auf der zwei konvexen Formen sich nicht schneiden dann finden die beiden Formen sind nicht schneidende “ oder mehr praktikabel für IT:

"Zwei konvexe Formen schneiden sich nur, wenn sie sich auf allen möglichen Achsen schneiden."

Für achsenausgerichtete Rechtecke gibt es genau 2 mögliche Achsen: x und y. Der Satz ist jedoch nicht auf Rechtecke beschränkt, sondern kann auf jede konvexe Form angewendet werden, indem nur die anderen Achsen hinzugefügt werden, auf denen sich die Formen schneiden könnten. Weitere Informationen zum Thema finden Sie in diesem Tutorial des Entwicklers von N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Umgesetzt sieht es so aus:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Achsen können als normalisierte Vektoren dargestellt werden.

Ein Bereich ist eine eindimensionale Linie. Der Start sollte auf den kleinsten projizierten Punkt gesetzt werden, das Ende auf den größten projizierten Punkt.

Anwenden auf das "überstrichene" Rechteck

Das Sechseck in der Frage wird durch "Abtasten" des AABB des Objekts erzeugt. Beim Sweepen wird jeder Form genau eine mögliche Kollisionsachse hinzugefügt: der Bewegungsvektor.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

So weit so gut, jetzt können wir schon prüfen, ob sich die beiden Sechsecke schneiden. Aber es wird noch besser.

Diese Lösung funktioniert für alle konvexen Formen (z. B. Dreiecke) und alle überstrichenen konvexen Formen (z. B. überstrichene Achtecke). Je komplexer die Form ist, desto weniger effektiv ist sie.

Bonus: Wo die Magie passiert.

Wie gesagt, die einzigen zusätzlichen Achsen sind die Bewegungsvektoren. Die Bewegung ist Zeit multipliziert mit Geschwindigkeit. In gewisser Weise sind sie also nicht nur Raumachsen, sondern Zeit-Raum-Achsen.

Das heißt, wir können aus diesen beiden Achsen den Zeitpunkt ableiten, zu dem die Kollision hätte eintreten können. Dazu müssen wir den Schnittpunkt zwischen den beiden Schnittpunkten auf den Bewegungsachsen finden. Bevor wir dies tun können, müssen wir jedoch beide Bereiche normalisieren, damit wir sie tatsächlich vergleichen können.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Als ich diese Frage stellte, akzeptierte ich bereits den Kompromiss, dass es mit dieser Methode einige seltene Fehlalarme geben wird. Aber ich habe mich geirrt, indem wir diese Zeitkreuzung überprüft haben, können wir testen, ob die Kollision "tatsächlich" stattgefunden hat und wir können diese Fehlalarme damit aussortieren:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Wenn Sie Fehler in den Codebeispielen bemerken, lassen Sie es mich wissen, ich habe es noch nicht implementiert und konnte es daher nicht testen.

Solange die überstrichenen Bereiche beide geschlossen sind (keine Lücken in der durch die Kantenlinien gebildeten Grenze), funktioniert Folgendes (reduzieren Sie einfach Ihre Kollisionstests auf Linie-Linie und Punkt-Gerade / Punkt-Tri):

1. Berühren sich ihre Kanten? (Linie-Linie-Kollisionen) Prüfen Sie, ob sich eine Kantenlinie eines überstrichenen Bereichs mit einer Kantenlinie des anderen überstrichenen Bereichs schneidet. Jeder überstrichene Bereich hat 6 Seiten.

2. Ist der Kleine im Großen? (Verwenden Sie achsenausgerichtete Formen (point-rect & point-tri)) Richten Sie die überstrichenen Bereiche neu aus (drehen Sie sie), so dass der größere achsenausgerichtet ist, und prüfen Sie, ob der kleinere intern ist (indem Sie prüfen, ob Eckpunkte vorhanden sind). sollten alle oder keine sein) befinden sich innerhalb des achsenausgerichteten Sweep-Bereichs. Dies geschieht, indem du dein Hex in Tris und Rects zerlegst.

Welcher Test Sie zuerst durchführen, hängt von der Wahrscheinlichkeit jedes Tests ab (führen Sie den am häufigsten vorkommenden Test zuerst durch).

Möglicherweise ist es einfacher, einen überstrichenen Begrenzungskreis (Kapsel statt Sechseck) zu verwenden, da es einfacher ist, ihn in zwei Halbkreise und ein Rechteck zu teilen, wenn er auf die Achse ausgerichtet ist. ..Ich lasse Sie die Lösung zeichnen