Konzept für saubere Kollisionserkennung

[Florian H]

Aloha,


Ich entwickle derzeit ein Physik-Spiel (für die Smartphone-Plattform Android) und brauche dabei natürlich auch Kollisionen zwischen beweglichen Elementen (gegeben durch Position X,Y und Geschwindigkeit X,Y).
Das ist ganz grundsätzlich eigentlich kein Problem, ich schau' halt, ob sich ein Objekt mit einem anderen überlappt und wenn ja, dann berechne ich deren neue Geschwindigkeit ("abprallen"). Zusätzlich "trenne" ich die Objekte wieder, um die Überlappung zu beseitigen (sodass sie sich berühren, aber nicht ineinander reinragen).

Allerdings führt das schnell zu Problemen, wenn mehrere Objekte aufeinanderliegen (beispielsweise ein großer Haufen Kugeln, der von der Schwerkraft nach unten gezogen wird). Hier kollidieren ja ständig alle Bälle und ändern ihre Richtung und werden neu platziert etc. - das führt zu hässlichen Sprüngen und durch mathematische Ungenauigkeiten bzw. sich aufschaukelnde Fehler dazu, dass Kugeln dauerhaft in andere reinrutschen oder komplett die Positionen vertauschen.
Der Grund: Eine Kugel kollidiert (während sie da auf dem Haufen liegen) mit einer anderen -> diese wird abgestoßen -> stößt auf eine andere Kugel -> wird wieder zurückgestoßen -> stößt wieder auf die andere -> ... doof.

Das ganze Konzept ist imo schon fehlerträchtig, weil immer nur einzelne Kollisionen zweier Objekte betrachtet werden, unabhängig davon, was alles davon abhängt bzw. worauf das Einfluss hat.
Doch was ist die bessere Methode? Wie machen es Physiksimulationen (wie Phun)? Wie erfasst man das gesamte Gefüge und nicht nur immer 1:1-Kollisionen?

meine Frage bezieht sich nicht auf die eigentliche Umsetzung in Code, ich suche eher ein Konzept wie man sowas angeht. Habe bei google leider nichts gefunden und mich in mehrere hunderttausend Zeilen Code einzulesen, nur um irgendwann die Kollisionsabfrage daraus extrahieren zu können, ist jetzt auch nicht so praktikabel

Ich will keine 100% realistische Physik (das gibt die Rechenleistung des Gerätes gar nicht her), aber sie soll funktionieren!


Grüßle, flo

[Medium]

Etwas Linderung verschafft man sich schon durch einen algebraischen Ansatz. Du wirst Position und Geschwindigkeit (gerichtet) ja als Vektoren vorliegen haben. Dann kannst du dir 2 Kugeln nehmen und Position+Geschw. als Geradengleichungen auffassen, und einen Schnittpunkt berechnen - sowie die neuen Geschwindigkeiten und Positionen. Gerade im Fall von Kugeln ist das noch relativ einfach, da man dies dann nicht für jedes Polygon / jede Linie der Objekte veranstalten muss, da der Radius da ja ne recht dankbare Sache ist.
Du betrachtest zwar noch immer 2er Kombinationen, aber diese dafür wenigstens deutlich richtiger. Das verhindert dann auch ein Durchstoßen bei zu großen Geschwindigkeiten im Verhältnis zur Objektdicke in der Flugrichtung!

Die Sache mit der gegenseitigen und u.U. vielfachen Kollisionen wird dann schon deutlich kniffliger, da man dann ja schon fast im Bereich von Fluiden ist - und da gibt's bisher nicht wirklich einfache und schnelle Verfahren, und selbst die langsamen komplizierten sind nur Näherungslösungen bzw. Modelle.
Fall du nicht gerade davon ausgehen musst dass 1000 sich berührende Kugeln tummeln, sondern immer nur ein paar wenige Kollisionen auftreten, könnte man sich ein quasi rekursives Verfahren ausdenken.
1. Wähle zufälliges Startobjekt
2. Berechne Kollision mit einem anderen
3. Falls Kollision: Pos/Geschw berechnen, und dann beide Objekte erneut betrachten, weiter bei Punkt 2
4. Falls keine Kollision, nächstes Objekt und weiter bei Punkt 2
5. Fortführen bis man wieder beim 1. Objekt ist, dann Bildausgabe, weiter bei Punkt 1

Nachteil ist eben, dass man bei sehr komplexen Szene sehr lange braucht, und man sicherlich auch endlose Szenarien konstruieren kann. Da müsste man im Zweifel mit einer maximalen Iterationstiefe bei Schritt 2 entgegenwirken - zulasten der Qualität der Simulation natürlich.

[jfheins]

Ich hätte da ne andere Idee: Verringer bei jedem Stoß den gesamtimpuls um einen kleinen Betrag (es gibt keine 100%igen elastischen Stöße) und setzte die Geschwindigkeit auf 0 sobald sie unter einen Schwellenwert fällt (z.B. 0,01 m/s)

Achja, und lass das mit dem zurücksetzen der Position - das erzeugt nur neue Kollisionn, wenn du Kugeln alle im Loch liegen. Da stört es weniger, wenn sie sich um einen Hauch überlappen

[Draos]

Vektoren gehen doch. Vorallem 2D super.

Gibt ja nur Gerade,Strecken (Geraden mit Parameterintervall), Kreise und Punkte.

Was kollidiert bei Dreiecken immer nur? Nein sind nicht nur Kanten. Es sind die Ecken der Objekte, die aber mit Kanten des anderen kollidieren. Somit musst du allerdings auch jede Kollision von Polygonen von alles Objekten betrachten, aber sollte man ja eh.

[Medium]

@jfheins: Das wäre lediglich eine sinnvolle Ergänzung, aber keineswegs ein "Modell" dass das genannte Problem löst. Bei deinem prinzipiellen Anzatz würde es zudem zu einem "Zusammensickern" der Objekte kommen, da sie immer weiter ineinander hinein rutschen. Eine halbwegs brauchbare (=glaubwürdige) Kollisionsberechnung für allgemeine Anwendung kommt nicht ohne Schnittpunktsberechnungen aus.
Aber auch das allein löst noch immer nicht das "Ganzheitlichkeits"-Problem des TEs. Daher der 2. Absatz in meiner Antwort. Das ist wohl das eigentliche Problem von Florian, und es ist auch kein allzu einfaches.

[vsilverlord]

hallo, mit der problematik habe ich mich auch schon eingehend beschäftigt!
Möglichkeit 1
Eigentlich so, wie du es gemacht hast, prüft ob der radius einer Koordinate irgendwo in einem anderen Radius drinnhängt; falls ja:
Kollisionsroutine, in der mit der Formel des elastischen Stosses die Geschwindigkeiten berechnet werden.
Außerdem hab ich eine boolsche Variable für jedes Objekt, die dafür sorgt, dass kein Viech mit einem anderen Viech immer wieder kollidiert, weil die beiden Kreise noch ineinander hängen und sich so verkeilen [schöner bug =) ] Nach jedem Vorgang wird die "kollidiert gerade"-Variable aller Objekte, die nirgendwo drinhängen, wieder auf 'false' gesetzt.
Vorteil: Funktioniert schnell und tadellos, auch mit vielen [ca.200] Objekten und einigermaßen physikalisch korrekt.
Nachteil: Falls 2 Kugeln oder mehr gleichzeitig auf eine Kugel drauffallen, muss man was extra programmieren, da das sonst einen Bug auslöst; Zuweilen kommt es vor, dass Kugelhaufen entstehen, die sich völlig seltsam verhalten [selten]

Möglichkeit 2:
Es wird bei jedem "Bewegungsvorgang" geprüft, ob die Kugel irgendwo reinfallen "könnte", falls das der Fall sein sollte, wird die zu berechnende Zeit so lange verringert, bis der Abstand zu dem Kollisionsobjekt einen Grenzwert besitzt (~0). Wenn dieser Wert erreicht wird, können die Geschwindigkeiten oder sogar Verformungen berechnet werden.
Vorteil: perfekt, um Verformungen und physikalisch korrekte Bewegungen berechnen und visualisieren zu können.
Nachteil: Bisweilen ist der Rechenaufwand so groß, dass die Bewegungen nicht mehr zeitlich korrekt ausgeführt werden; Große Objektanzahlen sind nahezu unmöglich.

[Medium]

Kleine Korrektur zu meinem Vorschlag oben:

Berechne zunächst alle möglichen Kollisionen im gerade aktuellen Timeframe. Alle Kollisionspaare in eine Liste, sortiere diese nach dem Zeitpunkt der Kollision innerhalb des Timeframes aufsteigend. (Leicht möglich anhand der Koeffizienten aus der Schnittpunktberechnung, der genaue (Echt-)Zeitliche Bezug ist ja unwichtig.)
Die erste Kollision ausführen, aber nur bis zu dem Punkt an dem sie sich berühren (bzw. miiiinimal dahinter, damit sie nicht noch einmal gefunden werden). Die neuen Geschwindigkeitsverktoren (bzw. deren Restanteil) zuweisen. Dann wieder alle möglichen Kollisionen berechnen, aber nun bei allen schon bewegten Objekten den Zeitanteil um den sie bewegt wurden hinzuaddieren. Dann wieder sortieren, usw. bis keine Kollision im Timeframe mehr statt findet.

Problem: Man muss für jede vorkommende Kollision n*(n-1)/2 (=alle) Kollisionen in Betracht ziehen, also wirklich den Schnitt bilden. Das kann ganz schön happig werden, aber dieses Verfahren sollte eine extrem gute Annäherung an die Realität ergeben.
Weiterhin ist zu bedenken, dass die Geschwindigkeitsvektoren die innerhalb des Timeframes partiell auf bewegte Objekte angewendet werden nicht die sind, die das Objekt für das nächste Timeframe hat. Es behält zwar die Richtung des letzten Vektors, dieser muss aber die Summe der Länge aller zwischendurch benutzten Vektoren haben. Das heisst du brauchst für jedes Objekt einen Geschwindigkeitsvektor und einen Längenakkumulator zusätzlich.

Darin ließen sich natürlich auch noch weitere physikalische Gegebenheiten einbetten wie Gleit- und Haftreibung, Elastizität und so weiter. Schneller wird's dann zwar auch nicht, aber hey, akkurat!

[Florian H]

Danke erstmal allen für den Input!

Zitat von Medium:

Kleine Korrektur zu meinem Vorschlag oben:

Berechne zunächst alle möglichen Kollisionen im gerade aktuellen Timeframe. Alle Kollisionspaare in eine Liste, sortiere diese nach dem Zeitpunkt der Kollision innerhalb des Timeframes aufsteigend. (Leicht möglich anhand der Koeffizienten aus der Schnittpunktberechnung, der genaue (Echt-)Zeitliche Bezug ist ja unwichtig.)
Die erste Kollision ausführen, aber nur bis zu dem Punkt an dem sie sich berühren (bzw. miiiinimal dahinter, damit sie nicht noch einmal gefunden werden). Die neuen Geschwindigkeitsverktoren (bzw. deren Restanteil) zuweisen. Dann wieder alle möglichen Kollisionen berechnen, aber nun bei allen schon bewegten Objekten den Zeitanteil um den sie bewegt wurden hinzuaddieren. Dann wieder sortieren, usw. bis keine Kollision im Timeframe mehr statt findet.

Das ist eine prima Idee, auf so einen "Geistesblitz" habe ich gewartet - ich werds nachher direkt mal testen

[jfheins]

Bei Mehrkörpersimulationen musst du dich entscheiden ob du den analytischen Ansatz wählst, der zwar physikalisch korrekt ist, aber langsam ist und dem numerischen der zwar nicht ganz korrekt ist aber dafür schnell.

Analytisch ist die Aufgabe

Zitat:

beispielsweise ein großer Haufen Kugeln, der von der Schwerkraft nach unten gezogen wird

nicht in kurzer Zeit zu lösen. Schon gar nicht in Echtzeit.
Guck dir mal da an: http://www.amm.mw.tum.de/fileadmin/A...anduhr3d_2.avi Das wurde analytisch gemacht, mit allem Pipapo - wenn du willst kann ich mal fragen, wie lange die daran gerechnet haben

Numerisch isses halt schneller und ungenauer.

[BUG]

In einem anderem Thema zu diesem Thema () wurde das folgende Tutorial zur Kollisionserkennung empfohlen:
http://www.eiserloh.net/gdc2006_Eise...csTutorial.ppt

Fand ich sehr informativ.


MfG,
Bug