Schmalphasige Kollisionserkennungsalgorithmen

Es gibt drei Phasen der Kollisionserkennung.

1. Broadphase : Es wird eine Schleife zwischen allen Objekten ausgeführt, die interagieren können. False Positives sind zulässig, wenn dies die Schleife beschleunigen würde.

2. Schmale Phase : Bestimmt, ob sie kollidieren und manchmal, wie, keine Fehlalarme

3. Lösung : Behebt die Kollision.

Die Frage, die ich stelle, betrifft die Engephase. Es gibt mehrere Algorithmen, die sich in Komplexität und Genauigkeit unterscheiden.

1. Hitbox-Schnittpunkt : Dies ist ein a-posteriori-Algorithmus, der die geringste Komplexität aufweist, aber auch nicht zu genau ist.

2. Farbe Kreuzung : Hitbox Kreuzung für jedes Pixel, a-posteriori, pixelgenaue, nicht accuratee in Bezug auf Zeit, höhere Komplexität

3. Theorem der Trennachse : Dies wird häufiger verwendet, genau für Dreiecke, jedoch a-posteriori, da es die Kante nicht finden kann, wenn es das letzte Bild berücksichtigt, ist es stabiler

4. Lineares Raycasting : Der A-priori-Algorithmus, der für die semi-realistisch aussehende Physik nützlich ist, findet den Schnittpunkt noch genauer als SAT, jedoch komplexer

5. Spline-Interpolation : A-priori, noch genauer als lineare Strahlen, noch mehr Koplexität.

Es gibt wahrscheinlich noch viel mehr, die ich vergessen habe. Die Frage ist, wann es besser ist, SAT zu verwenden, wann Strahlen, wann Splines und ob es etwas Besseres gibt.

Zwei, die Sie vermissen und die mir sofort auffallen, sind GJK und MPR.

GJK ist ein Algorithmus zum Finden des nächsten Punktes zweier konvexer Polygone. Mit ein wenig zusätzlicher Arbeit können Sie damit Einfallspunkte für sich überschneidende Objekte finden und so einen Kollisionsverteiler berechnen. Dies erfolgt über das Ausschneiden von Polygonen, genau wie bei Verwendung von SAT, aber GJK erspart Ihnen einige Schritte (da Sie bereits die nächsten Punkte haben).

MPR (Minkowski Portal Refinement) ist ein weiterer Algorithmus, der GJK ähnelt (beide verwenden Minkowski-Leerzeichen). Es kann nicht den nächstgelegenen Punkt zwischen sich nicht überschneidenden Objekten wie GJK finden, hat aber viele andere nette Eigenschaften für Spiele und ist eine Möglichkeit, einen Kontaktverteiler zu erhalten.

MPR ist eines der beliebtesten Spiele. Es ist sehr effizient, numerisch stabil und einfach zu implementieren.

Andere enge Phasen werden eher in Spezialspielen verwendet. Rennspiele verwenden normalerweise Ray Casting, um tatsächliche Reifen zu modellieren, und ein realistisches (oder sogar nur unterhaltsames) Verhalten ist mit der herkömmlichen Modellierung von Kollisionsform und Auflösung noch nicht möglich. Plattformer verwenden in der Regel auch hochgradig angepasste Kollisions- und Physikfunktionen, da die bevorzugte "Mario-ähnliche" Physik nicht mit herkömmlichen Physikalgorithmen modelliert wird. Sie werden auch oft verschiedene Kollisions- und Physikmethoden für Flüssigkeiten und dergleichen sehen, obwohl ich weniger darüber weiß.

Sehen:

• http://www.codezealot.org/archives/tag/gjk
• http://xenocollide.snethen.com/

Ich wollte sagen, sein Separating Axis Test , nicht Theorem.

Sie würden SAT für nicht bewegte Polygone (2D) verwenden, obwohl Sie es erweitern können, um mit relativen linearen Bewegungen fertig zu werden.

http://elancev.name/oliver/2D%20polygon.htm#tut3

Verwenden Sie GJK nicht in 2D, ich fand es tatsächlich langsamer als nur brutales Erzwingen von SAT.

Eine andere Technik, die Sie verwenden können, ist der Minkowski-Unterschied, bei dem ein Objekt auf einen Punkt verkleinert und das andere um die Form des ersten Objekts "vergrößert" wird. Dann testen Sie das kombinierte Objekt gegen den Punkt, der viel einfacher ist - dies gibt Ihnen Durchdringungsentfernung und Normalität. Ich finde dieses Tool konzeptionell sehr nützlich, um neue Probleme bei der Kollisionserkennung anzugehen. einfacher zu visualisieren als SAT.

Für bewegte und rotierende Polygone (und Polyeder) können Sie Conservative Advancement verwenden, um die genaue Zeit und den genauen Kontaktpunkt zu ermitteln.

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Sie können mehr über diese Techniken in diesem Blog-Beitrag lesen, den ich vor einiger Zeit geschrieben habe:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Hoffentlich hilft das!

Prost, Paul.

Dies hängt wirklich von der Art des Spiels ab, das Sie haben. Jede der oben genannten Methoden hat ihre eigenen Kompromisse.

Allerdings ist SAT meiner Erfahrung nach ein Standard für generische Physikbibliotheken, z. Box2D verwendet es ausgiebig (Angry Birds und viele andere Spiele verwenden Box2D).

Variationen von Farbschnittpunkten gemischt mit SAT- oder Hitbox-Schnittpunkten werden in Spielen wie Sonic, Megaman mit guten Ergebnissen verwendet.

Ich weiß allerdings nicht viel über # 4 und # 5.