2D kollidierende n-body simulation (schnelle Kollisionserkennung für große Anzahl von Bällen)
Ich möchte ein Programm schreiben, um eine Bewegung mit hoher Anzahl (N = 1000 - 10 ^ 5 und mehr) von Körpern (Kreisen) auf 2D-Ebene zu simulieren. Alle Körper haben gleiche Größe und die einzige Wechselwirkung zwischen ihnen ist elastische Kollision.
Ich möchte etwas wie 
aber in größerem Maßstab, mit mehr Kugeln und dichterer Füllung von das Flugzeug (kein Gasmodell wie hier, aber wie kochendes Wassermodell).
Also möchte ich eine schnelle Methode der Erkennung, dass Ball Nummer i hat einen anderen Ball auf seinem Weg innerhalb 2 * Radius + V * delta_t Abstand. Ich will keine Kollision mit N Kugeln für jeden von i ball suchen. (Diese Suche wird N ^ 2 sein.)
PS Sorry für Loop-animiertes GIF. Drücken Sie einfach Esc, um es zu stoppen. (Funktioniert nicht in Chrome).
3 Antworten
Dieser erste Schritt in der Physiksimulation ist die Kollisionserkennung für die breite Phase. Es gibt mehrere Ansätze, die hier beschrieben werden, aber die beiden grundlegenden sind räumliche Partitionierung, die Objekte in ein Raster aufteilen oder sort-and-sweep, bei dem alle Objekte entlang zweier Achsen sortiert werden.
Offensichtlich wollen Sie vermeiden, dass (N1 -) * N bei jeder Iteration auf Kollisionen prüft. Ein einfacher Ansatz wäre, den Bereich in ein 2D-Gitter aus Zellen aufzuteilen und dann einen einzelnen Durchgang durchzuführen, um herauszufinden, welche Zellen jeder Ball in der aktuellen Iteration durchläuft. Jeder Ball prüft dann nur auf Kollisionen mit Bällen, die durch die Zellen hindurchgehen.
Ich bin mir sicher, dass es anspruchsvollere Ansätze gibt, aber das könnte ein guter Anfang sein.
Die Gitterbreite / -länge sollte größer oder gleich dem Radius von ihnen sein und die Suche sollte sich auf den ersten Nachbarn befinden (8 + Mitte = 9 Gitter). Bei einer minimalen Rastergröße ist es zehn- bis fünfzehnmal so groß wie die Partikelberechnung.
Tags und Links collision-detection modeling