Sequential Impulses With Warmstarting (Последовательные импульсы)
Sequential Impulses With Warmstarting - метод решения системы ограничений в динамике твердых тел, предложенный Erin'ом Catto и подробно описанный в его блоге
Основной идеей SI является итеративный подход к разрешению ограничений. То есть вместо того, чтобы решать Mixed LCP "классическим" подходом, за O(n3), SI позволяет нам решать эту систему за линейное время O(n). Разумеется, решение получается лишь приближенное.
Как неоднократно заявлял сам Эрин, его подход математически эквивалентен Projected Gauss-Seidel солверу. Фактически, методы различаются лишь подходом к их программированию - если PGS работает напрямую с матрицей Якоби, каждая строка которой ограничивает одну степень свободы, то SI оперирует со значительно более интуитивно понятными терминами, такими как "изменение импульса", "плечо силы", "относительная скорость" и другие.
Под Warmstarting'ом же понимается инициализация всех импульсов системы каждый кадр их значениями с предыдущего кадра. Опять же, это классическйи подход, основанный на том, что обычно напряжения в точках взаимодействия тел от кадра к кадру меняются незначительно, и он применяется и в Projected Gauss-Seidel солвере, и в большинстве случаев значительно повышает сходимость системы.
Также Erin Catto разработал на основе метода псевдо скоростей (Pseudo Velocities), метода коррекции положений (position correction), очень важное усовершенствование к своему солверу, называемое Split Impulses (можно перевести как "раздельные импульсы"). Основной идеей является раздельное разрешение столкновений и проникновений. То есть отдельно решаются системы уравнений для импульсов, и для так называемых псевдоимпульсов, ответственных за "расталкивание" проникших друг в друга тел. Это позволяет избавиться от артефактов сильного отскока тел при большом взаимном проникновении, а так же от проблемы неправильного распределения скоростей после удара (проблема существует в классическом методе коррекции положений Баумгарте - Baumgarte position correction)
Ссылки:
Про PGS можно почитать, например, в статье XperienS'а
Про SI лучше всего прочитать в блоге Эрина Катто
Что такое Sequential Impulses With Warmstarting (Последовательные импульсы)?
5 февраля 2008 (Обновление: 11 июня 2009)
Комментарии [8]