6. Параллелизация PBD
Интро
PBD получился очень крутым. Но у него есть серьезный недостаток – последовательное разрешение ограничений.
Во всех вариациях PBD, которые мы рассматривали, мы последовательно обновляли позиции частиц. По одной за раз. Тк мы использовали Projected Gauss-Seidel, который подразумевает именно последовательное обновление позиций.
Для того чтобы ускорить процесс, можно использовать параллельные вычисления.
Одно из самых простых решений – использовать вместо Projected Gauss-Seidel метод Jacobi, который принципиально легко параллелизуется. На самом деле это не будет чистый Jacobi, тк этим методом решают системы линейных ограничений. Когда решают нелинейные системы линеаризуя их говорят, о том что решают с помощью Jacobi style метода.
Основная проблема – это зависимость между ограничениями. Если мы попытаемся обновить позиции частиц параллельно, то можем нарушить ограничения.
Источники
- Видос от создателя XPBD Mathias Muller Simulation on the GPU
Супер простая идея – два алгоритма – вставка фантомных верщин + ограничения к ним и раскраска графа Вставка фантомных вершин – заменяем вершину с которой больше всего ограничений на много фантомных вершин + одно ограничение.
- Оригинальная статья про добавление фантомных вершин Scalable Partitioning for Parallel Position Based Dynamics
Кластеризуем и объединяем вершины и раскрашиваем супер граф
- Оригинальная статья про кластеризацию Parallel Block Neo-Hookean XPBD using Graph Clustering
Раскраска – жадная раскраска графа. проходим по вершинам и раскрашиваем их в цвета, которые еще не встречались у соседей.
Нужно правильно перенумеровать вершины