2D-objektausgerichteter Bounding-Box-Schnittpunkttest

9

Ich habe zwei objektausgerichtete Begrenzungsrahmen (dh nicht achsenausgerichtet, sie drehen sich mit dem Objekt). Ich würde gerne wissen, ob sich zwei objektausgerichtete Felder überlappen. ( Bearbeiten: Hinweis - Ich verwende einen achsenausgerichteten Begrenzungsrahmen-Test, um entfernte Objekte schnell zu verwerfen. Es spielt also keine Rolle, ob die Quad-Routine etwas langsamer ist. )

Meine Boxen werden als vier x, y Punkte gespeichert. Ich habe nach Antworten gesucht, aber ich kann die Variablennamen und Algorithmen in Beispielen nicht verstehen, um sie auf meinen speziellen Fall anzuwenden.

Kann mir jemand helfen, mir klar und einfach zu zeigen, wie das geht? Vielen Dank. (Die jeweilige Sprache ist nicht wichtig, Pseudocode im C-Stil ist in Ordnung.)

2d collision-detection bounding-boxes AshleysBrain
quelle

Antworten:

5

Wenn Sie wissen, wo Sie suchen müssen, ist es einfach. Sie suchen nach oobb. Gehen Sie hier: http://www.realtimerendering.com/intersections.html .
Dort finden Sie einen Link zu dieser Site http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html
und dort den richtigen Code. (Strg + f "Schnittpunkt der Kästchen (2D)")

Es verwendet SAT und enthält Quellcodes und Artikel.

Notabene
quelle
Der von den Geometrictools beschriebene Algorithmus ist der, auf den ich hingewiesen hätte.
Jari Komppa
Ich verstehe, dass dies vor 4 Jahren war, aber erkläre immer eine Ablehnung und all das. Dies ist hübsch "Ihre Antwort ist in einem anderen Schloss", und jetzt scheint die Antwort im zweiten Fall nicht einmal da zu sein.
Yann
2

Der einfachere Weg ist wahrscheinlich, jeden Scheitelpunkt von Feld B gegen jede Seite von Feld A zu testen (berechnen Sie den vorzeichenbehafteten Abstand). Auf diese Weise können Sie jeden Scheitelpunkt als "vor" oder "hinter" dem Segment klassifizieren.

Wenn alle Scheitelpunkte von B als "vor" einem der Segmente von A klassifiziert sind, überlappen sich B und A nicht. sonst tun sie es.

Dies ist etwas kompliziert, so dass Sie möglicherweise einen Leistungsgewinn erzielen, indem Sie zuerst eine Kreis-Kreis-Prüfung durchführen und dabei die Begrenzungskreise der Quadrate verwenden (trivial zu berechnen).

ggambett
quelle
Ich mache zuerst einen achsenausgerichteten Begrenzungsrahmen-Test, um entfernte Objekte schnell zu verwerfen. Haben Sie weitere Details zum Quad-Quad-Test?
AshleysBrain
Drehen Sie beide Quads vorübergehend mit derselben Transformation, sodass einer von ihnen achsenausgerichtet endet. Verwenden Sie dann den SAT-Test, wie nicht erwähnt. Wenn das Ergebnis gefunden wird, kehren Sie die Drehung um, um sie zurückzubekommen.
Steve H