Comment effectuer une détection de collision sur des objets constitués de nombreux petits triangles?
13
Je comprends que n'importe quelle forme peut être créée (ou approximée) par des triangles plus petits. Tout rectangle peut être créé par 2 triangles plus petits. Tout cercle peut être créé par de nombreux triangles minces de «tranche de pizza». Comment cela se traduit-il en détection de collision?
Je comprends comment calculer le chevauchement d'un rectangle à l'aide des sommets. Je comprends comment calculer le chevauchement des cercles en utilisant le centre, les rayons et la distance.
Mais comment faire la détection de collision sur des formes faites de petits triangles? Pas de détails, mais juste le concept général ....
Mais comment faire la détection de collision sur des formes faites de petits triangles?
En ne le faisant pas.
La détection des collisions contre une collection de triangles arbitraires (ou pire, entre deux collections de triangles arbitraires) est d'un coût prohibitif.
Au lieu de cela, nous effectuons généralement la détection de collection de manière hiérarchique, en commençant d'abord par des formes simples et extrêmement grossières (comme des boîtes ou des sphères) qui se rapprochent (mal) de l'objet sous-jacent.
Cela nous permet de rejeter rapidement la majorité des collisions potentielles comme «ne se produisant pas», ce qui est le cas habituel. Dans le cas où une telle vérification brute passe, cela indique une collision réelle potentielle, et nous procédons à la vérification par rapport à une approximation plus détaillée de la forme sous-jacente (telle que celle faite de plusieurs formes de capsules étroitement ajustées, ou de nombreuses boîtes de délimitation alignées).
Essentiellement, la détection des collisions commence par des tests bruts et, au fur et à mesure que ces tests réussissent, se poursuit vers une représentation de plus en plus détaillée. Cette image, fournie par Shiro dans un commentaire à la réponse d' Alexandre , illustre comment un modèle complexe (un humain) peut être représenté par une série de formes plus simples:
Rarement avons-nous réellement besoin d'effectuer une collision au niveau d'un triangle individuel, et lorsque nous le faisons, nous avons généralement utilisé les méthodes les plus grossières pour explorer un très petit ensemble de triangles potentiels à tester. À ce stade, des algorithmes spécifiques sont utilisés pour effectuer les tests, tout comme vous testeriez si deux rectangles se chevauchent. Par exemple, vous pouvez déterminer si et où un rayon frappe un triangle .
Merci. Oui, si je faisais un jeu, j'utiliserais simplement un moteur existant. Mais, je veux juste comprendre les idées de base qui sont implémentées dans un moteur de détection de collision prédéfini. Dans votre diagramme ci-dessus, vous utiliseriez des mathématiques de rectangle pour voir si quelque chose touche TOUTE la douzaine de rectangles qui composent l'homme. Est-ce là l'idée de base?
JackOfAll
Ce sont des boîtes englobantes orientées (3D) et non des rectangles. Mais oui. Si je devais tester si un rayon (représentant, disons, une balle) est entré en collision avec le joueur, je testerais le rayon contre ces boîtes - peut-être après avoir d'abord testé contre une boîte géante représentant le personnage entier - pas contre chaque triangle du maillage de rendu).
L'idée est que vous pouvez utiliser une approximation approximative du personnage, comme les cadres de délimitation orientés montrés dans l'image ci-dessus, et tester d'abord pour faire un test de frappe moins cher, et s'il y a collision, puis descendre à un niveau inférieur SI NÉCESSAIRE, tester les triangles individuels contenus dans la boîte englobante. En règle générale, plusieurs BV différents peuvent être utilisés de manière hiérarchique, celui de l'extérieur étant moins précis mais le plus rapide à tester (sphère, boîte englobante), et forant vers quelque chose de plus spécifique (k-DOP), et potentiellement forant encore plus loin (triangles )
Kik
4
La détection de collision est basée sur la géométrie (primitives telles que ligne, plans, sphères, boîtes, capsules, cylindres).
Si vous devez effectuer une détection de collision sur des formes faites de triangle, par exemple un terrain qui n'est pas plat, vous devez tester tous les triangles qui forment le maillage.
Si vous arrivez à ce point, je vous conseille fortement d'utiliser un moteur de détection de collision prédéfini, car ce genre de choses devient assez complexe, assez rapide.
Comment faites-vous la détection de collision sur des formes composées de triangles?
JackOfAll
@JackOfAll il a déjà mentionné que dans sa réponse, c'est en utilisant généralement des formes géométriques i.stack.imgur.com/CAhxn.jpg
dimitris93
@JackOfAll J'ai modifié ma réponse; et comme le dit Shiro, si vous avez des "objets" plus complexes dans votre environnement (corps, chaises, voitures, etc ...), dans le développement de jeux, ils sont généralement constitués de primitives plus simples qui sont liées entre elles. La détection des collisions se fait sur les formes primitives, mais la simulation physique se fait ensuite sur l'ensemble du corps.
Vaillancourt
4
Je n'essaie pas littéralement de créer un jeu, je veux juste comprendre les idées de base qui sont implémentées dans un moteur de détection de collision prédéfini. Si je faisais un jeu, je ne réinventerais clairement pas la roue, d'accord.
La détection de collision est basée sur la géométrie (primitives telles que ligne, plans, sphères, boîtes, capsules, cylindres).
Si vous devez effectuer une détection de collision sur des formes faites de triangle, par exemple un terrain qui n'est pas plat, vous devez tester tous les triangles qui forment le maillage.
Si vous arrivez à ce point, je vous conseille fortement d'utiliser un moteur de détection de collision prédéfini, car ce genre de choses devient assez complexe, assez rapide.
la source