Моделирование динамики твердых тел на GPU Выполнили: Гриднев Максим Машинский Леонид Присивко Вячеслав гр. 3057/2

Постановка задачи Моделирование движения твердых тел (ТТ) в виртуальном пространстве 2 Требования: Ограничения движения ТТ: Столкновения Упругие и жесткие связи между телами Интерактивность: Моделирование в реальном времени (~10% от общего времени просчета) Детализированные статические объекты (ландшафт, окружение)

Обзор существующих решений на CPU Моделирование движения Обнаружение пересечений Широкая фаза Регулярная и древовидная сетка AABB, OBB, SAT Узкая фаза GJK(EPA) Lin-Canny V-Clip Реакция на пересечения 3

Модификация решений для GPU Алгоритмы должны обрабатывать данные для каждого твердого тела независимо и параллельно Модификация : o Разрешить зависимости между данными твердых тел, используемые алгоритмами o Перенести на GPU алгоритмы для одиночного тела или пары тел Динамика роста производительности CPU и GPU 4 Использование GPU может дать значительный прирост производительности

Моделирование движения Вход: N тел с кинематическими параметрами Алгоритм: Для каждого твердого тела 1.Расчет приращений кинематических параметров (функции состояния). 2.Получение новых значений параметров – решение задачи Коши метод Эйлера метод Рунге-Кутта 3.Применение полученных позиций и скоростей к телам Выход: N тел с новыми значениями параметров Для каждого тела данные независимы и вычисления выполняются параллельно 5

Обнаружение пересечений 6 Широкая фаза Узкая фаза Вход: N тел с заданными позициями и геометрией Алгоритм: 1.Для каждого из N тел на GPU построить список клеток сетки, в которых тело находится 2.Создание потенциально пересекающихся пар объектов на основе дискретного разбиения пространства на ячейки 3.Для каждой полученной пары на GPU выполнить грубую проверку a)AABB с AABB b)OBB с OBB Выход: Список пар тел, подозрительных на пересечение Вход: Список пар тел, подозрительных на пересечение Алгоритм: Для каждой пары на GPU выполнить точную проверку на пересечения используя алгоритм GJK Выход: Список пар пересекающихся сел, информация о пересечениях Рис.1. (a) Выровненный по осям ограничивающий параллепипед (AABB) (b) Ориентированный ограничивающий параллепипед (OBB)

Реакция на пересечения 7 Рис. 3. Пример реберной раскраски графа зависимостей Алгоритм параллельной обработки контактов: 1.Построение графа зависимостей 2.Построение реберной раскраски графа зависимостей 3.Формирование независимых от данных множеств пар - блоки 4.В каждом блоке пары обрабатываются на GPU параллельно 5.Расчет импульсов, применяемых к телам 1 блок 2 блок 3 блок Информация о пересечении - точки контактов 1.Контакт покоя Метод последовательных импульсов [Catto, 2006] 2.Ударный контакт Использование гипотезы Ньютона [Mitrich, 1994] Последовательная обработка контактов для каждого тела Рис.1. Контакт покояРис.2. Ударный контакт

Анализ производительности Увеличение производительности метода на GPU в 6-8 раз относительно реализации на CPU Cложность метода относительно количества обрабатываемых объектов – O(N 2 ) 8

Выводы Моделирование динамики твердых тел на GPU дает следующие преимущества: Разгрузка CPU для выполнения альтернативных задач Возможность увеличения количества обрабатываемых тел в 10 раз без потери производительности 9

Спасибо! 10

Литература 1.An Introduction to Physically Based Modeling: Rigid Body Simulation IUnconstrained Rigid Body Dynamics, David Baraff, An Introduction to Physically Based Modeling: Rigid Body Simulation IINonpenetration Constraints, David Baraff, GPU Gems 3: Part V - Physics Simulation, Real-Time Collision Detection, Christer Ericson, Physics on NVIDIA GPUs, Mark Harris, OpenCL Game Physics : Bullet: A Case Study in Optimizing Physics Middleware for the GPU, Erwin Coumans