Плюсы и минусы разных интеграторов [закрыто]

При создании таких вещей, как физика в играх, вам нужен интегратор. Я видел, что интеграция Verlet упоминала несколько мест как отличную альтернативу интеграции Эйлера. Например, в знаменитом документе Томаса Якобсена . Однако в этой статье Гленн Фидлер пишет:

Вместо того, чтобы познакомить вас с огромным количеством различных существующих интеграторов, я собираюсь перейти к поиску и сразу перейти к лучшему. Этот интегратор называется интегратором Рунге Кутты 4-го порядка, также известным как RK4.

Так что, видимо, нет серебряной пули. В чем плюсы и минусы разных интеграторов? Что касается простоты, скорости, точности, стабильности и т. Д. Какие интеграторы наиболее подходят для каких типов игр? Когда бы вы использовали Verlet, RK4 или другие? Стоит ли когда-нибудь использовать Эйлера?

Плюсы и минусы обоих методов:

RK4 Плюсы:

1. точность (благодаря своему лучшему ряду аппроксимации он дает точность 4-го порядка)
2. искусственное / по сути индуцированное демпфирование (немного похоже на неявные методы это делает) добавляет стабильности (тогда как простой шаг Эйлера не делает - он делает противоположное на самом деле, вводя энергию-призрак, которая накапливается и может погрузить систему в хаос)

RK4 Минусы:

1. затраты на вычисления: хотя RK4 и не так требователен по сравнению с неявными или гибридными методами IMEX, RK4 в 4 раза дороже, чем явный Euler, поскольку требует гораздо большего количества оценок функций. Это видно при стремлении к переднему краю оптимизации.
2. все еще нестабильно: в зависимости от типов задействованных сил, RK4 может быть таким же нестабильным, как и Эйлер. В среднем, RK4 немного более стабилен и имеет тенденцию извлекать выгоду из своих способностей демпфирования.
3. Не симплектическое: численное демпфирование сопряжено с издержками - вы не можете моделировать системы, где энергия / объем / и т. Д. потеря не должна применять видимый эффект с течением времени (например, молекулярная динамика, производные силы потенциального поля, вариационные проблемы)

Verlet Pros:

1. один или два раза сложность шага Эйлера (в зависимости от вашего вкуса Верле: положение или скорость).
2. симплектический: сохраняет внутреннюю энергию
3. Точность второго порядка: многие игры не требуют высокой точности результатов с плавающей запятой, а второй порядок более чем радует глаз в игровом сценарии (плюс: он использовался в симуляции неигрового сценария, когда он был «обнаружен», поэтому это не так уж плохо)

Verlet Минусы:

1. стабильный, но все же: вероятно, лучший явный метод с точки зрения стабильности. Он имеет тенденцию выигрывать, когда в систему добавляются жесткие ограничения, что позволяет уменьшить головную боль при реализации прогнозируемых ограничений в динамических движках, основанных на положении. Он уходит в бесконечность, если система возмущена большими внешними силами, и демпфирование / трение не добавляются. Несмотря на это, существуют определенные численно установленные пределы того, насколько большими могут быть внутренние (пружинные) силы, но они в среднем выше, чем то, что может сделать RK4.
2. низкая точность: бесполезно, если вам нужны высокие оценки точности
3. требует в среднем меньших временных шагов, чем RK4 для некоторых симуляций (RK4 выигрывает как от своей точности, так и от внутреннего демпфирования)

Использование одного над другим зависит от сценария. Если жесткость и большие внешние силы и виртуальные энергии являются проблемой, то рассмотрите другие методы, имеющие «неявное» слово в их описании / названии.

Обратите внимание, что некоторые авторы / книги используют термин «полуявный Эйлер» для фактического явного интегратора Эйлера, называемого симплектическим методом Эйлера (или Эйлера Кромера), из которого фактически получен Верлет. Некоторые люди также называют Verlet «методом перепрыгивания». Скорость Verlet и метод средней точки довольно похожи, так как оценка на шаге по времениt + 0.5*dtтребуется для шага, подобного предиктору-корректору. Методы IMEX (неявный-явный) также используются для именования двух похожих, но не идентичных подходов: разделить вычисления на жесткие и не жесткие части и использовать для них разные интеграторы (явный для не жестких, неявный для жестких) ИЛИ решить для скорость с неявным шагом обновления и явным образом обновляет позицию (это гибридный полуявный метод, относящийся к классу методов IMEX, потому что жесткие части больше всего влияют на вычисление ускорения). Неявные методы более громоздки и требуют решения системы одновременных нелинейных уравнений для всей конфигурации. Неявные методы используются для деформируемых тел и обычно не используются для отделенных твердых тел.

Как указано в одном из комментариев, если вы можете, не используйте Euler. Используйте либо метод средней точки, полу-неявный Эйлер или, за тот же счет, позицию-Verlet. Все они имеют чуть более высокую точность и заметно большую стабильность, чем явный интегратор Эйлера.

Рекомендуемое чтение мини-сравнения:

http://wiki.vdrift.net/Numerical_Integration

Реализации Эйлера имеют тенденцию быть очень быстрыми, но гораздо менее стабильными, чем альтернативы. Рунге Кутта медленнее, чем Эйлер, но гораздо точнее и стабильнее.

Я не очень хорошо разбираюсь в интеграции Verlet, поэтому не знаю, как она складывается с Эйлером и Рунге Куттой.

Если вам нужно, чтобы ваши симуляции были более точными или даже числовыми, Рунге Кутта - лучший из двух.

Если вам нужна быстрая и недорогая физика для простой игры, Euler - лучший выбор.

Прежде всего, я думаю, что вы должны использовать Euler, пока не почувствуете прямую необходимость использовать более продвинутую схему интеграции. Это быстро и легко реализовать.

Если вы испытываете проблемы со стабильностью, такие как системы пружин, которые никогда не успокаиваются, или если ваша симуляция требует высокого уровня точности, то начните экспериментировать с другими.

Один из тех, о которых я не упомянул выше, - это метод средней точки, который очень прост в реализации и требует только одного дополнительного шага интеграции.