Wie überprüfe ich die Kollision zweier sich bewegender 2D-Bounding-Boxen?

Question

Die OBBs haben eine Position (x, y), eine Geschwindigkeit (x, y) und eine Orientierung (Matrix). Bei regelmäßigen Updates müssen die OBBs miteinander kollidieren und den Bruch der Bewegung zurückgeben, der als erfolgreich angesehen wurde.

Ich habe den Polygon-Test auf dem GPWiki - http://gpwiki.org/index.php/Polygon_Collision betrachtet - aber es berücksichtigt nicht bewegliche Objekte oder ein Objekt, das vollständig in einem OBB ist.

Das Buch Echtzeit-Kollisionserkennung umfasst 3D-OBBs in Kapitel 4: Begrenzungsvolumen, aber die Methode zum Testen in 3 Dimensionen ist deutlich komplexer als in 2D.

Answer 1

Sie sagen 2D, aber auch 3D als komplexer zu nennen. Bei der Kollisionserkennung möchten Sie grundsätzlich testen, ob sich zwei Formen schneiden. In 2D mit Begrenzungsrahmen sind dies rectangles. Sie müssen einen Algorithmus verwenden, um zu sehen, ob sich die Rechtecke überschneiden, und auch prüfen, ob einer vollständig in einem anderen enthalten ist (3 Tests für den einfachen Algorithmus). Für 3d sind dies Würfel. Gleiche Sache. Schauen Sie sich matrix Objekt-Objekt-Schnittpunkte an und finden Sie die gewünschten. Überprüfen Sie, ob sich die Objekte selbst überschneiden, und ob der eine vollständig in dem anderen enthalten ist.

Diese Prozedur kann sich nicht nur auf Begrenzungsrahmen, sondern auch auf Begrenzungsbereiche oder auf tatsächliche Objekte selbst in konvexen Begrenzungshülsen, Polygonen oder vollständigen 3D-Objekten erstrecken. Das Endergebnis ist, wenn die Objekte durch Raum und Zeit fortschreiten, ob ihre Oberflächen kollidieren oder ob sie ineinander liegen. Für den Fall, dass Ihre Granularität zu grob ist und sie in der Situation, die Sie modellieren, kollidieren sollten, aber sie sich am Ende aneinander vorbei bewegen, sollten Sie einen zusätzlichen Schnittpunkttest durchführen, um zu sehen, ob ein zentraler, gewichteter Punkt in einem Objekt schneidet die Grenzen des anderen.

Answer 2

Wenn Sie zwei Begrenzungsbox (dh Rechtecke) mit einer beliebigen Orientierung (was ich davon ausgehen, bedeutet eine „Rotation“), dann würde ich Folgendes tun:

• ab einer Anfangsposition (wo ich Angenommen, die Begrenzungsrechtecke überschneiden sich nicht), übersetze jede Box basierend auf ihrer Geschwindigkeit vorwärts (wie auch immer du Bewegungen über die Zeit anlegst).
• Suchen Sie die Koordinaten der Ecken jeder übersetzten Bounding Box. Diese 4 Koordinaten definieren die Endpunkte der 4 Liniensegmente, die die Kanten der Begrenzungsbox bilden.
• Für Bounding Box # 1, Test für einen Schnittpunkt zwischen jedem seiner Liniensegmente und die 4 Liniensegmente der Bounding Box # 2. Sie können dies unter Verwendung von Standardgleichungen zum Berechnen des Schnittpunkts von zwei Linien tun, wie zum Beispiel here diskutiert.
• Wenn es eine Kreuzung gab, ermitteln Sie den Bruchteil einer Bewegung, die erfolgreich war, anhand der Koordinaten der Schnittpunkte und der bekannten Übersetzung, die Sie angewendet haben.
• Wiederholen Sie die obigen Schritte für jedes Update.

EDIT: Ein grober Pseudo-Code (unter Einbeziehung was in den Kommentaren diskutiert wurde) würde wie folgt aussehen:

...test for intersections between the OBB edges... 
if any intersections are found{ 
    ...run code for when OBBs are partially overlapping... 
}else{ 
    P = line segment whose endpoints are the OBB centers; 
    ...test for intersections between P and OBB edges... 
    if P intersects edges of both OBBs{ 
     ...run code for when OBBs are not touching... 
    }else{ 
     ...run code for when one OBB is completely inside the other... 
    } 
} 

Answer 3

Um Kollisionserkennung zwischen zwei orientierte Begrenzungsbox zu testen, würde ich verwenden Achse Trenn Satz (SAT). Tatsächlich kann SAT zur Kollisionserkennung zwischen zwei konvexen Formen verwendet werden. Diese Technik ist nicht zu komplex zu verstehen und hat eine angemessene Leistung. Der Satz kann leicht auf 3D erweitert werden.

EDIT:

Der Algorithmus, um zu bestimmen versucht, ist es möglich ist, eine Ebene zwischen zwei Objekten zu passen. Wenn eine solche Ebene existiert, wird das Objekt getrennt und kann sich nicht schneiden.

Um festzustellen, ob die Objekte getrennt sind, müssen die Objekte einfach auf die Ebene normal projiziert und die Intervalle verglichen werden, um festzustellen, ob sie sich überlappen.

Also gibt es offensichtlich eine unendliche Anzahl von Ebenen, die zwischen zwei getrennten Objekten passen können. Aber es wurde bewiesen, dass man nur eine Handvoll Flugzeuge testen muss.

Es kann gezeigt werden, dass für Boxen die zu prüfenden Trennebenen die Ebenen mit Normalen sind, die gleich den Achsen beider Boxen sind. Für 2 Boxen müssen Sie also nur 4 Trennebenen testen. Wenn Sie von den 4 Ebenen eine Trennebene gefunden haben, die die Boxen voneinander trennt, wissen Sie, dass sich die Box nicht überschneiden kann, und Sie geben ein Flag für keine Kollision zurück.

Wenn die vier Ebenen die Boxen nicht trennen können, muss die Box eine Kreuzung sein, und Sie haben eine Kollision.

Answer 4

Ein weiterer Vorschlag (die Eindämmung bedeckt, und ich denke, ist billiger):

Überprüfen Sie, ob eine der vier Ecken von # 1 sind innerhalb # 2, dann zu prüfen, ob eine der vier Ecken von # 2 innen sind # 1. Hier ist, wie ich vorschlagen würde, darüber zu gehen:

Angenommen, die Ecke von # 1, die Sie überprüfen, ist v, und die 4 Ecken von # 2 sind v1 ... v4. Inverse-rotate alle 5 Ecken durch die Orientierung von # 2. (Um einen Vektor u durch eine Orientierungsmatrix M umgekehrt zu drehen, multipliziere u mit M-transponiert: M^T u, vorausgesetzt, dass in deiner Konvention Orientierung durch Multiplikation nach links funktioniert.) Die resultierende zweite Box, nenne sie # 2 ' , ist jetzt Achse ausgerichtet - Sie können sofort überprüfen, ob v 'darin enthalten ist.

Wenn Sie einen # 1-Eckpunkt innerhalb von # 2 gefunden haben - stoppen Sie, Sie haben einen Schnittpunkt. Ansonsten - weiter.

Ein paar Optimierungen fallen mir sofort ein (vielleicht können Sie nicht rotierte Kopien der Scheitelpunkte in jeder Box speichern? Wenn die Größen festgelegt sind, können Sie sie vergleichen, um sofort einen der möglichen Eindämlinge zu entfernen und 3 mögliche Tests zu speichern ?), aber wenn Sie es nicht auf gazillions von Kastenpaaren anwenden, sollte dieser Test billig genug sein, wie es ist.

In Bezug auf die Bewegung, können Sie so tief wie Sie wollen dort - nachschlagen 'kontinuierliche Kollision', und sehen Sie selbst. (Ich erinnere mich besonders an einige schöne Arbeiten von Stephane Redon). Ich bin von ganzem Herzen der Meinung, dass kein Spiel all diese ausgefallenen Sachen macht: Wenn Sie sich wirklich extrem schnell bewegen, können Sie Ihren Zeitschritt unterteilen und Kollisionsprüfungen für jede Positions-/Orientierungsunteriteration durchführen.

(bearbeiten :) Es gab eine andere Diskussion right here darüber, mit netten Referenzen.

Answer 5

Sie sollten wahrscheinlich einen Quadtree implementieren (siehe wikipedia), um alle Objekte im Flugzeug zu verfolgen. Ich habe leider noch nie einen zur Kollisionserkennung implementiert, aber es scheint, dass andere people ähnliche Szenarien wie Quad-Bäume erstellen konnten.