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

Примеры использования движка
Примеры использования движка

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

Основной этап расчет

Для рассмотрения будем использовать версию 3.17 и пример, находящийся в исходниках по пути.

examples/HelloWorld/HelloWorld.cpp

В нем приведен минимальный набор действий для использования библиотеки. Ее будем изучать с использованием исходных кодов и документации.

Первым делом, в примере создается мир(btDiscreteDynamicsWorld) и два объекта в нем: земля(btBoxShape) и сфера на ней (btSphereShape).

На картинке приведенной ниже описаны основные действия выполняемые движком. Мир обновляется через команду stepSimulation. Сама команда проверяет частоту обновления мира через средства ОС, затем определяет кинематические положение и скорость всех объектов, применяет гравитацию, после чего определяет СубШаги, которые необходимо выполнить для корректной работы Bullet.

Общий алгоритм работы btDiscreteDynamicsWorld::stepSimulation
Общий алгоритм работы btDiscreteDynamicsWorld::stepSimulation

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

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

Алгоритм createPredictiveContactsInternal приведен на картинке ниже.

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

Выполнение функции createPredictiveContactsInternal и участвующие в процессе классы
Выполнение функции createPredictiveContactsInternal и участвующие в процессе классы

Здесь мы познакомимся с первыми классами. Базовый класс btCollisionWorld -- это основа Bullet. Поверх этого класса реализован класс btDiscreteDynamicsWorld, который описывает конкретную реализацию всей физики коллизий. Внутри Дискретного Мира(ДМ) реализованы вспомогательные классы btClosestNotMeConvexResultCallback и btSingleSweepCallback, реализующие взаимодействие между ДМ и другими объектами. 

Класс btRigidBody - основной для физических тел, взаимдействующих внутри движка.

Класс btDbvtBroadphase реализует основной этап анализа взаимодействия, используя две динамические иерархии/дерева объемного ограничения по алгоритму AABB( прямоугольным параллелепипедом). Одно дерево используется для статических объектов, второе -- для динамических: объекты могут перемещаться из одной иерархии в другую.

В принципе, весь анализ взаимодействия распределен автором на BroadPhase и NarrowPhase.

Класс btDbvt неотрывно связан с предыдущим: он представляет быстродействующее дерево вычисления ограничения объема взаимодействия, основанное на параллелепипеде, выровненном по осям Мира. Иначе, он ищет пары взаимодействующих объектов. Он может быстро вставлять, удалять или обновлять узлы. Узлы могут динамично вращаться вокруг иерархии, изменяя структуру основной топологии.

Класс btContinuousConvexCollision (относится к Narrow Phase) выполняет оценку времени соударения при угловом и линейном движении. Его основная задача выдерживать согласованность движения. Сейчас он использует идею консервативного движения Brian Mirtich, в дальнейшем предполагается добавление алгоритма Minkowski (уже реализован в библиотеке).

Алгоритм performDiscreteCollisionDetection выполняется следующим после ДПС, а сам он представлен на картинке ниже. В нем задействованы уже известные классы btCollisionWorld и btDbvtBroadphase, а также несколько новых.

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

 

Классы, функции и переменные, вовлеченные в выполнение функций performDiscreteCollisionDetection и calculateSimulationIslands
Классы, функции и переменные, вовлеченные в выполнение функций performDiscreteCollisionDetection и calculateSimulationIslands

Класс btCollisionDispatcher выполняет процедуры обработки пар взаимодействия типа ConvexConvex, ConvexConcave (Выпуклый-Выпуклый, Выпуклый-Вогнутый типы): вычисляет время взаимодействия, ближайшие точки и степень проникновения.

Класс btDefaultCollisionConfiguration определяет набор функций для алгоритмов коллизий, например btSphereSphereCollisionAlgorithm. Эти функции используются при расчете классом btCollisionDispatcher. Таким образом, можно имплементировать различное количество функций: можно расширять количество алгоритмов или уменьшать их в целях экономии места.

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

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

Функция calculateSimulationIslands представляет собой подход кусочной обработки множества взаимодействия всех тел.

Класс btUnionFind находит соединенные подмножества, из списка составленного в процессе выполнения функции createPredictiveContactsInternal.

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

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

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

Следующая по порядку вызываемая функция solveConstraints. Ее выполнение, как раз обеспечивает основные расчеты.

Классы, функции и переменные, используемые алгоритмом solveConstraints
Классы, функции и переменные, используемые алгоритмом solveConstraints

Класс btSequentialImpulseConstraintSolver выполняет основной объем. По документации, он реализует быстрый алгоритм SIMD, который основан на методе Гаусса — Зейделя.

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

btContactSolverInfo m_solverInfo;

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

btAlignedObjectArray<btSolverBody> m_tmpSolverBodyPool

где btSolverBody содержит информацию о (Здесь и далее не рассматривается физический смысл переменных):

П/п

Параметр

Описание/перевод

1

m_worldTransform

Положение в Мире

2

m_deltaLinearVelocity

Изменение линейной скорости

3

m_deltaAngularVelocity

Изменение угловой скорости

4

m_angularFactor

Угловой фактор(?)

5

m_linearFactor

Линейный фактор(?)

6

m_invMass

1/массу тела

7

m_pushVelocity

Скорость нажатия(?)

8

m_turnVelocity

Скорость поворота(?)

9

m_linearVelocity

Линейная скорость

10

m_angularVelocity

Угловая скорость

11

m_externalForceImpulse

Импульс внешней силы

12

m_externalTorqueImpulse

Вращательный момент внешней силы

 Эти данные сбрасываются на функции solveGroupCacheFriendlyFinish.

(?) -- здесь и далее отметка, о том что крайне непонятно название переменной

Набор данных о взаимодействии хранится тут:

п/п

Наименование переменной btConstraintArray

1

m_tmpSolverContactConstraintPool

2

m_tmpSolverNonContactConstraintPool

3

m_tmpSolverContactFrictionConstraintPool

4

m_tmpSolverContactRollingFrictionConstraintPool

где

typedef btAlignedObjectArray<btSolverConstraint> btConstraintArray;

, в котором btSolverConstraint содержит информацию:

П/п

Параметр

Описание/перевод

1

m_relpos1CrossNormal

Векторное произведение 1 относительного положения и нормали

2

m_contactNormal1

Нормаль 1 в точке контакта

3

m_relpos2CrossNormal

Векторное произведение 2 относительного положения и нормали

4

m_contactNormal2

Нормаль 2 в точке контакта (чаще всего равна по магнитуде и противоположна по направлению)

5

m_angularComponentA

Угловой компонент A(?)

6

m_angularComponentB

Угловой компонент B(?)

7

m_appliedPushImpulse

Примененный импульс нажатия/толчка(?)

8

m_appliedImpulse

Примененный импульс

9

m_friction

Трение

10

m_jacDiagABInv

Числовое значение от инвертированной суммы векторов, полученного из перемножения матрицы Тензора инерции тела и вектора № 1-3, далее умноженного снова на вектор №1-3

11

m_rhs

Переменная m_rhs, которая может быть равна импульсу скорости или сумме импульсов скорости(ошибка скорости на переменную №10) и проникновения(ошибка позиционирования на переменную №10), значения зависящие от наложения объектов друг на друга в процессе перемещения

12

m_rhsPenetration

Равна либо нулю, либо импульсу проникновения

13

m_cfm

Переменная, получаемая из значения m_contactCFM класса btManifoldPoint

14

m_lowerLimit

Значение нижнего лимита

15

m_upperLimit

Значение верхнего лимита

16

Объединение специального какого-то назначения

17

m_overrideNumSolver Iterations

Завязана на значение класса btTypedConstraint

18

m_frictionIndex

Завязана на размер m_tmpSolverContactConstraintPool

19

m_solverBodyIdA

Переменные для обращения к m_tmpSolverBodyPool

20

m_solverBodyIdB

Переменные для обращения к m_tmpSolverBodyPool

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

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

Следующая функция integrateTransformsInternal, в задачи которой входит выполнить итоговые перемещения. Впрочем, учитывается, что могут быть взаимные проникновения объектов, в результате которых появляются реакции. Значит некоторые объекты надо вернуть "обратно".

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

Классы функции и переменные, используемые integrateTransformsInternal
Классы функции и переменные, используемые integrateTransformsInternal

На этом оканчиваются СубШаги. Библиотека закончила производить весь набор действий с объектами и готова все повторить. По идее, значит, что все вышеперечисленные классы -- это минимальный набор для работы библиотеки.

Заключение

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

Комментарии (6)


  1. semenyakinVS
    09.01.2023 00:02
    +2

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


  1. bbs12
    09.01.2023 09:16

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


    1. starfair
      09.01.2023 13:38
      +1

      У вас ничего не выйдет, так как в окрестности черной дыры используется уже другая физика в расчётах, а именно численное решение формул ОТО (довольные сложные тензорные уравнения энергии - импульса в Римановской геометрии). А в данном движке обычные решатели Ньютоновской динамики.


  1. n0lavar
    09.01.2023 10:47

    Я правильно понимаю, что движок будет нормально работать только при "axis aligned" пространстве, а если у меня геоид, то я иду лесом? Что посоветуете использовать в таком случае?


    1. alex_forever_82
      11.01.2023 14:25

      AABB (Axis Align Bounding Box) используются только для поиска потенциальных коллизий. Сам мир может быть и более сложным, не обязательно ориентированным строго вдоль осей координат.


  1. tm1218
    09.01.2023 14:29

    Мир обновляется через команду stepSimulation.

    Можно было бы более конкретно описать, что это не просто какая-то абстрактная "команда", а метод класса btDiscreteDynamicsWorld