Algorithmes de détection de collision en phase étroite

Il existe trois phases de détection de collision.

1. Broadphase : il boucle entre tous les objecs qui peuvent interagir, les faux positifs sont autorisés, si cela accélère la boucle.

2. Narrowphase : détermine s'ils entrent en collision, et parfois, comment, pas de faux positifs

3. Résolution : résout la collision.

La question que je pose concerne la phase étroite. Il existe plusieurs algorithmes, différents en complexité et en précision.

1. Intersection Hitbox : il s'agit d'un algorithme a posteriori, qui a la plus faible complexité, mais n'est pas trop précis,

2. Intersection des couleurs : intersection Hitbox pour chaque pixel, a posteriori, pixel parfait, pas précis en termes de temps, complexité plus élevée

3. Théorème de l'axe de séparation : il est utilisé plus souvent, précis pour les triangles, cependant, a posteriori, car il ne peut pas trouver le bord, lors de la prise en compte de la dernière image, il est plus stable

4. Raycasting linéaire : l'algorithme A priori, utile pour une physique d'aspect semi-réaliste, trouve le point d'intersection, encore plus précis que SAT, mais avec plus de complexité

5. Interpolation spline : A priori, encore plus précise que les rayons linéaires, encore plus de coplexité.

Il y en a probablement beaucoup d'autres que j'ai oubliés. La question est de savoir quand est-il préférable d'utiliser SAT, quand les rayons, quand les splines et s'il y a quelque chose de mieux.

Deux qui vous manquent et qui me viennent immédiatement à l'esprit sont GJK et MPR.

GJK est un algorithme pour trouver le point le plus proche de deux polygones convexes. Avec un peu de travail supplémentaire, vous pouvez l'utiliser pour trouver des points d'incident pour les objets qui se croisent, et donc calculer un collecteur de collisions. Cela se fait via l'écrêtage de polygone, comme si vous utilisiez SAT, mais GJK vous enregistre quelques étapes (puisque vous aurez déjà les points les plus proches).

MPR (Minkowski Portal Refinement) est un autre algorithme, similaire à GJK (ils utilisent tous les deux des espaces Minkowski). Il ne peut pas trouver le point le plus proche entre des objets non intersectés comme GJK, mais il a beaucoup d'autres belles propriétés pour les jeux, et est un moyen à utiliser pour obtenir une variété de contacts.

MPR est l'un des plus populaires pour les jeux. Il est très efficace, numériquement stable et facile à mettre en œuvre.

D'autres phases étroites sont plus utilisées dans les jeux spécialisés. Les jeux de course utilisent généralement le lancer de rayons comme modélisation de pneus réels et il n'est pas encore possible d'obtenir un comportement réaliste (ou même juste amusant) en utilisant la modélisation traditionnelle de la forme et de la résolution des collisions. Les plates-formes utilisent également généralement des collisions et une physique hautement personnalisées, car la physique «Mario» préférée n'est pas modélisée avec des algorithmes de physique traditionnels. Vous verrez également souvent différentes méthodes de collision et de physique pour les fluides et autres, bien que j'en sache moins à leur sujet.

Voir:

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

Je voulais dire, son test d' axe de séparation , pas le théorème.

Vous utiliseriez SAT sur des polygones non mobiles (2D), bien que vous puissiez l'étendre pour faire face à un mouvement linéaire relatif.

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

N'utilisez pas GJK en 2D, j'ai trouvé son en fait plus lent que le simple forçage brutal SAT.

Une autre technique que vous pouvez utiliser est la différence de Minkowski, qui rétrécit un objet jusqu'à un point et «grandit» l'autre par la forme du premier. Ensuite, vous testez l'objet combiné contre le point, ce qui est beaucoup plus facile - cela vous donne une distance de pénétration normale. Je trouve que cet outil est conceptuellement très utile pour aborder de nouveaux problèmes de détection de collision; plus facile à visualiser que SAT.

Pour les polygones en mouvement et en rotation (et les polyèdres), vous pouvez utiliser Progression conservatrice pour trouver l'heure et le point de contact exacts.

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

Vous pouvez en savoir plus sur ces techniques dans cet article de blog que j'ai écrit il y a quelque temps:

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

J'espère que ça t'as aidé!

Santé, Paul.

Cela dépend vraiment du type de jeu que vous avez. Chaque méthode ci-dessus a ses propres compromis.

Cependant, SAT est assez standard dans mon expérience pour les bibliothèques génériques de physique, Ex. Box2D l'utilise beaucoup (Angry Birds, et de nombreux autres jeux utilisent Box2D).

Les variations d'intersection de couleurs mélangées à l'intersection SAT ou Hitbox sont utilisées dans des jeux comme Sonic, Megaman avec de bons résultats.

Je ne connais cependant pas grand-chose aux n ° 4 et n ° 5.