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

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

• Détection dynamique des collisions à l'aide de boîtes de délimitation orientées [PDF]

À 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?

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.

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!

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.

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.

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
}

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
 }
}