Ball-zu-Ball-Kollision - Erkennung und Handhabung

266

Mit Hilfe der Stack Overflow-Community habe ich einen ziemlich einfachen, aber unterhaltsamen Physik-Simulator geschrieben.

Alt-Text

Sie klicken und ziehen die Maus, um einen Ball zu starten. Es wird herumspringen und schließlich auf dem "Boden" anhalten.

Mein nächstes großes Feature, das ich hinzufügen möchte, ist die Kollision von Ball zu Ball. Die Bewegung des Balls wird in Axt- und Y-Geschwindigkeitsvektor aufgeteilt. Ich habe Schwerkraft (kleine Reduktion des y-Vektors bei jedem Schritt), ich habe Reibung (kleine Reduktion beider Vektoren bei jeder Kollision mit einer Wand). Die Bälle bewegen sich ehrlich und überraschend realistisch.

Ich denke meine Frage besteht aus zwei Teilen:

  1. Was ist die beste Methode, um eine Kollision von Ball zu Ball zu erkennen?
    Habe ich nur eine O (n ^ 2) -Schleife, die über jeden Ball iteriert und jeden anderen Ball überprüft, um festzustellen, ob sich der Radius überlappt?
  2. Welche Gleichungen verwende ich, um mit Kollisionen von Ball zu Ball umzugehen? Physik 101
    Wie wirkt es sich auf die Geschwindigkeit der x / y-Vektoren der beiden Kugeln aus? In welche Richtung gehen die beiden Bälle? Wie wende ich das auf jeden Ball an?

Alt-Text

Die Handhabung der Kollisionserkennung der "Wände" und der daraus resultierenden Vektoränderungen war einfach, aber ich sehe mehr Komplikationen bei Ball-Ball-Kollisionen. Bei Wänden musste ich einfach das Negativ des entsprechenden x- oder y-Vektors nehmen und es ging in die richtige Richtung. Bei Bällen glaube ich nicht, dass es so ist.

Einige schnelle Klarstellungen: Der Einfachheit halber bin ich mit einer perfekt elastischen Kollision im Moment in Ordnung, auch alle meine Bälle haben momentan die gleiche Masse, aber das könnte ich in Zukunft ändern.


Bearbeiten: Ressourcen, die ich nützlich gefunden habe

2d Ballphysik mit Vektoren: 2-dimensionale Kollisionen ohne Trigonometrie.pdf
Beispiel für die Erkennung von 2d Ballkollisionen: Hinzufügen einer Kollisionserkennung


Erfolg!

Ich habe die Ballkollisionserkennung und -reaktion großartig!

Relevanter Code:

Kollisionserkennung:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

Dies prüft auf Kollisionen zwischen jedem Ball, überspringt jedoch redundante Prüfungen (wenn Sie prüfen müssen, ob Ball 1 mit Ball 2 kollidiert, müssen Sie nicht prüfen, ob Ball 2 mit Ball 1 kollidiert. Außerdem wird die Überprüfung auf Kollisionen mit sich selbst übersprungen ).

Dann habe ich in meiner Ballklasse meine Methoden colliding () und resolveCollision ():

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Quellcode: Vollständige Quelle für Ball-zu-Ball-Collider.

Wenn jemand Vorschläge zur Verbesserung dieses grundlegenden Physiksimulators hat, lass es mich wissen! Eine Sache, die ich noch hinzufügen muss, ist der Drehimpuls, damit die Kugeln realistischer rollen. Irgendwelche anderen Vorschläge? Hinterlasse einen Kommentar!

mmcdole
quelle
16
Ich denke nicht, dass dieser Algorithmus gut genug ist, denn wenn sich Ihre Bälle zu schnell bewegen (z. B. schneller als 2 * Radius pro Frame, kann ein Ball ohne Kollisionen durch einen anderen Ball gehen.
Benji Mizrahi
@ Simulcal Könnten Sie Ihren Quellcode erneut hochladen (alle Links von filesropper.com scheinen fehlerhaft zu sein).
Könnten
1
Hier ist ein Link zur letzten Version von BallBounce, an der ich gearbeitet habe: dl.dropbox.com/u/638285/ballbounce.rar
mmcdole
@ An alle, die dazu beigetragen haben: Können Sie bitte etwas Licht ins Dunkel bringen, um diese Engine in 3D umzuwandeln? Wie diese großartige Engine auch in Java3D funktionieren kann.
statische Leere Haupt
2
Die Linie Vector2d impulse = mtd.multiply(i);sollte i * der normalisierte mtd-Vektor sein. So etwas wie:Vector2d impulse = mtd.normalize().multiply(i);
Klenwell

Antworten:

117

Um festzustellen, ob zwei Kugeln kollidieren, überprüfen Sie einfach, ob der Abstand zwischen ihren Mitten weniger als das Zweifache des Radius beträgt. Um eine perfekt elastische Kollision zwischen den Kugeln zu erzielen, müssen Sie sich nur um die Komponente der Geschwindigkeit kümmern, die in Richtung der Kollision verläuft. Die andere Komponente (tangential zur Kollision) bleibt für beide Bälle gleich. Sie können die Kollisionskomponenten erhalten, indem Sie einen Einheitsvektor erstellen, der in die Richtung von einer Kugel zur anderen zeigt, und dann das Punktprodukt mit den Geschwindigkeitsvektoren der Kugeln aufnehmen. Sie können diese Komponenten dann in eine perfekt elastische 1D-Kollisionsgleichung einfügen.

Wikipedia hat eine ziemlich gute Zusammenfassung des gesamten Prozesses . Für Kugeln beliebiger Masse können die neuen Geschwindigkeiten unter Verwendung der Gleichungen berechnet werden (wobei v1 und v2 die Geschwindigkeiten nach der Kollision sind und u1, u2 von zuvor sind):

v_ {1} = \ frac {u_ {1} (m_ {1} -m_ {2}) + 2m_ {2} u_ {2}} {m_ {1} + m_ {2}}

v_ {2} = \ frac {u_ {2} (m_ {2} -m_ {1}) + 2m_ {1} u_ {1}} {m_ {1} + m_ {2}}

Wenn die Kugeln die gleiche Masse haben, werden die Geschwindigkeiten einfach umgeschaltet. Hier ist ein Code, den ich geschrieben habe und der etwas Ähnliches bewirkt:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

In Bezug auf die Effizienz hat Ryan Fox Recht. Sie sollten in Betracht ziehen, die Region in Abschnitte aufzuteilen und dann in jedem Abschnitt eine Kollisionserkennung durchzuführen. Denken Sie daran, dass Bälle an den Grenzen eines Abschnitts mit anderen Bällen kollidieren können. Dies kann Ihren Code erheblich komplizierter machen. Effizienz wird wahrscheinlich keine Rolle spielen, bis Sie mehrere hundert Bälle haben. Für Bonuspunkte können Sie jeden Abschnitt auf einem anderen Kern ausführen oder die Verarbeitung von Kollisionen innerhalb jedes Abschnitts aufteilen.

Jay Conrod
quelle
2
Nehmen wir an, die Massen der beiden Bälle sind nicht gleich. Wie wirkt sich das auf die Vektoränderung zwischen Bällen aus?
mmcdole
3
Es ist eine Weile her seit der 12. Klasse, aber ich denke, sie bekommen ein Verhältnis des Impulses, das dem Verhältnis der Massen entspricht.
Ryan Fox
6
@ Jay, nur um darauf hinzuweisen, dass ein von Ihnen hinzugefügtes Gleichungsbild für eine eindimensionale Kollision ist, nicht für eine zweidimensionale.
mmcdole
@ Simucal. nicht wahr ... u und v sind Vektoren in dieser Gleichung. Das heißt, sie haben x-, y- (und z-) Komponenten.
Andrew Rollings
2
@ Simucal, Sie haben Recht, sie sind für den eindimensionalen Fall. Verwenden Sie für weitere Dimensionen einfach die Komponenten der Geschwindigkeit, die mit der Kollision übereinstimmen (aci, bci im Code). Die anderen Komponenten sind orthogonal zur Kollision und ändern sich nicht, sodass Sie sich keine Sorgen machen müssen.
Jay Conrod
48

Nun, vor Jahren habe ich das Programm so gemacht, wie Sie es hier vorgestellt haben.
Es gibt ein verstecktes Problem (oder viele, abhängig von der Sichtweise):

  • Wenn die Geschwindigkeit des Balls zu hoch ist, können Sie die Kollision verpassen.

Und auch in fast 100% der Fälle sind Ihre neuen Geschwindigkeiten falsch. Nun, nicht Geschwindigkeiten , sondern Positionen . Sie müssen neue Geschwindigkeiten genau an der richtigen Stelle berechnen . Andernfalls verschieben Sie die Bälle nur auf einen kleinen "Fehler" -Betrag, der aus dem vorherigen diskreten Schritt verfügbar ist.

Die Lösung liegt auf der Hand: Sie müssen den Zeitschritt so aufteilen, dass Sie zuerst zum richtigen Ort wechseln, dann kollidieren und dann für den Rest der Zeit wechseln.

avp
quelle
Wenn Verschiebungspositionen aktiviert sind timeframelength*speed/2, werden die Positionen statistisch festgelegt.
Nakilon
@ Nakilon: Nein, es hilft nur in einigen Fällen, aber im Allgemeinen ist es möglich, die Kollision zu verpassen. Und die Wahrscheinlichkeit, die Kollision zu verpassen, steigt mit der Größe des Zeitrahmens. Übrigens scheint Aleph die richtige Lösung gezeigt zu haben (ich habe sie aber nur überflogen).
avp
1
@avp, ich war nicht über Wenn die Geschwindigkeit des Balls zu hoch ist, können Sie die Kollision verpassen. , aber über deine neuen Positionen wird falsch sein . Da eine Kollision etwas später erkannt wird, als sie tatsächlich kollidierte, erhöht sich timeframelength*speed/2die Genauigkeit zweimal , wenn sie von dieser Position abgezogen wird.
Nakilon
20

Sie sollten die Speicherpartitionierung verwenden, um dieses Problem zu lösen.

Informieren Sie sich über Binary Space Partitioning und Quadtrees

grepsedawk
quelle
4
Wäre ein Sweep- und Prune- Algorithmus nicht besser als eine Space-Partitionierung ? Die Bälle bewegen sich schnell, daher muss jede Partitionierung regelmäßig aktualisiert werden, was zu Overhead führt. Ein Sweep und Prune könnte alle kollidierenden Paare in O (n log n) ohne vorübergehende Datenstrukturen finden. Hier ist ein gutes Tutorial für die Grundlagen
HugoRune
13

Zur Verdeutlichung des Vorschlags von Ryan Fox, den Bildschirm in Regionen aufzuteilen und nur nach Kollisionen innerhalb von Regionen zu suchen ...

Teilen Sie z. B. den Spielbereich in ein Quadratgitter auf (das willkürlich 1 Längeneinheit pro Seite enthält) und prüfen Sie, ob in jedem Gitterquadrat Kollisionen auftreten.

Das ist absolut die richtige Lösung. Das einzige Problem dabei (wie ein anderes Poster hervorhob) ist, dass Kollisionen über Grenzen hinweg ein Problem sind.

Die Lösung hierfür besteht darin, ein zweites Gitter mit einem vertikalen und horizontalen Versatz von 0,5 Einheiten zum ersten zu überlagern.

Dann befinden sich alle Kollisionen, die im ersten Raster über Grenzen hinweg liegen (und daher nicht erkannt werden), innerhalb der Rasterquadrate im zweiten Raster. Solange Sie die Kollisionen verfolgen, die Sie bereits behandelt haben (da es wahrscheinlich zu Überschneidungen kommt), müssen Sie sich keine Gedanken über die Behandlung von Randfällen machen. Alle Kollisionen befinden sich innerhalb eines Gitterquadrats auf einem der Gitter.

Andrew Rollings
quelle
+1 für eine genauere Lösung und um dem feigen Drive-by-Downvoter entgegenzuwirken
Steven A. Lowe
1
das ist eine gute Idee. Ich habe dies einmal gemacht und die aktuelle Zelle und alle benachbarten Zellen überprüft, aber Ihre Methode ist effizienter. Eine andere Möglichkeit, an die ich gerade gedacht habe, besteht darin, die aktuelle Zelle zu überprüfen und dann zu überprüfen, ob sie sich mit den aktuellen Zellengrenzen überschneidet. Wenn ja, überprüfen Sie die Objekte in DIESER benachbarten Zelle.
LoveMeSomeCode
10

Eine gute Möglichkeit, die Anzahl der Kollisionsprüfungen zu verringern, besteht darin, den Bildschirm in verschiedene Abschnitte aufzuteilen. Sie vergleichen dann nur jeden Ball mit den Bällen im selben Abschnitt.

Ryan Fox
quelle
5
Korrektur: Sie müssen nach Kollisionen mit denselben UND benachbarten Abschnitten
suchen
7

Eine Sache sehe ich hier zu optimieren.

Obwohl ich damit einverstanden bin, dass die Kugeln treffen, wenn die Entfernung die Summe ihrer Radien ist, sollte man diese Entfernung niemals tatsächlich berechnen! Berechnen Sie stattdessen das Quadrat und arbeiten Sie auf diese Weise damit. Es gibt keinen Grund für diese teure Quadratwurzeloperation.

Sobald Sie eine Kollision gefunden haben, müssen Sie die Kollisionen weiter auswerten, bis keine Kollisionen mehr vorhanden sind. Das Problem ist, dass der erste möglicherweise andere verursacht, die gelöst werden müssen, bevor Sie ein genaues Bild erhalten. Überlegen Sie, was passiert, wenn der Ball einen Ball am Rand trifft? Der zweite Ball trifft die Kante und prallt sofort in den ersten Ball zurück. Wenn Sie gegen einen Stapel Bälle in der Ecke stoßen, können einige Kollisionen auftreten, die behoben werden müssen, bevor Sie den nächsten Zyklus wiederholen können.

Was das O (n ^ 2) betrifft, können Sie nur die Kosten für die Ablehnung von fehlenden minimieren:

1) Ein Ball, der sich nicht bewegt, kann nichts treffen. Wenn eine angemessene Anzahl von Bällen auf dem Boden herumliegt, können viele Tests eingespart werden. (Beachten Sie, dass Sie immer noch prüfen müssen, ob etwas den stationären Ball getroffen hat.)

2) Etwas, das sich lohnen könnte: Teilen Sie den Bildschirm in mehrere Zonen, aber die Linien sollten unscharf sein - Bälle am Rand einer Zone werden als in allen relevanten (möglicherweise 4) Zonen aufgeführt. Ich würde ein 4x4-Raster verwenden und die Zonen als Bits speichern. Wenn ein UND der Zonen von zwei Kugelzonen Null zurückgibt, endet der Test.

3) Wie ich bereits erwähnt habe, mache nicht die Quadratwurzel.

Loren Pechtel
quelle
Vielen Dank für die Informationen auf der Quadratwurzelspitze. Wusste nichts über seine teure Natur im Vergleich zum Platz.
mmcdole
Eine andere Optimierung wäre, Bälle zu finden, die bei weitem nicht in der Nähe anderer Bälle sind. Dies würde nur dann zuverlässig funktionieren, wenn die Geschwindigkeiten der Kugeln eingeschränkt sind.
Brad Gilbert
1
Ich bin nicht einverstanden, nach isolierten Bällen zu suchen. Das ist genauso teuer wie das Erkennen der Kollision. Um Dinge zu verbessern, benötigen Sie etwas, das kleiner als O (n) für den betreffenden Ball ist.
Loren Pechtel
7

Ich habe eine ausgezeichnete Seite mit Informationen zur Kollisionserkennung und -reaktion in 2D gefunden.

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

Sie versuchen zu erklären, wie es aus akademischer Sicht gemacht wird. Sie beginnen mit der einfachen Kollisionserkennung von Objekt zu Objekt und fahren mit der Kollisionsreaktion und deren Skalierung fort.

Bearbeiten: Link aktualisiert

Markus Jarderot
quelle
3

Sie haben zwei einfache Möglichkeiten, dies zu tun. Jay hat die genaue Art der Überprüfung von der Mitte des Balls aus abgedeckt.

Der einfachere Weg ist, einen rechteckigen Begrenzungsrahmen zu verwenden, die Größe Ihres Rahmens auf 80% der Größe des Balls einzustellen und die Kollision ziemlich gut zu simulieren.

Fügen Sie Ihrer Ballklasse eine Methode hinzu:

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

Dann in Ihrer Schleife:

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}
FlySwat
quelle
1
Dies würde dazu führen, dass die Kugeln bei horizontalen und vertikalen Kollisionen zu 20% ineinander gehen. Könnte auch kreisförmige Begrenzungsrahmen verwenden, da der Wirkungsgradunterschied vernachlässigbar ist. Sollte auch (x-width)/2sein x-width/2.
Markus Jarderot
Guter Aufruf zum Vorrang Tippfehler. Sie werden feststellen, dass die meisten 2D-Spiele rechteckige Begrenzungsrahmen für nicht rechteckige Formen verwenden, da diese schnell sind und der Benutzer sie sowieso fast nie bemerkt.
FlySwat
Sie könnten einen rechteckigen Begrenzungsrahmen erstellen. Wenn ein Treffer vorliegt, aktivieren Sie den kreisförmigen Begrenzungsrahmen.
Brad Gilbert
1
@ Jonathan Holland, Ihre innere Schleife sollte für (int k = i + 1; ...) sein. Dadurch werden alle redundanten Überprüfungen beseitigt. (dh Überprüfung mit Selbstkollision und Überprüfung der Kollision ball1 mit ball2, dann ball2 mit ball1).
mmcdole
4
Tatsächlich ist ein quadratischer Begrenzungsrahmen in Bezug auf die Leistung wahrscheinlich schlechter als ein kreisförmiger Begrenzungsrahmen (vorausgesetzt, Sie haben die Quadratwurzel entfernt optimiert)
Ponkadoodle
3

Ich sehe es hier und da angedeutet, aber Sie könnten auch zuerst eine schnellere Berechnung durchführen, z. B. die Begrenzungsrahmen auf Überlappung vergleichen und dann eine radiusbasierte Überlappung durchführen, wenn dieser erste Test erfolgreich ist.

Die Additions- / Differenzmathematik ist für einen Begrenzungsrahmen viel schneller als alle Trigger für den Radius, und in den meisten Fällen schließt der Begrenzungsrahmen-Test die Möglichkeit einer Kollision aus. Wenn Sie dann erneut mit trig testen, erhalten Sie die genauen Ergebnisse, die Sie suchen.

Ja, es sind zwei Tests, aber insgesamt wird es schneller sein.

Jason Kleban
quelle
6
Du brauchst keinen Trigger. bool is_overlapping(int x1, int y1, int r1, int x2, int y2, int r2) { return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<(r1+r2)*(r1+r2); }
Ponkadoodle
3

Dies KineticModelist eine Implementierung des genannten Ansatzes in Java.

Trashgod
quelle
2

Ich habe diesen Code mit dem HTML Canvas-Element in JavaScript implementiert und er hat wunderbare Simulationen mit 60 Bildern pro Sekunde erstellt. Ich begann die Simulation mit einer Sammlung von einem Dutzend Bällen an zufälligen Positionen und Geschwindigkeiten. Ich fand , dass bei höheren Geschwindigkeiten, einen Glanz Kollision zwischen einer kleinen Kugel und einem viel größeren die kleine Kugel verursacht erscheint STICK zum Rande der größeren Kugel, und vor dem Trennen auf etwa 90 Grad um die größere Kugel nach oben verschoben. (Ich frage mich, ob jemand anderes dieses Verhalten beobachtet hat.)

Einige Protokollierungen der Berechnungen zeigten, dass der minimale Übersetzungsabstand in diesen Fällen nicht groß genug war, um zu verhindern, dass dieselben Kugeln im nächsten Zeitschritt kollidieren. Ich habe einige Experimente durchgeführt und festgestellt, dass ich dieses Problem lösen kann, indem ich die MTD basierend auf den relativen Geschwindigkeiten vergrößere:

dot_velocity = ball_1.velocity.dot(ball_2.velocity);
mtd_factor = 1. + 0.5 * Math.abs(dot_velocity * Math.sin(collision_angle));
mtd.multplyScalar(mtd_factor);

Ich habe überprüft, dass vor und nach dieser Korrektur die gesamte kinetische Energie bei jeder Kollision erhalten blieb. Der Wert von 0,5 im mtd_factor war ungefähr der Mindestwert, der festgestellt wurde, dass sich die Kugeln nach einer Kollision immer trennen.

Obwohl dieser Fix einen kleinen Fehler in der exakten Physik des Systems mit sich bringt, besteht der Nachteil darin, dass jetzt sehr schnelle Bälle in einem Browser simuliert werden können, ohne die Zeitschrittgröße zu verringern.

Stefan Musarra
quelle
1
Sünde (..) ist keine billige Funktion
PaulHK