2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [gesichtete Version] | [gesichtete Version] |
SaRu (Diskussion | Beiträge) K (Tippfehler bei den Quellcode-Beispielen zur Kollision zweier Strecken behoben: Am Ende sollte ub <= 1 geprüft werden und nicht erneut ua <= 1.) |
K (→Kollision Rechteck-Kreis (2D)) |
||
| (4 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt) | |||
| Zeile 441: | Zeile 441: | ||
** Die y-Koordinate des gedrehten Punkts <math>y'</math> wird ermittelt mit <math>y' = P_xs + P_yc</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. | ** 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) | ||
Version vom 11. September 2012, 12:02 Uhr
Klicke hier, um diese Version anzusehen.
