Публикации Проекты Форум Работа
Войти
ПрограммированиеСтатьи

Определение столкновения с полигональной моделью.

Автор:

==
==

В любой математической модели, определяющей движение игрового объекта, вряд ли удастся избежать проверки столкновения с окружающим миром через методы, работающие с полигональной моделью (ПМ). Конечно, мир можно представить геометрическими примитивами (сферами, "боксами" и т.д.), что эффективно по скорости вычислений и объему расходуемой памяти, но не всегда дает достаточную точность. Да и автоматизировать процесс подбора геометрических примитивов для аппроксимации ПМ сложно. Возникнет необходимость ручной работы, которая будет возложена на художников, и, скорее всего, вы услышите от них много неприятных слов, а может даже какие-нибудь новые выражения. Существует много вариантов решения задачи проверки пересечения с ПМ.  Наиболее популярные и эффективные используют пространственные деревья (spatial trees), представляющие собой иерархии окружающих объемов или разделенное пространство.

Математические модели движения объектов чаще всего используют следующие базовые функции:
- проверка пересечения геометрических примитивов с ПМ
- проверка пересечения двух ПМ
- определение столкновения выпуклых объектов, двигающихся с постоянными скоростями, с ПМ
- определение столкновения двух ПМ, двигающихся с постоянными скоростями.

Описываемый здесь метод, использует разновидность пространственного дерева для представления ПМ, а именно axis-aligned bounding boxes tree (AABBs tree). Этот метод хорошо подходит для реализации изложенных выше функций.

Критериями выбора метода являются: скорость работы, точность, расход памяти, сложность реализации и трудоемкость подготовки данных. Для решения задач, возникающих при разработке игр, AABBs деревья подходят очень хорошо: они универсальны (с их помощью можно реализовать все функции необходимые для определения столкновений), эффективны по скорости и расходу памяти. А также имеют дополнительные плюсы: точность результата легко регулируема, реализация проста, а подготовка данных (построение дерева) полностью автоматизирована.

AABBs tree - бинарное дерево, образованное иерархией описывающих "боксов", лежащих вдоль осей координат. Каждый AABB охватывает всех своих детей. Т.е. каждый узел дерева представляет собой AABB и две ссылки на детей: "позитивного" и "негативного". Здесь термины "позитивный" и "негативный" не означают, что один лучше другого, просто так сложилось в результате следования правилам построения дерева. По каждой координате, "ребенок" имеет меньший или равный своему родителю размер и может пересекаться со своим " братом". Листьями дерева являются треугольники.

AABBs дерево строится из ПМ, представленной не пустым списком треугольников, следующим образом:
1) Если множество треугольников T состоит только из одного треугольника,  переходим к пункту 7
2) Создаем новый узел U
3) Для множества треугольников T вычисляем AABB, который запоминаем в узле U дерева
4) Выбираем границу деления - плоскость, проходящую через середину наибольшей стороны AABB параллельно двум наименьшим граням
5) Множество T разбиваем на два непустых подмножества Tpositive  и Tnegative по положению центров проекций треугольников на нормаль делящей плоскости.
6) Рекурсивно повторяем последовательность действий для подмножеств Tpositive и Tnegative, начиная с пункта 1
7) Треугольник назначаем листом дерева, прекращаем рекурсию

Параллельность AABB осям координат является как основным преимуществом этого метода, так и его основным недостатком. Можно очень хорошо сэкономить на расходе памяти, упростить и ускорить методы проверки пересечения узла дерева с некоторыми геометрическими примитивами. С другой стороны AABBs tree проигрывает Oriented bounding boxes (OBBs) tree по точности охвата набора треугольников. Как следствие, возрастает количество итераций необходимых для проверки пересечения с деревом. AABBs tree занимает мало памяти за счет того, что не надо хранить ориентацию "бокса".  Более того, нормировав все величины по размеру корневого "бокса", можно перейти от переменных с плавающей точкой к переменным с фиксированной точкой. В коммерческой реализации, я использую переменные с фиксированной точкой, и каждый 3D вектор занимает всего 48 бит. Это дает неплохую точность и выигрыш по памяти в два раза по сравнению с использованием типа float. Скорость работы повышается за счет того, что методы проверки пересечения геометрических примитивов с AABB проще методов для OBB. Также деревья можно "слегка подрезать",  прекращая рекурсию построения дерева при достижении определенного (достаточно малого) размера AABB. Для повышения скорости можно также кэшировать узлы, с которыми в прошлый раз произошло пересечение, что позволяет в некоторых ситуациях получить заметный выигрыш.

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

Ниже приведены алгоритмы проверки пересечения с AABBs деревом и несколько сокращенный (для экономии места) текст программы, реализующей описанные в данной статье алгоритмы и структуры данных.

Алгоритм проверки пересечения AABBs дерева с геометрическим примитивом. Для проверки пересечения AABBs дерева с выпуклым объектом, двигающимся с постоянной скоростью, последовательность действий аналогична.
1) Если находимся в листе, проверяем пересечение геометрического примитива с треугольником-листом и с результатом проверки переходим на пункт 4.
2) Проверяем пересечение геометрического примитива с AABB. Если пересечения нет, переходим с отрицательным результатом на пункт 4.
3) Рекурсивно повторяем последовательность с пункта 1 для "позитивного" и "негативного" ребенка
4) Прекращение рекурсии и возвращение результата

Алгоритм проверки пересечения двух AABBs деревьев. Если деревья двигаются с постоянной скоростью, алгоритм остается неизменным, меняются только функции проверки пересечения примитивов.
1) Если мы находимся в узлах обоих деревьев, проверяем пересечение двух OBB (т.к. деревья обычно имеют различные системы координат). Если "боксы" пересекаются, продолжаем рекурсию спуском по дереву, имеющему больший размер AABB - повторяем с пункта 1. Если нет, возвращаем отрицательный результат проверки.
2) Если мы находимся в листе одного из деревьев и узле другого, проверяем пересечение треугольника с OBB. В случае пересечения, продолжаем спуск по дереву, в узле которого находимся - повторяем с пункта 2. Если нет, возвращаем отрицательный результат проверки.
3) Если  мы находимся в листьях обоих деревьев, проверяем пересечение двух треугольников с учетом координатных систем, возвращаем результат проверки.

struct TRIANGLE  // тройка вершин
{ 
  POINT3D V[3]; // класс POINT3D смотри в "Определение столкновений выпуклых объектов
                // движущихся с постоянными скоростями".
  
  TRIANGLE& operator *= ( const MATRIX& m ) {  // MATRIX - матрица 4x4
    for( int i=0; i<3; ++i ) V[i]*=m; return *this; 
  }
};

struct AABB // "бокс", лежащий вдоль осей координат
{
  POINT3D Min, Max;

  AABB( const POINT3D& Min_=POINT3D(0,0,0), const POINT3D& Max_=POINT3D(0,0,0) ) : 
    Min(Min_), Max(Max_) {}

  POINT3D Size() const { return Max-Min; }

  void EnlargeMe( const TRIANGLE& Triangle )
  {
    for( int i=0; i<3; ++i )
    {
      Min.x=std::min(Min.x,Triangle.V[i].x); 
      Min.y=std::min(Min.y,Triangle.V[i].y); 
      Min.z=std::min(Min.z,Triangle.V[i].z);

      Max.x=std::max(Max.x,Triangle.V[i].x); 
      Max.y=std::max(Max.y,Triangle.V[i].y); 
      Max.z=std::max(Max.z,Triangle.V[i].z);
    }
  }
  
  bool operator > ( const AABB& b ) const; //Сравнивает размеры двух "боксов"
};


class AABB_TREE
{
public:
  AABB_TREE() : pRootNode(NULL) {}
  ~AABB_TREE() { RecursiveSuicide(pRootNode); }

  // Строит AABB tree по списку треугольников, представленных тройками вершин,
  // итераторы указывают на неконстантные объекты для упрощения, 
  // вершины будут перемещены
  void Build( TRIANGLE* const pBeginT, TRIANGLE* const pEndT );

  // Методы, проверяющие пересечение с примитивами.
  bool TestIntersection( const class RAY& Ray, class POINT3D& Position, 
                         class POINT3D& Normal ) const;

  template <class GEOM_PRIMITIVE>
  bool TestIntersection( const GEOM_PRIMITIVE& gp ) const { 
    return pRootNode ? RecursiveTestIntersection(pRootNode,gp) : false; 
  }

  // Метод, проверяющий пересечение с другим объектом класса AABB_TREE.
  // m - матрица перехода из системы координат ABBTree в систему координат *this.
  bool TestIntersection( const AABB_TREE& ABBTree, const MATRIX& m ) const;

private:
  struct NODE;

  NODE* pRootNode;

  AABB_TREE( const AABB_TREE& ); // запрещаем копирование
  AABB_TREE& operator=( const AABB_TREE& ); // запрещаем присваивание

  void RecursiveSuicide( NODE* const pNode );
  bool IsPositiveTriangle( const TRIANGLE* const pT, const AABB& B, 
                           const int IndexOfMaxBoxDimension ) const;
  void RecursiveBuild( NODE*& pNode, TRIANGLE* const pBeginT, TRIANGLE* const pEndT );
  template <class GEOM_PRIMITIVE>
  bool RecursiveTestIntersection( const NODE* const pNode, 
                                  const GEOM_PRIMITIVE& gp ) const;
  void MakeOBBFromAABBAndMatrix( class OBB& obb, const AABB& aabb, const MATRIX& m ) const;
  bool RecursiveTestIntersection( const NODE* const pMyNode, const NODE* const pOutsideNode,
                                  const MATRIX& m ) const;
};


// Класс NODE содержит и Box и Triangle. Это сделано исключительно для упрощения, 
// в коммерческой реализации надо оптимизировать расход памяти.
struct AABB_TREE::NODE
{
  AABB Box;
  TRIANGLE Triangle;
  NODE* pPositive, * pNegative;

  NODE() : pPositive(NULL), pNegative(NULL) {}

  bool IsLeaf() const { 
    assert( (!pPositive&&!pNegative)||(pPositive&&pNegative) ); 
    return !pPositive; 
  }
};

 // Рекурсивно "рубит" дерево
void AABB_TREE::RecursiveSuicide( NODE* const pNode )
{
  if( pNode )
  {
    RecursiveSuicide(pNode->pPositive);
    RecursiveSuicide(pNode->pNegative);
    delete pNode;
  }
};

void AABB_TREE::Build( TRIANGLE* const pBeginT, TRIANGLE* const pEndT )
{
  RecursiveSuicide(pRootNode);
  pRootNode=NULL;

  if( pBeginT!=pEndT )
    RecursiveBuild(pRootNode,pBeginT,pEndT);
}

// Относит треугольник к позитивному или негативному множеству
bool AABB_TREE::IsPositiveTriangle( const TRIANGLE* const pT, const AABB& B, 
                                    const int IndexOfMaxBoxDimension ) const
{
  const POINT3D* const V=pT->V;
  const float C_0=V[0][IndexOfMaxBoxDimension], C_1=V[1][IndexOfMaxBoxDimension], 
              C_2=V[2][IndexOfMaxBoxDimension],
              MinC=std::min(std::min(C_0,C_1),C_2), MaxC=std::max(std::max(C_0,C_1),C_2),
              MiddlePointOfBox=(B.Min[IndexOfMaxBoxDimension]+B.Max[IndexOfMaxBoxDimension])*0.5f,
              MiddlePointOfTriangleProj=(MinC+MaxC)*0.5f;
  return MiddlePointOfTriangleProj>MiddlePointOfBox;
}

// Рекурсивно строит дерево
void AABB_TREE::RecursiveBuild( NODE*& pNode, TRIANGLE* const pBeginT, TRIANGLE* const pEndT )
{
  assert( pBeginT<pEndT );
  assert( pNode==NULL );

  pNode=new NODE;

  if( pEndT-pBeginT==1 )
  { //Это лист
    pNode->Triangle=*pBeginT;
  }
  else
  {
    // Вычисляем "бокс"
    AABB Box(POINT3D(FLT_MAX,FLT_MAX,FLT_MAX),POINT3D(-FLT_MAX,-FLT_MAX,-FLT_MAX));
    for( const TRIANGLE* pT=pBeginT; pT!=pEndT; ++pT ) Box.EnlargeMe(*pT);

    // Ищем максимальный размер
    int IndexOfMaxBoxDimension=0; const POINT3D Size(Box.Size()); float MaxBoxDimension=Size[0];
    for( int i=1; i<3; ++i ) if( Size[i]>MaxBoxDimension ) { 
      MaxBoxDimension=Size[i]; IndexOfMaxBoxDimension=i; 
    }

    // Делим треугольники на два подмножества
    TRIANGLE* pEndNegative=pBeginT, * pBeginPositive=pEndT;
    for( ; pEndNegative!=pBeginPositive; )
      if( IsPositiveTriangle(pEndNegative,Box,IndexOfMaxBoxDimension) )   
        std::swap(*pEndNegative,*(--pBeginPositive));
      else
        pEndNegative++;

    // Подмножество может оказаться пустым. 
    // Для борьбы с эти ассертом надо выбрать наибольший треугольник 
    // и отправить его в пустое подмножество.
    assert( pBeginT<pEndNegative && pEndNegative==pBeginPositive && pBeginPositive<pEndT );

    pNode->Box=Box;

    // Продолжаем рекурсию
    RecursiveBuild(pNode->pNegative,pBeginT,pEndNegative);
    RecursiveBuild(pNode->pPositive,pBeginPositive,pEndT);
  }
}

// Шаблонная функция-член класса, проверяет рекурсивно пересечение примитива с AABB tree
template <class GEOM_PRIMITIVE>
bool AABB_TREE::RecursiveTestIntersection( const NODE* const pNode, 
                                           const GEOM_PRIMITIVE& gp ) const
{
  assert( pNode );

  if( pNode->IsLeaf() )
    return ::TestIntersection(pNode->Triangle,gp); 
  else if( ::TestIntersection(pNode->Box,gp) )
    return RecursiveTestIntersection(pNode->pPositive,gp) || 
           RecursiveTestIntersection(pNode->pNegative,gp);

  return false;
}

bool AABB_TREE::TestIntersection( const AABB_TREE& ABBTree, const MATRIX& m ) const
{
  if( pRootNode && ABBTree.pRootNode )
    return RecursiveTestIntersection(pRootNode,ABBTree.pRootNode,m);
   
  return false;
}

// Делает из AABB и матрицы OBB
void AABB_TREE::MakeOBBFromAABBAndMatrix( class OBB& obb, const AABB& aabb, 
                                          const MATRIX& m ) const
{
  // Не привожу реализацию для экономии места
}

// Рекурсивно проверяет пересечение двух деревьев.
// m - матрица перехода из системы координат pOutsideNode в систему координат pMyNode.
bool AABB_TREE::RecursiveTestIntersection( const NODE* const pMyNode, 
                                           const NODE* const pOutsideNode, const MATRIX& m )const
{
  if( pMyNode->IsLeaf() )
  {
    // pMyNode-лист, pOutsideNode-узел или лист
    TRIANGLE Triangle(pMyNode->Triangle); Triangle*=m.GetInverse();
    return RecursiveTestIntersection(pOutsideNode,Triangle);
  }
  else
  {
    if( pOutsideNode->IsLeaf() )
    {// pMyNode-узел, pOutsideNode-лист
      TRIANGLE Triangle(pOutsideNode->Triangle); Triangle*=m;
      return RecursiveTestIntersection(pMyNode,Triangle);
    }
    else
    {// оба узлa
      if( pMyNode->Box>pOutsideNode->Box ) // не совсем корректное (без учета матрицы m) 
                                           // сравнение размеров "боксов"
      {
        return RecursiveTestIntersection(pMyNode->pPositive,pOutsideNode,m)
            || RecursiveTestIntersection(pMyNode->pNegative,pOutsideNode,m);
      }
      else
      {
        return RecursiveTestIntersection(pMyNode,pOutsideNode->pPositive,m)
            || RecursiveTestIntersection(pMyNode,pOutsideNode->pNegative,m);
      }
    }
  }
}

Список литературы:
http://www.win.tue.nl/~gino/solid/jgt98deform.pdf
http://www.ce.chalmers.se/staff/tomasm/pubs/cd_deform_eg.pdf
http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf
http://www.eg.org/EG/CGF/Volume18/Issue3/352.pdf
http://3map.snu.ac.kr/mskim/ftp/k-dops.pdf

24 июня 2002

Контакт Сообщества Участники Каталог сайтов Категории Архив новостей
GameDev.ru — Разработка игр
©2001—2023