Box3D ускорила обработку сложных столкновений с SIMD

В Box3D оптимизировали обнаружение столкновений сложных выпуклых тел с помощью широкого SIMD: одна грань первого тела проверяется сразу против четырёх рёбер второго. Подход отличается от «узкого» SIMD, где координаты одного трёхмерного вектора помещают в SIMD-регистр; здесь параллельно обрабатывают несколько независимых рабочих единиц.

Поводом стал тест Convex Pile, перенесённый из PEEL: в нём сбрасывают 5120 выпуклых оболочек по 32 точки. Box3D использует проверку разделяющих осей (SAT), чтобы определить признаки тел, направление контакта, точки контакта и требуемое раздвижение пересекающихся форм. Для двух сложных оболочек SAT должен сравнивать грани с вершинами и рёбра с рёбрами; число пар рёбер растёт квадратично и может стать главным расходом времени симуляции.

Для оболочки с 89 рёбрами требуется 7921 вызов проверки векторного произведения. Поэтому данные подготовили в формате «структура массивов», а рёбра второго тела сгруппировали по четыре для SIMD-проверок. На AMD Ryzen 9 7950X с частотой 4,42 ГГц автор сравнил выполнение от одного до восьми потоков; приведены лучшие результаты из четырёх запусков 500-шаговой симуляции. SSE2 дала более чем двукратное ускорение относительно скалярного варианта по времени всей симуляции, а не только проверки пар рёбер.

В Box3D реализованы только инструкции SSE2. Включение архитектуры AVX2 без отдельной реализации также улучшило результат; в будущем автор допускает реализацию AVX2 с одновременной проверкой восьми рёбер. Оптимизация почти не влияет на столкновения «коробка с коробкой», но полезна для сложных оболочек, например в сценах с разрушением. Рост сложности ограничен жёстким лимитом Box3D в 128 рёбер на оболочку; преобразование сложной оболочки в сетку может ослабить квадратичный рост, но делает форму менее подходящей для динамического тела.

Ключевые факты

• Box3D применяет широкий SIMD к проверкам пар рёбер: одно ребро сравнивается сразу с четырьмя рёбрами другой оболочки.
• В тесте Convex Pile участвуют 5120 выпуклых оболочек по 32 точки; у рассматриваемой оболочки 89 рёбер и 7921 комбинация рёбер.
• Вариант SSE2 оказался более чем вдвое быстрее скалярного режима по времени полной 500-шаговой симуляции.
• Эффект почти отсутствует для столкновений коробок, но заметен на сложных оболочках; Box3D ограничивает их 128 рёбрами.

Почему это важно

У SAT число проверок пар рёбер растёт квадратично. На сложных выпуклых оболочках эта часть способна доминировать в симуляции, а SIMD сокращает её стоимость без изменения метода столкновений.

Кому это важно

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

Как это применить

В Box3D доступна реализация на SSE2. Оптимизация требует хранить данные в формате «структура массивов» и группировать рёбра для параллельных проверок; включение архитектуры AVX2 в измерении также улучшило результат.

Можно ли доверять

Это технический отчёт разработчика Box3D с описанием алгоритма и условий теста: AMD Ryzen 9 7950X, 4,42 ГГц, от одного до восьми потоков, лучшие из четырёх запусков 500-шаговой симуляции. В тексте не приведены численные значения таблицы, кроме вывода о более чем двукратном преимуществе SSE2.

Риски и подводные камни

Выигрыш относится к сложным оболочкам с большим числом рёбер и не переносится на все типы столкновений. SAT сохраняет квадратичный рост числа проверок, а SIMD требует дополнительной подготовки данных; Box3D ограничивает оболочку 128 рёбрами.

«SSE2 более чем вдвое быстрее скалярного варианта.»

— автор технического разбора Box3D