Fonction de support dans l'algorithme GJK

Question

J'essaye d'implémenter l'algorithme GJK mais je me suis bloqué instantanément.

Le problème est d'implémenter la fonction de support qui n'est pas O (n^2). Comme c'est le cas maintenant, je calcule la différence complète de Minkowski, et il n'y a vraiment aucun intérêt à faire l'algorithme GJK. (ou est-ce?)

Ce que je veux dire par support-fonction est la fonction qui renvoie le point de la différence de Minkowski qui est le plus éloigné dans une direction spécifiée. Je suppose que cela ne devrait pas être O (n^2) comme c'est le cas dans mon implémentation actuelle.

Answer 1

La fonction de support la plus simple serait 0 (n), c'est-à-dire trouver le meilleur produit scalaire dans une direction.

public Vector3 MaxPointAlongDirection(Vector3 directionToMove) 
    { 
     float max = float.NegativeInfinity; 
     int index = 0; 
     for (int i = 0; i < vertices.Length; i++) 
     { 
      float dot = Vector3.Dot(vertices[i], directionToMove); 
      if (dot > max) 
      { 
       max = dot; 
       index = i; 
      } 
     } 
     return vertices[index]; 
    } 

Une autre approche plus rapide pour une coque convexe triangulaire serait l'escalade; 1 Calculez les informations d'adjacence pour chaque point. 2 Commencez par un point aléatoire pour trouver le meilleur produit scalaire pour tous les points adjacents. 3 Faire ce nouveau point le point courant répétez les étapes 2 4 arrêt lorsqu'aucune meilleur produit se trouve (ce qui serait valable puisque l'objet est convexe donc il a pas des maxima locaux)

ou une hiérarchie Dobkin-Kirkpatrick.

Dans le cas où les objets sont en rotation, le vecteur directionToMove peut être transformé par rapport à l'objet pivoté (en cours de traitement). De ce fait, il n'est pas nécessaire de faire pivoter tous les points.

Answer 2

Eh bien, le GJK vous donnerait le point le plus proche de la somme de Minkowski à l'origine. Si rien d'autre ne bouge, alors votre somme de Minkowski serait la même, et le point le plus proche aussi.

Habituellement, les gens supposent que les corps sont libres de bouger et de tourner. Dans ce cas, les résultats changent tout le temps.

Sur le cas de traduction, vous devriez pouvoir réutiliser votre différence Minkowski. Dans le cas de rotation, vous devrez recalculer. Ce serait un problème pour de nombreuses applications en temps réel.

Si votre algorithme utilise implicitement la différence de Minkowski, au moyen des fonctions de support, vous n'avez pas besoin de recalculer quoi que ce soit. C'est l'un des avantages de l'utilisation des fonctions de support.

Certaines formes ont une forme très facile pour la fonction de support. Dans ce cas, vous n'avez pas besoin de calculer quoi que ce soit. C'est un autre avantage. Et, enfin, vous pouvez ajouter les fonctions de support à faire pour la fonction de support d'une somme de Minkowski. Une grande propriété, puisque de cette façon vous pouvez former une famille de formes en utilisant des primitives, et obtenir que GJK travaille dessus.

Si vous avez une coque convexe de n points sur le plan, la fonction de support peut être précalculée en trouvant les bords du polygone de coque et en triant les angles des vecteurs normaux. Chaque sommet de la coque aura deux normales. Va juste séquentiellement et trouve si ta direction est entre ces vecteurs normaux. Cela vous donnerait O (n).

Vous pouvez également modifier l'ordre de comparaison et en faire O (log (n)).