2D-Kollisionserkennung

Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
[unmarkierte Version][gesichtete Version]
K (Collection-Klasse Vector als 2D Vector ist absurd.)
K (Anpassung für MathJax)
 
(44 dazwischenliegende Versionen von 7 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 Figuren ==
+
== 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.
  
−
=== Kollision zwischen zwei Rechtecken ===
+
=== Kollision zwischen zwei achsenausgerichteten Rechtecken ===
  
−
Die Prüfung einer Kollision von 2 Rechtecken ist die einfachste mögliche Prüfung, sofern keine Rotation vorhanden ist. Aufgrund der daraus resultierenden hohen Geschwindigkeit kann diese Prüfung komplexeren Prüfungen voran gestellt werden, um zu testen, ob 2 Objekte nah genug aneinander sind, damit eine Kollision möglich ist.
+
Die Prüfung einer Kollision zweier achsenausgerichteten (nicht rotierten) Rechtecken kann sehr effizient durchgeführt werden. Aufgrund der daraus resultierenden hohen Geschwindigkeit kann diese Prüfung komplexeren Prüfungen voran gestellt werden, um zu testen, ob zwei Objekte nah genug aneinander sind, damit eine Kollision möglich ist. Dazu testet man die sie umgebenden Rechtecke (''Bounding Rectangles'') auf Kollision.
  
−
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 diesem Beispiel wird für ein Rechteck die Position der oberen, linken Ecke und die Breite, sowie die Höhe, benutzt.
+
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|
−
==== Implementierung in C++ ====
+
<xh5>Implementierung in C++</xh5>
 
|
 
|
 
<sourcecode lang="cpp" tab="4">
 
<sourcecode lang="cpp" tab="4">
Zeile 30: Zeile 31:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
−
|}}
+
}}
−
 
+
−
==== Implementierung in C# ====
+
  
 +
{{Spoiler|
 +
<xh5>Implementierung in C#</xh5>
 +
|
 
<sourcecode lang="csharp" tab="4">
 
<sourcecode lang="csharp" tab="4">
 
bool rectangleCollision(Vector position1, float width1, float height1,
 
bool rectangleCollision(Vector position1, float width1, float height1,
Zeile 44: Zeile 46:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Python ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Python</xh5>
 +
|
 
<sourcecode lang="python" tab="4">
 
<sourcecode lang="python" tab="4">
 
def rectangleCollision(position1, width1, height1, position2, width2, height2):
 
def rectangleCollision(position1, width1, height1, position2, width2, height2):
Zeile 54: Zeile 58:
 
      position2[1] < position1[1] + height1
 
      position2[1] < position1[1] + height1
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Java ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Java</xh5>
 +
|
 
<sourcecode lang="java" tab="4">
 
<sourcecode lang="java" tab="4">
 
boolean rectangleCollision(float[] position1, float width1, float height1,
 
boolean rectangleCollision(float[] position1, float width1, float height1,
Zeile 66: Zeile 72:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
 +
}}
  
 
=== Kollision zwischen zwei Kreisen ===
 
=== Kollision zwischen zwei Kreisen ===
Zeile 72: 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.
  
−
==== Implementierung in C++ ====
+
{{Spoiler|<xh4>Implementierung</xh4>|
−
 
+
{{Spoiler|
 +
<xh5>Implementierung in C++</xh5>
 +
|
 
<sourcecode lang="cpp" tab="4">
 
<sourcecode lang="cpp" tab="4">
 
bool circleCollision(const Vector& position1, float radius1,
 
bool circleCollision(const Vector& position1, float radius1,
Zeile 89: Zeile 99:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in C# ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in C#</xh5>
 +
|
 
<sourcecode lang="csharp" tab="4">
 
<sourcecode lang="csharp" tab="4">
 
bool circleCollision(Vector position1, float radius1,
 
bool circleCollision(Vector position1, float radius1,
Zeile 107: Zeile 119:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Python ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Python</xh5>
 +
|
 
<sourcecode lang="python" tab="4">
 
<sourcecode lang="python" tab="4">
 
def circleCollision(position1, radius1, position2, radius2):
 
def circleCollision(position1, radius1, position2, radius2):
Zeile 122: Zeile 136:
 
return dx * dx + dy * dy <= radiusSum * radiusSum
 
return dx * dx + dy * dy <= radiusSum * radiusSum
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Java ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Java</xh5>
 +
|
 
<sourcecode lang="java" tab="4">
 
<sourcecode lang="java" tab="4">
−
boolean circleCollision(Vector<Float> position1, float radius1,
+
boolean circleCollision(float[] position1, float radius1,
−
                         Vector<Float> position2, float radius2) {
+
                         float[] position2, float radius2) {
−
float dx = position1.get(0) - position2.get(0);
+
float dx = position1[0] - position2[0];
−
float dy = position1.get(1) - position2.get(1);
+
float dy = position1[1] - position2[1];
 
 
 
// Langsame Version, benötigt Wurzel:
 
// Langsame Version, benötigt Wurzel:
Zeile 139: Zeile 155:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
 +
}}
  
 
=== Kollision zwischen zwei Geraden ===
 
=== Kollision zwischen zwei Geraden ===
Zeile 147: 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, und somit liegt keine Kollision vor. Beim Rechnen mit Fließkommazahlen muss man jedoch beachten, dass ein Vergleich mit Null nicht empfehlenswert ist, da es zu Ungenauigkeiten kommt. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante <code>EPSILON</code> dargestellt) gewählt werden, unterhalb dem 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>.
−
 
+
−
==== Implementierung in C++ ====
+
  
 +
{{Spoiler|<xh4>Implementierung</xh4>|
 +
{{Spoiler|
 +
<xh5>Implementierung in C++</xh5>
 +
|
 
<sourcecode lang="cpp" tab="4">
 
<sourcecode lang="cpp" tab="4">
 
bool lineCollision(const Vector& a1, const Vector& a2,
 
bool lineCollision(const Vector& a1, const Vector& a2,
Zeile 176: Zeile 186:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in C# ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in C#</xh5>
 +
|
 
<sourcecode lang="csharp" tab="4">
 
<sourcecode lang="csharp" tab="4">
 
bool lineCollision(Vector a1, Vector a2,
 
bool lineCollision(Vector a1, Vector a2,
Zeile 188: Zeile 200:
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Python ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Python</xh5>
 +
|
 
<sourcecode lang="python" tab="4">
 
<sourcecode lang="python" tab="4">
 
def lineCollision(a1, a2, b1, b2):
 
def lineCollision(a1, a2, b1, b2):
Zeile 197: Zeile 211:
 
return abs(denom) > EPSILON
 
return abs(denom) > EPSILON
 
</sourcecode>
 
</sourcecode>
 +
}}
  
−
==== Implementierung in Java ====
+
{{Spoiler|
−
 
+
<xh5>Implementierung in Java</xh5>
 +
|
 
<sourcecode lang="java" tab="4">
 
<sourcecode lang="java" tab="4">
−
boolean lineCollision(Vector<Float> a1, Vector<Float> a2,
+
boolean lineCollision(float[] a1, float[] a2,
−
  Vector<Float> b1, Vector<Float> b2)
+
                      float[] b1, float[] b2)
 
{
 
{
−
float denom = (b2.get(1) - b1.get(1)) * (a2.get(0) - a1.get(0)) -
+
float denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
−
  (b2.get(0) - b1.get(0)) * (a2.get(1) - a1.get(1));
+
  (b2[0] - b1[0]) * (a2[1] - a1[1]);
 
return Math.abs(denom) > EPSILON;
 
return Math.abs(denom) > EPSILON;
 
}
 
}
 
</sourcecode>
 
</sourcecode>
 +
}}
 +
}}
 +
 +
=== Kollision zwischen zwei Strecken ===
 +
 +
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|
 +
<xh5>Implementierung in C++</xh5>
 +
|
 +
<sourcecode lang="cpp" tab="4">
 +
bool lineSegmentCollision(const Vector& a1, const Vector& a2,
 +
  const Vector& b1, const Vector& b2)
 +
{
 +
const float denom = (b2.y - b1.y) * (a2.x - a1.x) -
 +
(b2.x - b1.x) * (a2.y - a1.y);
 +
if (abs(denom) < EPSILON) return false;
 +
 +
const float ua = ((b2.x - b1.x) * (a1.y - b1.y) -
 +
  (b2.y - b1.y) * (a1.x - b1.x)) / denom;
 +
const float ub = ((a2.x - a1.x) * (a1.y - b1.y) -
 +
  (a2.y - a1.y) * (a1.x - b1.x)) / denom;
 +
return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
 +
}
 +
</sourcecode>
 +
}}
 +
 +
{{Spoiler|
 +
<xh5>Implementierung in C#</xh5>
 +
|
 +
<sourcecode lang="csharp" tab="4">
 +
bool lineSegmentCollision(Vector a1, Vector a2,
 +
  Vector b1, Vector b2)
 +
{
 +
float denom = (b2.y - b1.y) * (a2.x - a1.x) -
 +
  (b2.x - b1.x) * (a2.y - a1.y);
 +
if (abs(denom) < EPSILON) return false;
 +
 +
float ua = ((b2.x - b1.x) * (a1.y - b1.y) -
 +
(b2.y - b1.y) * (a1.x - b1.x)) / denom;
 +
float ub = ((a2.x - a1.x) * (a1.y - b1.y) -
 +
(a2.y - a1.y) * (a1.x - b1.x)) / denom;
 +
return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
 +
}
 +
</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.

Von „https://www.spieleprogrammierer.de/wiki/2D-Kollisionserkennung“
Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Werkzeuge