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

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

Автор:

Часть 2. Разбиение пространства, пересечение фигур

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

Для особо непонятливых: необходимо хранить исходную позицию фигур (для положения (0,0), angle = 0) и текущую. С текущей работать, а когда потребуется передвинуть фигуры вслед за телом — использовать исходную для обновления текущей позиции. То есть текущая позиция нам никак не помогает в получении очередной текущей позиции. Ясное дело, что основной труд — это перемещение вершин многоугольника, потому как у окружности требуется перемещать всего одну точку — ее центр.

Для того чтобы быстрее определять пересечения между телами, разобьем плоскость на квадраты, то есть на хеш-ячейки. Поскольку плоскость бесконечна (ну обычно ;), то разобьем на квадраты не всю плоскость, а некоторый прямоугольник нашего игрового поля, а все остальное отнесем к отдельной особой хеш-ячейке. Размер ячейки разбиения — квадрата — не должен быть меньше двойного максимального радиуса тела. Теперь рассуждаем, каждое тело в своей текущей позиции принадлежит какому-то одному квадрату. При этом, размер квадрата подобран так, чтобы тело может максимально пересекать собой окружающие этот квадрат cоседей-квадратов (их будет 8). То есть все остальные квадраты нас не интересуют (точнее тела, лежащие в этих квадратах). Таким вот образом, двумерное хеширование позволяет быстро отсечь ненужные фигуры из алгоритма пересечения. Дальше — дело техники: надо искать пересечения с телами в текущем квадрате + в его соседях + в особом списке (помните про особый? — все, что вне игрового поля, сюда же можно заносить большие фигуры, которые не помещаются в одной ячейке). Ну, и не забывать при перемещении тела по полю, перекладывать его в список хеш-квадрата, соответствующего новой позиции тел.

Пересечение тел — это попытка найти пересечения между всеми фигурами тел. Возможны три алгоритмически разных случая: окружность-окружность, окружность-многоугольник, многоугольник- многоугольник. Однако, прежде чем использовать сложные алгоритмы пересечений, имеет смысл ввести оптимизационные проверки.

1.  пересечение описывающих квадратов (one, two — пересекаемые фигуры, (xc, yc) — центры описанной окружности радиуса R этих фигур):

  if (one->xc - one->R > two->xc + two->R) return false;
  if (two->xc - two->R > one->xc + one->R) return false;
  if (one->yc - one->R > two->yc + two->R) return false;
  if (two->yc - two->R > one->yc + one->R) return false;

2.  пересечение описывающих окружностей:

  double dx = one->xc - two->xc;
  double dy = one->yc - two->yc;
  double d = one->R + two->R;

  if (dx * dx + dy * dy > d * d) return false;

Вот теперь уже надо применять сложные методы для выявления случая пересечения окружность-многоугольниник и многоугольниник-многоугольниник.

Для двух многоугольников надо построить многоугольник, являющийся их пересечением. То есть «рассечь» сторонами одного многоугольника другой. Если есть непустой многоугольник пересечения, то исходные многоугольники пересекаются.

Случай окружность-многоугольник решается обходом сторон и вершин многоугольника с проверкой на пересечение с окружностью. Все нужные функции я уже привел.

Часть 3. Движение тела.

Для того, чтобы охарактеризовать движущееся тело нам необходимо для тела задать:

V = (Vx, Vy) — вектор скорости (линейной, то есть скорости движения тела по полю)
W — угловая скорость (то есть скорость вращения тела вокруг центра).

Несколько физических постулатов. Тело массой M движется как материальная точка массой M, совпадающая с центром масс тела. Форма тела здесь не имеет значения. К этому движению (так называемому, плоскому) добавляется вращение тела вокруг своего центра масс (это вращение никак не влияет на плоское движение и обратно). Опять-таки, форма тела не важна, важен только момент инерции. В отсутствие внешних сил линейная и угловая скорость тела не меняются, то есть тело продолжает двигаться (или стоять на месте) и вращаться. Как узнать, куда оно уехало (укрутилось) за период времени dt? Элементарно!

void update_position(double dt)
{
  x += Vx * dt; y += Vy * dt; angle += W * dt;
}

Вот, собственно и все по поводу движения.

Часть 4. Силы, действующие на тело.

Для того чтобы работать с силами телу придется еще задать:

M — массу, то есть сопротивляемость тела к движению.
I — момент инерции, то есть сопротивляемость тела к вращению.

Масса плоского тела обычно зависит от R * R. Момент инерции плоского круга радиуса R и массой M (равномерно распределенной по кругу) есть I = 0.5 * M * R * R.
То есть, если вы не знаете какую же в M и I цифру записать, делайте так: M = R * R; I = 0.5 * M * R * R. Если тело на ваш взгляд закручивается слишком легко — увеличивайте момент инерции, слишком тяжело сдвигается — уменьшайте массу и т.д.

Основная формула действия силы F (F — это вектор!) на тело массой M:

dV = F/M * dt,

где dV (dV — это тоже, разумеется, вектор) есть изменение скорости тела массой M за период dt под действием силы (постоянной в период dt).

Закручивающие силы действуют так же. Предположим, на наше тело действует толкающая сила F = (Fx, Fy) и закручивающая сила H (скаляр). Мы последовательно заходим в нашу процедуру движения тела с периодом dt. Как будет обновляться позиция тела? Примерно так:

void update_speed(double dt)
{
  Vx += Fx / M * dt; Vy += Fy / M * dt; W += H / I * dt;
}

void Tick(double dt)
{
  update_position (dt);
  update_speed(dt);
}

А теперь интересный момент — силы-то складываются! То есть если у нас есть несколько сил толкающих, то складываем их и то же для крутящих сил. И теперь используем Tick(), в который передаем суммарную силу. И результат будет такой, как если бы мы учитывали каждую силу в отдельности.

Выше мы проделали (весьма грубо) операцию интегрирования. При этом я предполагал, что на малом временном промежутке dt силы неизменны. Вообще говоря, это предположение не такое уж и тяжелое — для вашей игровой модели его может вполне хватить. Однако, если силы сильно меняются и вы хотите использовать более точные подсчеты — ищите сами метод Рунге-Кутта и изучайте формулу Тейлора.

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

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

23 апреля 2005 (Обновление: 9 янв. 2012)

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