Сколько и какие оси использовать для столкновения 3D OBB с SAT

Я внедряю SAT на основе:

• Динамическое обнаружение столкновений с использованием ориентированных ограничивающих рамок [PDF]

На странице 7, в таблице, она ссылается на 15 ось для проверки, чтобы мы могли найти столкновение, но только с Ax, Ay и Az, я уже получаю столкновения.

Зачем мне проверять все остальные случаи? Есть ли ситуации, когда просто Axe, Ay и Az недостаточно?

Вы можете получать ложные срабатывания. Столкновения обнаружены, но столкновения не имеют.

№ 15 происходит от

• 3 оси от объекта А (нормали лица)
• 3 оси от объекта B (нормали лица)
• 9 осей от всех пар ребер A и ребер B (3x3)
• = 15 всего

9 осей составлены из перекрестных произведений ребер A и ребер B

1. Ae1 x Be1 (Край 1 А, Крест 1, Б)
2. Ae1 x Be2
3. Ae1 x Be3
4. Ae2 x Be1
5. ... и так далее

Первые 6 осей (из нормали грани) используются для проверки, пересекает ли угол одного объекта грань другого объекта. (или правильнее устранить подобные столкновения)

Набор из 9 осей, образованных перекрестными произведениями ребер, используется для определения столкновения ребер на ребре, где нет вершины, проникающей в другой объект. Как «почти» столкновение на фото ниже. Предположим для остальной части этого ответа, что два поля на рисунке на самом деле не сталкиваются, а находятся на небольшом расстоянии.

Давайте посмотрим, что произойдет, если мы просто используем 6 нормалей лица для SAT. Первое изображение ниже показывает одну ось от синей рамки и 2 оси от желтой рамки. Если мы спроецируем оба объекта на эти оси, мы получим перекрытие для всех трех. Второе изображение ниже показывает две оставшиеся оси синего прямоугольника и оставшуюся ось желтого прямоугольника. Снова проецирование по этим осям покажет перекрытия на всех 3.

Так что только проверка 6 нормалей лица покажет перекрытия по всем 6 осям, что, согласно SAT, означает, что объекты сталкиваются, потому что мы не смогли найти разделение. Но, конечно, эти объекты не сталкиваются. Причина, по которой мы не нашли разделения, заключается в том, что мы не выглядели достаточно усердно!

Так как же нам найти этот пробел? На изображении ниже показана ось, на которой проекция обоих объектов обнаружит разделение.

Откуда мы берем эту ось?

Если вы представите, что вставили кусок жесткой карты в щель, эта карта будет частью разделяющей плоскости. Если мы проецируем на нормаль этой плоскости (черная стрелка на рисунке выше), мы увидим разделение. Мы знаем, что это за плоскость, потому что у нас есть два вектора, которые лежат на этой плоскости) Один вектор выровнен с краем синего цвета, а другой вектор выровнен с краем желтого цвета, и, как мы все знаем, нормаль к плоскости - это просто перекрестное произведение двух векторов, лежащих на плоскости.

Поэтому для OOBB нам нужно проверить каждую комбинацию (9 из них) перекрестных произведений краев двух объектов, чтобы убедиться, что мы не пропустили никакого разделения ребро-ребро.

Ответ Кена отмечает:

9 осей составлены из перекрестных произведений ребер A и ребер B

Несколько странно ссылаться на ребра, так как имеется 12 ребер по сравнению с 6 нормалями, когда вы можете также использовать три основных нормали для одного и того же вывода - ребра все выровнены с нормалями, поэтому я рекомендую использовать их вместо !

Также обратите внимание, что нормали, направленные вдоль одной и той же оси, но в другом направлении, игнорируются, и поэтому у нас остаются три уникальные оси.

Еще одна вещь, которую я хотел бы добавить, это то, что вы можете оптимизировать этот расчет, выйдя пораньше, если вы найдете разделяющую ось, прежде чем вычислять все оси, которые вы хотите проверить. Так что нет, вам не нужно проверять все оси в каждом случае, но вы должны быть готовы проверить их все :)

Вот полный список осей для тестирования, учитывая два OBB, A и B, где x, y и z относятся к базисным векторам / трем уникальным нормалям. 0 = ось x, 1 = ось y, 2 = ось z

1. a0
2. a1
3. a2
4. b0
5. b1
6. Би 2
7. крест (а0, б0)
8. крест (а0, б1)
9. крест (а0, б2)
10. крест (а1, б0)
11. крест (а1, б1)
12. крест (а1, б2)
13. крест (а2, б0)
14. крест (а2, б1)
15. крест (а2, б2)

Есть также небольшое предостережение, о котором вы должны знать.

Перекрестное произведение даст вам нулевой вектор {0,0,0}, когда любые две оси между объектами будут указывать в одном направлении.

Кроме того, так как эта часть была пропущена, вот моя реализация, чтобы проверить, перекрывается ли проекция или нет. Возможно, есть лучший способ, но это сработало для меня! (Используя Unity и его C # API)

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

пример работы c #, основанный на ответе Acegikmo (используя некоторые API Unity):

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