Войти
Физика для игрСтатьи

Физика на пальцах: импульсный движок (2 стр)

Автор:

Любопытно отметить, что на практике в принципе всё равно в каком порядке вызывать эти два метода интегрирования позиции и скорости - из-за малости изменяемых величин в первом приближении результаты будут одинаковы. В дальнейшем метод RigidBody::IntegrateVelocity() можно будет дополнить до случая прецессии, добавив уравения Эйлера, но мы их опустим, потому что симуляция и без них выглядит достаточно естественно. Они несложны, и каждый желающий сам сможет нагуглить для себя уравнения Эйлера регулярной прецессии.

Важно отметить, что при при больших значениях v или dt тело может переместиться за один квант времени так далеко, что проникнет внутрь другого тела. Существуют различные техники, называемые общим словом Continuous Collision Detection, которые препятствуют этому явлению, но и без на самом деле можно добиться прекрасного качества симуляции. Надо просто уметь аккуратно разрешать проникновения. О том, как это сделать, расскажу позже.

ЗЫ: Многие начинающие физ.программисты ошибочно полагают, что чем точнее интегратор они используют, тем лучше будет выглядеть конечный результат. Спешу разочаровать - наивно реализовывать интегратор Рунге-Кутта для интегрирования позиции и при этом использовать итеративные солверы, дискретный collision detection и прочие допущения, которые вносят несравнимо бОльшую ошибку, чем тот же интегратор Эйлера или Ньютона.

В каком порядке добавлять функциональность в двиг и как его отлаживать

Спешу сразу обрадовать - сразу что-то заработает едва ли. Разработку двига лучше всего вести по стадиям, и после добавления очередной стадии, проверять, как всё работает вместе. Я постараюсь описать основные стадии и способы их отладки:

1) Реализовать самые основные трансформации - перемещение, вращение. Чтобы удостовериться, что всё работает нормально, внимательно изучите, что вращение работает именно так, как требуется. Проблемы обычно бывают именно здесь - правосторонние/левосторонние системы координат, перевод из кватернионов в матрицы и так далее. Чтобы "прочувствовать" всю эту магию, я бы советовал вручную посоставлять матрицы поворота на простые углы(на pi, pi/2 вокруг базисных осей), поперемножать эти матрицы и так далее. Без этого понимания потом будет очень трудно писать солвер.

2) Научиться отображать отладочную геометрию. Всяческие векторы скорости, точки и нормали контакта, положение и ориентация тел - все эти механизмы ещё не раз нам помогут.

3) Добавить collision detection для случаев сфера vs сферы и бокс vs бокс. Любой алгоритм обнаружения столкновений нужно очень тщательно проверить. Создаём, к примеру, две статические сферы, вводим нехитрые кнопки для перемещения одной из них и отрисовываем контакты, вместе с нормалями. Потом переходим к боксам, проверяем правильность нахождения контактов ещё тщательнее, просто-таки выжимая все соки из отладочной отрисовки.

4) Проверяем, что тела нормально летят по прямой и вращаются вокруг собственной оси. Первый закон ньютона, грубо говоря. Проверяем правильность работы интегратора.

5) Удостоверяемся, что к телам конкретно применяется сила и импульс. Прикладываем одну или несколько сил или импульсов к разным точкам тел и смотрим на результат. К примеру, если приложить силу к центру масс, тело должно начать двигаться поступательно. Если приложить две противоположенных силы к углам бокса, он должен начать вращаться.

6) Берём две сферы, пускаем их друг навстречу другу, без гравитации. Массы задаём произвольные, а инвертированные моменты инерции - нулевые. Проверяем, что если поставить отскок, равный нулю, то ровно за одно решение единственного контакта их скорости становятся в точности равны. Если отскок единичный, то они при центральном ударе будто бы обмениваются скоростями. Далее проверяем нецентральные удары. Чтобы проверить, что всё работает верно, после решения каждого контакта считаем величину, называемую velocityProjection в статье про солверы и удостоверяемся, что она равна тому, чему мы её хотели приравнять(ноль в случае неупругого контакта, либо изначальная скорость со знаком минус в случае упругого соударения).

7) Проверяем то же самое для боксов. Должно получиться что-то вроде физики в стареньких платформерах - ящики должны нормально сталкиваться, но вращение у них закреплено, поэтому ориентированны они всегда одинаково. Сталкиваем их всевозможными способами, постоянно проверяя, что всё ок. На этом этапе совершенно нормально, если под действием гравитации тело будет постепенно "утопать" в земле. Эту проблему должен решить warmstarting, которого у нас пока нет.

8) Наверное, самый сложный этап, который обычно вызывает больше всего непонимания. Разрешение вращения. Если поставить invInertia в ненулевое значение, тела должны начать вращаться при определённых соударениях. Единственный способ отлаживать этот участок, который я нашёл - сталкивать сначала два невращающихся и проверять, что после соударения они получают нужное вращение(чтобы удостовериться, что механизм применения момент импульса работает верно). А потом наоборот - сталкивать два вращающихся, но неподвижных тела, чтобы удостовериться, что момент импульса даёт верный вклад в импульс, которым обмениваются тела. Больше всего во время всех этих экспериментов, наверное, поможет только физическая интуиция - пытаться представить, как должны себя повести тела при разных типах столкновения.

9) К этому моменту тела корректно сталкиваются, но постепенно проникают друг в друга при продолжительных взаимодействиях. Проблема решается, вводя warmstarting. Проблемы, которые здесь возникают, обычно связаны с тем, что неверно определяется "время жизни" каждого контакта. Отлаживаем это дело отдельно, например, отрисовывая разными цветами контакты, которые только что появились и те, что есть уже давно.

10) Добавляем трение. При отладке трения есть один нехитрый секрет - проще всего его отлаживать, установив коэффициент трения в бесконечность. То есть тела никогда не должны скользить друг по другу. Если это работает, проверяем, правильно ли работает коэффициент сухого трения.

11) Псевдоимпульсы. Я отлаживаю псевдоимпульсы примерно как обычные импульсы. То есть сначала ставлю тензор инерции в бесконечность, чтобы закрепить вращение и проверяю, расталкиваются ли тела на требуемое расстояние ровно за одну итерацию. Далее возвращаю вращение и ещё раз проверяю то же самое. То есть отлаживаю фактически лишь один кадр, а не поведение системы в течение продолжительного времени.

12) Дополнительные типы соединений, нестандартная функциональность. К этому моменту всё это уже не выглядит как магия и, думаю, читатель сам в состоянии будет придумать действенные методы отладки.

Майлстоуны


В этом разделе я постараюсь объяснить вопросы по деталям реализации, которые обычно возникают в процессе написания своей физики. Не спрашивайте только, почему я их так назвал. Захотелось.

Майлстоун первый - что такое тензор инерции. Как применять к телу силу и импульс?


Как же интуитивно понять и, наконец, использовать массу и момент инерции тела?
Предположим, что некоторой точке(point) тела(body) приложена сила(force). Часто требуется определить, какое же ускорение(линейное и угловое) при этом получает тело. С линейным ускорением всё просто - его можно найти по второму закону ньютона:
body.linearAcceleration += force * body.invMass;

то есть вектор ускорения тела изменяется на вектор силы, приложенной к нему, делённую на его массу - достаточно логичный и интуитивно понятный факт. К сожалению, с угловыми характеристиками всё чуть сложнее. Ключ к пониманию углового ускорения, на мой взгляд, лежит в проведении аналогий с линейными характеристиками.
Например, линейной силе можно поставить в соответствие момент силы - векторная величина, направление которой показывает, вдоль какой оси тело стремятся подкрутить, а модуль - насколько интенсивно. Подобно тому, как направление угловой скорости обозначает мгновенную ось вращения, а модуль - скорость этого вращения. Из школьного курса физики мы узнаём, что если сила force действует с плечом arm на тело, то оно испытывает момент силы torque:

Vector torque = (point - body.coordinates.pos) ^ force; //векторное произведение силы на плечо

А теперь вернёмся к нашему моменту инерции. Разложим момент torque в сумму трёх векторов, направленных вдоль главных осей инерции тела(вспомним xVector, yVector и zVector). Другими словами, найдём координаты вектора torque в координатах тела - кому как понятней. сделать это можно двумя математически эквивалентыми методами:
I:

Vector relativeTorque = body->coordinates->rotation.Transpose() * torque;

II:

Vector relativeTorque = Vector(body->coordinates->xVector * torque,
                        body->coordinates->yVector * torque,
                        body->coordinates->zVector * torque);

Далее, воспользовавшись определением главных моментов инерции, замечаем ещё одну аналогию с линейными характеристиками - вдоль главных направлений закон действия момента выглядит точь-в-точь как второй закон ньютона. Таким образом, угловое ускорение в координатах тела можно выразить так:

Vector relativeAngularAcceleration = Vector(relativeTorque.x * inertiaMoment.x, relativeTorque.y * inertiaMoment.y, relativeTorque.z * inertiaMoment.z);

ну а теперь дело за малым - перевести угловое ускорение из координат тела в мировые. Для наглядности снова сделаем это двумя способами:
I:

body.angularAcceleration += body.coordinates.orientation * relativeAngularAcceleration;

II:

body.angularAcceleration += body.coordinates.xVector * relativeAngularAcceleration.x + 
                          body.coordinates.yVector * relativeAngularAcceleration.y + 
                          body.coordinates.zVector * relativeAngularAcceleration.z;

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

При надобности оформим вышеизложенные бесценные методики в методы

void Body::ApplyForce(const Vector force, const Vector point); //применить силу к точке
void Body::ApplyForce(const Vector linearForce, const Vector torque); //применить силу и момент сил

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

Майлстоун первый с половиной - как считать тензор инерции и массу?

Ход конём - да хоть как. Дело в том, что если в работающем двиге взять и поменять все моменты, увеличив или уменьшив их случайно в два раза, то не подготовленный взгляд разницы особой и не заметит. Более того, многие разработчики часто искусственно увеличивают момент инерции почти на целый порядок, так как система при этом становится устойчивее. Таким образом, по крайней мере на время отладки двига, не будет особо большим допущением считать, что тензор инерции сложного тела - тензор инерции сферы или бокса порядка его размера. Хак, конечно, но сильных ошибок это не повлечёт. А когда всё остальное будет работать нормально, уверен, тензор инерции для произвольной геометрии читатель сможет уже посчитать сам. Напомню что объём сферы радиуса r считается по формуле 4/3 * pi * r * r * r, массу выражаем как плотность * объём, момент инерции считаем порядка 1/2 * масса * r * r. Ещё раз - если всё работает нормально, то точные значения этих коэффициентов не так уж важны.

Майлстоун второй - когда применять силу, когда ускорение, а когда импульс?

Часто бывает нужно воздействовать на тело, чтобы оно приняло некоторое конкретное ускорение, например, свободного падения. Так, приобретая ускорение acceleration, через промежуток времени dt его скорость изменится на acceleration * dt; Но, к примеру, во время столкновения двух стальных шариков, достаточно глупо пытаться найти силу(и ускорения), которые при этом возникают - потому что в контакте они находятся слишком короткий промежуток времени, ускорения огромны, а время их действия крайне мало. В этом случае гораздо легче оперировать терминами импульсов - шарики за время столкновения обмениваются совершенно конкретными(ни слишком малыми, ни слишком большими) импульсами, в результате чего напрямую меняется их скорость на величину velocity += impulse * invMass, с вращательными величинами оперируем аналогично первому майлстоуну. Общее правило - если воздействие продолжительное, то применяем к телу силу. Если нужно непосредственно придать ускорение, как в случае свободного падения - применяем ускорение. Если скорость меняется мгновенно(прыжок, столкновение, удар), то применяем импульс.

Майлстоун третий - степень свободы

Что же такое степень свободы? Для простоты количеством степеней свободы системы мы будем называть минимальное количество float-чисел для задания любого её допустимого положения. Так, к примеру, количество степеней свободы ящика, летающего в пространстве, равно шести, потому что его позицию можно задать положением его центра масс(три числа) + его ориентация(три угла эйлера). Скрепляя тела различным образом, мы уменьшаем общее количество степеней свободы. Каждая связь(иногда я буду называть её джойнтом - joint), ограничивает какое-то количество степеней свободы. Пара классических примеров:

Articulation joint:
Тип связи, когда две точки тел связываются. Например, два ящика сцеплены вершинами. Положение такой системы можно описать так: полное положение + ориентация первого ящика(6 чисел) и ориентация второго относительно него(ещё три угла эйлера). То есть articulation joint ограничивает три степени свободы.

Hinge Joint:
Джойнт по типу двери на петлях. Чтобы однозначно задать положение системы дверь+стена, мы можем сказать, где находится стена(шесть флотов) + угол, на который открыта дверь, итого семь числел. Значит, hinge joint ограничивает пять степеней свободы.
Джойнт, связывающий намертво два тела:
Очевидно, положение двух намертво связанных тел можно задать как положение одного большого тела - шесть флотов, джойнт ограничивает шесть степеней свободы.

Стоит отметить, что степени свободы можно выбирать Любым способом, когда они однозначно определяют состояние системы, проблема лишь в том, что некоторые из них вызывают слишком большие ошибки округления при действиях с числами с плавающей точкой. Проблему выбора правильных стоит доверить опыту ранее проделанных работ или своей интуиции :)

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

Майлстоун четвёртый - CCD и шаг интегрирования

Все вышеизложенные рассуждения велись из предположения, что тела перемещаются дискретными скачками, хоть и малыми. Если скорости тел слишком велики и/или велик шаг по времени, тела могут сильно проникать друг в друга или даже пролететь насквозь. Существуют техники, называемые continuous collision detection, которые гарантируют, что смогут предсказать контакты, которые случатся между текущим контактом и следующим. К сожалению, они обычно вычислительно трудоёмки, вносят лишнюю ошибку или работают для сильно ограниченного типа геометрий. Я бы рекомендовал(по первому времени - настоятельно) не заморачиваться и просто шаг по времени так, чтобы самое быстро тело за один шаг по времени пролетало расстояние, меньше размера самого маленького.

Мне кажется, я знаю, как сделать лучше. Почему так делать нельзя.

У вас всё как-то сложно. Мне же всего лишь для сфер и прямоугольничков!

Как показывают несколько десятилетий практики, существенно проще нельзя. Если со сферами ещё что-то и можно придумать, то прямоугольнички - самые настоящие выпуклые многоугольники, для которых придётся считать все эти контакты, лепить эти ваши солверы и ещё бог знает что. Упростить жизнь можно, запретив телам вращаться - все угловые компоненты обнуляются и можно попытаться решать контакты "на лету" - как только нашёл контакт, тут же его решать. В остальных случаях лучше сразу пытаться понять, как это делается нормально, иначе результат будет слишком медленный, физически неверный и/или узко специализированный.

Почему просто не решать все контакты по порядку их возникновения?

У многих начинающих девелоперов возникает желание реализовать, казалось бы, логичную схему:
- обнаруживаем ближайший во времени контакт. пусть он произойдёт через время t
- проматываем время на величину t(интегрируем)
- решаем контакт
- повторяем до просветления

Казалось бы, почему нет? Никаких систем, никаких проникновений. А вот почему. Представим просто шарик, который просто прыгает по поверхности стола. Между первым и вторым ударом о стол прошло время t. При каждом ударе о стол шарик теряет половину своей скорости. Тогда между вторым и третьим ударом пройдёт время t / 2. Между третьим и четвёртым - t / 4. А как вы думаете, сколько соударений нам надо будет посчитать, если мы захотим узнать, где будет шарик в момент, например, 3 * t? Ответ - бесконечность. Подходя к моменту 2 * t, частота ударов будет бесконечно увеличиваться и, рассматривая последовательные соударения, мы никогда не расчитаем, что же произойдёт дальше этой отметки.

Хотя такой подход в принципе неплохо себя показывает в системах, где нет гравитации. Биллиард, например.

Заключение

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

Код


Я всегда был твёрдо уверен, да и сейчас тоже, что к статьям по программированию не нужны примеры с кодом. Статья нужна для того, чтобы объяснить, как это работает и как это запрограммировать, а не чтобы своровать из неё код. Но волею судеб пришлось написать очень упрощённую версию своего физ.двига с открытым кодом, который достаточно близко следует логике статьи, плюс в нём реализовано несколько важных моментов, которые в статью не вошли. Поэтому я решил выложить его в открытый доступ.
Видео демонстрации демки:
Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

Её исходный код(Есть зависимость от SFML, в архив включён проект и скомпиленный SFML для студии 2013. Должно быть очень легко скомпилить под любой другой IDE/операционкой):
https://dl.dropboxusercontent.com/u/25635148/Seminars/SusliX%20Lite.zip

Страницы: 1 2

#collision detection, #физика, #solver

9 июля 2008 (Обновление: 22 мар 2015)

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