2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
(→Kollision zwischen zwei Strecken) |
K (Anpassung für MathJax) |
||
| (26 dazwischenliegende Versionen von 6 Benutzern werden nicht angezeigt) | |||
| Zeile 7: | Zeile 7: | ||
In diesem Artikel geht es um 2D-Kollisionserkennung, also die Überprüfung, ob sich zwei Objekte berühren oder schneiden. Für Anwendungen, bei denen dies eine zentrale Rolle spielt, empfiehlt sich auch ggf. der Einsatz einer [[Link-Sammlung#Physik|Physik-Engine]]. Eine Physik-Engine kann Kollisionen nicht nur sehr effizient erkennen, sondern auch physikalisch korrekt darauf reagieren. | In diesem Artikel geht es um 2D-Kollisionserkennung, also die Überprüfung, ob sich zwei Objekte berühren oder schneiden. Für Anwendungen, bei denen dies eine zentrale Rolle spielt, empfiehlt sich auch ggf. der Einsatz einer [[Link-Sammlung#Physik|Physik-Engine]]. Eine Physik-Engine kann Kollisionen nicht nur sehr effizient erkennen, sondern auch physikalisch korrekt darauf reagieren. | ||
| − | == Erkennung anhand geometrischer | + | == Erkennung anhand geometrischer Formen == |
Häufig werden Spielobjekte durch einfache geometrische Formen (Kreise, Rechtecke, Polygone) angenähert, da eine Kollisionserkennung für solche Formen einfacher bzw. schneller durchgeführt werden kann. Dabei nimmt man in Kauf, dass die physikalische Form des Objekts von seiner sichtbaren Form abweicht. Im Folgenden werden Kollisionstests für zweidimensionale Formen behandelt. | Häufig werden Spielobjekte durch einfache geometrische Formen (Kreise, Rechtecke, Polygone) angenähert, da eine Kollisionserkennung für solche Formen einfacher bzw. schneller durchgeführt werden kann. Dabei nimmt man in Kauf, dass die physikalische Form des Objekts von seiner sichtbaren Form abweicht. Im Folgenden werden Kollisionstests für zweidimensionale Formen behandelt. | ||
| Zeile 17: | Zeile 17: | ||
Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben. | Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 33: | Zeile 34: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 48: | Zeile 49: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 60: | Zeile 61: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 71: | Zeile 72: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 78: | Zeile 80: | ||
Dabei rechnen wir mit Hilfe des [http://de.wikipedia.org/wiki/Satz_des_Pythagoras Satz des Pythagoras] die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien. | Dabei rechnen wir mit Hilfe des [http://de.wikipedia.org/wiki/Satz_des_Pythagoras Satz des Pythagoras] die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 99: | Zeile 102: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 119: | Zeile 122: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 136: | Zeile 139: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 152: | Zeile 155: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 161: | 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>. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 194: | Zeile 189: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 208: | Zeile 203: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 219: | Zeile 214: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 230: | Zeile 225: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 236: | Zeile 232: | ||
Die Kollisionserkennung zwischen zwei Strecken erfolgt ähnlich wie bei den Geraden, nur mit einem kleinen Zusatz, denn Strecken haben einen Start- und Endpunkt. Deswegen werden Strecken auch als Geradenabschnitt bezeichnet. Es wird also wieder überprüft, ob die beiden Strecken parallel zu einander sind. Wenn dies der Fall ist und die Strecken sich auch nicht überlappen, liegt keine Kollision vor. Ansonsten muss noch überprüft werden, ob sich die Strecken in den angegebenen Abschnitten schneiden. Nur wenn das zutrifft, liegt eine Kollision vor. | Die Kollisionserkennung zwischen zwei Strecken erfolgt ähnlich wie bei den Geraden, nur mit einem kleinen Zusatz, denn Strecken haben einen Start- und Endpunkt. Deswegen werden Strecken auch als Geradenabschnitt bezeichnet. Es wird also wieder überprüft, ob die beiden Strecken parallel zu einander sind. Wenn dies der Fall ist und die Strecken sich auch nicht überlappen, liegt keine Kollision vor. Ansonsten muss noch überprüft werden, ob sich die Strecken in den angegebenen Abschnitten schneiden. Nur wenn das zutrifft, liegt eine Kollision vor. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 251: | 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 257: | Zeile 254: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 271: | 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> | ||
}} | }} | ||
| + | |||
| + | {{Spoiler| | ||
| + | <xh5>Implementierung in Python</xh5> | ||
| + | | | ||
| + | <sourcecode lang="python" tab="4"> | ||
| + | def lineSegmentCollision(a1, a2, b1, b2): | ||
| + | denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) - | ||
| + | (b2[0] - b1[0]) * (a2[1] - a1[1]) | ||
| + | if (abs(denom) < EPSILON): | ||
| + | return false | ||
| + | |||
| + | ua = ((b2[0] - b1[0]) * (a1[1] - b1[1]) - | ||
| + | (b2[1] - b1[1]) * (a1[0] - b1[0])) / denom | ||
| + | ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | ||
| + | (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom | ||
| + | return ua >= 0 and ua <= 1 and ub >= 0 and ub <= 1 | ||
| + | </sourcecode> | ||
| + | }} | ||
| + | |||
| + | {{Spoiler| | ||
| + | <xh5>Implementierung in Java</xh5> | ||
| + | | | ||
| + | <sourcecode lang="java" tab="4"> | ||
| + | boolean lineSegmentCollision(float[] a1, float[] a2, | ||
| + | float[] b1, float[] b2) | ||
| + | { | ||
| + | float denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) - | ||
| + | (b2[0] - b1[0]) * (a2[1] - a1[1]); | ||
| + | if (Math.abs(denom) < EPSILON) return false; | ||
| + | |||
| + | float ua = ((b2[0] - b1[0]) * (a1[1] - b1[1]) - | ||
| + | (b2[1] - b1[1]) * (a1[0] - b1[0])) / denom; | ||
| + | float ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) - | ||
| + | (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom; | ||
| + | return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1; | ||
| + | } | ||
| + | </sourcecode> | ||
| + | }} | ||
| + | }} | ||
| + | |||
| + | === Kollision zwischen einem Kreis und einer 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. | ||
| + | |||
| + | 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 ===== | ||
| + | |||
| + | 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 ===== | ||
| + | |||
| + | 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. | ||
| + | * 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>. | ||
| + | * 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 Sinus, <math>s</math>, wird ermittelt mit <math>s = \tfrac{R_x}{H}</math>. | ||
| + | ** Die x-Koordinate des gedrehten Punkts <math>x'</math> wird ermittelt mit <math>x' = P_xc - P_ys</math>. | ||
| + | ** Wenn <math>-r \le x \le r</math> zutrifft, liegt eine Kollision vor. | ||
| + | * Sonst: | ||
| + | ** 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>. | ||
| + | ** 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. | ||
| + | |||
| + | ===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.
