Как создать пользовательский 2D физический движок: таблица трения, сцены и Jump Table

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

 Темы, которые мы рассмотрим в этой статье:

• Трение
• Сцена
• Collision Jump Table

 Я настоятельно рекомендовал прочитать предыдущие две статьи в серии, прежде чем пытаться решить эту проблему. Некоторая ключевая информация в предыдущих статьях основана на этой статье.

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

Video Demo

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

Custom 2D Physics Engine: Friction, Scene and Jump Table

Трение

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

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

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

Custom Physics Engine Demo

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

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

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

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

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

\[ Equation 1:\\
j = \frac{-(1 + e)(V^{B}-V^{A})\cdot n)}
{\frac{1}{mass^A} + \frac{1}{mass^B}}\]

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

\[ Equation 2:\\
j = \frac{-(1 + e)((V^{B}-V^{A})\cdot t)}
{\frac{1}{mass^A} + \frac{1}{mass^B}}\]

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

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

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

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

Зная это, касательный вектор равен (где n - normal столкновения):

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

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

1

2

// Re-calculate relative velocity after normal impulse

3

// is applied (impulse from first article, this code comes

4

// directly thereafter in the same resolve function)

5

Vec2 rv = VB - VA

6

7

// Solve for the tangent vector

8

Vec2 tangent = rv - Dot( rv, normal ) * normal

9

tangent.Normalize( )

10

11

// Solve for magnitude to apply along the friction vector

12

float jt = -Dot( rv, t )

13

jt = jt / (1 / MassA + 1 / MassB)

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

 Закон Кулона

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

Состояние кулоновского трения:

\[ Equation 3: \\
F_f <= \mu F_n \]

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

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

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

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

1

2

// Re-calculate relative velocity after normal impulse

3

// is applied (impulse from first article, this code comes

4

// directly thereafter in the same resolve function)

5

Vec2 rv = VB - VA

6

7

// Solve for the tangent vector

8

Vec2 tangent = rv - Dot( rv, normal ) * normal

9

tangent.Normalize( )

10

11

// Solve for magnitude to apply along the friction vector

12

float jt = -Dot( rv, t )

13

jt = jt / (1 / MassA + 1 / MassB)

14

15

// PythagoreanSolve = A^2 + B^2 = C^2, solving for C given A and B

16

// Use to approximate mu given friction coefficients of each body

17

float mu = PythagoreanSolve( A->staticFriction, B->staticFriction )

18

19

// Clamp magnitude of friction and create impulse vector

20

Vec2 frictionImpulse

21

if(abs( jt ) < j * mu)

22

  frictionImpulse = jt * t

23

else

24

{

25

  dynamicFriction = PythagoreanSolve( A->dynamicFriction, B->dynamicFriction )

26

  frictionImpulse = -j * t * dynamicFriction

27

}

28

29

// Apply

30

A->velocity -= (1 / A->mass) * frictionImpulse

31

B->velocity += (1 / B->mass) * frictionImpulse

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

\[ Equation 4: \\
Friction = \sqrt[]{Friction^2_A + Friction^2_B} \]

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

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

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

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

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

Это связано с тем, как трение работает на микроскопическом уровне. Здесь помогает еще одна картина:

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

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

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

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

Scene

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

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

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

1

2

class Scene

3

{

4

public:

5

  Scene( Vec2 gravity, real dt );

6

  ~Scene( );

7

8

  void SetGravity( Vec2 gravity )

9

  void SetDT( real dt )

10

11

  Body *CreateBody( ShapeInterface *shape, BodyDef def )

12

13

  // Inserts a body into the scene and initializes the body (computes mass).

14

  //void InsertBody( Body *body )

15

16

  // Deletes a body from the scene

17

  void RemoveBody( Body *body )

18

19

  // Updates the scene with a single timestep

20

  void Step( void )

21

22

  float GetDT( void )

23

  LinkedList *GetBodyList( void )

24

  Vec2 GetGravity( void )

25

  void QueryAABB( CallBackQuery cb, const AABB& aabb )

26

  void QueryPoint( CallBackQuery cb, const Point2& point )

27

28

private:

29

  float dt     // Timestep in seconds

30

  float inv_dt // Inverse timestep in sceonds

31

  LinkedList body_list

32

  uint32 body_count

33

  Vec2 gravity

34

  bool debug_draw

35

  BroadPhase broadphase

36

};

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

 Другой важной функцией является Step(). Эта функция выполняет один цикл проверки столкновений, разрешения и интеграции. Это следует вызывать в цикле временного шага, описанном во второй статье этой серии.

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

Jump Table

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

В C ++ есть два основных способа, которые мне известны: двойная диспетчеризация и 2D-таблица переходов. В своих личных тестах я обнаружил, что таблица 2D-прыжков превосходна, поэтому я подробно расскажу о том, как это реализовать. Если вы планируете использовать язык, отличный от C или C ++, я уверен, что массив функций или объектов-функторов может быть создан аналогично таблице указателей на функции (это еще одна причина, по которой я решил говорить о таблицах переходов, а не о других опциях которые более специфичны для C ++).

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

1

2

enum Animal

3

{

4

  Rabbit

5

  Duck

6

  Lion

7

};

8

9

const void (*talk)( void )[] = {

10

  RabbitTalk,

11

  DuckTalk,

12

  LionTalk,

13

};

14

15

// Call a function from the table with 1D virtual dispatch

16

talk[Rabbit]( ) // calls the RabbitTalk function

Приведенный выше код фактически имитирует то, что сам язык C ++ реализует с помощью вызовов и наследования виртуальных функций. Однако C ++ реализует только одномерные виртуальные вызовы. 2D таблица может быть построена вручную.

Вот некоторый psuedocode для 2D таблицы переходов для вызова процедур коллизий:

1

2

collisionCallbackArray = {

3

  AABBvsAABB

4

  AABBvsCircle

5

  CirclevsAABB

6

  CirclevsCircle

7

}

8

9

// Call a collsion routine for collision detection between A and B

10

// two colliders without knowing their exact collider type

11

// type can be of either AABB or Circle

12

collisionCallbackArray[A->type][B->type]( A, B )

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

Обратите внимание, однако, что AABBvsCircle и CirclevsAABB являются почти дубликатами. Это необходимо! normal нужно перевернуть для одной из этих двух функций, и это единственное различие между ними. Это обеспечивает согласованное разрешение столкновений, независимо от комбинации разрешаемых объектов.

Заключение

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

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

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