Войти
abandonedСтатьи

Хитроумная процедурная анимация

Автор:

Всегда было обидно, что в игрульках нельзя подскользнуться или споткнуться, растянувшись, врезаться головой в косяк и т.д. Отсутствие такой возможности меня огорчает. Это сложно реализовать эвристиками, нужна 100% честная процедурная анимация на физическом движке, с помощью прикладывания моментов к регдоллу, + так будет Ъ. Один из возможных способов нахождения этих моментов я придумал этим летом, во время прогулки по лесу. Естественно, вдали от интернета и книг, поэтому уровень велосипедности ниже может зашкаливать. Получилось что-то слабо пригодное для жизни и геймдева, пишу, чтобы торжественно выкинуть эту идею из головы.
Сформулируем задачу. Допустим, мы хотим сделать анимацию на ключевых кадрах. Из теорем существования и единственности или иных соображений можно найти, что состояние классической системы полностью определяется заданием начальных координат и скоростей (К.О. в общем, но обращаю внимание). Поэтому каждый ключевой кадр должен задавать координаты и/или скорости всех частей регдолла. А задачей программы будет правильно перевести систему из одного состояния в другое.
По привычке я сформулировал задачу с точки зрения гамильтоновой механики. Это удобно тем, что координаты и импульсы являются независимыми функциями => легко задать граничные условия на скорость и координату. (Ниже будет рассказано, как я за это поплатился, и как пришлось выкручиваться).
Итак, H(q,p) - гамильтониан свободной системы, где q и p - векторы обобщённых координат и импульсов для всех степеней свободы системы.
Добавим теперь управляющие моменты u. Запишем сначала канонические уравнения для i-той степени свободы:
(1)[cht]
\frac{dp_i}{dt} = - \frac{\partial H}{\partial q_i}
[/cht]
(2)[cht]
\frac{dq_i}{dt} = \frac{\partial H}{\partial p_i}
[/cht]
И просто приплюсуем к верхнему u. А теперь - внимание, дилемма! От чего должны зависеть u? Вариантов два: либо от q и p, либо от t, то есть от времени. Для упрощения своей задачи выбрал вариант 2. Фактически он означает, что система будет управляться вне зависимости от внешних воздействий, так сказать "вслепую". Но это лечится.
Итак, получаем нечто вроде:
(1')[cht]
\frac{dp_i}{dt} = - \frac{\partial H}{\partial q_i} + u_i(t) =  -\frac{\partial H_c}{\partial q_i}
[/cht]
(2')[cht]
\frac{dq_i}{dt} = \frac{\partial H}{\partial p_i} = \frac{\partial H_c}{\partial p_i}
[/cht]
[cht]H_c[/cht] - "некая новая функция, но не совсем гамильтониан". Чтобы найти её явный вид, нужно решить тривиальную систему диффуров в частных производных {1', 2'}. Элементарно получается:
(3) [cht] H_c = H - u_i q_i + C [/cht]
(Вот если бы я взял u~p,q ничерта бы здесь не вышло.)  Константа С обозначает просто произвол при задании энергии, поэтому я её смело не пишу в дальнейшем. Находим функцию Лагража системы. Это делается по известному уравнению (лень набирать, взял из вики):
(4)Изображение
Теперь можно грабить корованы поставить дополнительное интегральное условие Ф на момент. Получится что-то вроде:
(5)[cht]
S = \int^{t_1+\tau}_{t_1}  {dt \left( p_i \frac {d q_i} {dt} - H_c(\vec{u}, \vec{q}, \vec{p}) + \lambda \Phi(\vec{u}, \vec{q}, \vec{p}) \right)}
[/cht]
lambda - множитель Лагранжа из одноимённого метода. t_1 - время, соответствующее начальному состоянию, t_1+tau - конечному. Дальше я легкомысленно решил, что нужно попробовать найти экстремаль аналитически, а потом уже думать, как этому делу научить компьютер. И тут же наткнулся на парадокс: очевидно, что проинтегрировав соответствующие уравнения Эйлера для одной степени свободы, мы должны получить четыре константы, чтобы выразить через них четыре граничных условия: скорости и координаты в начале и в конце. Но как нетрудно убедиться, их получается всего 3, т.е. управление одновременно и скоростями и координатами невозможно!??! Километров восемь (час) я прошагал ошарашенный, пытаясь найти ошибку в расчётах и рассуждая, правомерно ли было брать u зависящим только от t. Внимательный читатель наверно догадался, что дело в том, что уравнения Эйлера накладывают условие гладкости на эктремаль, а u(t) самом деле не обязана быть гладкой. Но до меня долго это не доходило. Когда же дошло, оказалось, что придётся разбивать интервал времени на два,.. искать условия сшивания,.. составлять систему нелинейных уравнений,.. полный отстой, короче. Решил, что аналитически это решать без толку.
Дальше я лихорадочно стал вспоминать все численные методы решения уравнений с двухточечным краевым условием, которым нас учили в универе, мол они мне что-нибудь подскажут. Их, собственно, два: метод прогонки и стрельбы. Первый я в своё время понял плохо, но запомнил, что он годен только для очень ограниченного класса задач, и отнюдь не для этого. Второй убог, ибо всяко придётся 100500 раз интегрировать уравнения Эйлера - степеней свободы-то много.

Внимательный читатель уже, наверно, догадался, что уравнения Эйлера тут вовсе не нужны, нужно напрямую минимизировать функционал. Но эта простая мысль меня долго обходила стороной. Всё оказалось просто - нужно временно забыть про u и варьировать q и p. Придумал такой способ: разбиваем интервал времени на N кусков, вместо интеграла (5) пишем сумму в приближении через трапеции и конечные разности. Для простоты пусть у нас одна степень свободы:
(6)[cht]
S = \sum^{N}_{j=1} 
{
    \left ( \frac{q_{j+1}+q_{j-1}-2 q_{j}}{2 dt} p_j - H_c(q_{j-1},q_{j},q_{j+1},p_{j-1},p_{j},p_{j+1},u_{j})+{\lambda}_j \Phi(q_j,p_j,u_j) \right) \Delta t
}
[/cht]
Теперь найдём [cht]\frac{d S}{d q_j}[/cht] и [cht]\frac{d S}{d p_j}[/cht] (7) . u(t) выразим из уравнения (1'), преобразованного в конечные разности:
(8) [cht]u_j =  \frac{p_{j+1}+p_{j-1}-2 p_{j}}{2 dt} + \frac{dH}{dq}[/cht]
Уравнение (8) я считаю очень удачным. Пользуясь им одним уже можно, в принципе, по готовой анимации найти управляющие моменты. (но не на практике)
Дальше действуем таким образом: выбираем некое начальное приближение, удовлетворяющее граничным условиям, и по (7) находим величины, на которые нужно сдвинуть ординаты точек q_j и p_j. Сдвигаем на -(значение по формуле (7))*SomeLittleConstant. Кажется, это называется методом градиентного спуска. Потом находим u_j по (8).
Минус этого метода в том, что он существенно локален. С увеличением N влияние перестановки одной точки на значение S уменьшается => сходимость стремительно ухудшается. Это можно решить небольшим хаком - сначала взять малое N, дождаться схождения, затем каждый интервал разбить ещё раз и запустить процесс заново; повторять это до готовности. Этот метод для системы с одной степенью свободы давал неплохие результаты (писал в Maple). Но самое весёлое, что полного схождения ждать вовсе необязательно. Схождение влияет только на оптимальность управления, т.е. насколько точно выполняется условие минимизации того дополнительного интегрального условия Ф, но на конечное положение не влияет. Т.е. выбрав произвольным образом начальное условие и сделав 0 итераций, мы всё равно получим управление, которое приводит систему в нужное положение, правда дурацким дёрганым способом. По-моему хорошее свойство для геймдева, где скорость на первом месте.

Теперь по поводу вопроса, который терзал читателя на протяжении всего прочтения. Откуда брать гамильтониан свободной системы? Писать ручками или сочинять мегаанализаторгеометриисоставительгамильтонианов ? (ахтунг, дальше идут чистой воды гипотезы, мной не проверенные!) Скорее 2, чем 1, но не всё так плохо. Сделаем такой хак: раз мы минимизируем функционал мелкими итерациями, то можно сгрубить (7). Например, оставить в уравнениях движения для каждого тела координаты и импульсы только тех тел, с которыми оно непосредственно взаимодействует; исходя из этого составить канонические уравнения; решить систему уравнений в частных производных (как в начале, но уравнений побольше). Всё это делается в каком-нибудь sympy.
Теперь нужно получившиеся уравнения (7) и (8) засунуть в С++, желательно без кодогенерации. С уравнением (7), по крайней мере, возможен такой хак: очевидно, экстремаль проходит вблизи минимумов. Можно представить (7) в виде полинома P, удовлетворяющего таким свойствам: все его производные от нулевой до N-ой в точках минимума функции равны производным функции. (Т.е. почти ряд Тейлора, но для нескольких точек.) Коэффициенты P находятся из СЛАУ.

Были ещё весьма подробные решения, как осуществить блендинг анимаций и равновесие. Всем этим я собирался заняться, пока не наткнулся на это, сделанное с помощью этого - их подход не осуществляет оптимального управления, но в остальном лучше и проще. So it goes. Пусть мои труды покоятся здесь с миром.

#физика, #процедурная анимация

5 февраля 2011 (Обновление: 9 фев. 2011)

Комментарии [2]