Advanced Games Physics

Kollisionerkennung an Objekten, die als Image vorliegen

Kollisionserkennung an photorealistischen Objekten

So richtig schön wird ein Spiel erst dann, wenn die Akteure und die Objekte fotorealistisch sind! Deshalb soll am Beispiel der Kollision eines künstlichen Himmelskörpers mit einem Kometen (hier Vektorbasierte Verfahren für Polygone) gezeigt werden, wie eine Kollisionerkennung an Objekten, die als Image vorliegen, zu lösen ist.

Die Herausforderung besteht darin, dass jedes fotorealistisch dargestellte Objekt einen Doppelgänger in Form einer Polygonkontur benötigt. Das Image ist zum Anschauen da, die Kontur, um Kollisionen berechnen zu können. Dazu muss das Objekt, dessen Image als .bmp- oder .png-Datei vorliegt, digitalisiert werden. Und zwar so, dass Kontur und Image deckungsgleich und maßstäblich zur Anwendung passend sind.

Kontur-Erfassung eines Images

Wegen der erforderlichen hohen Präzission beim Erfassen einer Kontur verbietet sich das Arbeiten mit Geräten geringer Display-Auflösung. Eine Möglichkeit zur Digitalsierung einer Kontur auf der Grundlage eines Images wird in der Desktop-Version dieser Seite vorgestellt.

Für die Verwendung einer digitalisierten Kontur genügt es, diese als file verfügbar zu haben. zeigt die Datenstruktur des files contour.txt. Dieses wird in einen Folder namens data des aufrufenden Programms geladen.

Mit größter Sicherheit gibt es im Internet unzählige Programme, mit deren Hilfe Images digitalisiert werden können. Dennoch habe ich mich dazu entschieden, ein weiteres Programm zu schreiben. Dieses Programm liefert deckungs­gleiche und maß­stäbliche Kontur-Daten. Darüber hinaus werden für spätere Anwendungen die normierte Fläche der Kontur A', die Koordinaten des Flächen­schwerpunktes S(x0', y0') und das normierte Flächen­trägheits­moment J' bereit gestellt. Alle Daten sind so auf­bereitet, dass sie zwischen allen hier vor­gestell­ten Beispiel­programmen die auch zwischen meinen Programmen aus­getauscht werden können.

download processing
download p5.js
run program

Wegen der erforderlichen Präzission beim Erfassen einer Kontur, ist das Arbeiten mit der Maus zu empfehlen. Deshalb sind die folgenden Anweisungen für die Mausbenutzung verfasst!


So ist das Erfassungsprogramm zu handhaben:
  • Vorbereitung
  1. Lade das zu erfassende Image in den Ordner "data" des Erfassungsprogramms. Sinnvoller Weise liegt das Image als .png-File vor und ist so orientiert, dass seine größte Abmessung entweder in x- oder y-Richtung zeigt! Images, die anders orientiert vorliegen, sind mit Hilfe eines Grafikprogramms so zu drehen, dass die größte Abmessung der oben aufgestellten Forderung entspricht.

  2. Benenne das Image-File in "image.png" um.

  3. Starte das Erfassungsprogramm Grund_0050_digitize_Objects.pde (processing) oder pGrund_0050_digitize_Objects.js (p5.js).

    Für einfache Anwendungen, d.h. das Objekt ist fixiert, werden die Werte für Fläche, Trägheitsmoment und Schwerpunkt nicht benötigt. Darum kann das Erfassungs­programm in einer vereinfachten Form gestartet werden. Standardmäßig ist das Erfassungsprogramm auf die einfache Erfassung eingestellt. Andernfalls (z.B. wenn nichtzentrale Stöße an einem beweglichen Objekt dargestellt werden sollen) ist in Zeile 12 des Programmcodes in der p5.js-Version die Variable imageCenter statt mit "center" mit "gravity" zu laden.




Abb. Laden und Einrichten eines Image zur Konturerfassung


  • Programmausführung
  1. Suche die größte Abmessung. Fasse mit der Maus den grünen Knopf links oberhalb des rot gezeichneten Quadrats und verschiebe das Quadrat so, dass entweder die linke Seite des Quadrats an die äußerste linke Abmessung des Images (größte Abmessung ist parallel zur x-Achse) oder die obere Seite an den obersten Punkt des Images (größte Abmessung ist parallel zur y-Achse).

  2. Fasse nunmehr den rechten unteren grünen Knopf mit der Maus und passe das Quadrat so an, dass entweder der rechte Rand des Quadrates die äußerste rechte Abmessung des Images (größte Abmessung ist parallel zur x-Achse) oder der untere Rand die tiefste Abmessung (größte Abmessung ist parallel zur y-Achse) berührt. Diese Maßnahmen führen dazu, dass die erfasste Kontur auf den Wert 1 normiert wird. D.h. die Ausdehnung der größten Abmessung erscheint in der erfassten Kontur mit dem Wert 1.

  3. Verschiebe das Quadrat so, dass das Fadenkreuz mit dem Mittelpunkt des Images übereinstimmt. Auf diese Weise wird sicher gestellt, dass bei einer späteren Anwendung Image und Kontur wirklich deckungsgleich sind.

  4. Jetzt kann mit der Konturerfassung begonnen werden. Klicke mit der Maus charakteristische Konturpunkte des Images an. Dieser Punkt wird rot gekennzeichnet auf dem Image zu sehen sein. Erfasse so weitere Punkte. Aus ökonomischen Gründen sollte die Anzahl von Konturpunkten möglichst klein bleiben!

  5. Korrekturen, Löschungen oder Erweiterungen der Kontur sind immer möglich: Anfassen eines vorhandenen Punktes und verschieben ändert die Koordinaten dieses Punktes, Klicken auf eine Verbindungsline erzeugt an dieser Stelle einen neuen Konturpunkt. Anklicken mit der rechten Maustaste (processing) oder linke Maustaste + Shift (p5.js) löscht diesen Konturpunkt. Betätigen des Buttons "new" löscht die gesamte erfasste Kontur und eine komplette Neueingabe ist möglich!

  6. Mit dem Button "close" wird die Kontur geschlossen, wenn das Objekt ein Körper ist. In der Regel ist dies der Fall, dann wird der letzte Konturpunkt mit den Werten des ersten Konturpunktes geladen.

  7. Mit dem Kommado "close" werden die Koordinaten des Schwerpunktes S (blaus Kreuz), die Fläche A und das Flächen­trägheits­moment J berechnet.

  8. Zuletzt werden mit dem Button "save" die normierten Kontur­koordinaten P'i und die weiteren normierten Kenngrößen A', J' und die Orientierung "x" oder "y" der größten Abmessung im File "data/contour.txt" abgespeichert ().


Aufbau des Files contour.txt

Abb. Aufbau des Files contour.txt


Kollisionserkennung und -behandlung

Für die Kollisionserkennung und -behandlung selbst ist es unwichtig, wo der Mittelpunkt der Kontur positioniert ist. Für die Anwendung aber schon! Denn, erfolgt ein Stoß auf das Objekt, das durch das Image repräsentiert wird, so ist es entscheidend für die Bewegung nach dem Stoß, ob dieser zentral oder dezentral erfolgte. Über die Konsequenzen kannst Du näheres unter Behandlung des dezentralen, elastischen Stoßes bzw. Wechselwirkung von Stoß und Drehimpuls erfahren.
In diesem Kapitel ist diese Thematik noch nicht relevant. Darum wurde das Kontur­erfassungs­programm so eingestellt, dass auf Trägheitsmoment und Schwerpunkt verzichtet wird. Vielmehr betrachten wir das Objekt als fixiert, was bedeutet, dass uns der Imagemittelpunkt als Bezug genügt. Damit wird garantiert, dass Image und Kontur einen gemeinsamen Mittelpunkt haben. Damit beide auch noch deckungsgleich sind wird sowohl das Image mittels resize(polygonWidth, 0) auf die gewünschte Breite gebracht, aber auch die Kontur mit eben diesem Wert polygonWidth entnormiert ().



Abb. Laden einer Kontur aus einem file und Entnormierung

Hier ist ein Beispiel für eine Kontur, die von einem Objekt abgenommen wurde. Das Image und damit auch die Kontur werden als unbeweglich betrachtet. Stöße der Kugel an das Objekt führen daher nur zur Reflexion der Kugel.
In der Darstellung ist die Deckungsgleichheit zu erkennen. Mit dem Button show/hide kann die Kontur zum Image sichtbar/unsichtbar geschaltet werden.
download p5.js
run program

Kollision an Multi-Polygonen - Flipper

Das oben beschriebene Verfahren der vektoriellen Kollisionserkennung eignet sich besonders gut für die Implementierung der Kollision an Multi-Polygonen als class (processing) oder object (p5.js). Dadurch wird es möglich, komplexe Anordnungen von vielen Hindernissen zu modellieren. Ein klassisches Beispiel hierfür ist das Spiel FLIPPER. Für jedes Hindernis wird eine Instanz eröffnet. Für jedes Hindernis wird auf Kollision geprüft und für jedes Hindernis wird eine nachträgliche Korrektur des Stoßortes vorgenommen.
So weit so gut. Die Herausforderung für die Implementierung besteht beim FLIPPER aber darin, die verschiedenen Geometrien des Spieles geeignet zu erfassen und gleichzeitig einen ökonomischen, d.h. Rechenzeit optimierten, Ablauf zu ermöglichen.

Berücksichtigen der Geometrien bedeutet, unterschiedliche Bewegungsabläufe zu berücksichtigen:
  1. Startkanal: Fall unter Berück­sichtigung der Strömungs­reibung
  2. Oberer Halbkreis: Fadenpendel
  3. Spielfeld mit Hindernissen: Schräger Wurf unter Reibungs­einfluss und Kollisions­erkennung Kollisionserkennung mit nach­träglicher Korrektur des Stoß­ortes
  4. Reflexionsfreie Bewegung auf Hindernissen: Schiefe Ebene und
  5. Rücklaufkanal: Schiefe Ebene

Insbesondere der Übergang von 3. zu 4. ist nicht unproblematisch. Einziges Unterscheidungsmerkmal ist die Abfolge von Kollisionen: Solange die Kugel noch springt, liegt der Zustand nach 3. vor. Zwischen jeder Kollision gibt es kollisionsfreie Phasen. Im Gegensatz dazu finden im Zustand 4. stets Kollisionen ohne Pause statt. Dies machen wir uns als Kriterium für das Weiterschalten von 3. auf 4. zu nutze. Das setzt aber eine sehr zuverlässig funktionierende Ortskorrektur während der Kollision voraus!
Um die CPU-Last klein zu halten, wird das Spielfeld segmentiert. D.h. je nach Aufenthaltsort der Kugel werden bestimmte Segmente zur Kollisionserkennung aktiv geschaltet, während in den nichtaktiven Segmenten keine Kollisionserkennung durchgeführt wird.

Der hier implementierte Flipper hat eine sehr überschaubare Struktur und nur eine Bedienungsmöglichkeit, nämlich den Zug-Griff rechts unten am Spielfeld. Wird der Zug-Griff nach unten gezogen und dann losgelassen, wird die Kugel losgeschnippt. Je weiter Du nach unten ziehst, desto stärker die Kraft (zu erkennen an der Geschwindigkeitsanzeige rechts neben dem Spielfeld).
Mit dem Button "visible" können die Hindernisse und die Segmentierung des Spielfeldes sichtbar gemacht werden. Ebenso werden die Vektoren für die Kollisionserkennung angezeigt. Viel Spaß!

download processing
download p5.js
run program

Ergebnisdiskussion: Der Programmierer wird immer wieder vor besondere Herausforderungen gestellt. Hier ist es die unvollständige Approximation einer gleichmäßigen Rundung durch ein Polygon, z.B. am oberen Halbbogen oder an den Hindernissen. So approximierte Objekte haben keinen konstanten Radius! Das führt bei Kollisionsentscheidungen, die sich auf einen konstanten Radius beziehen (z.B. zum Verlassen des oberen Halbbogens), zu Fehlern. Diese Fehler zu vermeiden, müssen diesen Entscheidungen gewisse Toleranzen eingeräumt werden, die wiederum zu anderen Fehlentscheidungen führen können. Hier ist also durch sorgfältiges Ausprobieren ein Optimum zu finden.



Bewegung auf Polygonen

Fotorealistisch dargestellte Objekte werden zwecks mathematischer Behandlung oft als Polygonzug approximiert. Hier soll die Bewegung eines rollenden Balls auf einer Oberfläche untersucht werden, die als Polygon vorliegt.
Auch wenn die Bewegung eines Balls auf einem Polygon auf den ersten Blick nichts mit Kollisionen zu tun hat, so sind es die Werkzeuge der Kollisionserkennung, die hier zu Einsatz kommen. Die einzelnen Polygonsegmente können als schiefe Ebene angesehen werden. Dort aber, wo diese schiefen Ebenen mit ungleichen Neigungswinkeln zusammen stoßen, gibt es eine Ecke an der die Bewegung des Balls von einer Ebene zur anderen übergeht. Dort sind Ort s und Geschwindigkeit vs auf die neuen Gegebenheiten Neigungswinkel β und daraus folgend die effektive Beschleunigung g_ einzustellen.
Ecken spielen dabei eine besondere Rolle, da es bei konkaven Ecken zwei Kontaktpunkte und bei konvexen Ecken eine Diskontinuität gibt, an der die Bewegung des Balls - zumindest zeitweise - in einen schrägen Wurf übergeht. Auch liegt, wie bei der Kollisionserkennung, das Problem in der Diskretisierung der Zeit. Es müssen Korrekturmaßnahmen gefunden werden, die das genaue Erkennen der Ecken ermöglichen. Andernfalls kommt es zu ruckhaften Bewegungsabläufen und zu Verletzungen der Energie- bzw. Impulserhaltungssätze.

Polygone mit ausschließlich konkaven Ecken

Beginnen wir mit dem weniger komplizierten Fall eines Polygons, das nur konkave Ecken aufweist. Solange sich der Ball weit genug von diesen Ecken entfernt bewegt, ist die Welt in Ordnung und die Bewegung erfolgt nach den Gesetzen der schiefen Ebene. Zweckmäßiger Weise wird wieder das s-Koordinatensystem angewendet, was die Berechnung der Bewegung vereinfacht, weil die Darstellung des bewegten Objektes mittels der Matrix-Befehle erfolgt.
Die Probleme beginnen, wenn sich der Ball einer Ecke nähert und diese dann durchläuft. Wie in zu ersehen ist, kann der Ball nicht bis an das Ende der aktuellen Schräge mit der Länge lengthi rollen, da er bereits die nächste Schräge i+1 berührt. Bei konvexen Ecken gibt es immer zwei solche Berührungspunkte, die die betreffenden Schrägen um die Abstände limiter verkürzen. Mit anderen Worten, die Bewegung auf der Schrägen i endet an der um den Abstand limiter verminderten Segmentlänge lengthi und setzt sich auf der Schrägen i+1 am Punkt limiter beginnend fort (wenn Du Dir die Bewegung von links nach rechts ablaufend denkst).
Dies ist der erste Grund, weshalb über die Bewegung an den Ecken eines Polygons nachgedacht werden muss. Falsch wäre es, die Bewegung des Balles erst mit dem Erreichen der Segmentlänge auf dem aktuellen Segment zu beenden und bereits am Nullpunkt des anschließenden Segments fortzusetzen. Eine diskontinuierliche Bewegung wäre die Folge!

Ball in einer konkaven Ecke

Abb. Ball in einer konkaven Ecke


Berechnung der Bewegungsgrenzen zwischen zwei Segmenten
Abb. Berechnung der Bewegungsgrenzen zwischen zwei Segmenten
Wie aus hervor geht, liegen die Limiter-Punkte im gleichen Abstand links und rechts vom Knick- Punkt. Denkst Du Dir eine Verbindungsgerade zwischen Knick-Punkt und Ballmittelpunkt, so stellt diese die Hypotenuse von zwei rechtwinkligen Dreiecken dar. Der Ballradius r bildet die Ankatheten beider Dreiecke. Wegen der Symmetrie sind beide Dreiecke kongruent und schließen die Winkel 1 2 · | β i + 1 β i | ein. Worin die β die Neigungswinkel der aneinander stoßenden Segmente bezeichnen. Damit können nun die Werte für die limiter berechnet werden:
()
l i m i t e r i + 1 = r · tan 1 2 · | β i + 1 β i |
zeigt die Abfolge der Bewegungsbereiche bei einer von links nach rechts ablaufenden Bewegung. Der Ball startet seinen Weg s(t) auf dem Segment i bei einem beliebigen Startwert s0 mit der aktuell geltenden effektiven Beschleunigung g', dem Neigungswinkel β und der Anfangsgeschwindigkeit v0. Dabei ist stets zu prüfen, ob der Wert s t < l e n g t h i l i m i t e r i + 1 überschritten wird. Ist dies der Fall, muss das Segment i verlassen werden. Für die Fortsetzung der Bewegung auf dem Segment i+1 sind nun die neuen Bewegungsparameter, wie effektive Beschleunigung g', Neigungswinkel β zu verwenden. Die Startgeschwindigkeit v0 im neuen Segment ist gleich der Geschwindigkeit v(t) beim Verlassen des alten Segments. Und der Startort ist gleich dem Wert des aktuellen Limiters s0 = limiteri+1.

Grenzen der Bewegung zwischen zwei Segmenten

Abb. Grenzen der Bewegung zwischen zwei Segmenten

Das zweite zu lösende Problem wird wieder durch die Diskretisierung der Zeit hervor gerufen. Betrachten wir zunächst a. Der Weg s, den der Ball auf dem Segment i nimmt, ist auf diskrete Wegelemente Δ s = v · Δ t beschränkt (blaue Querstriche auf dem Weg). Δt ist wieder das Zeitincrement, das durch die Bildwechselrate fest vorgegeben ist, und v ist die momentane Geschwindigkeit des Balls. So ist es leicht verständlich, dass das Ende des Segments abzüglich des Limiters nie genau getroffen wird. Der letzte Schritt auf dem Segment i ist also entweder zu kurz oder er ragt über das Segment minus Limiter hinaus. Dem entgegen zu wirken setzen wir nun wieder das voraus schauende Prognose-Verfahren ein. Auf die hier vorliegenden Verhältnisse bedeutet dies:
  1. Berechnung der Zeitspanne bis zum exakten Erreichen des Limiter-Punktes auf dem Segment i:
    ()
    Δ t r i g h t = l e n g t h i l i m i t e r i + 1 s v
  2. Berechnung der Endgeschwindigkeit an diesem Punkt. D.h. Die Differentialgleichung für die Geschwindigkeit ist jetzt mit dem verkürzten Zeitincrement Δright zu berechnen. Der Index right in Δright bedeutet, dass das verbleibende Zeitintervall rechts vom letzten regulären Zeitintervall steht, also nur für Bewegungen von links nach rechts gilt.
    Die so berechnete Endgeschwindigkeit ist gleich der Startgeschwindigkeit v0 für die Bewegung auf dem Segment i+1.
    ()
    v = v + g · Δ t r i g h t
    (Hier wird allerdings nur eine Abschätzung mit Hilfe des ungenaueren EULER-CAUCHY-Algorithmus zum Ende des aktuellen Segments vorgenommen.)
  3. Setzen des Startorts s0 auf dem neuen Segment. Dieser Ort geht zunächst vom Limiter aus, muss aber noch durch die Bewegung des Balls im restlichen Zeitintervall erweitert werden:
    ()
    s 0 = l i m i t e r i + 1 + v · Δ t Δ t r i g h t
    Im Programm wird für dies eine Zeitintervall das üblicherweise verwendete Increment dt um den Betrag dtright vermindert und nach dem Segmentübergang einmalig als Zeitincrement verwendet. So wird der Restweg des aktuellen Zeit-Intervalls im neuen Segment berechnet. Danach wird sofort dt = 1/frmRate wieder hergestellt.


Eckenübergang bei Bewegung von links nach rechts
Abb. a Eckenübergang bei Bewegung von links nach rechts

Eckenübergang bei Bewegung von rechts nach links
Abb. b Eckenübergang bei Bewegung von rechts nach links

b gilt analog für Bewegungen von rechts nach links. Wobei allerdings der Startort auf dem links liegenden Segment i
()
s 0 = l e n g t h i - 1 l i m i t e r i + v · Δ t Δ t l e f t
wobei
()
Δ t l e f t = s l i m i t e r i v
vom Ende dieses Segments aus gerechnet werden muss. Wegen der Bewegung von rechts nach links ist v negativ, daher ist der Restweg zu addieren!
Die Endgeschwindigkeit im aktuellen Segment ist gleich der Startgeschwindigkeit v0 für die Bewegung auf dem Segment i-1.
()
v = v + g · Δ t l e f t
(Auch hier wird für die Lösung der Bewegungs-DGl nur eine Abschätzung mit Hilfe des ungenaueren EULER-CAUCHY-Algorithmus zum Ende des aktuellen Segments vorgenommen.)


 Flowchart der Bewegungsberechnungen
Abb. Flowchart der Bewegungs­berechnungen


Die State-machine sieht für den vorliegenden Fall noch sehr einfach aus. Da die Kontur vereinbarungsgemäß nur aus Segmenten besteht, die an ihren Grenzen konkaven Ecken bilden, besteht die kritische Aufgabe nur in der genauen Feststellung eines Segmentwechsels. Während des Status "onGround" gelten die Gesetze der schiefen Ebene. Wegen der unterschiedlichen Steigungen der einzelnen Segmente herrschen unterschiedliche Hangabtriebskräfte vor, deren Werte aber vorab schon bekannt sind. Solange kein Segmentende (2) prognostiziert ist, bleibt der Status "onGround" (1) erhalten. Erst am Segmentende machen sich die Berechnungen von Startort und -geschwindigkeit für das neue Segment erforderlich. Dazu werden die oben beschriebenen Prognoseverfahren heran gezogen. Besondere Beachtung verdient hierbei die Richtungsinformation der Geschwindigkeit v, weil bei einer Bewegung nach rechts der Startort am Segmentanfang, andernfalls am Segmentende liegt.

Im Programmbeispiel wird der rollende Ball so plaziert, dass im Bereich der Bewegung nur konkave Ecken auftreten. Zur Demonstration der Wirksamkeit der Korrekturmaßnahmen werden die Standardlösung und die Lösung mit Korrekturmaßnahmen gegenüber gestellt. Um die Unterschiede deutlich zu machen, unterliegt die Bewegung keinerlei Reibungseinfluss.
Nach dem Aufruf und dem Start des Programmbeispiels wird die Bewegung des Balls ohne Korrekturmaßnahmen gezeigt. Der Button Korr/NoKorr erlaubt das Umschalten in den Korrekturmodus. Nach Umschaltung ist der Bewegungsablauf erneut zu starten. Weiterhin kann mit dem Button Shape zwischen zwei Konturen gewählt werden.
Um den Nachweis der energetischen Treue der verwendeten Algorithmen zu erbringen, wird hier der genauere Runge-Kutta-Solver zur Lösung der Bewegungsgleichungen eingesetzt. Zur Überprüfung der energetischen Treue wird die Gesamenergie Wges angezeigt. Zwecks detailierter Bewegungsstudien gibt es einen Debug-Modus, in dem die Bewegung Schritt weise abgearbeitet werden kann. Zur optischen Orientierung werden die Limiter als Marken auf dem Weg eingeblendet.
download p5.js
run program

Ergebnisdiskussion: Im Bewegungsmodus ohne Korrektur sind deutlich die Unstetigkeiten der Bewegung an den konkaven Ecken zu beobachten. Auch gibt es starke Schwankungen der Gesamtenergie Wges, obwohl insgesamt keine Änderungen außerhalb der Schwankungsbreite auftreten.
Anders im Korrektur-Modus. Hier verläuft die Bewegung im Übergang von einem Segment zum nächsten (oder vorhergehenden) flüssig und ruckelfrei. Auch die Schwankungen der Gesamtenergie Wges sind sehr klein. Allerdings akkumulieren sich die Energie-Fehlbeträge, so dass es zu einem fehlerhaften Energiezuwachs kommt. In der Praxis, unter dem Einfluss von Reibungseffekten, dürfte das aber keine Rolle spielen. Hier überwiegt der Nutzen einer gleichmäßigen Bewegung!
Noch eine Bemerkung zur Programm-Ökonomie: Alle geometrischen Vorgaben, die Konturelemente betreffend, sind feststehend. Deshalb ist es zweckmäßig, daraus abgeleitete Größen wie Neigungswinkel βi, Segmentlänge lengthi, gewichtete Gravitationskonstante g_i oder Limiter limiteri vorab in der setup()-Funktion zu berechnen. So stehen diese Werte in der draw()-Funktion unmittelbar und ohne Rechenaufwand zur Verfügung.

Allgemeine Polygone bei geringen Objektgeschwindigkeiten

Hier werden Bewegungen auf Polygonen mit konkaven und konvexen Ecken bei geringen Geschwindigkeiten untersucht. Die Beschränkung auf geringe Objektgeschwindigkeiten bedeutet, dass das Objekt an konvexen Ecken nicht abhebt, sondern über diese Ecke abrollt. Eine Testung auf eine Loslösung des Objektes vom Untergrund kann also entfallen!

Die Bewegung auf Polygonen mit konvexen Ecken führt auf zwei unterschiedliche Bewegungsmodi:
  1. Bewegung des Balls auf den Segmenten einschließlich der konkaven Ecken. Dies ist eine beschleunigte Bewegung im s-Koordinatensystem der schiefen Ebene und
  2. bei geringen Geschwindigkeiten rollt der Ball über konvexen Ecken ohne den Boden zu verlassen. Dies ist eine beschleunigte rotatorische Bewegung im φ - r-Koordinatensystem in Polarkoordinaten.

Im Gegensatz zu einem Profil mit ausschließlich konkaven Ecken, wo nur Geradenstücke d.h. Segmente aneinander gefügt werden, gibt es bei den konvexen Ecken einen Kreissektor zwischen den benachbarten Segmenten, der durch eine rotatorische Bewegung um die betroffene Ecke ausgefüllt werden muss. Das Betreten dieses Bereiches ist nicht mit einem Segmentwechsel verbunden. Trotzdem ist eine Parameterübergabe beim Betreten und auch beim Verlassen dieses Kreissektors erforderlich.

Treten konvexe Ecken auf, endet bzw. beginnt die geradlinige Bewegung auf den Segmenten i bzw. i+1 direkt an den Segmentgrenzen. Assoziiert mit den Segmentgrenzen sind die Normalen (in rote, gestrichelte Linien), zwischen denen der eingeschlossene Kreissektor liegt. Auch hier sind die Normalenwinkel φlinks und φrechts bekannt, da sie wie die anderen Konturparameter in der Setup()-Funktion vorab berechnet werden können.
Wie schon erwähnt, handelt es sich bei der Bewegung des Balls auf der Ecke um eine Drehbewegung des Ballmittelpunktes centerBall um den Eckpunkt Pi. Beim Übergang von geradliniger Bewegung zur Drehbewegung wird die Geschwindigkeit vs in die der Winkelgeschwindigeit ω der Drehbewegung umgerechnet:
()
ω = v s r B a l l

Bewegung auf konvexer Ecke
Abb. Bewegung über eine konvexe Ecke

Umgekehrt wird über die selbe Beziehung die Geschwindigkeit der linearen Bewegung aus der der Drehbewegung berechnet.

Innerhalb der Drehbewegung gilt die Differentialgleichung für die beschleunigte Drehbewegung (ohne Reibungseinfluss):
()
φ · · = g · cos φ r B a l l
Und der zugehörige Startwinkel ist abhängig von der Bewegungsrichtung gleich
()
φ = { φ l wenn ω < 0 (Bewegung nach rechts) φ r wenn ω 0 (Bewegung nach links)
Beachte! in p5.js und auch in processing ist die positive Drehrichtung entgegen der mathematischen orientiert!

Soweit so gut, die eigentliche Schwierigkeit besteht aber darin, die Grenzen zwischen den einzelnen Zuständen sicher und möglichst genau zu erkennen. Denn, wie bereits im vorherigen Abschnitt (Polygone mit ausschließlich konkaven Ecken) ausgeführt, verhindert die zeitliche Diskretisierung eine genaue Bestimmung des Objektstandorts. Darum muss auch bei der Bewegung auf der Ecke mit einem Prognoseverfahren analog zu bis gearbeitet werden:
(a)
Δ t r i g h t = | φ r φ ω |
bzw.
(b)
Δ t l e f t = | φ l φ ω |
So können bei jedem Übergang, egal ob von Segment zu Segment oder von Segment zu Ecke bzw. umgekehrt, Ort und Geschwindigkeit so berechnet werden, als würde das aktuelle Zeitfenster exakt an diesem Übergang enden oder beginnen. Das gewährleistet eine weitgehende Erhaltung der Energiebillanz.
Die Geschwindigkeit zum Ende des begonnenen Intervalls beim Übergang von der Drehbewegung zur Bewegung auf dem nächsten Segment wird wieder mit Hilfe des einfachen EULER-CAUCHY-Algorithmus abgeschätzt:
(a)
ω = ω + g · cos φ r B a l l · Δ t r i g h t
bzw.
(b)
ω = ω + g · cos φ r B a l l · Δ t l e f t
für die Gegenrichtung.
Beim Übergang von der Drehbewegung zur Bewegung auf einem Segment muss die Winkelgeschwindigkeit ω in die der schiefen Ebene v umgerechnet werden. Das erfolgt analog zu . Schließlich ist noch der Startort auf dem aktuellen Segment zu bestimmen, dies erfolgt wieder analog zu bzw. .

Die vorliegende State-machine basiert natürlich auf der vom vorangegangenen Beispiel () bekannten Lösung. Da nunmehr auch konvexe Ecken zugelassen sind, muss der Flowchart um den Zweig 3 erweitert werden. Sofern eine konkave Ecke vorliegt, erfolgt die Berechnung der Parameterübergabe wie gehabt über den Zweig 2 und der Status bleibt unverändert "onGround". Anders, wenn eine konvexe Ecke vorliegt. Dann erfolgt die Parameterübergabe an die Bewegungsgleichungen für die rotatorische Bewegung auf der Ecke (4) und der Status wird in "onEdge" geändert. In diesem Zustand 5 verbleibt die State-machine, bis das Ende der Bewegung auf der Ecke prognostiziert wird. Dann erfolgt die Berechnung der an die schiefe Ebene zu übergebenden Bewegungs-Parameter und die Bewegung wird auf dem anschließenden Segment fortgesetzt.

 Flowchart der Bewegungsberechnungen
Abb. Flowchart der Bewegungsberechnungen


Bewegungen auf Polygonen, die aus schiefen Ebene einschließlich der konkaven Ecken bestehen, wurde im Kapitel Polygone mit ausschließlich konkaven Ecken ausführlich behandelt. Mit dem Hinzutreten auch konvexer Ecken verkompliziert sich der Status-Baum ().

Konkave und konvexe Ecken wechseln sich ab oder folgen mehrfach aufeinander. Mit Hilfe des Buttons Game können unterschiedliche Anfangsbedingungen und unterschiedliche Konturen gewählt werden. So können verschiedene Bewegungsszenarien mit unterschiedlichen Anfangsbedingungen (Startort und -geschwindigkeit) überprüft werden.
Bewusst wird wieder auf die Anwendung irgendwelcher Reibungseinflüsse oder das Bouncing verzichtet, um die Korrektheit der Implementierung transparent machen zu können. Sollten Dir die vorgegebenen Konturen nicht genügen, kannst Du in dem inkludierten Programm contours.js weitere Konturen hinzufügen oder verändern. Allerdings sind Konturen mit senkrechten Segmenten Tabu!
Zum Feinstudium der Bewegungsabläufe gibt es noch den debug-Modus, in dem Du schrittweise die Bewegungen studieren kannst.
download p5.js
run program

Ergebnisdiskussion:
Auch bei dieser Lösung gibt es Unstimmigkeiten bei der energetischen Billanz über den gesamten Spielraum. Hauptursache hierfür sind fehlerhafte Parameterübergaben an den Ecken infolge der Zeitdiskretisierung. Solche Fehler dürften aber bei Berücksichtigung diverser Reibungsverluste kaum ins Gewicht fallen.
Zur Vollständigen Lösung einer Aufgabe dieses Problemkreises wäre die Einführung von Reibung und Bouncing sinnvoll.



Allgemeine Polygone

Hier werden wir das Projekt mit Bouncing und darum mit Reibungseinfluss entwickeln. Dies ermöglicht die umfassende und natürliche Bewegung auf beliebig gestalteten Untergründen.

Die Bewegung auf Polygonen mit konvexen Ecken führt im Allgemeinen auf drei unterschiedliche Bewegungsmodi:
  1. Bewegung des Balls auf den Segmenten einschließlich der konkaven Ecken. Dies ist eine beschleunigte Bewegung im s-Koordinatensystem der schiefen Ebene,
  2. bei geringen Geschwindigkeiten rollt der Ball über konvexen Ecken ohne den Boden zu verlassen. Dies ist eine beschleunigte rotatorische Bewegung im φ - r-Koordinatensystem in Polarkoordinaten und
  3. bei größeren Geschwindigkeiten hebt der Ball an den konvexen Ecken ab. Damit beginnt eine Bewegung nach den Gesetzen des schrägen Wurfs im x - y-Koordinatensystem.

Gegenüber den bisher behandelten Fällen ist nunmehr eine Entscheidung über den Bewegungsmodus an konvexen Ecken erforderlich. veranschaulicht die zwei möglichen Fälle:
  1. Der Ball rollt langsam auf die konvexe Ecke zu (dunkelblauer Geschwindigkeitsvektor und gestrichelte Bewegungspfad). Würde jetzt auf den Status "onFlight" geschaltet, beschriebe der Ball eine Flugbahn, bei der Ball unter das folgende Segment fallen würde. Also rollt der Ball in diesem Fall über die Ecke.
  2. Der Ball rollt hinreichend schnell auf die konvexe Ecke zu (hellblauer Geschwindigkeitsvektor und strich-gepunkteter Bewegungspfad). Jetzt genügen die Geschwindigkeitskomponenten, die an der Segmentgrenze aus der Bewegung auf der schiefen Ebene übergeben worden sind, um eine Flugbahn zu erzeugen, die außerhalb des Abrollkreises liegt. Damit ist der schräge Wurf möglich und der Ball springt (fliegt) über die Ecke.
Nun benötigen wir ein Kriterium, nach dem die Entscheidung roll or flight getroffen werden kann. Aus mathematischer Sicht wäre die Berechnung des Schmiegekreises der Wurfparabel sinnvoll. Ist nämlich der Radius des Schmiegekreis kleiner als der Ballradius, läge der erste Fall vor sonst der zweite. Da wir aber alle Bewegungen unter Reibungseinfluss berechnen wollen, steht uns die Parabelgleichung explizit nicht zur Verfügung. Daher habe ich einen pragmatischen Weg gewählt: Es wird für die vorliegenden Parameter der Aufenthaltsort des Balls im nächsten Zeitfenster prognostiziert. Liegt nun der Ballmittelpunkt innerhalb des Abrollkreises, dann liegt der erste Fall vor und Berechnung wird mit dem Status "onEdge" fortgesetzt. Andernfalls wird der Status "onFlight" eingeschaltet. In beiden Fällen wird der prognostizierte Ort nachträglich verworfen.

Abrollen oder Springen über die Ecke
Abb. Roll or Flight?


Für die Ausführung der flight-Phase steht uns der mathematische Apparat des schrägen Wurfs zur Verfügung. Und für die Landung des Balls auf dem Grund, egal, ob Segment oder Ecke, gibt es die oben beschriebene Kollisionserkennung mit nachträglicher Korrektur. Die dazu erforderlichen Includes findest Du im Ordner "p5_includes/pCollision_v3.0".
Wie bereits erwähnt werden alle Bewegungen unter Reibungseinfluss betrachtet. D.h. auch das Bouncing unterliegt einem Energie-Verlust. Dieser wird in x- bzw. y-Richtung unterschiedlich durch die Variablen bouncingGainX bzw. bouncingGainY berücksichtigt. Der damit verbundene stetige Energieabbau führt dazu, dass das Bouncing endlich ist und die Bewegung des Balls wieder in die Bewegung auf der schiefen Ebene übergehen kann.

Die in gezeigte state-machine stellt - unschwer zu erkennen - eine Erweiterung von dar. Hinzugekommen ist die Abfrage im Zustand 1 (rollOrFlight), die im Zustand 2 die Übergabe der Bewegungsparameter an die Flug-Phase und den Flug (3) selbst ausführt. Findet eine Bodenberührung statt, erfolgt eine Reflexion des Balls (Bouncing). Dabei wird geprüft, ob die Energie für ein weiteres Bouncing ausreicht (4). Ist das nicht der Fall, werden die Bewegungsparameter für eine Bewegung "onGround" bereitgestellt und die Bewegung auf der schiefen Ebene fortgesetzt.

 Flowchart der Bewegungsberechnungen incl. buncing
Abb. Flowchart der Bewegungsberechnungen



Dieses Beispielprogramm zeigt die gesamte Palette der Aufgabenstellung. Konkave und konvexe Ecken wechseln sich ab und das Bouncing ist möglich. Allerdings würde das Bouncing ohne Reibungseinfluss niemals aufhören. Darum wird nun auch der Reibungseinfluss berücksichtigt. Weil aber die Rollreibung und auch die Aufprallverluste beim Bouncing größere Einflüsse haben als die Strömungsreibung, wird auf die Implementierung letzterer verzichtet! Mit Hilfe des Buttons shape können unterschiedliche Untergründe gewählt werden. Sollten Dir die vorgegebenen Konturen nicht ausreichen, kannst Du in dem inkludierten Programm contours.js weitere Konturen hinzufügen oder verändern. Allerdings sind Konturen mit senkrechten Segmenten Tabu!
Zum Feinstudium der Bewegungsabläufe gibt es noch den debug-Modus, in dem Du schrittweise die Bewegungen studieren kannst.
download p5.js
run program

Ergebnisdiskussion:
Die vorliegende Lösung kommt den Erfordernissen eines natürlichen Bewegungsverlaufs sehr nahe. Die größten Schwierigkeiten bei der Implementierung sind auf die Folgen der Zeitdiskretisierung zurück zu führen. Allerdings fallen energetische Fehler wegen der Einführung von Reibungseffekten kaum ins Gewicht.
Bouncing gehört unbedingt zu einem natürlichen Bewegungsablauf und wird darum auch zugelassen.