Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Projected Gauss Seidel метод.

Projected Gauss Seidel метод.

Поделиться
ax77Новичокwww7 апр. 20175:55#0
Здравствуйте.
Может кто объяснить - кто первым использовал эту формулировку, и изобрел метод?
Почему Projected?
SuslikМодераторwww7 апр. 20176:50#1
projected — потому что каждое уравнение системы задаёт полупространство, ограниченное гиперплоскостью и каждая итерация метода проецирует текущую точку на это полупространство. изобрёли этот метод, рискну предположить, Гаусс с Зейделем. использовал этот метод где? если речь идёт об игровой физике, то одними из первых были Baraff, Witkin и компания.
XperienSПостоялецwww7 апр. 20177:46#2
В классическом PGS используются box constraints, так что там не совсем полупространство получается, но в целом все так.

По поводу изобретения это на самом деле сложный вопрос, потому что Гаусс с Зейделем они вроде как изобрели классический метод для решения СЛАУ, без ограничений; но я честно говоря не помню точно. Чтобы узнать более-менее точный ответ на этот вопрос, можно проштудировать ссылки в замечательной книге K. Murty, "Linear Complementarity, Linear and Nonlinear Programming", в частности - в главе 9.

А насчет использования в игровой индустрии, тут есть небольшой нюанс - в игрострое его стали использовать после того как придумали как его линеризовать по времени (стандартный PGS O(N*N)) - с учетом того что все джоинты которые используются в игровой физике соединяют всего два тела, составляющая матрицы в LCP - матрица Якоби - очень разреженная, поэтому можно с помощью аналитического разложения исходной матрицы можно свести матричные умножения из квадратичного к нескольким линейным от размерности матрицы. И, вроде бы, это было уже после Бараффа и Уиткина. Насколько я помню, первыми это сделали ребята из MathEngine, один из которых R. Tonge - и применили в какой-то из игр Croteam - вот ссылка с форума Bullet Physics Engine с небольшим обсуждением по теме. Детали истории я помню плохо, но судя по ссылкам я сказал все хотябы приблизительно верно :)

SuslikМодераторwww7 апр. 20178:40#3
XperienS
> ссылка с форума Bullet Physics Engine с небольшим обсуждением по теме. Детали
> истории я помню плохо, но судя по ссылкам я сказал все хотябы приблизительно
> верно :)
ссылка на тред 2006 года. в 2006 году у меня уже несколько лет был свой физический движок за линейную сложность. а первоизбретателем я не был, до меня были как минимум первые итерации box2d, но что-то мне подсказывает, что всё началось раньше, в самом начале 2000-х с каких-то ныне забытых движков вроде jiggle.

Правка: 7 апр. 2017 8:41

ax77Новичокwww7 апр. 201710:53#4
Спасибо за ответы. Наверняка разбирались вот с чем: уже неделю как пытаюсь осилить LCP - но вся информация на эту тему либо абстрактная (мат.книги) или сугубо по специфике (строительная механика). В целом суть понял так: LCP - те же линейные уравнения, только с ограничениями. Методов решения тоже несколько. Основные строго обоснованные - это Лемке и Данциг. Так же существуют много исследований, например из отечественных - решение методом Жордановых исключений.

Но: в самой формулировке задачи применительно к физ.моделированию LCP(q,M), непонятно вот что:

  • каких составляющих состоит вектор q?
  • какие значения в матрице М?
  • что хранит в себе матрица Якоби?
  • на какие величины накладываются ограничения?
    Т.е. что мы ищем, решая задачу?


    В общем целом на входе у нас есть список контактов тел, со всей нужной информацией. Такой так: координаты точек контактов, скорости тел, координаты центров масс, массы тел и проч.
    Решая LCP - мы решаем задачу применения импульсов к телам, то есть обрабатываем контакты и реагируем на них по физическим законам. Соответственно, ограничения LCP нужны для того, чтобы отфильтровать контакты, реакция на которые не нужна. Например - контакт по касательной, проникновения тел нет, но по факту они соприкасаются.
    Так вот: в статье [Erin Сatto "iterative dynamics with temporal coherence"] - утверждается, что PGS метод решает MLCP.
    Из чего возникают прочие вопросы - в чем отличия LCP от смешанной LCP? Лес становится темнее и темнее.

    Верно ли, что LCP в задачах физ.моделирования возникает так или иначе?
    Вроде бы вполне логично: есть тела, между ними взаимодействия, нужно это обработать физически, разрешая задачу математически.
    Не обязательно точно, главное - реалистично.
    Как можно решать контакты? Тоже два варианта, насколько нашел в интернете - или все сразу, или итеративно и бесконечно.

    Решая все и сразу - вполне закономерная сложность О(n3).
    Итеративно - O(n). Итеративная методика, основанная на импульсах вроде сейчас заложена в основе всех физ. движков (открытых, и как пишет Коуманс - закрытых, например Хавок). Bullet (SIConstraintSolver), ODE (quickstep), Box2D (ContactSolver) - все использует методику последовательных импульсов. При этом в Bullet есть интерфейсы MLCPSolver. И их реализации - Dantzig, Lemke. Тестировал их на Bullet Vehicle - логика такова, что если солвер LCP не находит решения - то конфигуратор переключает солвер на импульсный решатель. При этом чисто объективно визуально - Лемке работает ну очень медленно. В исходниках Лемке (от Bullet) причем об этом так и написано, что это аккуратная, но медленная реализация солвера LCP. Dantzik работает реалистично, но исходники - повергают в отчаяние. Понять, что там решается, простой смертный не в состоянии). Видно, что часть кода сгенерирована, но по какому принципу - загадка.

    На форме Bullet так же советуют - при решении задач с множеством ограничений (ragdoll, vehicle etc..) - использовать MLCP, иначе - стандартная конфигурация по умолчанию использует SISolver.

    Silver bullet не существует?

    И кстати, раз уж упомянули - кто нибудь использовал jiggle на серьезных задачах? Месяц назад смотрел его, но не плотно. Вроде как там физика тел задается файлами конфигурации?

  • SuslikМодераторwww7 апр. 201711:48#5
    насколько я помню, под MLCP понимаются LCP с дополнительными связями, которые описывают сухое трение. так как проекционным методам вроде гаусса-зейделя пофиг на эти связи, то они очень хорошо подходят для таких таких задач.

    jiggle — это старый демонстрационный движок, в индустрии, насколько я помню, не применялся.

    ответы на программистские вопросы вида "что хранится в матрице якоби" я старался описать в физике на пальцах: http://www.gamedev.ru/code/articles/?id=4706 там нет строгой математики и выводов, там есть только напальцевые соображения, как эти же уравнения можно получить в обход стандартной constraint-based математики и как их программировать.

    если хочется именно хардкора с полным конкретным из какой аксиоматики что берётся, то мы не так давно выводили это в треде: http://www.gamedev.ru/code/forum/?id=188342 . я в итоге-таки вывел конкретно те формулы, которые используются во всех физических движках, причём без читерства с угловой скоростью, как это обычно делается(где рассматривается просто 2д вращение). но по объёму треда можно оценить, через какую боль мне пришлось пройти.

    Правка: 7 апр. 2017 11:59

    XperienSПостоялецwww7 апр. 201719:01#6
    Все что я описал ниже это очень упрощенное представление, но должно дать интуитивное представление о том, что вообще происходит, для углубленного понимания я предлагаю ознакомиться с такими трудами как например "Rigid Body Simulation with Contact and Constraints" или "Ghosts and Machines: Variational Methods for Simulations of Multibodies Dry Frictional Contacts".

    Вектор q я думаю тебе не особо интересен, потому что насколько я помню в PGS он вообще тупо выкидывается (т.е. явно его посчитать конечно можно, но зачем).

    Матрица M это, если упрощенно, просто M = J*M^-1*J^T, т.е. Якоби помноженное на матрицу масс инвертированную (она блочно-диагональная, была бы просто диагональная если бы не тензоры инерции), помноженное на Якоби опять же, но транспонированную. Есть еще дополнения в виде регуляризации, но это уже отдельная история.

    Матрица Якоби в этом случае, в свою очередь, это матрица производных ограничивающей функции в пространстве. То есть интуитивно можно воспринимать как "а куда давить чтобы увеличить (или уменьшить) ограничивающую функцию". Продолжая интуитивную аналогию, это некий базис в котором нужно работать чтобы наиболее эффективно поменять ограничивающую функцию (читай, заставить джоинт работать).

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

    Решая задачу, мы вроде как ищем набор сил (или импульсов, или позиций) которые заставляют систему подчиняться твоему набору ограничений, и причем делают это не произвольно, а так сказать "реалистично". Представь что у тебя есть цепочка, и она в виду каких-то обстоятельств разъединилась. Соединить обратно цепочку можно бесконечным числом разных способов, например она внезапно может оказаться на марсе параллельно вектору гравитации, выровненная и чтоб все джоинты были в нужном состоянии. Но это нам не нужно, нам нужно чтобы изменения системы были минимальными для того чтобы в следующий временной шаг она выглядела реалистично. Отсюда приблизительно выплывает задача минимизации.

    MLCP - mixed LCP - это просто LCP у которого есть свободные переменные (без ограничений), т.е. по сути - если смешать обычное СЛАУ с LCP - получится MLCP, для PGS это совсем неважно, посколько для строчек без ограничений просто не делается проекция. Так что тут на самом деле толком ничего не усложняется.

    С точки зрения теории, что итеративные (PGS) что прямые (Dantzig/Lemke) в идеале дадут одинаковые решения, если итеративным дать бесконечное время и бесконечную мощность. Но с точки зрения практики, прямые методы могут провалиться с треском из-за проблем точности, например. А так же они очень медленные. Плюс прямых солверов - это что они за какое-то конечное время сойдутся к точному решению, если повезет. Т.е. если ты хочешь идеально жестких соединений, то нужно стараться использовать Lemke/Dantzig. Но в игровой индустрии на жесткость соединений (да и на точность в целом) - в основном плевать, затачивается под произвоидительность, так что я думаю что PGS можно назвать в некотором роде silver bullet для игростроя. Его бич правда это например ситуация когда игрок на бешенной скорости въезжает в регдолл, тогда руки ощутимо выходят из суставов. Или например если очень тяжелый объект поставить на очень легкий. Но обычно это объодят разными хаками.

    Правка: опечатки

    Правка: 8 апр. 2017 6:55

    ax77Новичокwww9 апр. 201717:12#7
    Благодарю за объяснения. Кто-нибудь плотно разбирал солверы таких продуктов как tokamak и ODE? На форуме читал про эти движки (как же давно это было 2004 и позже) - так же тестировал оба. Tokamak заводится легче и выглядит понятнее, ОДЕ - вроде как некогда был очень популярен (некогда?). В то же время код ОДЕ - выглядит мягко говоря не совсем читаемым. Понять например - что именно делает солвер - наверное можно, но... Код выглядит сгенерированным, совершенно загадка по какому принципу. bullet and box2d - вполне читаемые решения. При этом bullet везде использует интерфейсы под которые вполне возможно написать свою реализацию GJK or MLCP. А игрушки с ОДЕ под капотом до сих пор можно найти на AppStore. Так же собирал ОДЕ - версию из OpenXRay - но там двиг заточен под задачу, сильно усечен, переписан. Может есть еще текущие проекты - которые еще дописывают и используют эти движки.

    / Форум / Программирование игр / Физика

    2001—2017 © GameDev.ru — Разработка игр