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

Двумерный движок физики многоугольников и окружностей на основе метода импульсов.

Автор:

Здесь не будет полного описания движка, а скорее некий набор советов и т.д., полученных в процессе его написания.

Введение
Часть 1. Основы.
Часть 2. Разбиение пространства, пересечение фигур
Часть 3. Движение тела.
Часть 4. Силы, действующие на тело.
Часть 5. Удары и импульсы
Часть 6. Как это все работает.

Введение

В качестве языка программирования используется C++. Для тех, кто забыл или не знает небольшой справочник:

sqrt() — извлечение квадратного корня;
A /= B  — это A = A / B, A += B означает A = A + B и т.д;
fabs() — получить абсолютную величину (то есть для отрицательных чисел вычесть из нуля это число);
PI — число Пи;
double — это основной тип для вещественных чисел;
void f (double& a) — функция f(), не возвращает ничего (void), в нее передается ссылка на a типа double.

Часть 1. Основы.

Начнем с азов геометрии (далее все про двумерный случай). Двумерный вектор V — это два вещественных числа: Vx и Vy.
Записывать будем как (Vx, Vy). Вектор V из точки A в B это (Bx–Ax, By–Ay), то есть Vx = Bx – Ax, Vy = By – Ay.

Длина вектора V = sqrt(Vx*Vx + Vy * Vy). Это является расстоянием между началом и концом вектора.

Чтобы получить единичный вектор из вектора V, делаем так:

double l = sqrt(Vx * Vx + Vy * Vy)
if (fabs(l) < _E)
{
  Vx /= l;
  Vy /= l;
}

_E — это точность вычислений (скажем 1e–12).

Чтобы вектор V направить в обратную сторону:

  Vx = – Vx; Vy = – Vy;

Наша система декартовых координат такова: положительный конец оси X направлен вправо, а оси Y – вниз (а не вверх, как обычно!). Нетрудно думаю понять, что вращение «по часовой стрелке»  (то есть от оси X к оси Y кратчайшим образом) в системе с осью Y вверх выглядит в нашей системе как вращение «против часовой стрелки». Советую понять этот момент, чтобы потом не путаться.

В нашей системе (далее везде — только о такой системе), поворот вектора против часовой стрелке на 90 градусов есть вектор (–Vy, Vx). (по часовой: (Vy, –Vx) ). Вводим следующие ограничения — все многоугольники у нас будут выпуклые (грубо говоря, в них нет «впадинок», точно говоря, «все точки отрезка соединяющего любые две точки многоугольника принадлежат многоугольнику») и при этом вершины многоугольников заданы в порядке обхода многоугольника по часовой стрелке. Чтобы получить правильно направленную нормаль стороны многоугольника (то есть направленную изнутри многоугольника наружу) следует для стороны вычесть из следующей вершины предыдущую (напоминаю — вершины заданы для обхода многоугольника по часовой). Полученный таким образом вектор стороны поворачиваем против часовой стрелки, нормализуем его, то есть, делаем из него единичный. Это и есть нормаль стороны.

Введем теперь функцию (DOT2D – это класс двумерной точки, который помимо x и y включает указатель next на такую же точку, чтобы делать списки):

double orient(DOT2D* a, DOT2D* b, DOT2D* c)
{
  return (a->x - c->x)*(b->y - c->y) - (a->y - c->y) * (b->x - c->x);
}

Эта функция возвращает знак полуплоскости точки «c» относительно прямой (a, b). Если точка «c» лежит на прямой, то orient() возвращает 0.

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

Вернемся к поворотам. Что есть поворот на угол? Представим себе единичную окружность с центром в начале координат. Точку окружности, пересекаемую положительным концом оси X примем за нулевой угол. Точка, пересекаемая положительным концом оси Y — это угол PI / 2. То есть поворот на положительные углы в нашей системе координат идут по часовой стрелке (в «обычной» декартовой — против). Следующая функция — это поворот точки вокруг начала координат на заданный угол по часовой стрелке (в радианах):

void rotate(double& x, double& y, double sinA, double cosA)
{
  double xx = x * cosA - y * sinA;
  y = y * cosA + x * sinA;
  x = xx;
}

void rotate(double& x, double& y, double angle)
{
  rotate(x, y, sin(angle), cos(angle));
}

Вопрос на сообразительность: как повернуть не вокруг начала координат, а вокруг произвольной точки?

Ответ для несообразительных: переносим систему координат так, чтобы начало координат совпало с произвольной точкой. Поворачиваем. Переносим обратно.

Перенос системы координат в некоторую точку (x1, y1) означает, что каждая точка (x, y) переходит в (x–x1, y–y1) (нетрудно понять, что при этом точка (x1, y1) переходит в (0, 0)).

Еще немного разомнемся с векторами. Предположим, нам нужен единичный вектор, повернутый на некоторый угол. Как его получить? Возьмем единичный вектор, соответствующий нулевому углу. Это какой вектор? Правильно (1, 0) и сделаем rotate(). Что получим? Получим полезную функцию, возвращающую то, что нам нужно:

DOT2D AngleVector(double angle)
{
  return DOT2D(cos(angle), sin(angle));
}

Обратная функция (для единичного вектора!, PIPI = PI + PI):

double AngleOfVector(DOT2D V)
{
  double a = acos(V.x);
  if (V.y < 0) a = PIPI - a;
  return a;
}

Ну, и до кучи без комментариев набор полезных функций:

Площадь многоугольника (POLY2D: n — количество вершин, first — указатель на первую вершину в списке):

double POLY2D::Square()
{
  double S = 0.0;
  if (n < 3) return 0.0;
  DOT2D *v = first;
  for (int i=0;i<n;i++)
  {
    DOT2D *nv = v->next;
    if (nv == 0) nv = first;
    S = S + v->x * nv->y - nv->x * v->y;
    v = nv;
  }
  return fabs(S) * 0.5;
}

Расстояние от точки «c» до прямой (a, b) (всегда положительное, если убрать fabs(), то знак будет задавать полуплоскость):

double distance(DOT2D* a, DOT2D* b, DOT2D* c)
{
  double dx = a->x - b->x;
  double dy = a->y - b->y;
  double D = dx * (c->y - a->y) - dy * (c->x - a->x);
  return fabs(D / sqrt(dx * dx + dy * dy));
}

Пересекает ли окружность радиуса R с центром в (x, y) отрезок (A,B), длина которого есть L:

bool CircleIntersects(double x, double y, double R, double L, DOT2D* A, DOT2D* B, DOT2D* Z)
{
// единичный вектор отрезка AB
  double Xv = (B->x - A->x) / L;
  double Yv = (B->y - A->y) / L;
  double Xd = (A->x - x);
  double Yd = (A->y - y);
  double b = 2 * (Xd * Xv + Yd * Yv);
  double c = Xd * Xd + Yd * Yd - R * R;
  double c4 = c + c; c4 += c4;
  double D = b * b - c4;
  if (D < 0) return false; // нет корней, нет пересечений

  D = sqrt(D);
  double l1 = ( - b + D) * 0.5;
  double l2 = ( - b - D) * 0.5;
  bool intersects1 = ((l1 >= 0.0) && (l1 <= L));
  bool intersects2 = ((l2 >= 0.0) && (l2 <= L));
  bool intersects = intersects1 || intersects2;
  if (intersects && Z)
  {
    if (intersects1 && intersects2) 
    {
      l1 = (l1 + l2) * 0.5;
      Z->x = A->x + Xv * l1;
      Z->y = A->y + Yv * l1;
    }
    else if (intersects1)
    {
      Z->x = A->x + Xv * l1;
      Z->y = A->y + Yv * l1;
    }
    else 
    {
      Z->x = A->x + Xv * l2;
      Z->y = A->y + Yv * l2;
    }
  }
  return intersects;
}

Пересечение прямых:

double D2(double a11, double a12, double a21, double a22)
{
  return a11 * a22 - a12 * a21;
}

bool IntersectLines(DOT2D* a1, DOT2D* a2, DOT2D* b1, DOT2D* b2,DOT2D* c)
{
  double ady = a1->y - a2->y;
  double adx = a2->x - a1->x;
  double bdy = b1->y - b2->y;
  double bdx = b2->x - b1->x;
// определитель системы
  double D = D2(ady, adx, bdy, bdx);
  if (fabs(D) < _E) return true; // нет решения
  double aC = adx * a1->y + ady * a1->x;
  double bC = bdx * b1->y + bdy * b1->x;
  double DX = D2(aC, adx, bC, bdx);
  double DY = D2(ady, aC, bdy, bC);
  c->x = DX / D;
  c->y = DY / D;
  return false;
}

Проверка — ориентирован ли наш многоугольник как нужно (то есть, обходятся ли его вершины по часовой стрелке)?:

bool POLY2D::OrientedClockWise()
{
  if (n < 3) return false;
  DOT2D* a = first;
  DOT2D* b = first->next;
  return orient(a, b, b->next) > 0.0;
}

Повернуть односвязный список (привожу до кучи, задача из области программирования):

void POLY2D::revert_points()
{
  if (n == 0) return;
  DOT2D* dot = first;
  DOT2D* last = 0;
  while (dot)
  {
// запоминаем следующую точку
    DOT2D* next_dot = dot->next;
// ставим точку перед предыдущей
    dot->next = last;
    last = dot;
    dot = next_dot;
  }
  dot = first;
  first = last;
  last = first;
}

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

23 апреля 2005

#2D, #импульсы


Обновление: 9 января 2012

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