Je cherchais des méthodes efficaces pour la détection de collision dans une scène avec des objets statiques et dynamiques lorsque je suis tombé sur des "champs de distance".
J'ai essayé de rechercher et de comprendre ce concept, mais je n'ai pu trouver que des articles écrits dans un langage très complexe. Quelqu'un peut-il expliquer en termes simples quels sont les champs de distance et comment peuvent-ils être utilisés pour la détection de collision?
collision-detection
Muhammad Omer
la source
la source
Réponses:
Un champ de distance ( ou transformation de distance ou carte de distance ) est une structure quadrillée où chaque cellule de la grille représente la distance la plus courte entre cette cellule et une cellule possédant une autre propriété. Le plus souvent, cette «autre propriété» est un type de cellule de limite, comme un mur qu'un joueur ne peut pas franchir ou la surface d'un maillage.
Les champs de distance ont beaucoup d'applicabilité. Vous pourriez imaginer, par exemple, comment ils pourraient être utilisés pour mettre en œuvre le guidage de mouvement (en créant des cartes de distance pour les objets dangereux ou souhaitables et en pondérant les décisions de mouvement par eux).
Cependant, vous avez spécifiquement posé une question sur la collision. L'utilisation de champs de distance pour effectuer la détection de collision entre deux objets en mouvement peut rapidement devenir plutôt inefficace, car la reconstruction des champs de distance peut devenir très lente à mesure que l'étendue du champ augmente (en particulier en 3D, bien que les méthodes pour améliorer le temps de génération soient un domaine de recherche ).
La collision de champ de distance est donc principalement utilisée pour détecter la collision d'un objet dynamique avec un objet statique. Le plus souvent, j'ai vu cela pour détecter la collision d'objets en tissu (ou d'autres objets déformables) avec d'autres objets fixes de la scène .
En gros, cela est accompli en utilisant un champ de distance signé pour l'objet statique où un signe (souvent négatif) représente une cellule à l' intérieur du maillage et un autre (évidemment souvent positif) représente une cellule à l'extérieur du maillage. Les particules du maillage en tissu peuvent être transformées dans l'espace local du maillage statique, et les positions "avant" et "après" d'une particule au cours d'une étape de simulation de tissu donnée peuvent être vérifiées par rapport au champ de distance pour déterminer si le signe a changé (et ainsi une collision s'est produite). C'est la méthode discutée dans cet article de 2003 sur la simulation de tissu , par exemple.
Notez que je ne suggérerais pas d'utiliser les champs de distance comme seule méthode de détection de collision. Ils peuvent être assez efficaces pour ce qu'ils sont bons, mais ils ne sont pas bons dans tout. La meilleure façon de parvenir à une détection efficace des collisions consiste souvent à utiliser plusieurs méthodes, de manière hiérarchique, avec une précision croissante lorsque vous parcourez la hiérarchie.
la source
En géométrie et infographie et également utilisé en traitement d'image, un champ de distance (en termes simples), est une étiquette sur chaque cellule (pixel en traitement d'image) avec la distance de l'objet polygonal le plus proche ou un pixel avec des propriétés spéciales en traitement d'image .
En d'autres termes, c'est une étiquette pour chaque cellule qui a la valeur d'un objet le plus proche avec une propriété spéciale définie par la carte. L'objet varie en fonction de l'application.
L'image ci-dessus contient une carte de distance pour les pixels limites. Remarquez comment chaque pixel contient la distance au pixel limite le plus proche. La distance est calculée en utilisant la distance de Manhattan.
Il existe différentes façons de calculer la distance, les approches typiques incluent:
En conservant une carte de distance pour les objets de la scène, vous pouvez vérifier si deux objets entrent en collision en fonction de leur distance. Malheureusement, le maintien d'une telle carte coûte cher. Et cela est généralement utilisé dans les objets auto-entrecroisés comme les simulations de tissu où les cartes de distance peuvent être conservées et mises à jour plus efficacement en raison de la nature de l'objet.
la source