2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [unmarkierte Version] | [unmarkierte Version] |
(→Allgemeiner Ansatz) |
(→Kollision Kreis-Strecke) |
||
| Zeile 452: | Zeile 452: | ||
Allerdings ist die Strecke nur der Teil der Geraden, für den <math>t\in [0,1]</math> ist. Also setzt man | 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> | <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}||<r^2</math>, dann Kollidiert der Kreis im Punkt '''d''' mit der Strecke. | + | 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> | ||
| + | }} | ||
| + | }} | ||
Version vom 11. September 2012, 11:56 Uhr
Klicke hier, um diese Version anzusehen.
