Использование AABB

Как работать с AABB?

рис.1 пример AABB в 2D

Хранить AABB лучше в виде двух векторов - позиции в пространстве (P) и размеров (E), но если планируется использовать проверку на пересечение со сферой, можно также сохранить и минимальную (vMin) и максимальную (vMax) точки. (рис. 1, а также Пример класса AABB) Обратите внимание, что размеры AABB указываются относительно позиции в пространстве.

Итак, для того, чтобы построить AABB для объекта, нужно всего лишь найти размеры объекта по осям координат, т.е. границы объекта. 

Это можно сделать, например, следующим образом (предполагается, что Vertices - это массив, в котором находятся уже трансформированные в мировое пространство вершины объекта):

void cdAABB::CreateFromVertices(const TArray<mVector> &Vertices)
{
   vMin = vMax = Vertices[0];

   // ищем минимальную/максимальную точки
   for (int i=1;i<Vertices.Num();i++) 
   {
      // проходим по x,y,z
      for (int t=0;t<3;t++)
      {
         vMax[t] = max(vMax[t], Vertices[i][t]);
         vMin[t] = min(vMin[t], Vertices[i][t]);
      }
   }

   // вычисляем размеры
   E = (vMax - vMin) / 2.f;

   // и положение в пространстве
   P = vMin + E;
}

Легко заметить, что на проверку всех вершин объекта (которых может быть несколько сотен или даже тысяч) может уйти огромное количество времени - строить AABB придется каждый кадр, т.к. при вращении объекта размеры AABB меняются.
В случае же аппаратного T&L это вообще недопустимая трата ресурсов, т.к. работа ускорителя в части трансформации дублируется.

Обойти это проблему можно, если воспользоваться OBB - построить один раз Bounding Box и вращать его вместе с объектом, а для создания AABB использовать только 8 точек этого OBB. Таким образом всего за 8 трансформаций мы получаем AABB и теряем точность проверки (рис.2)	рис. 2 К вопросу о точности
зеленым цветом обозначен OBB,  красным - оптимальный AABB,  циановым - AABB, построенный с помощью OBB.

Также можно в качестве AABB использовать куб такого размера, чтобы объект в любом положении не выходил за его пределы. Разумеется, в этом случае вообще ничего пересчитывать не надо, но зато точность проверки существенно снижается.

Итак, полученный с помощью вышеперечисленных махинаций AABB иногда более чем в два раза превышает размеры самого объекта и здесь возникает законный вопрос - а зачем вообще такие сложности? Проще сразу использовать OBB и не мучиться с преобразованиями туда-сюда...
Однако проверка на столкновения с AABB все еще быстрее, чем любая другая, и хотя выбор AABB в качестве единственной проверки, мягко говоря, не является лучшим вариантом, использовать AABB для предварительной грубой проверки перед более точной и более медленной, можно и нужно.

Как обнаружить столкновение AABB-AABB?

Очень просто. Нужно всего лишь проверить существование разделяющей оси. В случае с AABB (которые выровнены в мировой системе координат) осей всего три - X, Y и  Z и если Bounding Box-ы не пересекаются, по крайней мере одна из них является разделяющей.  Рассмотрим пример в 2D и проверку по оси Х (рис.3)

рис.3 Проверка по оси Х

В данном случае AABB не пересекаются - ось Х является разделяющей, т.к.

|Tx| > (Ax + Bx) 

Проще говоря, если расстояние между центрами двух AABB по определенной оси больше, чем сумма их размеров по этой оси, то данная ось является разделяющей и эти AABB не пересекаются.

Вот пример кода, реализующего эту проверку:

const bool cdAABB::OverlapsAABB(const cdAABB &aabb) const
{
   const mVector T = aabb.P - P;
   return fabs(T.x) <= (E.x + aabb.E.x) &&
          fabs(T.y) <= (E.y + aabb.E.y) &&
          fabs(T.z) <= (E.z + aabb.E.z);
}

Как обнаружить столкновение AABB-OBB?

Как обнаружить столкновение AABB-Sphere?

рис. 4 Расстояние до сферы

Для проверки на пересечение со сферой можно воспользоваться алгоритмом Арво, чтобы вычислить расстояние от AABB до центра сферы. Вернее, поскольку нам нужно только сравнить это расстояние с радиусом сферы, достаточно будет вычислить квадрат расстояния (sqrt, как известно, довольно медленная операция). Принцип следующий - проверяем по всем осям, попадает ли центр сферы в AABB, и если нет, то вычисляем расстояние по этой оси от границы AABB до центра сферы. Сумма квадратов расстояний по осям, разумеется, даст нам квадрат расстояния от AABB до центра сферы ("квадрат гипотенузы..." и т.д.) (рис.4)

И если полученный квадрат расстояния меньше квадрата радиуса, то сфера не пересекается с AABB.

Пример кода:

const bool cdAABB::OverlapsSphere(const cdSphere &sphere) const
{
   float d = 0, a;

   // проходим по осям X,Y,Z
   for (int i=0;i<3;i++)
   {
      // если центр сферы лежит перед AABB,
      if (sphere.P[i] < vMin[i])
      {
         // то вычисляем квадрат расстояния по этой оси
         a = sphere.P[i] - vMin[i];
         d += a * a;
      }

      // если центр сферы лежит после AABB,
      if (sphere.P[i] > vMax[i])
      {
         // то вычисляем квадрат расстояния по этой оси
         a = sphere.P[i] - vMax[i];
         d += a * a;
      }
   }

   return d <= (sphere.R * sphere.R);
}

Как обнаружить пересечение AABB-Line?

Речь идет о линии, имеющей конечные точки.  Итак, линию можно представить как вырожденный OBB, у которого осталась только одно измерение и, соответственно, одна ось (она же направление линии), таким образом, проверка опять же сводится к поиску разделяющей оси. (рис.5)  Поскольку линия может быть направлена в любую сторону, кроме X,Y,Z придется проверить также их векторные произведения с  вектором направления линии. Всего получается 6 проверок.

рис. 5 Пересечение AABB и линии

Пример кода:

const bool cdAABB::OverlapsLineSegment(const mVector &mid,      // средняя точка линии
                                       сonst mVector &dir,      // направление линии
                                       const Scalar hl) const   // полудлина линии
{
   const mVector T = P - mid;
   float r;

   // проверяем, является ли одна из осей X,Y,Z разделяющей
   if ( (fabs(T.x) > E.x + hl*fabs(dir.x)) || 
        (fabs(T.y) > E.y + hl*fabs(dir.y)) ||
        (fabs(T.z) > E.z + hl*fabs(dir.z)) )
      return false;

   // проверяем X ^ dir
   r = E.y*fabs(dir.z) + E.z*fabs(dir.y);
   if ( fabs(T.y*dir.z - T.z*dir.y) > r )
      return false;

   // проверяем Y ^ dir
   r = E.x*fabs(dir.z) + E.z*fabs(dir.x);
   if ( fabs(T.z*dir.x - T.x*dir.z) > r )
      return false;

   // проверяем Z ^ dir
   r = E.x*fabs(dir.y) + E.y*fabs(dir.x);
   if ( fabs(T.x*dir.y - T.y*dir.x) > r )
      return false;

   return true;
}

Как обнаружить пересечение AABB-Triangle?

Пример класса AABB

class cdAABB
{
public:
  mVector Color;
  mVector P, E;       // положение в пространстве и размеры
  mVector vMin, vMax; // минимальная и максимальная точки

  void Create(const mVector &Pos, const mVector &Ext, 
              const mVector Col=mVector(1,1,1));

  void Move(const mVector &Step);
  void Draw() const;

  const BOOL OverlapsAABB(const cdAABB &aabb) const;
  const BOOL OverlapsOBB(const cdOBB &obb) const;
  const BOOL OverlapsSphere(const cdSphere &sphere) const;
  const BOOL OverlapsLineSegment( const mVector &mid, 
                                  const mVector &dir,
                                  const Scalar hl) const;
};