Интегрирование Верле

Метод численного интегрирования Верле (Verlet integration), или метод Штёрмера — численный метод, используемый для интегрирования уравнений движения материальной точки ($\ddot{\vec{x}} = \vec{a}(\vec{x},t)$). Часто используется для вычисления траекторий частиц в моделях молекулярной динамики и в компьютерных играх. Метод Верле более устойчив, чем более простой метод Эйлера, и имеет при этом другие качества, необходимые для моделирования физических процессов в реальном времени.

Назван в честь французского физика Лу Верле (Loup Verlet), который своей статьёй 1967 года популяризовал метод. Часто некорректно именуется «алгоритмом Верлета». Популярность у разработчиков компьютерных игр метод получил в 2000 году с выходом игры Hitman: Codename 47.

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

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

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

Ограничения

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

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

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

Ссылки

• Лекция «Реализация физики на основе интегрирования Верлета» на сайте GameDev.ru
• Перевод (не очень удачный) статьи «Advanced Character Physics»