Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Статьи / Проверка столкновений камеры с полигоном.

Проверка столкновений камеры с полигоном.

Страницы: 1 2 Следующая

Эта статья основана на довольно качественном исходнике с сайта gametutorials.com. Актуальность темы очень высока – в любом приличном 3D приложении должна быть проверка столкновений. Здесь мы рассмотрим два неплохих и не очень сложных метода.

Автор: Сахарных Николай

Начнем с основного алгоритма проверки пересечения сферы и полигона (т.е. в качестве модели столкновения будет сфера, описанная вокруг камеры).

Основной алгоритм
  Нахождение точки на данном отрезке, ближайшей к данной точке
  Определение положения сферы относительно плоскости
  Проверка пересечения сферы с ребром полигона
  Проверка принадлежности точки полигону
  Нахождение смещения, для движения центра сферы от пересеченного полигона
  Проверка на пересечение прямой и плоскости
  Нахождение точки пересечения прямой и плоскости
  Проверка пересечения прямой и полигона

Основной алгоритм

Опишем алгоритм в общих чертах: мы просматриваем каждый треугольник в списке и проверяем, пересекается ли сфера камеры с ним. Если мы нашли одно пересечение, то мы не останавливаемся. Могут быть кратные столкновения, поэтому важно проверить их все. Когда мы находим пересечение, вычисляем смещение, которое двигает сферу от пересеченной плоскости.

Теперь подробнее … Просматриваем все треугольники.
Инициализируем текущий тестируемый треугольник:

CVector3 vTriangle[3] = { pVertices, pVertices[i+1], pVertices[i+2] };

Шаг 1 – Определяем тип сферы по положению в пространстве относительно полигона.

Находим нормаль к текущему проверяемому полигону и инициализируем расстояние от нашей сферы до плоскости полигона:

CVector3 vNormal = Normal(vTriangle);
float distance = 0.0f;

Здесь мы определяем, находится сфера спереди, сзади или пересекает плоскость:
int classification = ClassifySphere(m_vPosition, vNormal, vTriangle[0], m_radius, distance);

Если  сфера пересекает плоскость полигона, то проверяем дальше:

if (classification == INTERSECTS)

Шаг 2 – Находим псевдо точку пересечения на плоскости полигона.

Сейчас нам нужно спроецировать центр сферы на плоскость треугольника, получив тем самым “точку пересечения” нашей сферы с плоскостью.

CVector3 vOffset = vNormal * distance;

Находим вектор положения сферы от плоскости и вычитаем его из вектора центра сферы. Получаем точку vIntersection, которая принадлежит плоскости треугольника (в дальнейшем – точка пересечения):

CVector3 vIntersection = m_vPosition - vOffset;

Шаг 3 – Проверяем, находится ли точка пересечения внутри периметра треугольника.

Сначала проверяем, находится наша точка пересечения внутри треугольника, если нет, то алгоритм переходит к Шагу 4, где мы проверяем сферу на пересечение с ребрами полигона.

Изображение

Теперь выясним, на каком же расстоянии нам следует проверять столкновение с ребрами. Казалось бы, что на расстоянии радиуса сферы. Но если проверить … возникают некоторые проблемы, когда мы находимся рядом с углом. Мы можем двигаться вперед, но нас все время отбрасывает назад. Это происходит на стыке двух полигонов. Рисунок демонстрирует эту проблему. Причиной является то, что первый полигон отталкивает нас назад, (мы его не пересекли, но пересекли ребро) и мы возвращаемся обратно, хотя реально с таким направлением скорости мы можем идти вперед (задевая стену). Можно исправить это: достаточно проверять столкновение на расстоянии (радиус / 2). Но нужно помнить, что это используется только для проверки с ребрами полигона. В результате получается более реалистично, при столкновениях около угла. Конечно, если бы мы использовали в качестве модели столкновения Bounding Box, цилиндр или эллипс, это действительно не было бы проблемой.

if (InsidePolygon(vIntersection, vTriangle, 3) ||
   EdgeSphereCollision(m_vPosition, vTriangle, 3, m_radius / 2))

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

vOffset = GetCollisionOffset(vNormal, m_radius, distance);

Сейчас, зная смещение, добавляем его к вектору позиции и вектору вида камеры. Это оттолкнет нас назад от плоскости. Мы не видим это, потому что проверяем столкновение перед прорисовкой сцены.

m_vPosition = m_vPosition + vOffset;

m_vView = m_vView + vOffset;

Основной алгоритм разобран, приступим к рассмотрению методов реализации отдельных функций, которые мы используем (также они могут пригодиться и для других приложений).

Но сначала некоторая математика, которая нужна для понимания дальнейших функций. Очень часто будет использоваться скалярное произведение, поэтому стоит его как-то обозначить в тексте.

Пусть будет: v1.v2 – скалярное произведение v1 и v2. Как же собственно его посчитать? Очень просто, воспользуемся формулой: v1.v2 = v1.x * v2.x + v1.y * v2.y + v3.x * v3.y. Если вспомнить еще одну формулу скалярного произведения: v1.v2 = |v1| |v2| cos (v1^v2), можно найти угол между векторами (в нашей статье это функция AngleBetweenVectors).

Теперь насчет уравнения плоскости. Напомню, что его можно записать так (пусть, например, для точки Point на плоскости): A * Point.x + B * Point.y + C * Point.z + D = 0 или Normal.Point + D = 0 (его еще называют нормальным векторным уравнением), где D – расстояние от начала координат до плоскости, а Normal – нормаль к плоскости. Отсюда несложно находится расстояние от начала координат до плоскости: D = -Normal.Point (в нашей статье – функция PlaneDistance от нормали и точки плоскости). Также можно записать еще одну известную формулу для произвольной точки Point: A * Point.x + B * Point.y + C * Point.z + D = (расстояние от точки до плоскости). Не буду приводить код, разобранных здесь функций, т.к. он очевиден.

Нахождение точки на данном отрезке, ближайшей к данной точке

Сначала создаем вектор vVector1 от конечной точки отрезка vA до нашей данной точки vPoint. Дальше создаем вектор vVector2 – нормализованный вектор направления отрезка (от конечной точки vA до конечной точки vB). Затем используем формулу расстояния для нахождения длины данного отрезка. Теперь используем скалярное произведение, проектируя vVector1 на вектор vVector2. Это необходимо для получения расстояния до нашего спроецированного вектора от vA. Если длина спроецированного вектора отрезка от vA (пусть равная t) меньше или равна 0, то ближайшей будет точка vA. Мы должны вернуть значение функции, равное позиции этой конечной точки. Иначе, если длина спроецированного вектора больше или равна длине нашего отрезка, то ближайшей будет точка vB. Таким образом, вернем vB. В другом случае искомая точка будет лежать на данном отрезке, вычислим её так: создадим вектор, длиной t и направлением вектора vVector2 (по отрезку от vA до vB), и добавим его к позиции точки vA.

CVector3 ClosestPointOnLine(CVector3 vA, CVector3 vB, CVector3 vPoint)
{
  CVector3 vVector1 = vPoint - vA;
  CVector3 vVector2 = Normalize(vB - vA);
  float d = Distance(vA, vB);
  float t = Dot(vVector2, vVector1);

  if (t <= 0) return vA;
  if (t >= d) return vB;
   
  CVector3 vVector3 = vVector2 * t;
  CVector3 vClosestPoint = vA + vVector3;
  return vClosestPoint;
}

Определение положения сферы относительно плоскости

Сначала мы должны найти расстояние от начала координат до нашей плоскости (функция PlaneDistance). Дальше используем известную формулу расстояния для нахождения расстояния от центра сферы до плоскости полигона. Если абсолютное значение расстояния, которое мы нашли меньше радиуса, значит, сфера пересекает плоскость. Иначе, если расстояние больше или равно радиусу, сфера находится полностью спереди плоскости. И, наконец, если сфера не пересекает и не спереди плоскости, значит, она сзади.

int ClassifySphere(CVector3 &vCenter, CVector3 &vNormal, CVector3 &vPoint, 
                    float radius, float &distance)
{
  float d = (float)PlaneDistance(vNormal, vPoint);
  distance = (vNormal.x * vCenter.x + vNormal.y * vCenter.y + 
            vNormal.z * vCenter.z + d);
  if (fabs(distance) < radius) return INTERSECTS;
    else if (distance >= radius) return FRONT;
  return BEHIND;
}

Проверка пересечения сферы с ребром полигона

Входные параметры: центр сферы, вершины полигона, количество вершин и радиус сферы. Мы возвращаем true, если сфера пересекается с одним из ребер полигона.

Просматриваем все вершины полигона. Находим ближайшую точку к центру сферы на текущем ребре (функция ClosestPointOnLine). Теперь считаем расстояние между этой ближайшей точкой и центром. Если это расстояние меньше радиуса – значит, произошло столкновение – возвращаем true. Иначе, если все ребра просмотрены и ничего не найдено – возвращаем false.

bool EdgeSphereCollision(CVector3 &vCenter, CVector3 vPolygon[], 
                        int vertexCount, float radius)
{
  CVector3 vPoint;
  for(int i = 0; i < vertexCount; i++)
  {
    vPoint = ClosestPointOnLine(vPolygon[i], 
          vPolygon[(i + 1) % vertexCount], vCenter);
    float distance = Distance(vPoint, vCenter);
    if (distance < radius) return true;
  }
  return false;
}

Проверка принадлежности точки полигону

Алгоритм несложный. Просматриваем все вершины. Теперь получим вектор от точки пересечения до текущей вершины: вычитаем вектор точки пересечения из вектора текущей вершины. Аналогично получим вектор от точки пересечения до следующей вершины. Затем находим угол между этими векторами и добавляем его к текущему углу Angle. Нетрудно доказать, что после просмотра всех вершин значение Angle будет равно 2*pi (360 градусов) только в том случае, если точка находится внутри полигона. В силу неточностей вычислений с плавающей точкой может быть, например, что угол будет равен (2*pi – 0.00001), поэтому проверяем, если угол больше либо равен 2*pi*const (константа близкая к единице), возвращаем true, точка находится внутри полигона, иначе возвращаем false.

bool InsidePolygon(CVector3 vIntersection, CVector3 Poly[], long verticeCount)
{
  const double MATCH_FACTOR = 0.99;      
  double Angle = 0.0;  CVector3 vA, vB;              
  for (int i = 0; i < verticeCount; i++) {  
    vA = Poly[i] - vIntersection;  
    vB = Poly[(i + 1) % verticeCount] - vIntersection;
    Angle += AngleBetweenVectors(vA, vB);  
  }
  if (Angle >= (MATCH_FACTOR * (2.0 * PI)) ) return true;        
  return false;                
}

Нахождение смещения, для движения центра сферы от пересеченного полигона

Сейчас объясню математику, которая здесь нужна. Сначала, у нас есть нормаль к плоскости, радиус сферы, также расстояние от центра сферы до плоскости. В случае пересечения сферы спереди полигона, алгоритм работает так: мы должны вычесть расстояние до плоскости из радиуса, затем перемножить новое расстояние с нормалью к плоскости. Полученный вектор расстояния (т.е. часть, выходящая за полигон) будет совпадать по направлению с вектором нормали. Для примера, скажем, у нас есть следующие значения: vNormal = (1, 0, 0), radius = 5, distance = 3. Если мы вычтем расстояние из радиуса сферы, мы получим: (5 – 3 = 2). Число 2 говорит о том, что наша сфера заходит за плоскость на расстояние 2. По существу, мы должны отодвинуть сферу назад на 2 единицы. Как мы узнаем, в каком направлении? Эта часть простая, у нас есть вектор нормали, который показывает направление плоскости. Если мы перемножим нормаль на остаток расстояния, мы получим: (2, 0, 0). Это новый вектор смещения показывает направление и как далеко мы должны отодвинуть назад. Мы добавляем этот вектор к вектору позиции сферы, получая новую позицию, при которой сфера правильно лежит на плоскости. Если столкновение произошло сзади полигона – меняем знаки. Определить, где произошло столкновение, просто: если расстояние больше нуля, столкновение спереди полигона, иначе – сзади полигона. Код приведен ниже:

CVector3 GetCollisionOffset(CVector3 &vNormal, float radius, float distance)
{
  CVector3 vOffset = CVector3(0, 0, 0);
  if (distance > 0) {
    float distanceOver = radius - distance;
    vOffset = vNormal * distanceOver;
  } else {
    float distanceOver = radius + distance;
    vOffset = vNormal * (-distanceOver);
  }
  return vOffset;
}

Существует одна проблема с проверкой на столкновение сзади полигона: если камера будет двигаться очень быстро, и центр пройдет мимо передней части полигона, это примется как столкновение с задней частью и движения камеры назад от плоскости не будет. Эту проблему можно решить, убрав if/else проверку, но только в том случае, если вы не используете заднюю сторону полигона.

Страницы: 1 2 Следующая

27 сентября 2003

#collision detection


Обновление: 24 января 2011

2001—2017 © GameDev.ru — Разработка игр