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

Определение столкновений выпуклых объектов движущихся с постоянными скоростями.

Автор:

Впервые с необходимостью определения столкновений объектов движущихся на высоких скоростях я столкнулся во время разработки игры PulseRacer, вышедшей на Xbox. Это гоночная игрушка с машинками, размер которых не превышает полутора метров, а скорость огромна — свыше 300 км/ч.

Временной шаг dt был выбран равным 1/50 секунды, такая величина dt дает в целом достаточную точность и не требует серьезных вычислительных затрат. Не трудно подсчитать, что за шаг интегрирования машина перемещалась примерно на 2 метра. Первое решение было таким: аппроксимируем каждую машину боксом, потом делаем проверку пересечения стационарных «боксов».  В случае пересечения, путем рекурсивного деления вектора перемещения на 2 получаем точку и время первого пересечения. Такой алгоритм работал некорректно, машины иногда проваливались друг в друга или неестественно отскакивали.  Это происходило из-за того, что перемещение значительно превышало длину автомобиля. Во втором варианте решения действовали иначе: аппроксимировали перемещения машин за один шаг «боксами» и попарно проверяли на пересечение. Результат был также плачевен — автомобили вели себя, прямо скажу, странно. Эти методы эффективны только тогда, когда перемещение объекта за время dt меньше половины «длины объекта». И тогда последнее, что нам оставалось попробовать это проверка столкновения двух боксов движущихся с постоянными скоростями и не имеющих скорости вращения. Результат был великолепен, функция проверки коллизии работала быстро, а модуль физики четко обрабатывал столкновения. Поступательная скорость машины велика настолько, что скоростью вращения можно пренебречь.

Рассмотрим перемещение двух «боксов» DP0 и DP1  за время dt, скорости будут равны V0= DP0/dt и V1 = DP1/dt.

Надо реализовать функцию, принимающую координаты двух «боксов» и их скорости, возвращающую факт наличия пересечения и время первого касания.

bool TestIntersection( const class OBB& Box0, const class POINT3D& V0,
              const class OBB& Box1, const class POINT3D& V1,
              float& IntersectionTime );

class OBB // Oriented bounding box
{
public:
   class POINT3D Origin,  // Центр
                           Extents, // Размер
       Orientation[3]; // Ориентация
//:
};

Для реализации TestIntersection подойдет Метод разделяющих осей (The Method of Separating Axes). Этот метод применяется для проверки пересечения двух выпуклых объектов. Выбирается несколько осей, на которые проецируются фигуры, если хотя бы на одной из осей проекции не пересекаются, значит, и объекты не пересекаются.

Изображение

Для выбора осей в 3D пространстве применяется следующее правило: к разделяющим осям относятся нормали граней и векторные произведения ребер фигур. Например, для пары боксов разделяющих осей образованных за счет нормалей граней будет 6, а за счет векторных произведений ребер 9. Для проверки пересечения "бокса" и треугольника надо использовать три неколлинеарных нормали граней "бокса", нормаль к треугольнику и девять векторных произведений, образованных тремя ребрами треугольника и тремя неколлинеарными ребрами "бокса".

Метод разделяющих осей можно надстроить так, чтобы использовать его и для динамических объектов, двигающихся с постоянной скоростью. При этом легко можно вычислить время первого касания объектов Tfirst,  если объекты изначально пересекаются Tfirst=0. Относительная скорость  V=V1-V0. Проецируем V на разделяющие оси. Если проекции фигур двигаются в противоположных направлениях, значит, столкновения не может произойти. Столкновение произойдет только в том случае, если все проекции двигаются на встречу друг другу. Фигуры пересекаются только тогда, когда пересекаются все их проекции, отсюда Tfirst = max ( TfirstI ), i=0..n-1, n-количество разделяющих осей, TFirsti - время первого касания для каждой проекции. Время разъединения фигур Tlast = min (TlastI),  i=0..n-1, TlastI - время разъединения для каждой проекции. Если Tfirst<= Tlast, столкновение произойдет, и время первого касания будет равным Tfirst. Приведу реализацию обобщенного метода проверки пересечения двух выпуклых объектов, двигающихся с постоянными скоростями. Для частных случаев (проверка пересечения двух "боксов", проверка пересечения "бокса" и треугольника) функция требует оптимизации.

#include <vector>
#include <assert.h>

class POINT3D
{
public:
  float x, y, z;

  POINT3D(const float x_=0, const float y_=0, const float z_=0): x(x_), y(y_), z(z_) {}

  float operator [ ] ( const unsigned int i ) const { 
      assert( i<3 );  
      return reinterpret_cast<const float*>(this)[i]; 
  };
  float Dot( const POINT3D& p ) const { return x*p.x+y*p.y+z*p.z; }
  POINT3D Cross( const POINT3D& p ) const  { 
      return POINT3D( y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x ); 
  }
  POINT3D operator - (const POINT3D& p) const {return POINT3D( x-p.x, y-p.y, y-p.y);}
};

class CONVEX
{
public:
  typedef std::vector<POINT3D> CONTAINER;

  CONTAINER FaceNormals, EdgeDirections, Vertices;
  POINT3D Velocity;
};


// проверяет пересечение по одной оси, эта функция может применяться и для 
// частных случаев, например, в функции проверяющей пересечение двух "боксов"
bool OneAxisTest( 
  const POINT3D& Axis, // ось
  const POINT3D& V,    //относительная скорость
  const float min0, const float max0, // проекция первой фигуры
  const float min1, const float max1, // проекция второй фигуры
  float& TimeFirst, // время столкновения
  float& TimeLast // время разъединения
  )
{
  assert( min0<=max0 && min1<=max1 );
  assert( TimeFirst<=TimeLast );

  const float speed=Axis.Dot(V);

  if( max1<min0 ) // проекция 1 слева от проекции 0
  {
    if( speed<=0 ) return false; // проекции "разбегаются"
    const float oospeed=1.0f/speed;
    float T=(min0-max1)*oospeed; if ( T>TimeFirst ) TimeFirst=T;
           T=(max0-min1)*oospeed; if ( T<TimeLast ) TimeLast=T;
    if( TimeFirst>TimeLast ) return false; // "быстрый выход"
  }
  else if( max0<min1 ) // проекция 1 справа от проекции 0
  {
    if( speed>=0 ) return false; // проекции "разбегаются"
    const float oospeed=1.0f/speed;
    float T=(max0-min1)*oospeed; if( T>TimeFirst ) TimeFirst=T;
           T=(min0-max1)*oospeed; if( T<TimeLast ) TimeLast=T;
    if( TimeFirst>TimeLast ) return false; // "быстрый выход"
  }
  else // проекции пересекаются
  {
    if( speed>0 )
    {
      const float T=(max0-min1)/speed; if( T<TimeLast ) TimeLast=T;
      if( TimeFirst>TimeLast ) return false; // "быстрый выход"
    }
    else if( speed<0 )
    {
      const float T=(min0-max1)/speed; if( T<TimeLast ) TimeLast=T;
      if( TimeFirst>TimeLast ) return false; // "быстрый выход"
    }
  }
  
  return true;
}

namespace // пустое namespace для ограничения видимости из других файлов
{
  // проецирует выпуклый объект на одну ось
  void ProjectConvex( const CONVEX& Convex, const POINT3D& Axis,
                      float& pmin, float& pmax )
  {
    assert( Convex.Vertices.size()>0 );

    pmin= pmax= Convex.Vertices.begin()->Dot(Axis);

    for( CONVEX::CONTAINER::const_iterator i=Convex.Vertices.begin()+1;
         i!=Convex.Vertices.end(); ++i )
    {
      const float proj= i->Dot(Axis);
      pmin= std::min(pmin,proj);
      pmax= std::max(pmax,proj);
    }
  }

// вспомогательный метод для проверки пересечения по одной оси
  bool OneAxisTest( const CONVEX& Convex0, const CONVEX& Convex1, 
                               const POINT3D& Axis, // ось
                               const POINT3D& V, // относительна скорость
                               float& TimeFirst, float& TimeLast )
  {
    float min0=0, max0=0, min1=0, max1=0;
    ProjectConvex(Convex0,Axis,min0,max0);
    ProjectConvex(Convex1,Axis,min1,max1);
    return ::OneAxisTest(Axis,V,min0,max0,min1,max1,TimeFirst,TimeLast);
  }
}

// Проверяет пересечение двух выпуклых объектов
bool TestIntersection( const CONVEX& Convex0,
                       const CONVEX& Convex1, // Выпуклые объекты
                       float& IntersectionTime  // принимает время до которого 
                       // выполняется проверка, возвращает время первого касания
                               )
{
  const POINT3D V=Convex1.Velocity-Convex0.Velocity;  // относительная скорость
  float TimeFirst=0, TimeLast=IntersectionTime;

  typedef CONVEX::CONTAINER::const_iterator ITERATOR;

  for( ITERATOR i0=Convex0.FaceNormals.begin(); i0!=Convex0.FaceNormals.end(); ++i0 )
    if(  !OneAxisTest(Convex0,Convex1,*i0,V,TimeFirst,TimeLast) )
      return false;

  for( ITERATOR i1=Convex1.FaceNormals.begin(); i1!=Convex1.FaceNormals.end(); ++i1 )
    if( !OneAxisTest(Convex0,Convex1,*i1,V,TimeFirst,TimeLast) )
      return false;

  for( ITERATOR i0=Convex0.EdgeDirections.begin(); i0!=Convex0.EdgeDirections.end(); ++i0 )
    for( ITERATOR i1=Convex1.EdgeDirections.begin(); i1!=Convex1.EdgeDirections.end(); ++i1 )
      if( !OneAxisTest(Convex0,Convex1,i0->Cross(*i1),V,TimeFirst,TimeLast) )
        return false;

  assert( 0<=TimeFirst && TimeFirst<=TimeLast );
  IntersectionTime=TimeFirst;
  return true;
}

Для точного расчета поведения машин после столкновения понадобится определить область касания. Она может представлять собой отрезок, точку или полигон. Вычисления можно провести аналитически или численно, путем «дробления фигур на куски». В первом случае легко допустить ошибку при реализации (аналитические выкладки весьма сложны), во втором — время работы функции может оказаться слишком большим. Есть и третий вариант — приблизительно получить область касания исходя из положения объектов и их скоростей, во многих математических моделях этого достаточно.

Полезная ссылка:
http://www.magic-software.com/Documentation/MethodOfSeparatingAxes.pdf

#collision detection

22 июня 2002 (Обновление: 24 сен 2009)

Комментарии [7]

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