Wie lässt sich am schnellsten überprüfen, ob sich zwei sich bewegende AABBs überschneiden?

Ich habe zwei AABBs, die sich bewegen. Wie kann ich am schnellsten überprüfen, ob sie sich unter einem Frame schneiden?

Mit Bewegen meine ich nicht nur, um mit der üblichen Rechteckschnittmethode zu prüfen, sondern eine Art einfachen, einfachen Swept-Test, der nur einen Booleschen Wert zurückgibt, keine Trefferzeit oder irgendetwas anderes.

Was ich denke ist, es einfach so zu machen:

Aber dieses Hexagon ist ziemlich komplex und ich weiß nicht, wie man einen AABB - Polygon - Schnitt berechnet. Gibt es vielleicht einen einfacheren Weg?

Jede Programmiersprache, die Ihnen am besten gefällt, kann ich problemlos portieren.

Vielen Dank.

Verwenden Sie die Minkowski-Summe

Eine gute Möglichkeit, dieses Problem zu lösen, besteht darin, den Schnittpunkt zwischen einer Bewegungslinie ( v ), die zum Ursprung ( v ' ) verschoben wurde, und der Minkowski-Summe von A , die am Ursprung ( A' ) um 180 Grad gedreht wurde , und seinen Hindernissen (nur B) zu betrachten in diesem Fall): A‘ ⊕ B .

Im folgenden Bild platziere ich einen Klaps in den Ursprung eines beliebigen Koordinatensystems. Dies vereinfacht das Verständnis, da das Drehen von A um 180 Grad zu A ' führt und v in den Ursprung übersetzt gleich v' ist .

Die Minkowski-Summe ist das grüne Rechteck, und die Schnittpunkte eines sich bewegenden A und eines stationären B können durch Ausführen der Schnittlinie AABB ermittelt werden . Diese Punkte sind mit den blauen Kreisen markiert.

Im folgenden Bild wurde ein anderer Ursprung verwendet und es wurden die gleichen Schnittpunkte gefunden.

Mehrere bewegliche AABBs

Damit dies für zwei AABBs funktioniert, die sich in einem bestimmten Zeitraum linear bewegen, würden Sie subtrahieren Geschwindigkeitsvektor von B vom Geschwindigkeitsvektor von A und verwenden diesen als Liniensegment für den Schnittpunkt zwischen Linie und AABB.

Pseudocode

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Kollisionsreaktion

Abhängig vom Gameplay würden Sie entweder eine feinkörnigere Kollisionserkennung durchführen (möglicherweise enthalten die AABBs Maschen) oder mit der nächsten Phase fortfahren: Kollisionsreaktion.

Bei einer Kollision gibt der AABB-Schnittpunkt-Algorithmus entweder 1 oder 2 Schnittpunkte zurück, je nachdem, ob A seine Bewegung innerhalb von B beendet oder durch ihn läuft. (Dies schließt die entarteten Fälle aus, in denen A B entlang ihrer Seiten oder entlang einer ihrer jeweiligen Ecken streift.)

In beiden Fällen ist der erste Schnittpunkt entlang des Liniensegments der Kollisionspunkt. Sie würden diesen Punkt in die richtige Position im Weltkoordinatensystem zurückversetzen (der erste hellblaue Kreis im zweiten Bild entlang des ursprünglichen v , nennen Sie ihn p ) und dann entscheiden (z. B. für elastische Kollisionen durch Reflektieren von v entlang der Kollisionsnormalen bei p ), wie die tatsächliche Position für A am Ende des Rahmens sein wird ( bei + 1 ).

Wenn es mehr als nur 2 Collider gibt, wird dies etwas komplexer, da Sie die Kollisionserkennung auch für den zweiten, reflektierten Teil von v durchführen möchten .

OBB - Orientierter Begrenzungsrahmen. Hier ist ein Tutorial

Tatsächlich wird ein Begrenzungsrahmen mit dem Geschwindigkeitsvektor von Objekt A als y-Achse (nach oben) ausgerichtet. Seine Breite und Höhe können durch den Start- und Endpunkt von Objekt A berechnet werden. Sie vergleichen dies dann mit dem AABB von Objekt B (das als OOBB behandelt wird) und Ihrem Goldenen.

Wenn Sie nur nach einem schnellen Schnittpunkttest suchen, um zu sehen, ob sie sich möglicherweise schneiden KÖNNEN, können Sie einen AABB erstellen, der den AABB von Objekt A sowohl an der Start- als auch an der Endposition umgibt. Wenn sich ein AABB nicht mit diesem alles umfassenden AABB überschneidet, dann gibt es keine Überschneidung; Dies kann jedoch zu Fehlalarmen führen. Daher sollten Sie diesen Test nur als vorläufigen Test verwenden.

Sie benötigen keine OOBs und benötigen keine zeitversetzte Kollisionserkennung. Verwenden Sie einfach den normalen AABB-Wobbeltest, siehe diesen Link . Im Wesentlichen macht es genau das, was Sie in Ihrem Diagramm haben: Der sich bewegende AABB wird vom Startpunkt zum Endpunkt "gewobbelt" und dann zur Kollisionserkennung gegen andere, statische AABBs verwendet.

Wenn Sie befürchten, dass dieser Fegtest teurer ist, weil er eine "Aufprallzeit" ergibt, denken Sie, dass Sie vorzeitig optimieren.

Ausführlichere Informationen zu Wobbeltests finden Sie in dem hervorragenden Buch: Echtzeit-Kollisionserkennung von Christer Ericson.

Sie müssen zuerst die Bewegung in kleinere Schritte zerlegen und diese Informationen zur Berechnung eines AABB auf hoher Ebene verwenden. Wenn sich die großen AABBs überschneiden, können Sie die kleineren Schritte überprüfen, um eine genauere Darstellung zu erhalten.

Das Abschätzen, ob möglicherweise eine Kollision aufgetreten ist oder nicht, indem AABB (oder OOBB) nur anhand der Start- und Endposition überprüft wird, kann zu Kollisionen führen, wenn sich eines der Objekte schnell dreht und in einer Dimension länger ist als in einer anderen.

Um einen genaueren Schätzwert für AABB zu berechnen, zerlegen Sie die Bewegung in kleinere Schritte und drehen Sie den AABB (jetzt nur ein Kästchen, nicht achsenausgerichtet), während sich das Objekt dreht und bewegt Schritt. Die Max- und Min-Punkte für jede Achse geben den AABB an, der die gesamte Bewegung des Objekts einschließt.

Wenn es einen Schnittpunkt mit dem größeren AABB gibt, können Sie die kleineren AABBs verwenden, die bereits berechnet wurden, um zu bestimmen, wo die Kollision möglicherweise stattgefunden hat. Für jedes der kleineren AABBs, die sich mit dem anderen Objekt schneiden, können Sie dann die teurere Netzschnittpunkterkennung durchführen.

Sie müssen die Bewegung in kleinere Bewegungsschritte zerlegen. Beispielsweise:

Sie möchten die Bewegung mit den größeren Komponenten (in diesem Fall der X-Achse) zerlegen und dann in jedem Schritt auf Kollision prüfen.

Dies mag zu teuer aussehen, aber bedenken Sie, dass ein Objekt, das sich in jedem Zyklus schneller als mit seiner eigenen Breite bewegt, EXTREM schnell ist, sodass dieses Szenario nicht so häufig ist, wie Sie vielleicht zuerst denken.

Sie sollten auch relative Geschwindigkeiten für die Kollisionsprüfung verwenden, damit ein AABB "statisch" ist und der andere mit einer Geschwindigkeit von seiner eigenen Geschwindigkeit minus der Geschwindigkeit des "statischen" fährt.

Der schnellste Weg, um zu sehen, ob sie können kreuzen, besteht darin, das sich bewegende AABB mit der Geschwindigkeit zu erweitern.

Zum Beispiel bewegt sich der AABB mit 0,1 x / Frame nach rechts, dann verlängern Sie ihn so, dass die linke Kante dieselbe bleibt und die rechte Kante 0,1 weiter ist. Dann können Sie mit dem neuen AABB überprüfen. Wenn false, liegt keine Kollision vor. (frühe Rückkehr und genau für kleine Geschwindigkeiten).

Dann können Sie prüfen, ob sich das Ende und das Start-AABB des sich bewegenden Objekts überschneiden. Wenn true, dann gib true zurück.

Andernfalls müssen Sie prüfen, ob die Diagonale die statische ABB schneidet.

Dabei werden die Koordinaten der Diagonale ermittelt, wobei x = linker Rand der statischen und rechter Rand, um festzustellen, ob sich das y im unteren und oberen Bereich befindet. (Umgekehrt wiederholen)