Détection de collision: un tas de cas particuliers?

J'écris un moteur physique simple en 2D. Mon premier objectif est de faire fonctionner la détection de collision. Je sais que mes objets finiront par être constitués de formes primitives, mais je me demandais - une bibliothèque de détection de collision serait-elle composée d'un tas de fonctions spéciales, comme "rayAndLine", "rectangleRectangle", "rectangleCircle" etc., ou est existe-t-il un cadre commun et sous-jacent pour la détection de collision qui fonctionne quelles que soient les primitives utilisées pour créer la forme?

Faire fonctionner la détection de collision est un excellent premier objectif pour votre moteur physique 2D. C'est bien que vous ayez décidé que pour l'instant vous travaillez spécifiquement en 2D, car toutes les règles en 2D ne fonctionnent pas en 3D, malgré la quantité d'algorithmes liés à la dimension n, à un moment donné, vous devez les spécialiser (faites plus variante spécifique comme la façon dont le produit croisé ne satisfait que l'identité Jacobi en 3D).

Votre question concerne intrinsèquement l'architecture et la conception du cadre, pas la physique 2D, donc la préoccupation de ce que votre bâtiment devrait être séparé dans votre esprit pour la façon dont ces pièces sont utilisées. Essentiellement, vous devez séparer la mentalité de construction du moteur / bibliothèque / framework de son utilisation dans un autre projet.

Architecturer des moteurs de résolution: Avec n'importe quel moteur mathématique, nous voulons essentiellement mettre des valeurs dans une fonction, et nous nous attendons à ce que les valeurs qui en sortent soient utiles pour faire une simulation intéressante.

Les éléments centraux de ce processus devraient être aussi abstraits que possible tandis que les éléments atomiques (les plus petits éléments de données / méthodes utiles) devraient être spécifiques à des fins individuelles et être utiles pour composer ensemble. Dans notre cas, presque le seul atomique utile est un vecteur 2D, qui devrait être une seule classe d'objets qui permet l'expression d'une structure (x, y), et qui a des méthodes pour toutes les opérations mathématiques de base qui sont utiles pour les calculs vectoriels en 2D. Addition, soustraction, normalisation, normal (perpendiculaire), produit croisé, produit scalaire, amplitude / longueur, et tout ce que vous rencontrez qui est spécifiquement inhérent à vector -> opérations vectorielles ou vector -> opérations en nombre réel. Si vous utilisez un langage basé sur une classe, un simple class Vectoravec chacun d'eux comme fonction membre ou surcharge d'opérateur ferait très bien l'affaire.

Une fois tous les types atomiques construits, vous composeriez leurs algorithmes dans une autre couche au-dessus de notre type atomique Vector. Mon rendez-vous serait un Lineet un Curve. Nous déciderons ici que a Curveest hors de portée pour cela et nécessite beaucoup de spécialisation (le concept auquel vous faites référence ci-dessus comme créant de nombreuses fonctions de cas spécial). À partir de, Vectorje composerais également un en Rectangletant que Vectorprimitive 4 , je composerais à Circlepartir d'un vecteur en utilisant a Vectoret a radius, puis je composerais également un à Polygonpartir Vectorde. Polygondoit être créé à partir de Vectoret non Lineici car chaque ligne partagerait un point en double avec la dernière ligne du polygone.

Vous avez maintenant des formes, mais nous ne savons pas quoi en faire.

Détection de collision La détection de collision n'est pas une science exacte et il n'y a pas un seul algorithme parfait (ou aucun). Il existe de nombreuses méthodes qui peuvent être utilisées pour obtenir une variété d'effets de qualité ou même avoir plus de précision que d'autres. Fondamentalement, cependant, il peut être séparé en quelques niveaux de préoccupation différents et donc en quelques processus différents.

La détection de collision en phase large est l'acte de sectionner les zones où nous nous soucions de ce qui pourrait / pourrait / doit entrer en collision, et de les séparer pour le processus en phase étroite. En 2D, je recommande généralement d'utiliser un arbre quadruple pour cela. Pour cela, nous aurons besoin de ce que Rectanglenous avons construit plus tôt et de lui fournir une détection de collision AABB. Cela signifie Axis Aligned Bounding Box et nous l'utiliserons pour déterminer que pour une boîte non tournante dans Alaquelle aucune partie de la boîte Bn'existe A. Il découle de l'hypothèse qu'aucune partie de Bne peut exister à l'intérieur d' Aune collision s'il y a intersection.

Un arbre quadruple est un processus récursif dans lequel vous déterminez une profondeur maximale ou autorisez la quantité de votre objet à empêcher à la place une profondeur de récursion infinie. Il regroupe les corps physiques en 4 régions (d'où le nom) et devrait vous permettre d'accéder à chaque quad séparément. Vous entreriez alors dans chacun de ces quatre quads, et effectuez le même processus que je ne vais pas décrire ici par souci de concision mais qui est disponible ici: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees- pour détecter les collisions probables dans l'espace 2D - gamedev-374

Collision en phase étroiteest le processus consistant à parcourir vos groupes de formes dont nous avons déjà déterminé qu'elles entreront / pourraient / entrer en collision et à effectuer un contrôle de collision plus discret, à ce stade, nous commençons à nous soucier de savoir si les objets tournent ou non (j'ai gagné '' t couvrir cela, lorsque vous êtes passé ces phases de collision cherchent à détecter la collision avec un moment angulaire) et quelle forme est réellement leur corps de collision. Pour effectuer cette partie de la collision, vous spécialiserez vos méthodes comme vous l'avez décrit ci-dessus (création de fonctions spécifiques pour AABBvsCircle, OBBvsCircle, CirclevsCircle, PolygonvsPoint, PolygonvsCircle, PointvsCircle, etc.) Cependant, ces méthodes elles-mêmes peuvent également être effectuées de manière stratifiée comme ci-dessus.

Vos contrôles de séparation primitives sont les discrets, les méthodes de détection de collision spécialisés ou les généraux comme SAT selon le cas d' utilisation et doit tout simplement retourner soit une valeur true / false, ou retourner un objet relationnel tel qu'un Manifold, Joint, CollisionObjectetc. , qui aurait une connexion avec les deux formes détectées comme étant en collision, et toute information à leur sujet nécessaire pour résoudre la collision, comme la profondeur de collision ou la vitesse (les données dont vous avez besoin dans votre manifold dépendent de la méthode de résolution que vous utilisez). Cet objet que vous passez ensuite à un Solverqui devrait éliminer les différences entre toutes les différentes formes qui pourraient entrer en collision, en acceptant uniquement un Manifoldet en n'acceptant aucune information particulière sur les formes.

Résumé Le Solverprendra le Manifoldproduit en entrant en collision une primitive Aavec une primitive B, en utilisant d'abord un regroupement de phases large (tout contre monde) puis une détection de phase étroite (A contre B) et si les formes sont non polygonales doivent être spécialisées, le Solverproduit alors soit nouveau Vectors pour les positions et les vitesses des formes en collision, ou un objet que le PhysicsEnvironmentou Worldpeut ensuite utiliser pour résoudre la collision sur ses enfants, puis enfin mettre à jour le QuadTreeet répéter ce processus sur l'image suivante. Si les deux formes en collision sont des polygones, la spécialisation ne doit être effectuée que dans le souci d'améliorer les performances, sinon simplement en utilisant le théorème de l'axe de séparation