[Перевод] Создаём собственный физический 2D-движок06.11.2017 15:33

image

Часть 2: ядро движка.


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


Введение


В предыдущем посте я рассмотрел тему разрешения импульсов силы. Прочитайте сначала его, если вы ещё это не сделали!

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

  • Интегрирование
  • Метки времени
  • Модульная архитектура
    • Тела
    • Формы
    • Силы
    • Материалы
  • Широкая фаза
    • Отсечение дубликатов контактных пар
    • Система слоёв
  • Проверка пересечения полупространств




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


Интегрирование очень просто в реализации, и в Интернете есть много информации об итеративном интегрировании. В этом разделе я в основном рассмотрю функцию правильного интегрирования, и подскажу места, где можно найти более подробную информацию, если вам будет интересно.

Во-первых, нужно разобраться с тем, что же такое ускорение. Второй закон Ньютона гласит:

$Уравнение \: 1:\\F = ma$


Он утверждает, что сумма всех сил, действующих на объект, равна массе этого объекта m, умноженной на ускорение a. m указывается в килограммах, a — в метрах/с, а F — в ньютонах.

Немного преобразуем уравнение для вычисления a и получим:

$Уравнение \: 2:\\ a = \frac{F}{m}\\ \therefore\\ a = F * \frac{1}{m}$


Следующий этап включает в себя ускорение для перемещения объекта из одного места в другое. Поскольку игра отображается в дискретных отдельных кадрах, создающих иллюзию анимации, необходимо вычислить места каждой из позиций этих дискретных шагов. Более подробный анализ этих уравнений см. в демо интегрирования Эрина Катто с GDC 2009 и в дополнении Ханну к симплектическому методу Эйлера для повышения стабильности в средах с низким FPS.

Интегрирование явным методом Эйлера показано в следующем фрагменте кода, где x — это позициия, а v — скорость. Стоит заметить, что, как объяснено выше, 1/m * F — это ускорение: 

// Явный метод Эйлера
x += v * dt
v += (1/m * F) * dt


dt здесь обозначает дельту (прирост) времени. Δ — это символ дельты, и его можно буквально прочитать как «изменение в величине», или записать как Δt. Поэтому когда вы видите dt, это можно читать как «изменение времени». dv — это «изменение скорости».

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

// Симплектический метод Эйлера
v += (1/m * F) * dt
x += v * dt


Заметьте, что я всего лишь преобразовал порядок двух строк кода — см. вышеупомянутую статью Ханну.

В этом посте объясняются численные неточности явного метода Эйлера, но учтите, что Ханну начинает рассматривать RK4, который лично я не рекомендую: gafferongames.com: неточность метода Эйлера.

Этих простых уравнений достаточно для перемещения всех объектов с линейной скоростью и ускорением.


Метки времени


Поскольку игры отображаются с дискретными интервалами времени, нам требуется способ управляемой манипуляции временем между этими шагами. Видели ли вы когда-нибудь игру, которая работает на разных компьютерах с разной скоростью? Это пример игры, выполняемой со скоростью, зависящей от мощности компьютера.

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

Детерминированный физический движок — это такой движок, который при одинаковом вводе всегда будет делать одно и то же. Это необходимо во многих типах игр, в которых геймплей должен быть чётко привязан к поведению физического движка. Кроме того, это необходимо для отладки нашего движка, потому что для выявления ошибок поведения движка оно должно быть неизменным.

Для начала давайте рассмотрим простую версию постоянной метки времени. Вот пример: 

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )


Этот код ждёт и рендерит игру, пока не пройдёт достаточно времени для обновления физики. Прошедшее время записывается, а дискретные блоки времени размером с dt берутся из accumulator и обрабатываются физикой. Это гарантирует, что в любых условиях физике передаётся одинаковое значение, и что переданное физике значение является точным отображением действительного времени, прошедшего в реальной жизни. Блоки dt удаляются из accumulator, пока accumulator не становится меньше блока dt.

Здесь мы можем устранить пару проблем. Первая связана с тем, сколько времени требуется на обновление физики: что будет, если обновление физики займёт слишком много времени и с каждым игровым циклом accumulator будет всё больше и больше? Это называется «спиралью смерти». Если не решить эту проблему, то движок быстро придёт к полному останову, если расчёт физики будет недостаточно быстрым.

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

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  // Избавляемся от спирали смерти и ограничиваем dt, таким образом
  // ограничивая количество вызовов UpdatePhysics за
  // один игровой цикл.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  RenderGame( )


Теперь, если выполняющая этот цикл игра обнаружит простой по каким-то причинам, то физика не утянет себя в спираль смерти. Игра просто будет выполняться немного медленнее, как и следует.

Следующая проблема гораздо меньше по сравнению со спиралью смерти. Этот цикл получает блоки dt из accumulator, пока accumulator не становится меньше dt. Это здорово, но в accumulator всё равно остаётся немного времени. В этом заключается проблема.

Допустим, что в accumulator каждый кадр остаётся 1/5 от блока dt. На шестом кадре в accumulator будет достаточно оставшегося времени на выполнение ещё одного обновления физики для всех других кадров. Это приведёт к тому, то примерно в одном кадре в секунду, или около того, будет выполняться немного больший дискретный прыжок во времени, и это может быть очень заметно в игре.

Чтобы решить эту проблему, необходимо использовать линейную интерполяцию. Звучит пугающе, но не бойтесь — я покажу реализацию. Если вы хотите понять, как её реализуют, то в Интернете есть множество ресурсов, посвящённых линейной интерполяции.

// линейная интерполяция для a от 0 до 1
// от t1 до t2
t1 * a + t2(1.0f - a)


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

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

Вот полный пример: 

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// Единицы измерения - секунды
float frameStart = GetCurrentTime( )

// основной цикл
while(true)
  const float currentTime = GetCurrentTime( )

  // Сохраняется время, прошедшее с начала последнего кадра
  accumulator += currentTime - frameStart( )

  // Записывается начало этого кадра
  frameStart = currentTime

  // Избавляемся от спирали смерти и ограничиваем dt, таким образом
  // ограничивая количество вызовов UpdatePhysics за
  // один игровой цикл.
  if(accumulator > 0.2f)
    accumulator = 0.2f

  while(accumulator > dt)
    UpdatePhysics( dt )
    accumulator -= dt

  const float alpha = accumulator / dt;

  RenderGame( alpha )

void RenderGame( float alpha )
  for shape in game do
    // вычисляем интерполированную трансформацию для рендеринга
    Transform i = shape.previous * alpha + shape.current * (1.0f - alpha)
    shape.previous = shape.current
    shape.Render( i )


Таким образом, все объекты в игре могут отрисовываться в переменные моменты между дискретными метками времени физики. Это позволяет элегантно обрабатывать все ошибки и накопление остатка времени. На самом деле рендеринг будет выполняться немного позже вычисленной физики, но при наблюдении за игрой всё движение замечательно сглаживается интерполяцией.

Игрок никогда не догадается, что рендеринг постоянно отстаёт от физики, потому что он будет знать только то, что видит, а видеть он будет идеально плавные переходы от одного кадра к другому.

Вы можете задаться вопросом: почему мы не интерполируем из текущей позиции до следующей? Я пробовал так сделать и оказалось, что для этого требуется, чтобы рендеринг «догадывался», где объекты будут находиться в будущем. Объекты в физическом движке часто могут внезапно менять своё движение, например, при коллизциях, и когда такие резкие изменения происходят, объекты телепортируются в другое место из-за неточных интерполяций на будущее.


Модульная архитектура


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

Словосочетание «модульная архитектура» может звучать пафосно и переусложнённо, но на самом деле оно вполне логично и довольно просто. В этом контексте под «модульной архитектурой» всего лишь подразумевается, что мы можем разбить физические объекты на отдельные части, чтобы можно было соединять и разъединять их удобным способом.

Тела


Физическое тело — это объект, содержащий всю информацию о каком-то конкретном физическом объекте. В нём будут храниться форма (или формы), из которых состоит объект, данные о массе, трансформации (позиция, поворот), скорость, крутящий момент, и т.д. Вот как будет выглядеть тело body: 

struct body
{
  Shape *shape;
  Transform tx;
  Material material;
  MassData mass_data;
  Vec2 velocity;
  Vec2 force;
  real gravityScale;
};


Это отличная отправная точка для создания структуры физического тела. Здесь приняты логичные решения для создания хорошей структуры кода.

Во-первых, стоит заметить, что форма помещается в тело с помощью указателя. Благодаря этому создаётся слабая связь между телом и его формой. Тело может содержать любую форму, а форма тела может произвольно изменяться. На самом деле, тело может быть представлено несколькими формами, и такое тело будет называться «составным», потому что состоит из нескольких форм. (В этом туториале я не буду рассматривать составные тела.)

2d4f60d07eb8c3363697bcf42cbf9a7a.png
Интерфейс тела и формы.

Сам shape ответственен за вычисление граничных форм, вычисления массы на основании плотности и за рендеринг.

mass_data — это небольшая структура данных для хранения связанной с массой информации: 

struct MassData
{
  float mass;
  float inv_mass;

  // Для вращений (будут рассматриваться ниже)
  float inertia;
  float inverse_inertia;
};


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

$Уравнение 3:\\ масса = плотность * объём$


Когда дизайнеру нужно, чтобы форма была более «массивной» или «тяжёлой», то ему стоит изменять плотность формы. Эту плотность можно использовать для вычисления массы формы с помощью её объёма. Это правильный способ действий в такой ситуации, потому что на плотность не влияет объём и она никогда не меняется во время выполнения игры (если только это не обеспечивается специальным кодом).

Некоторые из примеров форм, таких как AABB и окружности, можно найти в предыдущей части туториала.

Материалы


Все эти разговоры о массе и плотности приводят нас к вопросу: где же хранится значение плотности? Оно находится в структуре Material: 

struct Material
{
  float density;
  float restitution;
};


После задания значений материала этот материал можно передать форме тела, чтобы тело могло вычислить массу.

Последнее, о чём стоит упомянуть — это gravity_scale. Масштабирование гравитации для разных объектов очень часто пригождается при тонкой настройке игрового процесса, поэтому в каждое тело стоит добавить это значение специально под эту задачу.

Полезные настройки для самых распространённых материалов можно использовать для создания значения перечисления объекта Material: 

Rock       Density : 0.6  Restitution : 0.1
Wood       Density : 0.3  Restitution : 0.2
Metal      Density : 1.2  Restitution : 0.05
BouncyBall Density : 0.3  Restitution : 0.8
SuperBall  Density : 0.3  Restitution : 0.95
Pillow     Density : 0.1  Restitution : 0.2
Static     Density : 0.0  Restitution : 0.4


Силы


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

Это позволяет действовать на объект любому количеству сил, и для приложения к объектам новых видов сил не потребуется написание нового кода.

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

HeavyObject object
for body in game do
  if(object.CloseEnoughTo( body )
    object.ApplyForcePullOn( body )


Функция ApplyForcePullOn() может относиться к небольшой силе, притягивающей body к HeavyObject, только если body находится достаточно близко.

cd818242d421cd805393309b8e619ef9.png


Два объекта, притянутые к большему объекту, двигающемуся мимо них. Силы притяжения зависят от расстояния до большого прямоугольника.

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


Широкая фаза


В предыдущей статье серии мы ввели процедуры распознавания коллизий. Эти процедуры на самом деле независимы от того, что называется «узкой фазой». Различия между широкой и узкой фазами можно довольно просто найти в Google.

(Вкратце: мы используем широкую фазу распознавания коллизий для определения того, какие пары объектов могут сталкиваться, а затем узкую фазу распознавания коллизий, чтобы проверить, действительно ли они сталкиваются.)

Я хочу привести пример кода с объяснением того, как реализовать широкую фазу вычислений пар алгоритма с временной сложностью $O(n^2)$.

$O(n^2)$ означает, что время, потраченное на проверку каждой пары потенциальных коллизий, зависит от квадрата количества объектов. Здесь используется нотация «О» большое.

Так как мы работаем с парами объектов, то будет полезно создать подобную структуру: 

struct Pair
{
  body *A;
  body *B;
};


Широкая фаза должна собрать группу возможных коллизий и сохранить их все в структурах Pair. Затем эти пары могут быть переданы другой части движка (узкой фазе) для последующего решения.

Пример широкой фазы: 

// Генерирует список пар.
// При вызове этой функции все предыдущие пары сбрасываются.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Пространство кэша для AABB, которое будут использоваться
  // для вычисления граничного прямоугольника каждой формы
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Пропуск проверки с самим собой
      if(A == B)
        continue

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}


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

Отсечение дубликатов


В последнем разделе есть одна проблема: будет возвращаться множество дубликатов пар! Эти дубликаты нужно убрать из результатов. Если у вас нет под рукой библиотеки сортировки, то для этого понадобится знакомство с алгоритмами сортировки. Если вы пишете на C++, то вам повезло: 

// Сортируем пары для выявления дубликатов
sort( pairs, pairs.end( ), SortPairs );

// Создаём очередь из многообразий для решения
{
  int i = 0;
  while(i < pairs.size( ))
  {
    Pair *pair = pairs.begin( ) + i;
    uniquePairs.push_front( pair );

    ++i;

    // Пропускаем дубликаты, выполняя итерации, пока не найдём уникальную пару
    while(i < pairs.size( ))
    {
      Pair *potential_dup = pairs + i;
      if(pair->A != potential_dup->B || pair->B != potential_dup->A)
        break;
      ++i;
    }
  }
}


После сортировки всех пар в определённом порядке можно считать, что у всех пар в контейнере pairs есть по соседству дубликат. Поместим все уникальные пары в новый контейнер uniquePairs, и на этом работа по отсечению дубликатов закончена.

The last thing to mention is the predicate SortPairs(). Эта функция SortPairs() используется для сортировки. Она может выглядеть вот так: 

bool SortPairs( Pair lhs, Pair rhs )
{
  if(lhs.A < rhs.A)
    return true;

  if(lhs.A == rhs.A)
    return lhs.B < rhs.B;

  return false;
}


Члены lhs и rhs можно расшифровать как «left hand side» (сторона слева) и «right hand side» (сторона справа). Эти члены обычно используются для работы с параметрами функций, в которых элементы можно логически рассматривать как левую и правую часть какого-то уравнения или алгоритма.

Система слоёв


Система слоёв нужна для того, чтобы различные объекты никогда не сталкивались друг с другом. Она необходима, чтобы пули, летящие от определённых объектов, не влияли на другие определённые объекты. Например, игроки одной команды ракетами должны наносить урон врагам, но не друг другу.

5b0a69ce6c5ce842ddd558cb407fa7eb.png


Объяснение системы слоёв: некоторые объекты сталкиваются друг с другом, другие же нет.

Систему слоёв лучше всего реализовать с помощью битовых масок. Чтобы узнать, как битовые маски используются в движках, см. для ознакомления краткое введение в битовые маски для программистов, страницу на Википедии и раздел Filtering в руководстве Box2D.

Система слоёв реализуется в широкой фазе. Здесь я просто вставлю готовый пример широкой фазы: 

// Генерирует список пар.
// При вызове этой функции все предыдущие пары сбрасываются.
void BroadPhase::GeneratePairs( void )
{
  pairs.clear( )

  // Пространство кэша для AABB, которое будут использоваться
  // для вычисления граничного прямоугольника каждой формы
  AABB A_aabb
  AABB B_aabb

  for(i = bodies.begin( ); i != bodies.end( ); i = i->next)
  {
    for(j = bodies.begin( ); j != bodies.end( ); j = j->next)
    {
      Body *A = &i->GetData( )
      Body *B = &j->GetData( )

      // Пропуск проверки с самим собой
      if(A == B)
        continue

      // Учитываться тольк соответствующие слои
      if(!(A->layers & B->layers))
        continue;

      A->ComputeAABB( &A_aabb )
      B->ComputeAABB( &B_aabb )

      if(AABBtoAABB( A_aabb, B_aabb ))
        pairs.push_back( A, B )
    }
  }
}


Система слоёв оказывается высокоэффективной и очень простой.


Пересечение полупространств


Полупространство можно рассматривать в 2D как одну сторону прямой. Определение того, находится ли точка на одной или другой стороне прямой — довольно распространённая задача, и при реализации собственного физического движка нужно хорошо разобраться в ней. Очень плохо, что эта тема, как мне кажется, нигде в Интернете подробно не раскрыта, и мы это исправим!

Общее уравнение прямой в 2D имеет следующий вид:

$Уравнение \: 4:\\ Общая \: форма: ax + by + c = 0\\ Нормаль \: к \: прямой: \begin{bmatrix} a \\ b \\ \end{bmatrix}$


470d9422c9dfd2cc6dd2c7ffb1391a08.png

Учтите, что несмотря на своё название, вектор нормали не всегда обязательно нормализирован (то есть он не обязательно имеет длину 1).

Чтобы определить, находится ли точка на определённой стороне прямой, всё, что нам нужно — подставить точку в переменные x и y уравнения и проверить знак результата. Результат 0 будет означать, что точка находится на прямой, а положительное/отрицательное значение означают разные стороны прямой.

И на этом всё! Зная это, от точки до прямой является результатом предыдущей проверки. Если вектор нормали не нормализован, то результат отмасштабирован на величину вектора нормали.


Заключение


К этому этапу вы можете создать с нуля полный, хотя и очень простой физический движок. В следующих частях мы рассмотрим более сложные темы: трение: ориентация, и динамическое дерево AABB.

Часть 3: трение, сцена и таблица переходов


В этой части статьи мы рассмотрим следующие темы:

  • Трение
  • Сцена
  • Таблица переходов коллизий



Видео демо


Вот краткое демо того, над чем мы будем работать в этой части:



Трение


Трение — это часть системы разрешения коллизий. Трение всегда прикладывается к силе, приложенной к объектам, в направлении, противоположном их движению.

В реальной жизни трение — это невероятно сложное взаимодействие между различными веществами и для его моделирования принимаются серьёзные допущения и аппроксимации. Эти допущения относятся к математике и обычно формулируются примерно так: «трение можно приближенно представить как один вектор», аналогично тому, как динамика твёрдых тел симулирует взаимодействия реального мира, допуская использование недеформируемых тел с одинаковой по всему объёму плотностью.

Взгляните на видео демо из первой части статьи:


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

Импульсы силы, снова?


Как вы наверно помните из первой части туториала, для разделения проникновения двух объектов при коллизии необходимо значение j, представляющее собой величину импульса силы. Эту величину можно обозначить как jnormal или jN, потому что она используется для изменения скорости вдоль нормали коллизии.

Для добавления реакции трения необходимо вычислить ещё одну величину, обозначаемую как jtangent или jT. Трение можно смоделировать как импульс силы. Эта величина будет изменять скорость объекта вдоль отрицательного касательного вектора коллизии, или, другими словами, вдоль вектора трения. В двух измерениях вычисление вектора трения является решаемой задачей, но в 3D она становится гораздо сложнее.

Трение довольно просто, и мы можем снова воспользоваться нашим предыдущим уравнением для j, только заменим все нормали n на касательный вектор t.

$Уравнение \: 1:\\ j = \frac{-(1 + e)(V^{B}-V^{A})\cdot n)} {\frac{1}{mass^A} + \frac{1}{mass^B}}$


Заменим n на t:

$Уравнение \:2:\\ j = \frac{-(1 + e)((V^{B}-V^{A})\cdot t)} {\frac{1}{mass^A} + \frac{1}{mass^B}}$


Хотя в этом уравнении на t заменено всего одно вхождение n, после добавления вращения необходимо будет заменить ещё несколько вхождений, кроме одного в числителе Уравнения 2.

Теперь возникает вопрос, как же вычислить t. Касательный вектор — это вектор, перпендикулярный нормали коллизии, который направлен ближе к нормали. Это может сбивать с толку — не волнуйтесь, у нас есть рисунок!

На рисунке ниже видно, что касательный вектор перпендикулярен нормали. Касательный вектор может быть направлен влево или вправо. Если влево, то он «дальше» от относительной скорости. Однако он определяется как перпендикуляр к нормали, направленный «ближе» к относительной скорости.

2da8630ac62eafce3052c27bbf5c4b7a.png


Различные виды векторов в кадре времени коллизии твёрдых тел.

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

Если мы знаем это, то касательный вектор равен (где n — нормаль коллизии):

$V^R = V^{B}-V^{A} \\ t = V^R - (V^R \cdot n) * n $


Чтобы определить величину трения jt, нам осталось только непосредственно вычислить значение из представленных выше уравнений. Вскоре мы рассмотрим и другие хитрости после вычисления этого значения, поэтому это не единственное, что нужно для нашего разрешения коллизий: 

// Перерасчёт относительной скорости после приложения
// нормального импульса (импульса силы из первой статьи, этот код идёт сразу
// после в той же функции разрешения)
Vec2 rv = VB - VA

// Вычисляем касательный вектор
Vec2 tangent = rv - Dot( rv, normal ) * normal
tangent.Normalize( )

// Вычисляем величину, прилагаемую вдоль вектора трения
float jt = -Dot( rv, t )
jt = jt / (1 / MassA + 1 / MassB)


Вышеприведённый код непосредственно соответствует Уравнению 2. Повторюсь, важно понимать, что вектор трения указывает в направлении, противоположном касательному вектору. Поэтому мы должны добавить знак «минус» при скалярном произведении относительной скорости по касательной, чтобы вычислить относительную скорость вдоль касательного вектора. Знак «минус» переворачивает касательную скорость и внезапно указывает в направлении, в котором должно аппроксимироваться трение.

Закон Амонтона — Кулона


Закон Амонтона — Кулона — это та часть симуляции трения, в которой испытывают затруднение большинство программистов. Мне самому пришлось достаточно долго изучать его, чтобы найти правильный способ моделирования. Хитрость в том, что закон Амонтона — Кулона — это неравенство.

Он гласит:

$Уравнение \:3: \\ F_f <= \mu F_n$


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

Нормальная сила — это просто наша старая величина j, умноженная на нормаль коллизии. Так что если вычисленная jt (представляющая собой силу трения) меньше нормальной силы в μ раз, то мы можем использовать нашу величину jt в качестве трения. Если же нет, то вместо неё надо использовать нормальную силу, умноженную на μ. Это условие «если» ограничивает наше трение каким-то максимальным значением, где максимумом будет нормальная сила, умноженная на μ.

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

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

// Перерасчёт относительной скорости после приложения
// нормального импульса (импульса силы из первой статьи, этот код идёт сразу
// после в той же функции разрешения)
Vec2 rv = VB - VA

// Вычисляем касательный вектор
Vec2 tangent = rv - Dot( rv, normal ) * normal
tangent.Normalize( )

// Вычисляем величину, прилагаемую вдоль вектора трения
float jt = -Dot( rv, t )
jt = jt / (1 / MassA + 1 / MassB)

// PythagoreanSolve = A^2 + B^2 = C^2, вычисляем C для заданных A и B
// Используем для аппроксимации мю для заданных коэффициентов трения каждого тела
float mu = PythagoreanSolve( A->staticFriction, B->staticFriction )

// Ограничиваем величину трения и создаём вектор импульса силы
Vec2 frictionImpulse
if(abs( jt ) < j * mu)
  frictionImpulse = jt * t
else
{
  dynamicFriction = PythagoreanSolve( A->dynamicFriction, B->dynamicFriction )
  frictionImpulse = -j * t * dynamicFriction
}

// Прикладываем
A->velocity -= (1 / A->mass) * frictionImpulse
B->velocity += (1 / B->mass) * frictionImpulse


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

$Уравнение \:4: \\ Friction = \sqrt[]{Friction^2_A + Friction^2_B}$


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

Важно то, что в сравнении используется абсолютное значение jt, потому что теоретически сравнение ограничивает «сырые» величины каким-то порогом. Поскольку j всегда положительно, его нужно перевернуть, чтобы оно представляло истинный вектор трения в случае использования динамического трения.

Статическое и динамическое трение


В предыдущем фрагменте кода без каких-либо объяснений были введены статическое и динамическое трение. Я посвящу целый раздел объяснению разницы между ними и необходимости этих двух типов значений.

При трении происходит кое-что интересное: чтобы объекты перешли из состояния покоя в движение, им требуется «энергия активации». Когда два объекта покоятся один на другом в реальной жизни, требуется довольно большая энергия, чтобы столкнуть один из них и заставить двигаться. Однако когда мы заставили объект скользить по другому, часто после этого для поддержания скольжения требуется меньше энергии.

Так происходит из-за принципа работы трения на микроскопическом уровне. Здесь поможет ещё одна иллюстрация:

177c82774d44b39d0acb6c488a4fbd33.png


Микроскопические причины необходимости энергии активации при трении.

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

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

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

С другой стороны, если при вычислении jt величина выше порога, то можно считать, что объект уже превысил «энергию активации», и в такой ситуации используется меньший импульс силы трения, что выражается в меньшем коэффициенте трения и немного ином вычислении импульса силы.


Сцена


Если вы внимательно прочитали раздел «Трение», то поздравляю! Вы завершили самую сложную (по моему мнению) часть всего туториала.

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

Вот пример того, как может выглядеть структура сцены: 

class Scene
{
public:
  Scene( Vec2 gravity, real dt );
  ~Scene( );

  void SetGravity( Vec2 gravity )
  void SetDT( real dt )

  Body *CreateBody( ShapeInterface *shape, BodyDef def )

  // Вставляет тело в сцену и инициализирует тело (вычисляет массу).
  void InsertBody( Body *body )

  // Удаляет тело из сцены
  void RemoveBody( Body *b
    
            
© Habrahabr.ru