Войти
ПрограммированиеСтатьиГрафика

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

Теперь рассмотрим довольно полезный метод проверки пересечения прямой и полигона, который можно использовать в качестве проверки на столкновение камеры с полигоном. Его мы опишем в качестве нескольких функций для лучшего понимания.

Проверка на пересечение прямой и плоскости

Для начала, нам нужно получить вектор нормали к нашей плоскости. Дальше найдем расстояние от начала координат до нашей плоскости, через вектор нормали к плоскости и любой точкой на этой плоскости (функция PlaneDistance). Теперь получаем расстояние от одной из конечных точек данного отрезка до плоскости, используя уже известную формулу: Ax + By + Cz + D = (расстояние до плоскости), где D – расстояние от начала координат до нашей плоскости. Аналогично получаем расстояние от второй точки нашего отрезка. Сейчас у нас есть два расстояния от нашей плоскости до концов отрезка. Если при перемножении получится отрицательное число, значит, мы пересеклись, возвращаем true. Это правильно, потому что обе точки должны лежать по обеим сторонам плоскости (например, -1 * 1 = -1). Возвращаем false в случае, если расстояния до обеих точек имеют один знак – точки лежат по одну сторону (например, при расстояниях (-1;-2) или (3;4) точки лежат по одну сторону, а при (-1;1) – по разные).

bool IntersectedPlane(CVector3 vPoly[], CVector3 vLine[], 
                          CVector3 &vNormal, float &originDistance)
{
  float distance1=0, distance2=0;                  vNormal = Normal(vPoly);
  originDistance = PlaneDistance(vNormal, vPoly[0]);

  distance1 = ((vNormal.x * vLine[0].x) + (vNormal.y * vLine[0].y) +
                   (vNormal.z * vLine[0].z)) + originDistance;
  distance2 = ((vNormal.x * vLine[1].x) + (vNormal.y * vLine[1].y) +
                   (vNormal.z * vLine[1].z)) + originDistance;

  if (distance1 * distance2 >= 0) return false;
  return true;
}

Нахождение точки пересечения прямой и плоскости

1)  Для начала нужно получить вектор нашей прямой, затем нормализовать его (т.е. изменить длину на 1). Дальше выберем произвольную точку на нашей прямой.

2)  Используем уравнение плоскости (расстояние = Ax + By + Cz + D), для нахождения расстояния от одной из точек на прямой до плоскости (для этого используем скалярное произведение нормали к плоскости и нашей произвольной точки прямой + расстояние от начала координат до плоскости – его мы получаем в качестве параметра функции).

3)  Получаем скалярное произведение между вектором прямой и вектором нормали к плоскости (это будет cos угла между ними, т.к. оба длины 1). Поскольку мы используем деление, мы должны убедиться, что не получим ошибку деления на ноль. Если мы получим 0, это означает, что существует бесконечно много искомых точек, потому что прямая будет лежать на плоскости (вектор нормали перпендикулярен прямой (vNormal.vLineDir = 0)). В этом случае, нам нужно вернуть любую точку на прямой.

4)  Теперь делим расстояние, найденное в п.2 на скалярное произведение (cos угла), для получения расстояния от нашей произвольной точки до точки пересечения (или гипотенузы треугольника – см. рисунок). На самом деле, если внимательно читать, можно заметить, что делим мы на cos внешнего угла треугольника (а нужно на cos внутреннего), поэтому чтобы получить правильный ответ, нужно умножить, например, числитель на (-1) (т.к. cos a = -cos (pi-a)). Сейчас находим искомую точку: перемножаем найденное расстояние на вектор прямой и добавляем к позиции выбранной произвольной точки.

Изображение

CVector3 IntersectionPoint(CVector3 vNormal, CVector3 vLine[], double distance)
{
  CVector3 vPoint, vLineDir;
  double Numerator = 0.0, Denominator = 0.0, dist = 0.0;

  vLineDir = vLine[1] - vLine[0];
  vLineDir = Normalize(vLineDir);

  Numerator = - (vNormal.x * vLine[0].x + vNormal.y * vLine[0].y +
           vNormal.z * vLine[0].z + distance);
  Denominator = Dot(vNormal, vLineDir);

  if( Denominator == 0.0) return vLine[0];
  dist = Numerator / Denominator;

  vPoint.x = (float)(vLine[0].x + (vLineDir.x * dist));
  vPoint.y = (float)(vLine[0].y + (vLineDir.y * dist));
  vPoint.z = (float)(vLine[0].z + (vLineDir.z * dist));

  return vPoint;
}

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

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

bool IntersectedPolygon(CVector3 vPoly[], CVector3 vLine[], int verticeCount)
{
  CVector3 vNormal;
  float originDistance = 0;

  if (!IntersectedPlane(vPoly, vLine,   vNormal,   originDistance))
    return false;
  CVector3 vIntersection = IntersectionPoint(vNormal, vLine, originDistance);
  if(InsidePolygon(vIntersection, vPoly, verticeCount)) return true;

  return false;
}

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

В этой статье мы познакомились с основными методами проверки столкновений с полигоном и их подробной реализацией. Метод, использующий сферу, очень популярен и может пригодиться во многих проектах, где нужна быстрая проверка и где принимается модель камеры – сфера. Стоит отметить, что это один из несложно реализуемых среди остальных методов проверки столкновений. Проверка пересечения отрезка с полигоном может использоваться не только как столкновение камеры, но и, например, в выборе 3D объектов, поэтому этот метод очень полезен в любых приложениях.

Страницы: 1 2

#collision detection

27 сентября 2003 (Обновление: 24 янв 2011)

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