Comment fonctionne la détection 3D des collisions et des objets?
je me le suis toujours demandé. Dans un jeu comme GTA où il ya 10s de milliers d'objets, comment le jeu sait dès que vous êtes sur un paquet de santé?
il ne peut pas y avoir un écouteur d'événement pour chaque objet? L'itération n'est pas bon non plus? Je me demande comment c'est fait.
6 réponses
il n'y a pas de réponse unique à cela, mais les grands mondes sont souvent espacés en utilisant quelque chose comme un quadtree ou KD-tree qui apporte des temps de recherche pour trouver les voisins les plus proches en dessous du temps linéaire (puissance fractionnaire, ou au pire O( N^(2/3) ) pour un jeu en 3D). Ces méthodes sont souvent appelées BSP pour le partitionnement de l'espace binaire.
en ce qui concerne la collision détection, chaque objet a aussi généralement un volume limite mesh (ensemble de polygones formant une coque convexe) associé à elle. Ces mailles très simplifiées (parfois un simple cube) ne sont pas dessinées mais sont utilisées pour la détection des collisions. La méthode la plus rudimentaire est de créer un plan qui est perpendiculaire à la ligne reliant les points médians de chaque objet avec le plan coupant la ligne au point milieu de la ligne. Si le volume limite d'un objet a des points sur de part et d'autre de cet avion, il s'agit d'une collision (il suffit de tester un des deux volumes limitants par rapport à l'avion). Une autre méthode est l'algorithme de distance amélioré GJK . Si vous voulez un tutoriel pour plonger à travers, consultez Nehe Productions' OpenGL leçon #30 .
incidemment, les volumes limitants peuvent également être utilisés pour d'autres optimisations comme ce qui est appelé occlusion queries . C'est un processus de détermination des objets qui sont derrière d'autres objets (obturateurs) et n'ont donc pas à être transformés et rendus. Les volumes limites peuvent également être utilisés pour Frustum culling qui est le processus de déterminer quels objets sont en dehors du volume de visualisation en perspective (trop près, trop loin, ou au-delà de votre angle de champ de vision) et donc ne doivent pas être rendus.
comme Kylotan l'a noté, en utilisant une limite le volume peut générer de faux positifs lors de la détection de l'occlusion et ne fonctionne tout simplement pas du tout pour certains types d'objets tels que les toroïdes (par exemple en regardant à travers le trou dans un donut). Avoir des objets comme ceux-ci occlude correctement est un tout autre fil sur portail-élimination .
Quadtrees and Octrees , another quadtree , sont des moyens populaires, en utilisant le partitionnement de l'espace, pour accomplir ceci. L'exemple suivant montre une réduction de 97% du traitement par rapport à une recherche de collisions par la force brute paire-par-paire.
une technique courante dans les moteurs de physique de jeu est la méthode sweep-and-prune. Cela est expliqué dans notes SIGGRAPH de David Baraff (voir le chapitre mouvement avec des contraintes). Havok l'utilise certainement, je pense que C'est une option dans Bullet, mais je ne suis pas sûr pour PhysX.
l'idée est que vous pouvez regarder les chevauchements de aabbs (axis-aligned bounding boxes) sur chaque axe; si la projection de deux objets aabbs se chevauchent sur les trois axes, alors le Aabbs doit se chevaucher. Vous pouvez vérifier chaque axe relativement rapidement en triant les points de début et de fin de L'AABBs; il y a beaucoup de cohérence temporelle entre les cadres car habituellement la plupart des objets ne se déplacent pas très vite, donc le tri ne change pas beaucoup.
une fois que sweep-and-prune détecte un chevauchement entre AABBs, vous pouvez faire la vérification plus détaillée pour les objets, par exemple sphère vs boîte. Si le contrôle détaillé révèle une collision, vous pouvez alors résoudre la collision en appliquant forces, et / ou déclencher un événement de jeu ou jouer un effet sonore.
Correct. Normalement, il n'y a pas d'écouteur d'événements pour chaque objet. Souvent il y a une structure d'arbre non-binaire dans la mémoire qui imite votre carte de jeux. Imaginez une station de métro/carte de métro. Cette structure de mémoire est une collection de choses dans le jeu. Vous le joueur, les monstres et les éléments que vous pouvez ramasser ou des éléments qui pourraient exploser et vous faire du mal. Ainsi, lorsque le joueur se déplace autour du jeu, le pointeur d'objet du Joueur est déplacé dans la structure mémoire du jeu/de la carte.
voir Comment faire pour que mes entités de jeu connaissent les choses qui les entourent?
Je voudrais recommander le livre solide de Christer Ericson sur la détection de collision en temps réel. Il présente les bases de la détection des collisions tout en fournissant des références sur les efforts de recherche contemporains.
détection de Collision en temps réel (la série Morgan Kaufmann dans la technologie Interactive 3-d)
Il ya beaucoup d'optimisations peuvent être utilisées.
Premièrement-tout objet (disons avec l'index i par exemple) est limité par le cube, avec les coordonnées centrales CXi , CYi , et la taille Si
Deuxièmement - détection de collision fonctionne avec des estimations:
a) trouver tous les cubes pairs i, j avec la condition: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
B) maintenant, nous ne travaillons qu'avec les couples got en a). Nous calculons les distances entre eux plus précisément, quelque chose comme Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)) , objets maintenant représentés comme ensembles de quelques nombres de figures simples - cubes, sphères, cônes - et nous utilisant des formules de géométrie pour vérifier ces intersections de figures.
c) Les objets de b) avec des intersections détectées sont traités comme des collisions avec calcul physique etc.