Genaue Kollisionen

[Aphton]

Steinigt mich bitte nicht, weil ich hier uralte Threads ausgrabe..

Ich hab mir vor kurzem auch genauer Gedanken darüber gemacht, wie man den Kollisionszeitpunkt (relativ) genau berechnet.

Problembeschreibung (Beispiel)
Wenn sich zwei Objekte mit einer bestimmten Geschwindigkeit v1 und v2 zueinander bewegen, dann kann es passieren, dass
zwischen Zustand A und B, wobei A der Zustand vor dem Positionupdate (Position += Velocity) ist und B der Zustand danach, eine Kollision stattgefunden hat,
aber der einfache Kollisionscheck das nicht erkennt!

Code:

Objekte:
[X]--------->v1
v2<--[Y]

Zustand A:
[X]      [Y]

Zustand B:
   {Y]       [X]

Ich habe die Objekte als umschließende Kugeln betrachtet (Bounding Spheres), die aus Position, Velocity und Radius bestehen.
Anschließend habe ich als erstes den Zeitpunkt berechnet (approximiert), wo sie den kürzesten Abstand voneinander auf ihren Bahnen haben.
Wenn sie hier kollidieren (Abstand kleiner als Summe beider Radien), so habe ich den Zeitpunkt berechnet (approximiert), wann es gerade eben zu keiner Kollision kommt.
Ähnlicher Ansatz, wie ihn NamenLozer beschreibt.

Im Anhang befindet sich eine kleine Demo, die das ganze in 2d realisiert! Funktioniert aber genauso auch in 3d.
Kritsiert die Struktur nicht, darauf habe ich keinen Wert gelegt - habe es auf die schnelle entwickelt!

Bin für (algorithmische) Verbesserungsvorschläge offen, da das hier mein erster Lösungsansatz ist.
Gibt es bessere Methoden?

Als Optimierung benutzt man doch Quadtrees (2d) und Octrees (3d) und prüft nur Objekte im selben Node auf Kollision (um unnötigen Kollisionscheck zu vermeiden).
Diese Methode wirkt doch dem entgegen; es kann ja durchaus passieren, dass Objekt X in Node 1 mit Objekt Y in Node 2 kollidiert, da die Velocity sehr groß ist~.
Wie integriert man das?

[Medium]

Um das zu berücksichtigen, müsste man alle Quads betrachten, die beide Objekte zwischen den zwei Zeitpunkten durchqueeren. (Es könnten ja durchaus auch mehrere Quads sein.) Man macht also im Grunde erst eine Ermitttlung der Quads der potenziellen Kollidierer auf ihrem Weg innerhalb des Timeframes, dann eine Kollisionsprüfung der beteiligten Quads (aka: welche Quads werden von beiden Partnern durchquert?), und wenn dabei dann Quads übrig bleiben, die beide Bahnen enthalten, wird wirklich die genaue Prüfung gemacht.

Da ich das Teil jetzt nicht angegucken kann, aber dennoch interessiert bin: Du müsstest ja zwei Kollisionspunkte bei Bounding-Circles bekommen. Einen eintretenden, einen Austretenden. Wie unterscheidest du zwischen den beiden, um nicht fälschlicherweise mit dem hinteren zu hantieren?

[Aphton]

Hierbei handelt es sich nur um eine Zeitpunktsbestimmung, wo gerade eben keine Kollision stattfindet (preCollisionCircles). Eine Kollisionsverarbeitung ist gar nicht drinnen, darum gings ja gar nicht.
Außerdem kriege ich höchstens einen Kollisionspunkt ~ Berührungspunkt!

Aber die Idee mit allen Quads in Bewegungsrichtung ist eig. naheliegend. Danke!

[Namenloser]

Achja, wo Aphton das gepostet hat, könnte ich ja eigentlich auch mal meine Lösung von damals posten...

Aber ich warne euch: Der Code ist noch viel hässlicher. Dafür ist er wohl mathematisch exakt (von eventuellen Float-Ungenauigkeiten mal abgesehen). Ich hatte mich „damals“, wohl auch mangels mathematischer Kenntnisse (die ich heute wahrscheinlich/vielleicht hätte), sehr lange daran (und an der Fehlersuche) aufgehalten. Irgendwann war mir deshalb alles egal und ich wollte nur noch, dass es funktioniert, und nachdem es das tat, hab ich es nicht mehr angerührt .

Letztlich habe ich aber das umgesetzt, was in der von mir verlinkten Präsentation beschrieben wurde: Aus „bewegtem Kreis + bewegtem Kreis“ wird „fester Kreis + bewegter Kreis“ und daraus wird „fester, größerer Kreis + Strahl“.

Man kann in dem Test-Formular mit der linken bzw. rechten Maustaste die beiden Kreise platzieren und mit linker/rechter Maustaste bei gedrückter Shift-Taste ihre Bewegungsrichtung und Geschwindigkeit einstellen. Die Semantik ist hier also auch etwas anders als bei Aphtons Testprojekt.