Kollisionserkennung zwischen Accelerating Spheres

Question

Ich bin ein Physik-Engine/Simulator zu schreiben, die 3D-Raumflug, Planeten-/Stern Gravitation, Schiff Schub- und relativistische Effekte beinhaltet. Bisher geht es sehr gut, aber eine Sache, die ich brauche Hilfe bei der Mathematik der Kollisionserkennung algorithmus.

Die iterative Simulation von Bewegung, die ich im Grunde bin mit wie folgt:

. (Anmerkung: 3D-Vektoren sind alle CAPS)

For each obj 

    obj.ACC = Sum(all acceleration influences) 

    obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2  (*EQ.2*) 

    obj.VEL = obj.VEL + (obj.ACC * dT) 

Next 

Wo:

obj.ACC is the acceleration vector of the object 
obj.POS is the position or location vector of the object 
obj.VEL is the velocity vector of the object 

obj.Radius is the radius (scalar) of the object 

dT is the time delta or increment 

Was ich im Grunde tun müssen, ist eine effiziente Formel finden, die für zwei Objekte aus (EQ.2) oben leitet (obj1, obj2) und sagen, ob sie jemals kollidieren, ein Und wenn ja, zu welcher Zeit. Ich brauche die genaue Zeit so beide, dass ich feststellen kann, ob es in diesem Zeitschritt ist (weil accelleratons zu verschiedenen Zeitschritten anders sein wird) und so auch, dass ich die genaue Position finden kann (was ich weiß, wie zu tun, angesichts der Zeit)

Für diesen Motor, ich alle Objekte als Kugeln bin Modellierung, all diese Formel/algortithim braucht, ist zu tun, um herauszufinden, welche Punkte:

(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius) 

wo .Distance einen positiven Skalar ist. (Sie können auch beide Seiten quadrieren, wenn dies einfacher ist, um die in der .Distance-Berechnung implizite Quadratwurzelfunktion zu vermeiden).

(Ja, mir sind viele, viele andere Kollisionsdetektionsfragen bekannt, jedoch scheinen ihre Lösungen für ihren Motor und ihre Annahmen sehr spezifisch zu sein, und keiner scheint meinen Bedingungen zu entsprechen: 3D, Kugeln und Beschleunigung . innerhalb der Simulation Schritten Lassen Sie mich wissen, wenn ich falsch bin)

---

einige Klärungen.

1) Es genügt nicht, für mich für * Überschneidung * der beiden Sphären zu prüfen, vor und nach dem Zeitinkrement. In vielen Fällen werden ihre Geschwindigkeiten und Positionsänderungen ihre Radien weit überschreiten.

2) RE: Effizienz, ich brauche keine Hilfe (an dieser Stelle sowieso) in Bezug wahrscheinliche Kandidaten für Kollisionen zu bestimmen, denke ich, dass ich die überdachten habe.

---

Eine weitere Klärung, die viel kommen zu sein scheint:

3) Meine Gleichung (EQ.2) inkrementeller Bewegung ist eine quadratische Gleichung, die sowohl Geschwindigkeit und Beschleunigung gilt:

obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 

den Physik-Engines, die ich gesehen habe (und sicherlich jeden Spiel-Engine, die ich je gehört habe) nur lineare Gleichungen der inkrementellen Bewegung, die nur Geschwindigkeit gelten:

obj.POS = obj.POS + (obj.VEL * dT) 

dieser Grund habe ich nicht die allgemein veröffentlichten Lösungen zur Kollisionserkennung auf dem Stack gefunden verwenden kann Überlauf, auf Wikipedia und im gesamten Web, z. B. zum Auffinden der Kreuzung/engsten Annäherung von zwei Liniensegmenten. Meine Simulation beschäftigt sich mit variablen Beschleunigungen, die für die Ergebnisse von grundlegender Bedeutung sind. Was ich also brauche, ist die Kreuzung/engste Annäherung von zwei parabolischen Segmenten.

Answer 1

Auf der Webseite, auf die sich Ashelley bezieht, wird die Methode des nächsten Annäherungspunktes für den Fall entwickelt, dass sich zwei Objekte mit konstanter Geschwindigkeit bewegen. Ich glaube jedoch, dass die gleiche Vektor-Kalkül-Methode verwendet werden kann, um ein Ergebnis im Fall von zwei Objekten abzuleiten, die sich beide mit einer konstanten Nicht-Null-Beschleunigung bewegen (quadratische Zeitabhängigkeit).

In diesem Fall ist die zeitliche Ableitung der Abstandsquadratfunktion 3. Ordnung (kubisch) statt 1. Ordnung. Daher gibt es 3 Lösungen für die Zeit der engsten Annäherung, was nicht überraschend ist, da der Weg beider Objekte gekrümmt ist, so dass mehrere Schnittpunkte möglich sind. Für diese Anwendung möchten Sie wahrscheinlich den frühesten Wert von t verwenden, der innerhalb des vom aktuellen Simulationsschritt definierten Intervalls liegt (falls eine solche Zeit existiert).

arbeitete ich die Ableitung der Gleichung aus, die die Zeiten der nächsten Annäherung geben sollte:

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

wo:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (vor Update)

D_POS = ob1.POS-obj2.POS (auch vor dem Update)

und dot(A, B) = A.x*B.x + A.y*B.y + A.z*B.z

(Beachten Sie, dass das Quadrat der Größe |A|^2dot(A, A) mit berechnet werden kann)

dies für t lösen, müssen Sie wahrscheinlich Formeln wie die, die verwenden found on Wikipedia.

Natürlich gibt dies nur den Moment nächsten Ansatz. Sie müssen die Entfernung in diesem Moment testen (mit etwas wie Gl. 2). Wenn es größer als (obj1.Radius + obj2.Radius) ist, kann es ignoriert werden (d. H. Keine Kollision). Wenn die Entfernung jedoch geringer ist, kollidieren die Sphären vor diesem Moment. Sie könnten dann eine iterative Suche verwenden, um die Entfernung zu früheren Zeiten zu testen. Es könnte auch möglich sein, eine andere (noch kompliziertere) Herleitung zu finden, die die Größe berücksichtigt, oder eine andere analytische Lösung zu finden, ohne auf iteratives Lösen zurückzugreifen.

bearbeiten: wegen der höheren Ordnung, sind nur einige der Lösungen der Gleichung tatsächlich Momente der am weitesten Trennung. Ich glaube in allen Fällen, dass entweder 1 der 3 Lösungen oder 2 der 3 Lösungen eine Zeit der äußersten Trennung ist. Sie können testen, analytisch, ob Sie bei einer min oder max sind durch die zweite Ableitung bezüglich der Zeit der Bewertung (bei den Werten von t, die Sie durch das Setzen der ersten Ableitung auf Null gefunden):

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

Wenn die zweite Ableitung zu einer positiven Zahl führt, dann wissen Sie, dass die Entfernung für die gegebene Zeit t ein Minimum und kein Maximum ist.

Answer 2

Scheint wie Sie die Closest Point of Approach (CPA) wollen. Wenn es weniger als die Summe der Radien ist, haben Sie eine Kollision. Es gibt Beispielcode in der Verbindung. Sie können jedes Bild mit der aktuellen Geschwindigkeit berechnen und prüfen, ob die CPA-Zeit unter Ihrer Tick-Größe liegt. Sie können die CPA-Zeit sogar zwischenspeichern und nur aktualisieren, wenn die Beschleunigung auf eines der Elemente angewendet wurde.

Answer 3

Zeichnen Sie eine Linie zwischen der Start- und Endposition jeder Kugel. Wenn sich die resultierenden Liniensegmente schneiden, kollidieren die Sphären definitiv irgendwann und eine kluge Mathematik kann herausfinden, zu welcher Zeit die Kollision stattgefunden hat. Überprüfen Sie auch, ob der Mindestabstand zwischen den Segmenten (wenn sie sich nicht schneiden) immer kleiner als 2 * Radius ist. Dies wird auch auf eine Kollision hinweisen.

Von dort können Sie Ihre Delta-Zeit zurücktreten, um genau bei der Kollision zu passieren, damit Sie die Kräfte korrekt berechnen können.

Haben Sie überlegt, eine Physikbibliothek zu verwenden, die diese Aufgabe bereits erfüllt? Viele Bibliotheken verwenden weit fortgeschrittenere und stabilere (bessere Integratoren) Systeme, um die Gleichungssysteme zu lösen, mit denen Sie arbeiten. Bullet Physics kommt in den Sinn.