6. Параллелизация PBD

Интро

PBD как метод получился очень крутой. Но у него есть серьезный недостаток – последовательное разрешение ограничений.

Во всех вариациях PBD, которые мы рассматривали, мы последовательно обновляли позиции частиц. По одной за раз. Тк мы использовали Gauss-Seidel.

Для того чтобы ускорить процесс, можно использовать параллельные вычисления.

https://sci-hub.se/https://doi.org/10.1111/cgf.12570 раскраска

Супер простая идея – два алгоритма – вставка фантомных верщин + ограничения к ним и раскраска графа Вставка фантомных вершин – заменяем вершину с которой больше всего ограничений на много фантомных вершин + одно ограничение.

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

Нужно правильно перенумеровать вершины

https://www.q-minh.com/publication/pbnh-xpbd/pbnh-xpbd.pdf кластеризация