Bewegung mit Kollisionserkennung Teil 2

Posted: 4th Februar 2011 by xaedes in Kaufhausschlacht
2

Teil 1 – Einführung
Teil 2 – Kollision mit Gerade
Teil 2 – Kollision mit Gerade – Demoprogramm
Teil 3 – Kollision mit Strecke
Teil 3 – Kollision mit Strecke – Demoprogramm

Übersicht:

  1. Rechenweg
  2. Quellcode und Demo

So jetzt wissen wir was wir brauchen. Damit fangen die Berechnungen auch schon an. Zusätzlich brauchen wir aber noch den Lot von der Begrenzungslinie zu den beiden Zielpunkten z und z‘. Der Lot zu z‘ sollte eine Länge von r, also dem Radius des Figurenkreises haben, damit die Figur die Begrenzungslinie gerade so nicht überschreitet. Die Länge des Lotes zu z bezeichnen wir mit d.

Das führt uns zu folgender Skizze des zu Grunde liegenden mathematischen Problemes:

Die gepunktete Seite unter der Geraden g ist der abzugrenzende Bereich.

Nochmal eine Zusammenfassung aller Variablen:

s Startpunkt
v Bewegungsvektor
z unkorrigierter Zielpunkt
z‘ korrigierter Zielpunkt
r Radius der Figur
d Abstand des unkorrigierten Zielpunktes zur Begrenzungskante
x Abstand des unkorrigierten Zielpunktes zum korrigierten Zielpunkt
g Gerade, die von p_{L1} und p_{L2} aufgespannt wird
h Gerade, die von s und v aufgespannt wird
\alpha Winkel zwischen den Geraden g und h
n_{g} Normale zur Geraden g
n_{h} Normale zur Geraden h
p_1 Schnittpunkt des Lotes mit dem korrigierten Zielpunkt
p_2 Schnittpunkt des Lotes mit dem unkorrigierten Zielpunkt
p_{L1} Erster Endpunkt der Begrenzungskante
p_{L2} Zweiter Endpunkt der Begrenzungskante

Wichtig ist dabei noch zu erwähnen, dass die Endpunkte der Begrenzungskanten einer BoundingBox gegen den Uhrzeigersinn angegeben werden müssen. Damit können wir an Hand der Normale der Begrenzungskante bestimmen, ob ein Punkt außerhalb der BoundingBox oder innerhalb liegt. Wenn die Punkte richtig angegeben sind zeigt die Normale nach außen wie in der Skizze zu sehen ist.

Achtung Fehlerquelle !!!

In der Computergrafik ist das Koordinatensystem normalerweise kopfüber gezeichnet, so dass die linke obere Ecke des Zeichenbereichs den Koordinatenursprung bildet und die Achsen nach rechts und nach unten verlaufen. Auf Grund dessen ändert sich hier die Reihenfolge in der die Kanten angegeben werden müssen. Bei seltsamen Ergebnissen, sollte man überprüfen, ob man hierauf geachtet hat.


Nun zum Rechenweg
gegeben: \\ s, \overrightarrow{v}, p_{L1}, p_{L2}\\ gesucht: \\ z'\\

Der korrigierten Zielpunkt z‘ kann berechnet werden indem vom unkorrigierten Zielpunkt z der auf Länge x skalierte Bewegungsvektor \overrightarrow{v} abgezogen wird:
z'=z-\frac{x\cdot \overrightarrow{v}}{|\overrightarrow{v}|} \\

Offensichtlich wird also der Wert von x benötigt. Anhand der Skizze ist zu erkennen, das x die Hypotenuse des durch z, z‘ und \alpha aufgespannten rechtwinkligen Rechteckes ist. Es gilt also folgende Beziehung:
r-d = sin(\alpha)\cdot x \\ x= \frac{r-d}{sin(\alpha)} \\

Der Sinus von \alpha kann über den Kosinus von \alpha berechnet werden, welcher über das Skalarprodukt zweier Vektoren, die die Richtung der beiden Geraden g und h darstellen, berechnet wird:
sin(\alpha)=\sqrt{1-cos^2(\alpha)} \\ \\ cos(\alpha)=\frac{\overrightarrow{v} \cdot (\overrightarrow{p_{L2}}-\overrightarrow{p_{L1}})} {|\overrightarrow{v}| \cdot | \overrightarrow{p_{L2}}-\overrightarrow{p_{L1}} |} \\ \\ \\

Weiterhin muss noch der Abstand d des unkorrigierten Zielpunktes z zur Geraden g berechnet werden.

d=(\overrightarrow{z}-\overrightarrow{p_{L2}}) \cdot \overrightarrow{n_{g,0}} \\
Eigentlich ist das nicht wirklich der Abstand, da nicht der Betrag, sondern ein vorzeichenbehafteter Wert übernommen wird. Hier ist die Orientierung der Normale der Geraden g wichtig. Sollte z außerhalb des von der Begrenzungskante begrenzten Bereiches liegen, ist dieser Wert positiv, sollte er innerhalb liegen, ist er negativ. Sollte dies der Fall sein ergibt sich folgende Situation:

Da d negativ ist, gilt weiterhin folgende Beziehung:
x= \frac{r-d}{sin(\alpha)} \\ \\ \\ x= \frac{r+|d|}{sin(\alpha)} \\

Die Normale einer Gerade in der Ebene (also in 2D) wird einfach durch den Richtungsvektor der Gerade berechnet:
\overrightarrow{n_{g,0}} = \frac{n_{g}}{|n_{g}|} \\ \overrightarrow{n_{g}} = \begin{pmatrix}p_{L1}.y - p_{L2}.y \\ p_{L2}.x - p_{L1}.x \end{pmatrix} \\

Damit lassen sich alle benötigten Werte auf bekannte Werte zurückführen und die korrigierte Zielposition z‘ kann ausgerechnet werden.

Da die Begrenzungskante nicht alleine ist, sondern zusammen mit anderen Kanten einen Bereich abgrenzt, wollen wir nur die Kollision von einer Seite der Kante aus betrachten. Es könnte sonst zu ungewollten Ergebnissen kommen wie hier dargestellt:

Wenn die rote Linie zuletzt verarbeitet würde, würde die „korrigierte“ Zielposition z‘ immer noch falsch sein. Wirklich korrekte Positionen werden wie hier durch den grünen Kreis z`` nur durch Kollisionen mit Linien aus der richtigen Richtung (in den abgrenzenden Bereich hinein) erzeugt.
Es muss also überprüft werden, ob die Bewegung auf die Kante zu geht oder von ihr weg. Dazu folgende Skizze:

Die blaue Gerade h‘ führt in den abgegrenzten Bereich hinein und die rote Gerade von ihm weg.
Um herauszufinden welcher Fall für die aktuelle Gerade h eingetreten ist, berechnen wir den vorzeichenbehafteten Abstand d_h und überprüfen das Vorzeichen. Nur Geraden mit negativen Werten müssen beachtet werden.
d_h = \overrightarrow{v} \cdot \overrightarrow{n_{g,0}}


Demo und Quellcode

Wer das alles einfach mal ausprobieren will, oder ein wenig Quellcode dazu sehen will, dem empfehle ich mein Demoprogramm hierzu anzuschauen :
Demonstrationsprogramm zu diesem Teil

Allerdings ist es damit noch nicht getan, denn es gibt Situationen wo dieser einfache Ansatz nicht ausreicht. Momentan behandeln wir die Begrenzungskante nämlich als Gerade und nicht als begrenzte Strecke mit Start- und Endpunkt. Das Demoprogramm verdeutlicht dies noch einmal.

Was dazu beachtet werden muss zeige ich im nächsten Teil.

  1. Bewegung mit Kollisionserkennung Teil 1 « Was mir so einfällt sagt:
    4. Februar 2011 um 12:55 Uhr

    […] Bewegung mit Kollisionserkennung Teil 2 […]

  2. Bewegung mit Kollisionserkennung Teil 2 – Demonstrationsprogramm « Was mir so einfällt sagt:
    4. Februar 2011 um 20:24 Uhr

    […] Bewegung mit Kollisionserkennung Teil 2 […]