Was ist ein guter Algorithmus zur Erkennung von Kollisionen zwischen sich bewegenden Kugeln?

27

Wenn (zum Zwecke der Kollisionserkennung) 3D-Objekte in einem Spiel durch Kugeln dargestellt werden, was ist ein guter Algorithmus zum Erkennen einer Kollision zwischen Kugeln?

Wenn jedes Objekt eine Position ab dem letzten Frame und eine neue (gewünschte) Position hat, was ist ein guter Algorithmus, der Kollisionen identifiziert, bei denen sich die Kugeln im vorherigen Frame nicht überschnitten haben und sie sich im zweiten Frame möglicherweise nicht überschneiden. aber sie haben sich irgendwo dazwischen geschnitten?

collision-detection kevin42
quelle

Antworten:

18

Im Grunde suchen Sie nach einer Spur.

Diese Seite wird Ihnen wahrscheinlich helfen: http://www.realtimerendering.com/intersections.html

Moving Sphere / Sphere: (Position) Fügen Sie der statischen Kugel den Radius der sich bewegenden Kugel hinzu und behandeln Sie die sich bewegende Kugel als Strahl. Verwenden Sie diesen Strahl, um eine Strahl-Kugel-Kreuzung durchzuführen. Siehe Gomez; Schröder für Code (Artikel hat Fehler in der Ableitung, Code ist in Ordnung); und RTR2, p. 622.

Tetrade
quelle
1
Das funktioniert nicht, wenn sich beide Kugeln bewegen (auch nicht, wenn Sie es zweimal tun). Mir scheint, Sie müssten zuerst einen Abstandsprüfvorgang zwischen den Linien durchführen, die Bewegung a und die eine Bewegung b überspannen, und wenn dieser kleiner als Radius a + Radius b ist, liegt möglicherweise eine Kollision vor. Danach würde ich überprüfen, wo dieser Zeitpunkt für Kugel a ist und wo für Kugel b, um zu sehen, ob die Zeiten nahe sind. In diesem Fall würde ich die Geschwindigkeit anhand der Entfernung überprüfen. Wenn es sich dennoch um eine mögliche Kollision handelt, würde ich die Geschwindigkeit schrittweise verfeinern.
Kaj
15
Eigentlich muss man die Bewegung nur relativieren. Wenn sich also beide Kugeln bewegen, subtrahieren Sie einfach die Geschwindigkeit einer der Kugeln von beiden, sodass Sie eine "sich bewegende" und eine "stationäre" Kugel haben. Dann können Sie die oben genannten verwenden.
Tetrad
8

Verwenden Sie einen Sweep-Test, wie in diesem Gamasutra-Artikel gezeigt.

Firas Assaad
quelle
4

Aus meinem Kopf:

  1. Erstellen Sie zwei Liniensegmente von der Mitte jedes Kreises, von wo aus er begonnen hat, bis zu der Stelle, an die er sich in diesem Zeitschritt bewegt hat.
  2. Ermitteln Sie den Mindestabstand zwischen diesen beiden Liniensegmenten. wie hier erklärt .
  3. Wenn dieser Abstand kleiner oder gleich dem Radius des ersten Kreises plus des zweiten ist, kollidierten sie. sonst nicht.

Und das ist alles, was dazu gehört. Ich würde erwarten, dass das ziemlich schnell geht.

Robert Massaioli
quelle
1

Hier ist ein weiterer schöner Gamasatura- Artikel.

Mateen Ulhaq
quelle
1
Mir ist klar, dass dies 7 Jahre später ist, aber diese Antwort ist nur ein Link. Glücklicherweise lebt der Link noch, aber wenn es nicht so wäre, wäre Ihre Antwort ... keine Antwort.
Draco18s
0

Als jemand zu sprechen, der dies getan hat: Es ist den Aufwand nicht wert . Wenn Ihr Spieldesign es nicht unbedingt benötigt und es es mit ziemlicher Sicherheit nicht tut, werden Sie weitaus mehr Mühe darauf verwenden, die Arbeit zu beschleunigen, als Sie wirklich erwarten. Und es wird langsamer sein, als Sie es wollten.

ZorbaTHut
quelle
Er könnte für alles, was Sie wissen, ein Billardspiel machen.
Kaj
Wenn er ein Poolspiel machen würde, würde sein "Game Design es unbedingt brauchen" .
deft_code
Sie haben recht, erfinden Sie das Rad nicht neu . Aber nur zum Üben kann es sich lohnen.
User712092
4
Ich stimme der direkten Entmutigung als Antwort nicht zu .
Bobobobo
Ich bin mit @bobobobo einverstanden, die Frage ist nicht, ob es sich lohnt oder nicht, ein zukünftiger Benutzer, der diesen Thread sieht, braucht möglicherweise unbedingt die Antwort, unabhängig von den Kosten. Das wäre besser als Kommentar.
TomTsagk
0

Es gibt einen Artikel über das Ableiten der Kollisionserkennung mit Mathematik auf Flipcode . Es hat Kreis-Kreis. So können Sie den Kollisionspunkt genau erkennen und prüfen, ob überhaupt eine Kollision vorliegt.

user712092
quelle
Mir ist klar, dass dies 7 Jahre später ist, aber diese Antwort ist nur ein Link. Glücklicherweise lebt der Link noch, aber wenn es nicht so wäre, wäre Ihre Antwort ... keine Antwort.
Draco18s
0

Die Kollisionserkennung für sich bewegende Objekte wird in der Regel als "Berechnung des überstrichenen Volumens" bezeichnet. Hier finden Sie einige Codes / Artikel zu diesem Thema.

http://www.gpu-voxels.org/demos/ (Demo)

Quellcode-Bibliotheken:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Artikel:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (Leider kein Quellcode)

http://www.realtimerendering.com/intersections.html (ziemlich umfangreiche Linksammlung)

TarmoPikaro
quelle
1
Antworten, die nur einen Link enthalten (oder in diesem Fall mehrere), enthalten keine tatsächliche Antwort. Sie sollten die relevanten Informationen in Ihren Beitrag aufnehmen, damit Ihr Beitrag nach dem Erlöschen dieser Links immer noch verständlich ist.
Draco18s
Informationen hinter Links erklären im Moment etwas besser als ich. Es gibt auch Demovideos hinter Links, die einen Eindruck davon vermitteln, was in Echtzeit passiert.
TarmoPikaro
1
meta.stackexchange.com/a/8259/313685
Draco18s