Wie löse ich Kollisionen von zusammengesetzten Formen mit SAT?

16

SAT ist eine gute Möglichkeit, Kollisionen zwischen beliebigen konvexen Polygonen zu bestimmen. Sie erhalten sogar den Vektor, der zum Auflösen einer Kollision benötigt wird.

Um Kollisionen zwischen komplexen (nicht konvexen) Formen aufzulösen, dachte ich an eine Art zusammengesetzte Form, die aus mehreren konvexen Polygonen besteht. Wenn eine Kollision in der breiten Phase auftritt (z. B. Kreis gegen Kreis oder AABB gegen AABB), würde die Kollision durch Überprüfen jedes Polygons in der zusammengesetzten Form gegen jedes Polygon in der anderen zusammengesetzten Form gelöst.

Ich frage mich, wie ich die Objekte am besten trennen kann. Ein naiver Ansatz wäre, einfach den Vektor mit der höchsten Größe zu nehmen und diesen zur Trennung zu verwenden. Im folgenden Bild wäre dies V 2

SAT Beispiel 1

Wenn die Trennvektoren jedoch in verschiedene Richtungen zeigen, kann die Kollision nicht sofort aufgelöst werden und erfordert möglicherweise mehrere Iterationen. Im nächsten Bild trennen wir also mit V 1 und in einer anderen Iteration mit V 2 (oder etwas in der Nähe von V 2 , da sich die Form um den Betrag von V 1 bewegt hätte ).

SAT Beispiel 2

Dieser Ansatz schlägt fehl, wenn Vektoren getrennt werden, die in die entgegengesetzte Richtung zeigen, oder in einem Fall, wie in der folgenden Abbildung dargestellt:

SAT Beispiel 3

Hier würden wir endlos zwischen dem Staat auf der linken und dem Staat auf der rechten Seite iterieren.

Um hier also eine tatsächliche Frage zu stellen: Was ist eine vernünftige Herangehensweise an dieses Problem? Ich denke, es ist eine vernünftige Idee, zusammengesetzte Polygone für komplexe Formen zu verwenden, aber ich frage mich wirklich, wie Kollisionen in diesem Fall gelöst werden sollten. Wie erkenne ich eine Sackgasse, wie im dritten Bild gezeigt?

Blödmann
quelle
Können Sie klarstellen, wofür Sie den Vektor verwenden möchten?
Wird
@Will Der Vektor sollte verwendet werden, um die Kollision aufzulösen, damit sich die Formen nicht mehr überlappen. So konnte ich das gelbe Objekt um den resultierenden Vektor verschieben und die beiden Objekte würden nicht mehr kollidieren.
Bummzack

Antworten:

7

Ich glaube, Sie versuchen vielleicht, einen Vierkantschlüssel in ein rundes Loch zu stecken, indem Sie SAT so anwenden, wie Sie es sind. Es ist offensichtlich nicht für Konkav-Konkav-Kollisionen ausgelegt, und obwohl ich Ihre Bemühungen lobe, es für diesen Zweck anzupassen, gibt es Überlegungen, die es unwahrscheinlich machen, dass dies funktioniert.

Realismus

Winkelimpulse und deren Anstoßeffekte sind hier das A und O.

Die Reihenfolge der Kontaktpunkte ist wichtig für eine realistische Kollisionsauflösung. In der realen Welt wird immer einer dieser Punkte vor dem anderen auffallen. Und nur wenn Sie diese Kontaktreihenfolge und die Ergebnisse jeder "Unterkollision", die dadurch dargestellt wird, emulieren, können Sie erwarten, dass Sie in der Simulation ein realistisches Ergebnis erzielen. Dies ist einer der Gründe, warum Sie Ihre Konkavität zunächst in eine konvexe zerlegen - es ermöglicht die stückweise Erkennung, welcher Teil zuerst geschlagen hat. Natürlich kann dies auch nach meinem Kommentar unter der Überschrift "Weniger Realismus" emuliert werden.

Ihre konvexen Fixtures bilden zusammen den Umriss und den Schwerpunkt des Objekts (und in komplexeren Simulationen kann jedes Fixture auch die Dichte unterschiedlich beeinflussen). Der Grund, warum ich dies erwähne, ist, dass Sie bei der realistischen Auflösung von Kollisionen nicht nur den linearen, sondern auch den Winkelimpuls berechnen müssen, der jeder "Unterkollision" Ihrer Kontaktpunkte folgt. Es ist nicht so einfach wie das grundlegende "Auseinanderdrücken", das Sie mit SAT anwenden.

Dies ändert sich dann vollständig die Art des Problems, denn wie Sie sehen können, ist es sinnlos ist immer und zu versuchen , zu verwenden , 2 oder mehr Kontaktstellen, weil es wirklich nur das erste, was zählt ist. Nachdem Sie den ersten Impuls in Bezug auf den linearen und den Winkelimpuls aufgelöst haben, müssen Sie ihn für weitere Kollisionen neu berechnen, da sich die Ausrichtungen der einzelnen Objekte geändert haben. Darüber hinaus muss die Erkennung jedes einzelnen Kontakts in diesem Schritt möglicherweise innerhalb desselben Schritts erfolgen oder auch nicht - je nach dem Zeitpunkt zwischen den Kontakten, zu dem sich der erste Kontaktpunkt des Objekts berührt, wird ein nachfolgender linearer und winkliger Impuls angelegt, und dann Kontaktpunkt berührt, und so weiter.

Weniger Realismus

Vorausgesetzt, Sie sind überhaupt nicht an der Auflösung von Winkelimpulsen interessiert, wird das Beste, was Sie mit SAT tun können, im Wesentlichen genau zu dem, was Sie tun würden, wenn Sie diese Polygone mit etwas wie Graham's Scan als konvex verpacken: Durch die einfache Trennung auseinander drücken Vektor. Mit anderen Worten, es macht wenig Sinn, drei Vektoren hintereinander aufzulösen, wie Sie gezeigt haben. Es ist das größte im ganzen Haufen, das zählt.

BEARBEITEN als Antwort auf Ihre Frage

Was Sie tun müssen, wenn Sie einen vereinfachenden Ansatz wünschen, ist wie folgt:

  • Bestimmen Sie die korrekte Richtung der Verschiebung. Dies geschieht am einfachsten durch konvexes Hüllen und Bestimmen der Normalen zur Trennachse.

  • Nun müssen Sie die Verschiebung bestimmen Größe . Warum können wir nicht einfach die von SAT angegebene Größe verwenden? Denn wenn Sie darüber nachdenken, werden die Eindringtiefen für konvexe Hüllen möglicherweise größer sein als für ihre passenden konkaven Hüllen - denken Sie an zwei E, die ihre Zähne ineinander haben! Finden Sie wie oben beschrieben alle Kontaktpunkte für einen bestimmten Schritt, aber finden Sie sie parallel zu den Achsennormalen, da dies die richtige Verschiebungsrichtung ist. Bestimmen Sie nun, welcher dieser parallelen Überlappungsvektoren am längsten ist. Verschiebe es durch dieses, verwerfe den Rest und fahre mit dem nächsten Physikschritt fort.

Ingenieur
quelle
Ich glaube ich verstehe was du meinst. Im Szenario "weniger realistisch" würde ich also nicht nur die (kürzesten) von SAT angegebenen Vektoren für die einzelnen Polygone auswerten, sondern müsste auch die anderen (größeren) Überlappungen berücksichtigen und im schlimmsten Fall die konvexe Hülle verwenden?
Bummzack
Siehe (neueste) Bearbeitung.
Ingenieur