Интеграция Верлета

Интеграция (или алгоритм) Верлета — численный метод, используемый для интегрирования уравнений движения. Часто используется для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верлета более стабилен, чем более простой метод Эйлера и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени.

Основной алгоритм

Алгоритм Верлета [1] используется для вычисления следующего местоположения точки по текущему и прошлому, без использования скорости. Формула получается следующим образом. Записывается разложение в ряд Тейлора вектора $\vec{x}(t)$ местоположения точки в моменты времени t + Δt и t − Δt.

$\vec{x}(t + \Delta t) = \vec{x}(t) + \vec{v}(t)\Delta t + \frac{\vec{a}(t) \Delta t^2}{2} + \frac{\vec{b}(t) \Delta t^3}{6} + O(\Delta t^4)\,$

$\vec{x}(t - \Delta t) = \vec{x}(t) - \vec{v}(t)\Delta t + \frac{\vec{a}(t) \Delta t^2}{2} - \frac{\vec{b}(t) \Delta t^3}{6} + O(\Delta t^4).\,$

Где
$\vec{x}$ — позиция точки,
$\vec{v}$ — скорость,
$\vec{a}$ — ускорение,
$\vec{b}$ — рывок (производная ускорения по времени).
Суммируя эти 2 уравнения и выражая $\vec{x}(t + \Delta t)$ получим:

$\vec{x}(t + \Delta t) = 2\vec{x}(t) - \vec{x}(t - \Delta t) + \vec{a}(t) \Delta t^2 + O(\Delta t^4).\,$

Таким образом значение точки может быть вычислено без знания скорости.

Ограничения

Основная особенность алгоритма состоит в возможности накладывать на систему точек различные ограничения. Например, можно связать некоторые из них твёрдыми стержнями заданной длины. При этом алгоритм работает следующим образом:

• Вычисляются новые положения тел по формуле выше.
• Для каждой связи удовлетворяется ограничение, которое она накладывает, то есть расстояние между точками приводится таким, каким оно должно быть.
• Шаг 2 повторяется несколько раз, тем самым все условия удовлетворяются(разрешается система условий).

Данный метод, несмотря на многократное повторение шага 2 очень эффективен.

Ссылки

• Лекция "Реализация физики на основе интегрирования Верлета"
• Перевод статьи "Advanced Character Physics"