Физика на пальцах: импульсный движок

Автор: Александр Санников

Введение
План Работы - вместо содержания
Применяемые допущения
Общие принципы. Как это вообще работает?
  Обнаружение столкновений
  Разрешение столкновений
  Интегририрование
В каком порядке добавлять функциональность в двиг и как его отлаживать
Майлстоуны
  Майлстоун первый - что такое тензор инерции. Как применять к телу силу и импульс?
  Майлстоун первый с половиной - как считать тензор инерции и массу?
  Майлстоун второй - когда применять силу, когда ускорение, а когда импульс?
  Майлстоун третий - степень свободы
  Майлстоун четвёртый - CCD и шаг интегрирования
Мне кажется, я знаю, как сделать лучше. Почему так делать нельзя.
  У вас всё как-то сложно. Мне же всего лишь для сфер и прямоугольничков!
  Почему просто не решать все контакты по порядку их возникновения?
  Заключение
  Код

Введение

План Работы - вместо содержания

- Сначала я опишу допущения, которые мы будем использовать
- Далее я вкратце опишу общие принципы, по которым вообще работает импульсный физический движок.
- Рассмотрю каждый шаг работы двига более подробно
- Далее рассмотрим, какие проблемы при написании двига возникают чаще всего и как их отлаживать
- Процесс понимания общефизических механизмов работы, которые нам понадобятся, я разделю на независимые прикладные задачи - майлстоуны, понимание каждой отдельной из них будет бесповоротно приближать нас к познанию дзена всей целостности и элегантности теормешной теории в целом :)
- Далее я опишу некоторые ошибочные пути, по которым так и норовят пойти начинающие разработчики и объясню, почему так лучше не делать.

Применяемые допущения

  Любое моделирование физики подразумевает какие-то допущения, упрощения, и наш случай - не исключение. Из таких допущений кроме совсем уж интуитивно понятных стоит выделить:
- Подразумеваем, что время идёт дискретно(малыми шажками), причём точность просчёта достаточно сильно зависит от величины кванта времени. Понятно, что если мы возьмём шаг времени dt слишком маленьким, функцию обновления физики придётся вызывать 1 / dt раз в секунду, что при слишком маленьком dt может быть слишком большой цифрой и банально вылиться в тормоза :) Из чисто практических соображений скажу лишь, что dt обычно нет смысла делать меньше 1 / 100 и опасно делать больше 1 / 40(может вылиться в дрожание, проваливание итп)
- Полагаем, что величина кванта времени от кадра к кадру меняется не слишком резко. В идеале она постоянна.
- Допускаем, что во время каждого кванта времени укаждого тела линейная скорость, угловая скорость, ускорения, приложенные силы и прочие показатели не меняются.
- Считаем, что в конце каждого кванта времени скорость скачкообразно изменяется в зависимости от ускорения (на величину acceleration * dt), а позиция скачкообразно меняется соответственно но величину. Мы не будем удивляться тому, что слишком быстро летящий мяч пролетает насквозь через сетку ворот, если за кадр он пролетает расстояние, сравнимое с его размерами.
- Мы не рассматриваем регулярную прецессию, полагая, что каждый квант времени тело просто-напросто вращается вокруг вектора своей угловой скорости. При желании ничто не помешает нам имплементирвать законы Эйлера динамики прецессии.
- Мы допускаем возможность того, что одно тело провалится в другое в особо экстремальных ситуациях. Это заметно, к примеру, когда используется слишком большая скорость или слишком большой шаг времени. Хинт состоит в том, что мы разрешаем соприкасающимся телам всегда проникать друг в друга на малую величину, назовём её deltaDepth(в других источниках называется skin width). Смысл такого экстравагантного допущения будет объяснён позже.

Общие принципы. Как это вообще работает?

- воздействуем на физический мир
- обновляем физический мир
- отрисовываем его новое состояние
- повторяем

Самый интересный для нас шаг в этой схеме - второй. Именно здесь и происходит вся магия физ. двига - он определяет, в какое состояние перейдёт физическая система в следующий момент времени, спустя dt. Этот шаг в свою очередь, уже внутри двига разбивается ещё на три подшага:

1) Обнаружение столкновений
2) Разрешение столкновений
3) Интегририрование

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

Обнаружение столкновений

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

К сожалению, тут не всегда всё просто и однозначно. Часто, особенно в случае глубокого взаимопроникновения и/или невыпуклых геометрий, указать конкретные точки взаимодействия тел может быть сложно. Об одном из подходов обнаружения столкновений для достаточно широкого круга геометрий - те, которые можно описать Support Mapping'ом, я более подробно рассказал в статье. Расчёт контактов для каждого типа взаимодействующих геометрий для каждого случая в своём роде уникален и одного подхода, который бы покрывал сразу все случаи, к сожалению, нет.

Разрешение столкновений

После того, как мы обнаружили все контакты, нам нужно сделать нечто, чтобы они хотя бы не становились всё глубже. В идеале хотелось бы даже невзначай их нейтрализовать(сделать так, чтобы самый глубокий контакт имел глубину ноль) и ещё желательно не нарушить при этом законы сохранения энергии и импульса. Для этого был разработан специальный механизм, ограничивающий взаимное перемещение тел, посредствам введения связей, или джойнтов. Например, для каждого контакта создаётся специальный тип джойнта - контактный, который ограничивает одну степень свободы, запрещая телам проникать друг в друга вдоль нормали контакта. Это сделать не так-то просто, придётся попотеть над матаном и вспомнить если не теормех, то хотя бы школьную физику и компонент двига, который этим занимается, называется солвером. О том, как работают импульсные солверы, я попытался более-менее доступно объяснить в другой своей статье

Интегририрование

Наверное, самый простой шаг. К этому моменту у нас уже посчитаны, какими должны быть скорости тел, чтобы они перестали друг в друга проникать, также мы опционально посчитали вектора, вектора, на которые их надо сместить(pseudovelocities), чтобы нейтрализовать пересечения и всё, что нам остаётся - это проинтегрировать скорости и ускорения на малый промежуток времени dt. Так как мы не заморачиваемся с высокими порядками точности, то используем интегратор Эйлера.

Прежде чем приступить к интегрированию положения, стоит определиться, как мы это самое положение будем задавать. Положение тела определяется координатами его центра масс и ориентацией. Если координаты центра масс - обыкновенный вектор, то с ориентацией может быть несколько сложнее. Мы предполагаем, что ориентация тела задана тремя векторами - его направлениями вправо, вверх и вдаль. Назовём их xVector, yVector, zVector. Если записать координаты(столбцы) этих векторов в строку, мы получим матрицу 3х3 - матрицу его поворота. Иногда для наглядности я буду использовать матрицу поворота всю целиком, а иногда - разложенную на эти три вектора. Так, к примеру, эти три вектора являются направлениями главных моментов инерции тела, как их использовать в такой интерпретации я расскажу чуть позже. Я специально оперирую отдельными векторами "вправо"/"вверх"/"вдаль", чтобы у читателя была возможность понимать, что же значат все эти формулы, откуда они берутся, а вопросы "с какой стороны мне домножать этот вектор на матрицу? D:" решались сами собой. После того, как читатель начинает себя уютно чувствовать в подобной арифметике, он может смело переходить на более общепринятый вид - матрицы. Там всё то же самое, просто записывается чуть короче.

Далее о скоростях. Если вектор linearVelocity - это то, на сколько смещается тело за единицу времени, то angularVelocity - это угол, на который поворачивается тело за единицу времени вокруг своего центра масс. Мы считаем, что любое тело мгновенно движется именно таким образом - перемещается на мало расстояние и поворачивается на малый угол вокруг центра масс. Учитывая то, что мы постоянно модифицируем линейную и угловую скорости во время решения контактов, это верно.

Итак, обратно к интегрированию. Сначало посчитаем, какое значение примут линейная и угловая скорости тела, спустя время dt:

void Body::IntegrateVelocity(float dt)
{
  linearVelocity += linearAcceleration * dt;
  angularVelocity += angularAcceleration * dt; 
}

Со смещением тела чуть сложнее. За малый промежуток времени тело успевает: