6. Kapitel

Kollisionsbehandlung mit Ortskorrektur

Kollisionsbehandlung

In den meisten Anwendungsfällen dient die Kollisionserkennung der Ausführung von Stößen. Dabei stoßen bewegte Objekte, die sich mit typischen Geschwindigkeiten v_Object bewegen, aufeinander. Würden die Objektbewegungen, d.h. die Änderungen der Objekt-Orte je Zeiteinheit, kontinuierlich sein, bräuchten wir überhaupt nicht über dieses Thema zu sprechen. Nun ist aber in der digitalen Welt die Zeit nicht analog, sondern diskretisiert. Sinnvoller Weise verwenden wir den Kehrwert der Bildwechselfrequenz als Zeitquant ().
Wird nun ein Objekt mit der Geschwindigkeit v bewegt, kann es infolge der diskretisierten Zeit nicht mehr jeden beliebigen Ort einnehmen, sondern nur solche Orte, die der diskretisierten Zeit entsprechen:

()

Das hat u.a. zur Folge, dass der Kollisionsort nur mit der Unschärfe

()

bestimmt werden kann. Das führt

bei einer erkannten Kollision dazu, dass die kollidierenden Körper ineinander "eindringen". Etwas, was in der Realität nicht vorkommen kann.
aber u.U. auch dazu, dass die Kollision überhaupt nicht erkannt wird, wenn sich die Körper relativ zueinander zu schnell bewegen.

Der erstgenannte Fall zwingt uns über die Behandlung nach einer erkannten Kollision nachzudenken. Zwar ist klar, dass bei einer Kollision die Objektgeschwindigkeiten vor und nach der Kollision den Stoßgesetzen folgend umgerechnet werden müssen. Aber ist das wirklich so einfach? Betrachten wir doch mal den Fall, der in dargestellt ist.
Eine Kugel nähert sich unter einem sehr flachen Winkel einer Ebene. Zum Zeitpunkt t_i-1 berührt die Kugel die Ebene noch nicht. Aber bereits zum Zeitpunkt t_i, der um einen Bildwechsel später liegt, ist die Kugel so weit fortgeschritten, dass die Kollisionsbedingung entsprechend erfüllt ist und eine Berührung der Ebene signalisiert.
Dieser Augenblick sollte nun als die Kollision registriert und die Kugelgeschwindigkeit gemäß der geltenden Stoßgesetze umgerechnet werden.

Abb. Fehlerhafte Reflexion infolge "Eindringens"

Aber schauen wir genauer hin, stellen wir fest, dass die Kugel die Ebene nicht nur berührt, sondern in diese sogar "eindringt". Das passiert natürlich in der Realität nicht, aber bei uns schon! Das liegt an der Diskretisierung der Zeitachse. Nur bei Bildwechseln werden die Standorte neu berechnet. Und da sich unsere Zeitachse in Sprüngen von dt = 1/frmRate vorwärts bewegt, wird der wahre Kollisionszeitpunkt gar nicht wahrgenommen und die Kugel fliegt in die Ebene hinein. In liegt der Zeitpunkt t_i relativ weit hinter dem wahren Kollisionszeitpunkt, so "dringt" die Kugel relativ weit in die Ebene hinein.
Da eine Kollision registriert wurde, wird die Kugel jetzt an der Ebene reflektiert. Unglücklicher Weise findet diese Kollision in einer spitzen Ecke eines Polygons statt. So kann es dazu kommen, dass bereits beim nächsten Bildwechsel wieder eine Kollision erfolgt, die aber nicht als neues Ereignis registriert wird, sondern noch der ersten Kollision zugerechnet wird. Die Folge ist, dass die nächste Ortsberechnung zur Zeit t_i+1 einen neuen Ort erfolgt, bei dem die Kugel noch immer in der Ebene "steckt". Damit sind die Bedingungen für die Erkennung einer Kollision wieder gegeben und eine erneute Reflexion wird berechnet. Diese geht aber wieder in die Richtung, die die Kugel zum Zeitpunkt t_i-1 hatte. So beginnt das Spiel von vorn und die Kugel kann die Ebene nie verlassen (es sei denn, die Ebene ist begrenzt). Eine solche Konstellation tritt nicht sehr häufig auf, aber sie tritt auf. Ursachen hierfür können Rundungsfehler oder eine gewollte Dämpfung beim Stoß sein.
Die Folgen dieses Effektes können sein, dass, wenn mehrere Kugeln im Spiel sind, diese nach einer Kollision "verklumpen" oder statt an einer Ebene reflektiert zu werden, parallel an dieser entlang "rutschen". So ist also klar, dass hier Gegenmaßnahmen erforderlich sind, um dieses "Eindringen" zu verhindern.
Im folgenden Programmbeispiel kannst Du den letztgenannten Effekt beobachten. Drücke einfach den START-Button und lass die Kugel laufen. Nach einer kurzen Zeit (nach ca. 35 Kollisionen) siehst Du die Kugel in die Wand eindringen, danach kann sie sich nicht mehr davon lösen! Erst am nächsten Segment ist dies wieder möglich.

Bitte einen Augenblick Geduld
während das Programm geladen wird!

Abb. Kollisionserkennung ohne Korrekturmaßnahmen

Die Erkennung einer Kollision erst nach der Berührung oder gar dem Eindringen des bewegten Objektes hat Nachteile bei großen Objektgeschwindigkeiten, die zu einem Eindringen oder im Extremfall Überspringen der stoßenden Körper führen können. zeigt den prinzipiellen Programmablauf der Stoßerkennung, -behandlung und -ausführung. Dieses Verfahren gewährleistet nicht, dass der berechnete Stoßort mit dem tatsächlichen Stoßort zusammen fällt. Das führt in einigen Fällen zu unerwartetem Verhalten nach der Kollision.
Gesucht wird also ein Verfahren zur Kollisionserkennung, dass diese Nachteile vermeidet, zu mindest aber minimiert. Im folgenden sollen zwei Verfahren einer Ortskorrektur besprochen werden.

Abb. Kollisionsbehandlung ohne Orts-Korrektur

Kollisionserkennung mit vorausschauender Prognose des Stoßortes

Betrachten wir die folgende Standardsituation: zwei Kugeln bewegen sich aufeinander zu und kollidieren. Besitzen beide Kugeln die gleichen Massen m, bewegen sie sich nach dem Zusammenstoß gemäß der Stoßgesetze (Stoß/Zentraler elastischer Stoß) mit jeweils der Geschwindigkeit der anderen Kugel von einander fort.
Was Du beim Experimentieren in der beschriebenen Kollisionssituation, insbesondere bei großen Objektgeschwindigkeiten, beobachten kannst, ist das gegenseitige "Eindringen" beim Stoß des einen Objektes in das andere, weil der Zusammenstoß zweier Objekte in der Regel erst dann bemerkt wird, wenn der Stoßort bereits überschritten ist. Den Beobachter stört das nicht, weil das Auge viel zu träge reagiert, um dieses Malheur während des einen Frames zu bemerken. Aber unter ungünstigen Bedingungen kann dieses Verhalten Folgen haben. Z.B. "verkleben" Objekte nach einem Stoß oder registrieren überhaupt keine Kollision, weil die Orte, die beim nächsten Bildwechsel errechnet werden, bereits jenseits der beiden Kugeln liegen. Zur Behebung dieses Problems werden wir jetzt nicht nur die aktuellen Objektorte, sondern auch noch die aktuellen Objektgeschwindigkeiten zur Ermittlung des Kollisionsortes heranziehen.

Ausgangspunkt ist die Überlegung, dass der Stoßort auch im Voraus berechnet werden kann. Das ist möglich, weil - zumindest für die Dauer eines frames - alle Objektgeschwindigkeiten bekannt und unveränderlich sind. Also sind alle Bewegungen zwischen zwei frames gleichförmig. Daher berechnen wir anstelle der Distanzen zwischen den Objekten, den Zeitpunkt, zu dem sich beide Wege der auf Kollisionskurs befindlichen Objekte so weit angenähert haben, dass sie sich berühren.

Zur Verdeutlichung dieser Idee schauen wir uns den einfachsten Fall, nämlich den zentralen Stoß an (). Im oberen Teilbild wird die einfache Kollisionserkennung gezeigt. Im unteren Teilbild die Kollisionserkennung mit Prognose des Stoßortes.
Gehen wir davon aus, dass zum Zeitpunkt t_n - oben wie unten - beide Objekte kurz vor der Kollision stehen.

oberes Teilbild: Infolge der Geschwindigkeiten beider Objekte haben sich die Objekte im folgenden frame so weit bewegt, dass sie die Orte x₁(t_n+1) bzw. x₂(t_n+1) einnehmen. Unglücklicher Weise sind diese Orte aber so weit fortgeschritten, dass sich beide Objekte teilweise überlappen. Zur Erinnerung: der Zeitpunkt des neuen frames ergibt sich aus dem vorangegangen Zeitpunkt zu t_n+1 = t_n + Δt! (Δt = 1/frmRate bezeichnet die Zeitspanne zwischen den Bildwechseln.)
unteres Teilbild: Hier wird gar nicht erst die Berechnung des neuen frames abgewartet, sondern noch im jeweils aktuellen frame eine Prognose des künftigen Ortes berechnet, die dann ein verkürztes Intervall Δt' liefert. Damit kann nun der exakte Stoßort berechnet werden. Mit t' bzw. Δt' werden hier korrigierte Zeitgrößen bezeichnet!

Abb. Kollisionserkennung mit und ohne Prognose des Stoßortes

Die Prognose des richtigen Stoßortes wird auf eine Zeitprognose zurück geführt. Es wird nämlich gefragt, ob die verbleibende Zeit t' bis zum Stoß größer oder gleich/kleiner der regulären Framedauer dt ist. Dazu werden für beide Objekte lineare Gleichungen aufgestellt (), die mathematisch die Orte beider Objekte auf der Basis der aktuellen Orte und der aktuellen Geschwindigkeiten berechnen:

()

x_{1} (t') = x_{1} (t_{n}) + v_{x_{1}} \cdot t'

x_{2} (t') = x_{2} (t_{n}) + v_{x_{2}} \cdot t'

Nun kann die Summe beider Objektradien mit der Differenz der beiden Objektorte (die ja eine Funktion der Zeit t' sind) verglichen werden ():

()

r_{1} + r_{2} = (x_{2} (t_{n}) + v_{x_{2}} \cdot t') - (x_{1} (t_{n}) + v_{x_{1}} \cdot t')

Da es sich hier um eine lineare Funktion von der Zeit handelt, weiterhin die Geschwindigkeiten als konstant (da gleichförmige Bewegung vorliegt) angesehen werden kann, ist es ein Leichtes, die Zeit t' bis zum Stoß zu berechnen ():

()

t' = | \frac{r_{1} + r_{2} - [x_{2} (t_{n}) - x_{1} (t_{n})]}{(v_{x_{2}} - v_{x_{1}})} |

Für die spätere Anwendung ist es zweckmäßig, den Betrag der Zeit t' zu verwenden. Denn sie kann auch negative Werte annehmen, nämlich dann, wenn sich beide Körper nach dem Stoß wieder von einander entfernen!

Somit liegt ein Stoß vor, wenn t' ≤ dt wird. Ja, und wie erfolgt nun die Ortsberechnung? Ganz einfach. Das bis dahin geltende Zeitincrement dt wird bei erkanntem Stoß einmalig durch t' ersetzt. Dadurch sind die Objektorte genau um die Summe der Objektradien von einander entfernt.

Dem muss nun im Programmablauf der Ortsberechnung Rechnung getragen werden (). Jetzt müssen die Prognose des Stoßortes, d.h. die Kollisionserkennung, und die Kollisionsbehandlung voneinander getrennt werden, muss doch die Ortsberechnung im Fall des zu erwartenden Stoßes mit einem anderen Zeitincrement berechnet werden.

Abb. Kollisionserkennung mit Prognose des Stoßortes

Im Beispielprogramm sind im direkten Vergleich eine Standard-Kollisionserkennung (oben) und die Kollisionserkennung mit Ortsprognose zu sehen. Im Gegensatz zu einer normalen Anwendung wird hier der Programmablauf nach jedem Bildwechsel (frame) gestoppt. So kannst Du beobachten, wie sie die Kugel aufeinander zu bewegen. Betätigen des Buttons next aktiviert das Programm bis zum Ablauf des nächsten frames. Mit dem Schieberegler v2 kann die Geschwindigkeit der zweiten Kugel verändert werden.

Wer sich schon einmal mit der Quantentheorie befasst hat, dem dürfte dieses Thema bekannt vorkommen. Die Wahrscheinlichkeit, dass ein Objekt hinter einem Hindernis auftaucht, ist in der Nanowelt nicht gleich null. Dieser Effekt wird Tunnel-Effekt genannt.

on/off

Ergebnisdiskussion: Bei geringen Relativgeschwindigkeiten ist im oberen Experiment das gegenseitige Eindringen der Kugeln gut zu beobachten, während im unteren Experiment dank der Ortsprognose ein exaktes Berühren ohne Eindringen zu sehen ist.
Im oberen Experiment kann die fehlerhafte Kollisionserkennung so weit getrieben werden, dass eine Kollision überhaupt nicht mehr registriert werden kann, weil die diskreten Orte eine Kollision unmöglich machen. Wähle dazu eine Geschwindigkeit v₂ ≈ -30 m/s.

Etwas unübersichtlicher sieht die Prognoseerstellung beim dezentralen Stoß aus. Prinzipiell werden aber die gleichen Überlegungen wie oben angestellt. Die Vorhersage des Stoßortes führt auf eine interpretationsbedürftige Gleichung ():

()

t' = \frac{\pm \sqrt{(Δ {v_{x}}^{2} + Δ {v_{y}}^{2}) \cdot {(r_{1} + r_{2})}^{2} - {(Δ x \cdot Δ v_{y} - Δ y \cdot Δ v_{x})}^{2}} - (Δ x \cdot Δ v_{x} + Δ y \cdot Δ v_{y})}{Δ {v_{x}}^{2} + Δ {v_{y}}^{2}}

worin

Δ x = x_{2} - x_{1}

Δ y = y_{2} - y_{1}

Δ v_{x} = v_{x_{2}} - v_{x_{1}}

Δ v_{y} = v_{y_{2}} - v_{y_{1}}

bedeuten.

Interpretationsbedürftig, weil eine Quadratwurzel stets zwei Lösungen hat. Schauen wir uns dazu an. Daraus ist zu ersehen, dass sowohl vor, als auch nach dem Stoßort Kugelabstände, die genau unserer Bedingung 2r entsprechen, auftreten können (der Zustand nach dem Stoß ist dabei natürlich nur fiktiv, da ja nach dem Stoß die Bewegungen in andere Richtugen fortgesetzt werden). Die uns interessierende Zeit bis zum Stoß t' ist auf jeden Fall kleiner als die Zeit bis nach dem Stoß. Darum kommt nur die negative Wurzel für unsere weitere Verwendung in Frage. Um zu vermeiden, dass das Wurzelargument negativ wird - das kann bei großen Abständen auftreten - sollte auch dieser Zustand bei der Implementierung abgetestet werden.

Abb. Ortsberechnung mit Prognose des Stoßortes

Das Beispielprogramm erlaubt den Vergleich zwischen einer Kollisionserkennung mit und ohne Ortsprognose. Im Stoßmoment stoppt die Programmabarbeitung zum Zwecke einer optischen Kontrolle der Stoßsituation. Mit Betätigung des Buttons next wird das Programm fortgesetzt.
Du hast außerdem die Möglichkeit, vor Betätigung des START-Buttons per drag'n drop Ort und Startgeschwindigkeit beider Objekte zu verändern.

Ergebnisdiskussion: Die Wirkung der Ortsprognose für die Kollisionserkennung ist gut zu beobachten. Was besonders auffällt, sind deutlich unterschiedliche Bewegungen nach dem Stoß zwischen Standard-Kollisionserkennung und Erkennung mit Ortsprognose!

Symbol	Bedeutung
t	Zeit [s]
Δt	Zeitquant, Dauer zwischen den Bildwechseln [s]
t'	Zeit bis zum Zusammenstoß [s]
r	Objektradius [m]