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

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

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

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

examples/HelloWorld/HelloWorld.cpp

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

btContactSolverInfo m_solverInfo;

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

btAlignedObjectArray<btSolverBody> m_tmpSolverBodyPool

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

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

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

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

где

typedef btAlignedObjectArray<btSolverConstraint> btConstraintArray;

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

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

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

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

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

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

Заключение

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