OBB gegen OBB-Kollisionserkennung

20

Angenommen, Sie haben zwei Begrenzungsrahmenobjekte, von denen jedes die aktuellen Eckpunkte des Rahmens in einem Vektor speichert, wobei alle Eckpunkte des Objekts relativ zu einer gemeinsamen Achse gedreht und verschoben werden.

Hier ist ein Bild, um mein Problem zu veranschaulichen:

Wie kann ich herausfinden, ob die beiden OBBs Links überlappen, um die Lösung des Problems zu erläutern? Nichts zu verworren bitte ...

Joshua Barnett
quelle

Antworten:

16

Ein OBB ist eine konvexe Hülle. Ein konvexer Rumpf ist eine 3D-Form, die auf ihrer Oberfläche keine "Unebenheiten" aufweist. Jede "Erhebung" (Vertex) auf dem konvexen Rumpf ragt nach außen , niemals nach innen. Wenn Sie eine Ebene durch eine konvexe Hülle schneiden, erhalten Sie (nur ein) konvexes Polygon. Wenn Sie sich in einer konvexen Hülle befinden und einen nach außen gerichteten Laser abfeuern, können Sie die Oberfläche der Hülle nur einmal (niemals zweimal) durchstoßen .

Der Separating Axis Theorem Test kann verwendet werden, um Kollisionen von konvexen Hüllen zu erkennen. Der SAT-Test ist einfach. Es funktioniert in 2D und 3D. Obwohl die Bilder unten in 2D vorliegen, können sie genauso gut in 3D angewendet werden.

Konzept

Dies ist das Schlüsselkonzept, das Sie mit SAT verwenden:

  • Zwei Formen kreuzen sich nur, wenn sie sich überlappen, wenn sie auf jede normale Achse beider Formen "projiziert" werden .

Die "Projektion" einer Form auf einen 1D-Vektor sieht so aus (was ich "Quetschen" nenne)

Eine Form mit roten Ecken und einer Achse

Bildbeschreibung hier eingeben

"Projizieren der Form auf die Achse" bedeutet, dass von jedem Punkt der Form eine Senkrechte abgesetzt wird, um auf der Achse zu landen. Sie können sich das so vorstellen, als würden Sie die Punkte mit einer Hand "zerquetschen", die alles sammelt und senkrecht zur Achse zerquetscht.

Bildbeschreibung hier eingeben

Was Ihnen noch bleibt: Punkte auf einer Achse

Bildbeschreibung hier eingeben

SAT sagt:

Damit sich zwei konvexe Rümpfe schneiden, müssen sie sich auf jeder Achse überlappen (wobei jede Normale auf einer der beiden Formen als zu überprüfende Achse gilt).

Nimm diese 2 Formen:

Bildbeschreibung hier eingeben

Sie sehen , dass sie sich nicht schneiden, kann so versuchen , ein paar Achsen zu zeigen wurde eine Überlappung nicht passieren.

Versuch der oberen Normalen des Fünfecks:

Bildbeschreibung hier eingeben

Das sind die Ausmaße. Sie überschneiden sich.

Bildbeschreibung hier eingeben

Versuchen Sie es mit der linken Seite des Rechtecks. Jetzt überlappen sie sich in dieser Achse nicht, daher KEINE SCHNITTSTELLE.

Bildbeschreibung hier eingeben

Algorithmus:

Für jedes Gesicht normal auf beiden Formen:

  • Ermitteln Sie die minimale und maximale Ausdehnung (größter und kleinster Wert) der Projektion aller Eckpunkte beider Formen auf diese Achse
  • Wenn sie sich nicht überlappen, keine Kreuzung .

Und das war's auch schon. Der Code, mit dem SAT funktioniert, ist sehr kurz und einfach.

Hier ist ein Code, der demonstriert, wie eine SAT-Achsenprojektion durchgeführt wird:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Vorwahl:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}
Bobobobo
quelle
Hullinator implementiert den SAT-Test für konvexe Hüllen
Bobobobo
tolle Erklärung! Vielen Dank. Ich denke , dass Sie einen Tippfehler in der Leitung haben: „kann so versuchen , ein paar Achsen zu zeigen waren eine Überlappung nicht passiert.“, Denn dann gehen Sie Beispiele zu geben , wo sie tun überlappen. Danke noch einmal!
Müssen Sie die Tests nicht auch für alle Querprodukte der Normalen durchführen? Dies sagt der Artikel geometrictools.com/Documentation/DynamicCollisionDetection.pdf .
iNFINITEi
Es ist erwähnenswert, dass diese spezielle SAT-Methode nur in 2D funktioniert. In 3D müssen Sie mehr als nur die Normalen jedes Gesichts erhalten. Sobald Sie die richtigen Normalen haben, ist der Rest des Prozesses (Projekt, Vergleich) genau der gleiche.
Fund Monica Klage
Es ist wirklich schwierig, anhand Ihrer 2D-Bilder zu erkennen, in welche Richtung die Pfeile zeigen.
WDUK
7

Sie sollten auf jeden Fall den Satz der Trennachsen nachschlagen . Es ist für konvexe Objekte. Es gibt eine Regel: "Wenn sich zwei konvexe Objekte nicht schneiden, gibt es eine Ebene, in der sich die Projektion dieser beiden Objekte nicht schneidet."

Sie finden einige Beispiele im Wiki . Aber es ist etwas komplizierter als für Ihren Fall.

Etwas passenderes für Ihr Problem finden Sie hier (zwei Autos kollidieren).

Zacharmarz
quelle
1

Weitere SAT- Artikel.

Der letzte Artikel auf dieser Seite enthält vollständigen Code, ich glaube, er ist in FLASH, ich habe keine Ahnung, aber ich hatte genau 0 Probleme, als ich SAT zum ersten Mal verwenden musste, sollte es nicht schwer sein, ihn in C ++ umzuwandeln Machen Sie dasselbe für andere Sprachen. Das Einzige, was Sie hinzufügen müssen, ist das Speichern des Verschiebungsvektors bei jeder Berechnung (wenn es natürlich der kleinste ist, werden Sie dies verstehen, wenn Sie mehr über SAT erfahren), der Code in diesem Tutorial tut dies also nicht Sie erhalten den zuletzt berechneten Vektor.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Gute, alte N-Game-Tutorials. Beste SAT-Theorie im Web.

http://www.metanetsoftware.com/technique/tutorialA.html

dreta
quelle
Es ist so irritierend, dass niemand die voll funktionsfähige Quelle mit allen erforderlichen Klassen veröffentlicht. Ich habe seinen Code in eine eigene Demo portiert, aber es funktioniert einfach nicht. :( Dies ist mein bisheriges Projekt, wenn mir jemand beim Debuggen helfen könnte, wäre das großartig. Link
Joshua Barnett
Was meinst du damit, dass es nicht funktioniert? Achten Sie darauf, wie Sie Ihre Scheitelpunkte speichern. Im Bild haben Sie sie in einem kartesischen Koordinatensystem. Im Tutorial speichert er die Scheitelpunkte als Vektoren relativ zum Schwerpunkt (Sie müssen lediglich den Schwerpunkt von Ihren eigenen Scheitelpunkten subtrahieren oder Entfernen Sie die Linien, in denen er seine eigenen Eckpunkte modifiziert.) Funktionen wie das Skalarprodukt, das Sie selbst erstellen können. Sie benötigen keine Anleitung für diese Funktionen. Der Rest sollte einfach sein. Es ist kein Material zum Kopieren und Einfügen. Lernen Sie SAT, bevor Sie versuchen, es zu implementieren
Dreta
So habe ich es implementiert: SAT.as , Shape2D.as , Was meinst du mit Zentroid? Die Mitte des Polygons wie (x, y)?
Joshua Barnett
Im Moment habe ich eine Funktion getOBB (), die Scheitelpunkte zurückgibt, wie in meinem Originalbild beschrieben. Dies wird aus dem Vektor <b2Vec2> berechnet, der die Eckpunkte der Form, eine Winkelvariable und eine Positionsvariable enthält.
Joshua Barnett
ja, die Mitte, der Typ erstellt seine Polygone durch Abgeben von Offsets von der Mitte, idk AS3, aber von dem, was ich sehe, projizieren Sie Ihre Scheitelpunkte so, wie sie sind ), außerdem prüfen Sie nicht, welcher Trennungsvektor der kleinste ist,
sondern