Warum durchdringen Objekte in diesem einfachen Kollisionslöser?

7

Der folgende Code stammt aus einem Microsoft XNA-Beispiel hier . Dies ist eine recht einfache Starrkörpersimulation, bei der viele physikalische Effekte (z. B. Drehimpuls) ignoriert werden. Es wird jedoch versucht, Objekte (Kugeln) auseinander zu drücken, damit sie sich nicht gegenseitig durchdringen.

Die Simulation ermöglicht jedoch nicht nur das Eindringen von Kugeln, sondern wenn viele Kugeln übereinander gestapelt sind, können sich kleine Kugeln fast vollständig in größeren Kugeln befinden. Wenn ich dafür sorge, dass alle Kugeln den gleichen Radius und die gleiche Masse haben, funktioniert die Simulation recht gut (mit minimaler Durchdringung).

Kann jemand erklären, warum es überhaupt eine gegenseitige Durchdringung gibt? Da es die Positionen der Kugeln bewegt, scheint es, dass eine gegenseitige Durchdringung unmöglich sein sollte.

Für jede Kugel in der Simulation wird diese Methode für jede andere Kugel aufgerufen.

/// <summary>
// Given 2 spheres with velocity, mass and size, evaluate whether
// a collision occured, and if so, excatly where, and move sphere 2
// at the contact point with sphere 1, and generate new velocities.
/// </summary>
private void SphereCollisionImplicit(Sphere sphere1, Sphere sphere2)
{
    const float K_ELASTIC = 0.75f;

    Vector3 relativepos = sphere2.Position - sphere1.Position;
    float distance = relativepos.Length();
    float radii = sphere1.Radius + sphere2.Radius;
    if (distance >= radii)
    {
        return; // No collision
    }

    // Add epsilon to avoid NaN.
    distance += 0.000001f;

    Vector3 relativeUnit = relativepos * (1.0f / distance);
    Vector3 penetration = relativeUnit * (radii - distance);

    // Adjust the spheres' relative positions
    float mass1 = sphere1.Mass;
    float mass2 = sphere2.Mass;

    float m_inv = 1.0f / (mass1 + mass2);
    float weight1 = mass1 * m_inv; // relative weight of sphere 1
    float weight2 = mass2 * m_inv; // relative weight of sphere 2. w1+w2==1.0

    sphere1.Position -= weight2 * penetration;
    sphere2.Position += weight1 * penetration;

    // Adjust the objects’ relative velocities, if they are
    // moving toward each other.
    //
    // Note that we're assuming no friction, or equivalently, no angular momentum.
    //
    // velocityTotal = velocity of v2 in v1 stationary ref. frame
    // get reference frame of common center of mass
    Vector3 velocity1 = sphere1.Velocity;
    Vector3 velocity2 = sphere2.Velocity;

    Vector3 velocityTotal = velocity1 * weight1 + velocity2 * weight2;
    Vector3 i2 = (velocity2 - velocityTotal) * mass2;
    if (Vector3.Dot(i2, relativeUnit) < 0)
    {
        // i1+i2 == 0, approx
        Vector3 di = Vector3.Dot(i2, relativeUnit) * relativeUnit;
        i2 -= di * (K_ELASTIC + 1);
        sphere1.Velocity = (-i2) / mass1 + velocityTotal;
        sphere2.Velocity = i2 / mass2 + velocityTotal;
    }
}

Insbesondere denke ich, dass dies:

sphere1.Position -= weight2 * penetration;
sphere2.Position += weight1 * penetration;

Sollte eine gegenseitige Durchdringung völlig verboten sein, warum nicht?

Olhovsky
quelle

Antworten:

5

Ich denke, Ihr Problem kommt von mehreren Kollisionen.

Betrachten Sie drei Bereiche A, B und C.

A sitzt da.

B trifft A. Gut.

C trifft B. B wird in A gestoßen. Ups.

Loren Pechtel
quelle
Ja, aber jetzt korrigiert C seine Position sowohl gegen A als auch gegen B. Ich verstehe, was Sie meinen, aber die Beispiele, die ich mit 3 Kugeln ausgearbeitet habe, scheinen zu funktionieren - also bin ich mir nicht sicher, ob das wirklich das Problem ist. Ich glaube auch, dass diese iterative Methode genau das ist, wie die meisten spielphysikalischen Simulationen Kollisionen auflösen. Auch hier könnte ich mich irren, ich bin mir nicht sicher. Möglicherweise verhindert das Lösen von Kollisionen nacheinander auf diese Weise nur dann die gegenseitige Durchdringung, wenn Sie die kontinuierliche Kollisionserkennung verwenden.
Olhovsky
Dies kann tatsächlich genau der Grund sein. Brandon schlug etwas Ähnliches vor. +1 für den nützlichen Beitrag, ob es sich um den genauen Grund handelt oder nicht.
Olhovsky
5

Dieser Code nimmt die Kollision zwischen zwei Kugeln und bewegt sie basierend auf ihrer Masse und Geschwindigkeit.

Hier ist eine wirklich einfache Illustration, um zu zeigen, warum zwischen einer blauen Kugel und einer grünen Wand eine Penetration besteht.

Geben Sie hier die Bildbeschreibung ein

In diesem Beispiel befindet sich die Mitte des Balls 5 Fuß vom Rand der Wand entfernt. Der Ball bewegt sich mit 1 Fuß pro Sekunde und Sie laufen mit einer Bildrate von 1 Bild pro Sekunde. Bei Frame 4 gibt es keine Penetration, aber Frame 5 hat Penetration. Es gibt keine Möglichkeit zu wissen, dass Frame 5 kollidiert. Sie können also nicht einfach Stopp sagen, wenn es an der Wand ankommt. Stattdessen überprüfen Sie jeden Rahmen, ob sich der Ball teilweise in der Wand befindet. Wenn dies der Fall ist, bewegen Sie es um das Ausmaß der Penetration zurück und wenden Sie die Reflexionsgeschwindigkeit an. So funktionieren die meisten Kollisionserkennungsalgorithmen. Die Alternative besteht darin, jedes Bild zu überprüfen, wie weit Sie von einer Kollision in eine bestimmte Richtung entfernt sind. Das Problem dabei ist, dass Sie wissen müssen, in welche Richtung Sie prüfen müssen. Dies würde in Ihrer Situation nicht funktionieren, daher ist die Route, die Sie nehmen, die richtige.

Der Nachteil dieses Ansatzes ist die Nervosität, die Sie wahrscheinlich erleben. Wenn dieses Skript einem Ball sagt, dass er sich basierend auf der letzten Kollision bewegen soll, bewegt er sich möglicherweise, um in einen anderen Ball einzudringen, wodurch der Ball zurückgeschickt wird, um mit dem ersten zu kollidieren. Lass es hin und her springen. Sie können die Masse der Objekte ändern, um dies zu unterstützen. Dadurch springen sie etwas weniger drastisch zurück oder verringern die Geschwindigkeit, mit der sie überhaupt kollidieren.

Brandon
quelle
Eigentlich ist das Problem nicht die "Jitteryness" (die Instabilität). Ich bin mit der Instabilität einverstanden und kann dies später mit einer Entfernungskorrekturschwelle auf Kosten der Genauigkeit korrigieren. Das Problem, das ich habe (na ja, und das Microsoft hat, da es der Code ist), ist, dass die gegenseitige Durchdringung nicht gelöst wird. Das heißt, es ist nicht nur nervös, sondern es gibt auch viel gegenseitige Durchdringung, obwohl der Code die Penetration zu lösen scheint. Irgendeine Idee warum das so ist? Habe ich etwas in deiner Antwort verpasst? Danke übrigens für die Eingabe!
Olhovsky
Oh, ich denke, Sie sagen, dass mehrere Kollisionen nicht richtig aufgelöst werden, weil mehrere Bälle aus einander herausgeschoben werden, ähnlich wie bei Loren - stimmt das?
Olhovsky
Richtig, das ist die Nervosität, die auch dazu führt, dass sie nicht richtig kollidieren
brandon
Nicht wirklich. Instabilität! = Durchdringung. Objekte können (aufgrund der Penetrationsauflösung) zittern, ohne sich gegenseitig zu durchdringen. Sowieso +1 :)
Olhovsky
5

Sie sollten sich über spekulative Kontakte informieren, um zu erfahren, wann Kollisionen auftreten, bevor Sie diese Art von Penetration erreichen.

Jason Roelofs
quelle
+1 für diesen guten Link. Eigentlich habe ich gestern wegen dieses Artikels eine Mitgliedschaft in Pauls Blog gekauft.
Olhovsky
1

SphereCollisionImplicit () wird aufgerufen, nachdem sich die Kugeln bewegt haben. Diese Bewegung hätte mit Kollision und Durchdringung enden können, diese Methode löst das.

Startrahmen:

  1. An anderer Stelle in Ihrem Code wird die Position durch die Geschwindigkeit aktualisiert.

  2. Dann wird diese Methode aufgerufen, um festzustellen, ob dies zu einer Kollision / Penetration geführt hat.

  3. Wenn ja, trennt es sie und reflektiert / ändert ihre Geschwindigkeiten.

  4. Im nächsten Frame werden die Positionen mit neuer / geänderter Geschwindigkeit aktualisiert ... gehe zu 1.

Steve H.
quelle
Ich verstehe nicht, was du sagen willst. Derzeit macht es in diesem XNA-Beispiel genau das, was Ihre Aufzählungszeichen sagen, und das Zeichnen der Kugeln erfolgt direkt nach Schritt 3. Warum gibt es also immer noch eine gegenseitige Durchdringung? Wie Sie sagten, erwarten wir, dass Schritt 3 sie trennt.
Olhovsky
Schritt 1 und 4 können ein Eindringen verursachen. Schritt 3 entfernt das Eindringen, falls es aufgetreten ist.
Steve H
Der Punkt dieser Frage ist, dass die Penetration nicht vollständig entfernt wird. Siehe andere Antworten, warum das so ist.
Olhovsky
1

Es gibt eine gegenseitige Durchdringung, da jedes Mal, wenn die Position und Geschwindigkeit eines Balls geändert wird, überprüft werden muss, ob er mit einem anderen Ball kollidiert ist, der zuvor in der Schleife überprüft wurde. Zum Beispiel bei 3 Bällen:

Start 1. Ball #A wird gegen Ball #B geprüft, keine Kollision

  1. Ball #A wird gegen Ball #C geprüft, keine Kollision

  2. Ball #B wird gegen Ball #A geprüft, keine Kollision

  3. Ball #B wird gegen Ball #C geprüft, Kollision gefunden !! Ball #B und #C werden bewegt.

  4. Ball #C wird gegen Ball #A geprüft, keine Kollision

  5. Ball #C wird gegen Ball #B geprüft, keine Kollision

Erledigt

Also ... Schritt 2 hat möglicherweise Ball #B in Ball #A verschoben, was zu einer gegenseitigen Durchdringung geführt hat.

Ich denke, wenn ein Ball bewegt wird, muss er gegen alle anderen Bälle überprüft werden, wenn er bewegt wird. In diesem Szenario stößt Ball #B auf Ball #C, Richocheting Ball #B auf Ball #A, Richocheting Ball #A auf Ball #C!, Was Ball #B erneut trifft ....

Wie viele Richochets verarbeiten Sie in einem Frame? Müssen Sie auch nach jedem Richochet erneut alle Wände überprüfen?

Start 1. Ball #A wird gegen Ball #B geprüft, keine Kollision

  1. Ball #A wird gegen Ball #C geprüft, keine Kollision

  2. Ball #B wird gegen Ball #A geprüft, keine Kollision

  3. Ball #B wird gegen Ball #C geprüft, Kollision gefunden !! Ball #B und #C werden bewegt.

  4. Starten Sie die Schleife #B und #C neu ...

  5. Ball #B wird gegen Ball #A geprüft, Kollision gefunden !! Ball #B und #A werden bewegt

  6. Starten Sie die Schleife #B und #A neu ...

  7. Ball #A wird gegen Ball #B geprüft, keine Kollision

  8. Ball #A wird gegen Ball #C geprüft, Kollision gefunden !! Ball #A und #C werden bewegt

  9. Starten Sie die Schleife #A und #C neu

  10. Ball #A wird gegen Ball #B geprüft, keine Kollision

  11. Ball #A wird gegen Ball #C geprüft, keine Kollision

  12. Ball #B wird gegen Ball #A geprüft, keine Kollision

  13. Ball #B wird gegen Ball #C geprüft, Kollision gefunden !! Ball #B und #C werden bewegt

  14. Starten Sie die Schleife #B und #C neu

  15. Ball #B wird gegen Ball #A geprüft, keine Kollision

  16. Ball #B wird gegen Ball #C geprüft, keine Kollision

  17. Ball #C wird gegen Ball #A geprüft, keine Kollision

  18. Ball #C wird gegen Ball #B geprüft, keine Kollision erfolgt

fuul
quelle
Eigentlich ist es das nicht. Kollisionen werden gegen alle anderen Bälle geprüft, das Problem liegt in der Reihenfolge der Schecks (wie in der Antwort mit dem grünen Häkchen angegeben :). Das Prüfen gegen alle anderen Bälle allein reicht nicht aus.
Olhovsky