Combien et quels axes utiliser pour une collision OBB 3D avec SAT

29

J'ai implémenté le SAT sur la base de:

À la page 7, dans le tableau, il fait référence aux 15 axes à tester pour que nous puissions trouver une collision, mais avec seulement Ax, Ay et Az, je reçois déjà des collisions.

Pourquoi dois-je tester tous les autres cas? Existe-t-il une situation où seuls Ax, Ay et Az ne suffisent pas?

GriffinHeart
la source

Réponses:

56

Vous obtenez peut-être des faux positifs. Collisions détectées mais pas vraiment en collision.

Le nombre 15 vient de

  • 3 axes de l'objet A (normales de face)
  • 3 axes à partir de l'objet B (faces normales)
  • 9 axes de toutes les paires d'arêtes de A et d'arêtes de B (3x3)
  • = 15 au total

Les 9 axes sont constitués de produits croisés des bords de A et des bords de B

  1. Ae1 x Be1 (arête 1 de A arête transversale 1 de B)
  2. Ae1 x Be2
  3. Ae1 x Be3
  4. Ae2 x Be1
  5. ... etc

Les 6 premiers axes (à partir des normales de face) sont utilisés pour vérifier s'il y a un coin d'un objet qui coupe une face de l'autre objet. (ou plus correctement pour éliminer ces types de collisions)

L'ensemble des 9 axes formés par les produits croisés des bords est utilisé pour considérer la détection de collision bord à bord, où aucun sommet ne pénètre dans l'autre objet. Comme la collision «presque» sur la photo ci-dessous. Supposons pour le reste de cette réponse que les deux cases de l'image ne se heurtent pas réellement, mais sont séparées par une petite distance.

entrez la description de l'image ici

Regardons ce qui se passe si nous utilisons simplement les normales à 6 faces pour SAT. La première image ci-dessous montre un axe de la boîte bleue et 2 axes de la boîte jaune. Si nous projetons les deux objets sur ces axes, nous obtiendrons un chevauchement sur les trois. La deuxième image ci-dessous montre les deux axes restants de la boîte bleue et l'axe restant de la boîte jaune. Une nouvelle projection sur ces axes montrera des chevauchements sur les 3.

Ainsi, la simple vérification des 6 normales de face affichera des chevauchements sur les 6 axes, ce qui, selon le SAT, signifie que les objets entrent en collision, car nous n'avons pas pu trouver de séparation. Mais bien sûr, ces objets ne se heurtent pas. La raison pour laquelle nous n'avons pas trouvé de séparation est parce que nous n'avons pas regardé assez fort!

entrez la description de l'image ici entrez la description de l'image ici

Alors, comment allons-nous trouver cet écart? L'image ci-dessous montre un axe sur lequel la projection des deux objets révélera une séparation.

entrez la description de l'image ici

D'où tirons-nous cet axe?

Si vous imaginez glisser un morceau de carte rigide dans l'espace, cette carte fera partie du plan de séparation. Si nous projetons sur la normale de ce plan (flèche noire dans l'image ci-dessus), nous verrons la séparation. Nous savons ce que ce plan est parce que nous avons deux vecteurs qui se trouvent sur ce plan) Un vecteur est aligné avec le bord de bleu et l'autre vecteur est aligné avec le bord de jaune et comme nous le savons tous, la normale à un plan est simplement le produit croisé de deux vecteurs se trouvant sur le plan.

Ainsi, pour les OOBB, nous devons vérifier chaque combinaison (9 d'entre eux) de produits croisés des bords des deux objets pour nous assurer de ne manquer aucune séparation bord-bord.

Ken
la source
2
Super explication! Et merci pour les photos. Comme le note @Acegikmo, c'est un peu déroutant quand vous dites que "9 axes sont constitués de produits croisés des bords de A et des bords de B", car nous pouvons simplement utiliser les normales plutôt que les bords. Merci encore :)
5
@joeRocc Pour les cuboïdes, vous avez raison, utilisez simplement les normales, car les normales et les bords sont alignés, mais pour d'autres formes (par exemple, tétraèdres, autres polyèdres), les normales ne sont pas alignées avec les bords.
Ken
Merci beaucoup mec! Je lisais ce joli livre intitulé "Développement du moteur de physique des jeux" et je suis tombé sur ce problème. Je ne savais pas pourquoi utilisons-nous 15 axes. Merci beaucoup. Maintenant, je suis assez confiant pour m'en vanter. ; D
Ankit singh kushwah
11

Les notes de réponse de Ken :

Les 9 axes sont constitués de produits croisés des bords de A et des bords de B

Il est un peu déroutant de se référer aux bords, car il y a 12 bords par rapport à 6 normales, alors vous pourriez aussi bien utiliser les trois normales principales pour la même sortie - les bords sont tous alignés avec les normales, donc je recommande de les utiliser à la place !

Notez également que les normales pointant le long du même axe, mais dans une direction différente, sont ignorées, et nous nous retrouvons donc avec trois axes uniques.

Une autre chose que j'aimerais ajouter, c'est que vous pouvez optimiser ce calcul en quittant tôt si vous trouvez un axe de séparation, avant de calculer tous les axes que vous souhaitez tester. Donc, non, vous n'avez pas besoin de tester tous les axes dans tous les cas, mais vous devez être prêt à les tester tous :)

Voici une liste complète des axes à tester, étant donné deux OBB, A et B, où x, y et z font référence aux vecteurs de base / trois normales uniques. 0 = axe x, 1 = axe y, 2 = axe z

  1. a0
  2. a1
  3. a2
  4. b0
  5. b1
  6. b2
  7. croix (a0, b0)
  8. croix (a0, b1)
  9. croix (a0, b2)
  10. croix (a1, b0)
  11. croix (a1, b1)
  12. croix (a1, b2)
  13. croix (a2, b0)
  14. croix (a2, b1)
  15. croix (a2, b2)

Il y a aussi une petite mise en garde, que vous devez savoir.

Le produit croisé vous donnera un vecteur nul {0,0,0} lorsque deux axes quelconques entre les objets pointent dans la même direction.

De plus, puisque cette partie a été omise, voici mon implémentation pour vérifier si la projection se chevauche ou non. Il y a probablement une meilleure façon, mais cela a fonctionné pour moi! (Utilisation d'Unity et de son API C #)

// aCorn and bCorn are arrays containing all corners (vertices) of the two OBBs
private static bool IntersectsWhenProjected( Vector3[] aCorn, Vector3[] bCorn, Vector3 axis ) {

    // Handles the cross product = {0,0,0} case
    if( axis == Vector3.zero ) 
        return true;

    float aMin = float.MaxValue;
    float aMax = float.MinValue;
    float bMin = float.MaxValue;
    float bMax = float.MinValue;

    // Define two intervals, a and b. Calculate their min and max values
    for( int i = 0; i < 8; i++ ) {
        float aDist = Vector3.Dot( aCorn[i], axis );
        aMin = ( aDist < aMin ) ? aDist : aMin;
        aMax = ( aDist > aMax ) ? aDist : aMax;
        float bDist = Vector3.Dot( bCorn[i], axis );
        bMin = ( bDist < bMin ) ? bDist : bMin;
        bMax = ( bDist > bMax ) ? bDist : bMax;
    }

    // One-dimensional intersection test between a and b
    float longSpan = Mathf.Max( aMax, bMax ) - Mathf.Min( aMin, bMin );
    float sumSpan = aMax - aMin + bMax - bMin;
    return longSpan < sumSpan; // Change this to <= if you want the case were they are touching but not overlapping, to count as an intersection
}
Acegikmo
la source
1
Bienvenue sur le site. Veuillez consulter le centre d'aide , et notez en particulier que ce site n'est pas un forum et que "répondre" à d'autres réponses n'est pas une bonne idée (car votre "réponse" peut ne pas apparaître avant le message auquel vous répondez). Il est préférable d'écrire vos réponses de manière autonome et d'utiliser des commentaires si vous souhaitez spécifiquement clarifier un message existant.
Josh
Merci pour la clarification Acegikmo! J'étais un peu dérouté par la référence aux bords aussi. @Josh Petrie vous devriez mettre des smileys à la fin de vos commentaires pour que les débutants sachent que vous ne les
voir mon commentaire ci-dessus concernant les bords par rapport aux normales
Ken
2

exemple c # de travail basé sur la réponse d'Acegikmo (en utilisant des API d'unité):

using UnityEngine;

public class ObbTest : MonoBehaviour
{
 public Transform A;
 public Transform B;

 void Start()
 {
      Debug.Log(Intersects(ToObb(A), ToObb(B)));
 }

 static Obb ToObb(Transform t)
 {
      return new Obb(t.position, t.localScale, t.rotation);
 }

 class Obb
 {
      public readonly Vector3[] Vertices;
      public readonly Vector3 Right;
      public readonly Vector3 Up;
      public readonly Vector3 Forward;

      public Obb(Vector3 center, Vector3 size, Quaternion rotation)
      {
           var max = size / 2;
           var min = -max;

           Vertices = new[]
           {
                center + rotation * min,
                center + rotation * new Vector3(max.x, min.y, min.z),
                center + rotation * new Vector3(min.x, max.y, min.z),
                center + rotation * new Vector3(max.x, max.y, min.z),
                center + rotation * new Vector3(min.x, min.y, max.z),
                center + rotation * new Vector3(max.x, min.y, max.z),
                center + rotation * new Vector3(min.x, max.y, max.z),
                center + rotation * max,
           };

           Right = rotation * Vector3.right;
           Up = rotation * Vector3.up;
           Forward = rotation * Vector3.forward;
      }
 }

 static bool Intersects(Obb a, Obb b)
 {
      if (Separated(a.Vertices, b.Vertices, a.Right))
           return false;
      if (Separated(a.Vertices, b.Vertices, a.Up))
           return false;
      if (Separated(a.Vertices, b.Vertices, a.Forward))
           return false;

      if (Separated(a.Vertices, b.Vertices, b.Right))
           return false;
      if (Separated(a.Vertices, b.Vertices, b.Up))
           return false;
      if (Separated(a.Vertices, b.Vertices, b.Forward))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Right, b.Forward)))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Up, b.Forward)))
           return false;

      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Right)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Up)))
           return false;
      if (Separated(a.Vertices, b.Vertices, Vector3.Cross(a.Forward, b.Forward)))
           return false;

      return true;
 }

 static bool Separated(Vector3[] vertsA, Vector3[] vertsB, Vector3 axis)
 {
      // Handles the cross product = {0,0,0} case
      if (axis == Vector3.zero)
           return false;

      var aMin = float.MaxValue;
      var aMax = float.MinValue;
      var bMin = float.MaxValue;
      var bMax = float.MinValue;

      // Define two intervals, a and b. Calculate their min and max values
      for (var i = 0; i < 8; i++)
      {
           var aDist = Vector3.Dot(vertsA[i], axis);
           aMin = aDist < aMin ? aDist : aMin;
           aMax = aDist > aMax ? aDist : aMax;
           var bDist = Vector3.Dot(vertsB[i], axis);
           bMin = bDist < bMin ? bDist : bMin;
           bMax = bDist > bMax ? bDist : bMax;
      }

      // One-dimensional intersection test between a and b
      var longSpan = Mathf.Max(aMax, bMax) - Mathf.Min(aMin, bMin);
      var sumSpan = aMax - aMin + bMax - bMin;
      return longSpan >= sumSpan; // > to treat touching as intersection
 }
}
Bas Smit
la source