2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
(→Verdrehte Gerade) |
K (Anpassung für MathJax) |
||
| (14 dazwischenliegende Versionen von 5 Benutzern werden nicht angezeigt) | |||
| Zeile 165: | Zeile 165: | ||
Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (<math>P_a = P_b</math>), bekommt man folgende Gleichungen für <math>x</math> und <math>y</math> der Punkte <math>P_a</math> und <math>P_b</math>: | Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (<math>P_a = P_b</math>), bekommt man folgende Gleichungen für <math>x</math> und <math>y</math> der Punkte <math>P_a</math> und <math>P_b</math>: | ||
| − | : <math> | + | : <math>\begin{align} x_{A_1} + u_a(x_{A_2} - x_{A_1}) & = x_{B_1} + u_b(x_{B_2} - x_{B_1}) \\ y_{A_1} + u_a(y_{A_2} - y_{A_1}) & = y_{B_1} + u_b(y_{B_2} - y_{B_1}) \end{align} </math> |
| − | \begin{align} | + | |
| − | x_{A_1} + u_a(x_{A_2} - x_{A_1}) & = x_{B_1} + u_b(x_{B_2} - x_{B_1}) \\ | + | |
| − | y_{A_1} + u_a(y_{A_2} - y_{A_1}) & = y_{B_1} + u_b(y_{B_2} - y_{B_1}) | + | |
| − | \end{align} | + | |
| − | </math> | + | |
Diese Gleichungen werden nun nach <math>u_a</math> und <math>u_b</math> aufgelöst: | Diese Gleichungen werden nun nach <math>u_a</math> und <math>u_b</math> aufgelöst: | ||
| − | : <math> | + | : <math>\begin{align} u_a & = \frac{(x_{B_2} - x_{B_1})(y_{A_1} - y_{B_1}) - (y_{B_2} - y_{B_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \\ u_b & = \frac{(x_{A_2} - x_{A_1})(y_{A_1} - y_{B_1}) - (y_{A_2} - y_{A_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \end{align}</math> |
| − | \begin{align} | + | |
| − | u_a & = \frac{(x_{B_2} - x_{B_1})(y_{A_1} - y_{B_1}) - (y_{B_2} - y_{B_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \\ | + | |
| − | u_b & = \frac{(x_{A_2} - x_{A_1})(y_{A_1} - y_{B_1}) - (y_{A_2} - y_{A_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} | + | |
| − | \end{align} | + | |
| − | </math> | + | |
Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind <math>u_a</math> und <math>u_b</math> undefiniert, also sind die beiden Geraden parallel zueinander. Wenn die Geraden dann nicht identisch sind, liegt keine Kollision vor. Der Einfachheit halber ignorieren wir den Fall der identischen Geraden und geben "''keine Kollision''" aus. Beim Rechnen mit Fließkommazahlen muss beachtet werden, dass ein Vergleich mit Null auf Grund von Rechenungenauigkeiten nicht empfehlenswert ist. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante <code>EPSILON</code> dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. <math>10^{-8}</math>. | Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind <math>u_a</math> und <math>u_b</math> undefiniert, also sind die beiden Geraden parallel zueinander. Wenn die Geraden dann nicht identisch sind, liegt keine Kollision vor. Der Einfachheit halber ignorieren wir den Fall der identischen Geraden und geben "''keine Kollision''" aus. Beim Rechnen mit Fließkommazahlen muss beachtet werden, dass ein Vergleich mit Null auf Grund von Rechenungenauigkeiten nicht empfehlenswert ist. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante <code>EPSILON</code> dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. <math>10^{-8}</math>. | ||
| Zeile 258: | Zeile 248: | ||
const float ub = ((a2.x - a1.x) * (a1.y - b1.y) - | const float ub = ((a2.x - a1.x) * (a1.y - b1.y) - | ||
(a2.y - a1.y) * (a1.x - b1.x)) / denom; | (a2.y - a1.y) * (a1.x - b1.x)) / denom; | ||
| − | return ua >= 0 && ua <= 1 && ub >= 0 && | + | return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1; |
} | } | ||
</sourcecode> | </sourcecode> | ||
| Zeile 278: | Zeile 268: | ||
float ub = ((a2.x - a1.x) * (a1.y - b1.y) - | float ub = ((a2.x - a1.x) * (a1.y - b1.y) - | ||
(a2.y - a1.y) * (a1.x - b1.x)) / denom; | (a2.y - a1.y) * (a1.x - b1.x)) / denom; | ||
| − | return ua >= 0 && ua <= 1 && ub >= 0 && | + | return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1; |
} | } | ||
</sourcecode> | </sourcecode> | ||
| Zeile 297: | Zeile 287: | ||
ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | ||
(a2[1] - a1[1]) * (a1[0] - b1[0])) / denom | (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom | ||
| − | return ua >= 0 and ua <= 1 and ub >= 0 and | + | return ua >= 0 and ua <= 1 and ub >= 0 and ub <= 1 |
</sourcecode> | </sourcecode> | ||
}} | }} | ||
| Zeile 316: | Zeile 306: | ||
float ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | float ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | ||
(a2[1] - a1[1]) * (a1[0] - b1[0])) / denom; | (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom; | ||
| − | return ua >= 0 && ua <= 1 && ub >= 0 && | + | return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1; |
} | } | ||
</sourcecode> | </sourcecode> | ||
| Zeile 324: | Zeile 314: | ||
=== Kollision zwischen einem Kreis und einer Geraden === | === Kollision zwischen einem Kreis und einer Geraden === | ||
| − | [[Datei:Kollision kreis senkr-gerade.gif|miniatur|Veranschaulichung des Idealfalls mit senkrechter Geraden]] | + | ==== Genereller Ansatz ==== |
| + | |||
| + | Der im Folgenden beschriebene Ansatz arbeitet mit Vektoren und funktioniert für beliebige Dimensionen (2D: Gerade und Kreis, 3D: Gerade und Kugel). Der Kreis habe den Mittelpunkt mit dem Ortsvektor <math>\vec c</math> und den Radius <math>r</math>. Dann lautet die Gleichung für die Ortsvektoren <math>\vec x</math> der Punkte auf dem Kreis: | ||
| + | |||
| + | : <math>(\vec x - \vec c)^2 = r^2</math> | ||
| + | |||
| + | Sei <math>\vec o</math> der Ortsvektor eines beliebigen Punkts auf der Geraden und <math>\vec d</math> der Richtungsvektor der Geraden. Dann ist die parametrische Form der Geraden gegeben durch: | ||
| + | |||
| + | : <math>{\vec x}(t) = \vec o + t \cdot \vec d</math> | ||
| + | |||
| + | Nun setzen wir <math>\vec x(t)</math> in die Kreisgleichung ein. Wir bringen die Gleichung in die richtige Form für die [http://de.wikipedia.org/wiki/Quadratische_Gleichung#p-q-Formel p-q-Formel], so dass wir nach <math>t</math> auflösen können: | ||
| + | |||
| + | : <math>\begin{align} \left( {\vec x}(t) - \vec c \right) ^2 &= r^2 \\ \left( (\vec o + t \cdot \vec d) - \vec c \right)^2 &= r^2 \\ (\vec o + t \cdot \vec d)^2 - 2 \cdot (\vec o + t \cdot \vec d) \cdot \vec c + {\vec c}^2 &= r^2 \\ {\vec o}^2 + 2t \cdot \vec o \cdot \vec d + t^2 \cdot {\vec d}^2 - 2 \cdot \vec o \cdot \vec c - 2t \cdot \vec d \cdot \vec c + {\vec c}^2 &= r^2 \\ t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + {\vec o}^2 - 2 \cdot \vec o \cdot \vec c + {\vec c}^2 - r^2 &= 0 \\ t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + (\vec o - \vec c)^2 - r^2 &= 0 \\ t^2 + t \left( \frac{2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c}{{\vec d}^2} \right) + \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2} &= 0 \end{align}</math> | ||
| + | |||
| + | Durch Anwendung der p-q-Formel erhalten wir zwei Lösungen für <math>t</math>: | ||
| + | |||
| + | : <math>\begin{align} t_1 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} - \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} \\ t_2 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} + \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} \end{align}</math> | ||
| + | |||
| + | Wenn der Richtungsvektor <math>\vec d</math> der Geraden normiert ist (Länge 1 hat), dann kann die Division durch <math>{\vec d}^2</math> weggelassen werden, was eine etwas effizientere Implementierung ermöglicht. | ||
| + | |||
| + | Betrachten wir den Ausdruck unter der Wurzel, der bei beiden Lösungen gleich ist. Es gibt drei Fälle, die eintreten können: | ||
| + | |||
| + | # ''Der Ausdruck ist negativ:'' Die Wurzel einer negativen Zahl ist für reelle Zahlen nicht definiert. In unserem Fall bedeutet das, dass die Gerade den Kreis nicht schneidet. | ||
| + | # ''Der Ausdruck ist 0:'' In diesem Fall ist <math>t_1 = t_2</math>, was bedeutet, dass die Gerade den Kreis ''berührt'' (es gibt nur einen gemeinsamen Punkt, dessen Ortsvektor <math>\vec o + t_1 \cdot \vec d</math> ist). | ||
| + | # ''Der Ausdruck ist größer als 0:'' Die Gerade schneidet den Kreis in den beiden Punkten mit den Ortsvektoren <math>\vec o + t_1 \cdot \vec d</math> und <math>\vec o + t_2 \cdot \vec d</math>. | ||
| + | |||
| + | {{Spoiler|<xh5>Implementierung</xh5>| | ||
| + | {{Spoiler| | ||
| + | <xh6>Implementierung in C++</xh6> | ||
| + | | | ||
| + | <sourcecode lang="cpp" tab="4"> | ||
| + | // c: Mittelpunkt des Kreises | ||
| + | // r: Radius des Kreises | ||
| + | // o: Ein Punkt auf der Geraden | ||
| + | // d: Richtungsvektor der Geraden | ||
| + | // p_outT: Optionaler Zeiger. Falls p_outT != 0 und es gibt eine Kollision, | ||
| + | // dann enthalten p_outT[0] und p_outT[1] die beiden Lösungen t1 und t2. | ||
| + | // Die Schnittpunkte sind o + t1 * d bzw. o + t2 * d. | ||
| + | bool circleLineCollision(const Vector& c, float r, | ||
| + | const Vector& o, const Vector& d, | ||
| + | float* p_outT = 0) | ||
| + | { | ||
| + | // Kehrwert der Länge von d vorberechnen, um die Berechnung zu beschleunigen (Divisionen sind langsam!). | ||
| + | const float invDSq = 1.0f / d.lengthSq(); | ||
| + | |||
| + | // Term vorberechnen, der mehrfach benötigt wird. | ||
| + | const float p = (Vector::dot(d, c) - Vector::dot(o, d)) * invDSq; | ||
| + | |||
| + | // Nun kann der Ausdruck unter der Wurzel berechnet werden (Diskriminante). | ||
| + | const float discriminant = p * p - ((o - c).lengthSq() - r * r) * invDSq; | ||
| + | |||
| + | if (discriminant < 0.0f) | ||
| + | { | ||
| + | // Keine Kollision! | ||
| + | return false; | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | // Kollision! Wir gehen davon aus, dass es zwei Schnittpunkte gibt. | ||
| + | // Der Benutzer kann später selber entscheiden, ob er diese als einen einzigen behandeln möchte, | ||
| + | // falls sie nah genug beieinander liegen. | ||
| + | if (p_outT) | ||
| + | { | ||
| + | // Die beiden Lösungen für t ausrechnen und ausgeben. | ||
| + | const float squareRoot = sqrt(discriminant); | ||
| + | p_outT[0] = p - squareRoot; | ||
| + | p_outT[1] = p + squareRoot; | ||
| + | } | ||
| + | |||
| + | return true; | ||
| + | } | ||
| + | } | ||
| + | </sourcecode> | ||
| + | }} | ||
| + | }} | ||
| + | |||
| + | ==== Geometrischer Ansatz speziell für 2D ==== | ||
| + | |||
| + | [[Datei:Kollision kreis senkr-gerade.gif|miniatur|Veranschaulichung des Idealfalls mit senkrechter Geraden.]] | ||
| + | Im Folgenden wird ein geometrischer Ansatz beschrieben, der für den zweidimensionalen Fall sehr anschaulich ist. Er lässt sich jedoch nicht ohne Weiteres auf mehr Dimensionen übertragen. | ||
| + | |||
Der einfachste Fall für eine Prüfung auf eine Kollision liegt vor, wenn die Gerade senkrecht oder waagerecht ist und der Mittelpunkt des Kreises, nachfolgend <math>M</math> genannt, dem Nullpunkt des Koordinatensystems entspricht oder die Gerade den Nullpunkt des Koordinatensystems schneidet. Ist die Gerade senkrecht, dann gibt es eine Kollision, wenn <math>-r \le P_x \le r</math> zutrifft. Ist die Gerade waagerecht, gibt es eine Kollision, wenn <math>-r \le P_y \le r</math> zutrifft. <math>r</math> steht in dem Fall für den Radius des Kreises, <math>P_x</math> für die x-Koordinate eines beliebigen Punkts auf der Geraden und <math>P_y</math> für die y-Koordinate eines beliebigen Punkts, <math>P</math> auf der Geraden. | Der einfachste Fall für eine Prüfung auf eine Kollision liegt vor, wenn die Gerade senkrecht oder waagerecht ist und der Mittelpunkt des Kreises, nachfolgend <math>M</math> genannt, dem Nullpunkt des Koordinatensystems entspricht oder die Gerade den Nullpunkt des Koordinatensystems schneidet. Ist die Gerade senkrecht, dann gibt es eine Kollision, wenn <math>-r \le P_x \le r</math> zutrifft. Ist die Gerade waagerecht, gibt es eine Kollision, wenn <math>-r \le P_y \le r</math> zutrifft. <math>r</math> steht in dem Fall für den Radius des Kreises, <math>P_x</math> für die x-Koordinate eines beliebigen Punkts auf der Geraden und <math>P_y</math> für die y-Koordinate eines beliebigen Punkts, <math>P</math> auf der Geraden. | ||
Nachfolgend soll der erste Fall als Idealfall genommen werden. In den Fällen, in denen der Kreis vom Nullpunkt versetzt oder die Gerade weder senkrecht noch waagerecht ist, wird zuerst die Umrechnung vorgenommen, sodass die Überprüfung erfolgen kann. | Nachfolgend soll der erste Fall als Idealfall genommen werden. In den Fällen, in denen der Kreis vom Nullpunkt versetzt oder die Gerade weder senkrecht noch waagerecht ist, wird zuerst die Umrechnung vorgenommen, sodass die Überprüfung erfolgen kann. | ||
| − | ==== Verschobener Kreis ==== | + | ===== Verschobener Kreis ===== |
Wenn die Gerade senkrecht oder waagerecht ist, <math>M</math> aber nicht dem Nullpunkt des Koordinatensystems entspricht, dann muss von dem Punkt <math>P</math> der Geraden, der für die Kollisionsprüfung verwendet werden soll, <math>M</math> abgezogen werden. Diese Berechnung kann unabhängig davon durchgeführt werden, ob die Gerade waagerecht oder senkrecht ist. Da bei einer Subtraktion von <math>M</math> von <math>M</math> das Ergebnis immer der Nullpunkt des Koordinatensystems ist, entfällt diese Berechnung. Auf den über diese Rechnung erhaltenen Punkt kann wieder die jeweilige oben angeführte Überprüfung durchgeführt werden. | Wenn die Gerade senkrecht oder waagerecht ist, <math>M</math> aber nicht dem Nullpunkt des Koordinatensystems entspricht, dann muss von dem Punkt <math>P</math> der Geraden, der für die Kollisionsprüfung verwendet werden soll, <math>M</math> abgezogen werden. Diese Berechnung kann unabhängig davon durchgeführt werden, ob die Gerade waagerecht oder senkrecht ist. Da bei einer Subtraktion von <math>M</math> von <math>M</math> das Ergebnis immer der Nullpunkt des Koordinatensystems ist, entfällt diese Berechnung. Auf den über diese Rechnung erhaltenen Punkt kann wieder die jeweilige oben angeführte Überprüfung durchgeführt werden. | ||
| − | ==== Beliebige Gerade ==== | + | ===== Beliebige Gerade ===== |
Ist die Gerade nicht senkrecht oder waagerecht, so muss diese erst gedreht werden, damit sie senkrecht oder waagerecht ist. Um einen Punkt um den Mittelpunkt des Koordinatensystems zu drehen, kann man die Berechnungen <math>P'_x = P_x \cdot cos(\alpha) - P_y \cdot sin(\alpha)</math> und <math>P'_y = P_x \cdot sin(\alpha) + P_y \cdot cos(\alpha)</math> verwenden. <math>P'</math> stellt dabei den Punkt nach der Drehung dar. Für diese Drehung muss also nicht der entsprechende Winkel selbst, sondern dessen Ergebnis der Sinus- und Kosinus-Funktion ermittelt werden. Wenn man einen weiteren Punkt der Geraden, nachfolgend <math>Q</math> genannt, nimmt, kann man diese über das dadurch darstellbare rechtwinklige (Steigungs-)Dreieck ermitteln. Die Rechnungen dafür lauten <math>sin(\alpha) = \tfrac{\text{Gegenkathete}}{\text{Hypotenuse}}</math> und <math>cos(\alpha) =\tfrac{\text{Ankathete}}{\text{Hypotenuse}}</math>. Da die Drehung gegen den Uhrzeigersinn geht, muss für eine steigende Gerade ein anderer Wert gewählt werden, als für eine fallende Gerade. Für eine steigende Gerade ist die Seite des Dreiecks, die sich durch die x-Koordinaten errechnet, die Gegenkathete und für eine fallende Gerade ist die Seite des Dreiecks, die sich durch die y-Koordinaten errechnet die Gegenkathete. | Ist die Gerade nicht senkrecht oder waagerecht, so muss diese erst gedreht werden, damit sie senkrecht oder waagerecht ist. Um einen Punkt um den Mittelpunkt des Koordinatensystems zu drehen, kann man die Berechnungen <math>P'_x = P_x \cdot cos(\alpha) - P_y \cdot sin(\alpha)</math> und <math>P'_y = P_x \cdot sin(\alpha) + P_y \cdot cos(\alpha)</math> verwenden. <math>P'</math> stellt dabei den Punkt nach der Drehung dar. Für diese Drehung muss also nicht der entsprechende Winkel selbst, sondern dessen Ergebnis der Sinus- und Kosinus-Funktion ermittelt werden. Wenn man einen weiteren Punkt der Geraden, nachfolgend <math>Q</math> genannt, nimmt, kann man diese über das dadurch darstellbare rechtwinklige (Steigungs-)Dreieck ermitteln. Die Rechnungen dafür lauten <math>sin(\alpha) = \tfrac{\text{Gegenkathete}}{\text{Hypotenuse}}</math> und <math>cos(\alpha) =\tfrac{\text{Ankathete}}{\text{Hypotenuse}}</math>. Da die Drehung gegen den Uhrzeigersinn geht, muss für eine steigende Gerade ein anderer Wert gewählt werden, als für eine fallende Gerade. Für eine steigende Gerade ist die Seite des Dreiecks, die sich durch die x-Koordinaten errechnet, die Gegenkathete und für eine fallende Gerade ist die Seite des Dreiecks, die sich durch die y-Koordinaten errechnet die Gegenkathete. | ||
Fasst man alle Berechnungen zusammen, erhält man die folgende Vorgehensweise. Es wird angenommen, dass zwei Punkte der Gerade <math>P</math> und <math>Q</math> gegeben sind. | Fasst man alle Berechnungen zusammen, erhält man die folgende Vorgehensweise. Es wird angenommen, dass zwei Punkte der Gerade <math>P</math> und <math>Q</math> gegeben sind. | ||
| − | * Die Differenz der Punkte P und Q, <math>R</math> wird mit <math>R = \left| P - Q \right|</math> ermittelt. | + | * Die Differenz der Punkte <math>P</math> und <math>Q</math>, <math>R</math> wird mit <math>R = \left| P - Q \right|</math> ermittelt. |
| − | * Die Hypotenuse <math>H</math> wird ermittelt durch <math>H = \sqrt{R_x^2 + R_y^2}</math>. | + | * Die Hypotenuse <math>H</math> wird ermittelt durch <math>H = \sqrt{{R_x}^2 + {R_y}^2}</math>. |
* Wenn <math>P_x < Q_x \land P_y < Q_y \lor P_x > Q_x \land P_z > Q_z</math> zutrifft: | * Wenn <math>P_x < Q_x \land P_y < Q_y \lor P_x > Q_x \land P_z > Q_z</math> zutrifft: | ||
** Das Ergebnis des Kosinus, <math>c</math>, wird ermittelt mit <math>c = \tfrac{R_y}{H}</math>. | ** Das Ergebnis des Kosinus, <math>c</math>, wird ermittelt mit <math>c = \tfrac{R_y}{H}</math>. | ||
| Zeile 348: | Zeile 418: | ||
** Das Ergebnis des Kosinus, <math>c</math>, wird ermittelt mit <math>c = \tfrac{R_x}{H}</math>. | ** Das Ergebnis des Kosinus, <math>c</math>, wird ermittelt mit <math>c = \tfrac{R_x}{H}</math>. | ||
** Das Ergebnis des Sinus, <math>s</math>, wird ermittelt mit <math>s = \tfrac{R_y}{H}</math>. | ** Das Ergebnis des Sinus, <math>s</math>, wird ermittelt mit <math>s = \tfrac{R_y}{H}</math>. | ||
| − | ** Die y-Koordinate des gedrehten Punkts <math>y'</math> wird ermittelt mit <math>y' = P_xs | + | ** Die y-Koordinate des gedrehten Punkts <math>y'</math> wird ermittelt mit <math>y' = P_xs + P_yc</math>. |
** Wenn <math>-r \le y \le r</math> zutrifft, liegt eine Kollision vor. | ** Wenn <math>-r \le y \le r</math> zutrifft, liegt eine Kollision vor. | ||
| + | |||
| + | ===Kollision Kreis-Strecke=== | ||
| + | Insbesondere für Kreis-Rechteckkollision ist es wichtig, den Punkt auf einer Strecke zu finden, der dem Mittelpunk der Kugel am nähesten liegt. | ||
| + | |||
| + | ====Allgemeiner Ansatz==== | ||
| + | Wir betrachten eine Strecke durch 2 Punkte <math>\boldsymbol{x}</math> und <math>\boldsymbol{y}</math> und einen Kreis mit radius <math>r</math> und Mittelpunkt <math>\boldsymbol{m}</math> ('''x''','''y''','''m''' Vektoren im <math>\mathbb{R}^n</math>). Der einfachheit halber definieren wir: <math>\boldsymbol{a} = \boldsymbol{y-x}</math> (Richtungsvektor der Geraden durch die Strecke, nicht normalisiert, sondern ist genau so lang wie die Strecke) und <math>\boldsymbol{b = m-x}</math> (Verbindungsvektor vom Startpunkt und dem Mittelpunkt) | ||
| + | |||
| + | Daraus lässt sich der Punkt berechnen, an dem der Mittelpunkt der Geraden <math>g: \boldsymbol{v} = \boldsymbol{x}+\boldsymbol{a}\cdot t</math> am nähesten ist. Nun gilt: | ||
| + | <math>t = \frac{\langle a,b\rangle}{\langle a,a\rangle}</math> (<math>\langle a,b\rangle</math> ist das Skalar/Punktprodukt von a unb b) | ||
| + | Allerdings ist die Strecke nur der Teil der Geraden, für den <math>t\in [0,1]</math> ist. Also setzt man | ||
| + | <math>t*=\begin{cases}0&t<0\\t& t\in [0,1]\\1& t > 1\end{cases}</math> | ||
| + | Der Punkt auf der Strecke, der dem Kreis am nähesten ist, ist dann <math>\boldsymbol{d} = \boldsymbol{x}+\boldsymbol{a}\cdot t*</math>. Wenn nun <math>||\boldsymbol{m}-\boldsymbol{x}||^2<r^2</math>, dann Kollidiert der Kreis im Punkt '''d''' mit der Strecke. | ||
| + | |||
| + | =====Komplexität===== | ||
| + | Diese Berechnungen benötigen 0 Quadratwurzeln, 3*n Multiplikationen und n Divisionen und lassen sich damit sehr schnell durchführen. | ||
| + | |||
| + | ===Kollision Rechteck-Kreis (2D)=== | ||
| + | Ein Rechteck fasst man als 4 Strecken auf. Man berechnet den Minimalen Abstand (und die Position des Basispunkts) des Kreises von allen 4 Seiten, nimmt von den 4 Abständen (bzw. deren Quadrate, um Wurzeln zu vermeiden) das Minimum. Wenn dieses kleiner als r² ist, dann kollidiert der Kreis mit dem Rechteck im dazugehörigen Basispunkt. | ||
| + | |||
| + | |||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
| + | {{Spoiler| | ||
| + | <xh5>Implementierung in C++</xh5> | ||
| + | | | ||
| + | <sourcecode lang="cpp" tab="4"> | ||
| + | Vector2 PointLineDist(Vector2 point, Vector2 linestart, Vector2 lineend) | ||
| + | { | ||
| + | Vector2 a = lineend - linestart; | ||
| + | Vector2 b = point - linestart; | ||
| + | double t = dot(a, b)/(length(a)²); | ||
| + | if (t < 0) t = 0; | ||
| + | if (t > 1) t = 1; | ||
| + | return linestart + a * t; | ||
| + | } | ||
| + | |||
| + | struct CollisionResult | ||
| + | { | ||
| + | bool isCollided; | ||
| + | Vector2 collisionPoint; | ||
| + | float distanceSq; | ||
| + | } | ||
| + | |||
| + | // Gibt zurück, ob eine Kollision stattfand und wenn ja, wo, und wie lang der (minimale, quadratische) Abstand zum Rechteck ist. | ||
| + | CollisionResult RectangleCircleKollision(Rect rect, Circle circle) | ||
| + | { | ||
| + | float minDistSq = HUGE_VAL; | ||
| + | Vector2 basePoint = Vector2(0,0); | ||
| + | // Seiten durchgehen, Schleife kann (bzw muss, je nachdem wie Rect aussieht) entrollt werden | ||
| + | for(int i=0; i<4 ;i++) | ||
| + | { | ||
| + | Vector2 base = PointLineDist(circle.mid, rect.points[i], rect.points[(i+1) % 4]); | ||
| + | if(lengthsq(circle.mid-base)<minDistSq) | ||
| + | { | ||
| + | // Kürzerer Abstand, neu zuweisen. | ||
| + | minDistSq = lengthsq(circle.mid - base); | ||
| + | basePoint = base; | ||
| + | } | ||
| + | } | ||
| + | return {minDistSq < circle.radius * circle.radius, | ||
| + | basePoint, | ||
| + | minDistSq}; | ||
| + | } | ||
| + | </sourcecode> | ||
| + | }} | ||
| + | }} | ||
| + | |||
| + | ====Beliebige Polygone im 2-dimensionalen==== | ||
| + | Derselbe code kann auch für Beliebige konvexe Polygone verwendet werden, wenn man Rect durch eine Polygonklasse ersetzt (und den Modulo-Operator anpasst) | ||
Aktuelle Version vom 28. September 2017, 23:24 Uhr
Klicke hier, um diese Version anzusehen.
