XperienS
>1)
>2)
>3)
экспо, там, кажись, вообще коллижны резолвятся неверно, то есть их надо сначала решить верно и только потом уже думать, как устаканивать
hellobody
> очень интересно было бы послушать про альтернативный вариант "отмотке времени"
ну, вообще говоря, обычно в двигах делается так:
есть обычные тела и есть(и то не всегда) так называемые "bullets". при апдейте мирового времени на достаточно малую величину(больше 1/50 секунды брать не рекомендуется) все тела кроме "пуль" сдвигаются на этот временной шаг, как если бы коллижнов за это время не было. появляются взаимопроникновения, которые решаются дополнительным проходом солвера, то есть солвер помимо того, что считает, как тела "отскочут" друг от друга при соударении, выполняет ещё одну задачу - каким-то образом расталкивает проникшие тела. как это делать, много написано в блоге эрина катто на gphysics.com, но если что, я тоже могу рассказать. а для "bullets" используются отдельные алгоритмы continuous collision detection, например, с отмоткой времени. правда, время обычно никто не отматывает, обычно делают примерно так:
перемещают "пули" на некоторую величину по времени, eps. смотрят, если пуля за это время повела себя подозрительно(эвристиками устанавливается, что она прошла сквозь какое-то тело), шаг времени уменьшается вдвое, пулю вместо того, чтобы сдвигать на eps, сдвигают на eps/2, снова делают проверку, не пролетела ли она что-нибудь. если считается, что не пролетела, пробуют следующую величину - eps * 3 / 4. таким образом, бинарным поиском по времени, более-менее точно устанавливается момент соударения пули с припятствием.
но реальность такова, что обсчёт пуль - вообще дорогая штука, куда логичнее их обсчитать, например, рейкастом, просто выпустив луч и посмотрев, во что он попадает.
есть ещё один подход, используемый в физ.двиге bullet(с пулями из предыдущего параграфа ничего общего не имеет), где телам пересекаться вообще типа запрещено. но это "типа", честно говоря, здесь ключевое, нельзя сказать, это делает его самым физичным из всех двигов, при желании можешь почитать, что они там придумали, мне рассказывать лень, но, честно говоря, ничего гениального.
XperienS
>1)
>2)
>3)
экспо, там, кажись, вообще коллижны резолвятся неверно, то есть их надо сначала решить верно и только потом уже думать, как устаканивать
hellobody
> очень интересно было бы послушать про альтернативный вариант "отмотке времени"
ну, вообще говоря, обычно в двигах делается так:
есть обычные тела и есть(и то не всегда) так называемые "bullets". при апдейте мирового времени на достаточно малую величину(больше 1/50 секунды брать не рекомендуется) все тела кроме "пуль" сдвигаются на этот временной шаг, как если бы коллижнов за это время не было. появляются взаимопроникновения, которые решаются дополнительным проходом солвера, то есть солвер помимо того, что считает, как тела "отскочут" друг от друга при соударении, выполняет ещё одну задачу - каким-то образом расталкивает проникшие тела. как это делать, много написано в блоге эрина катто на gphysics.com, но если что, я тоже могу рассказать. а для "bullets" используются отдельные алгоритмы continuous collision detection, например, с отмоткой времени. правда, время обычно никто не отматывает, обычно делают примерно так:
перемещают "пули" на некоторую величину по времени, eps. смотрят, если пуля за это время повела себя подозрительно(эвристиками устанавливается, что она прошла сквозь какое-то тело), шаг времени уменьшается вдвое, пулю вместо того, чтобы сдвигать на eps, сдвигают на eps/2, снова делают проверку, не пролетела ли она что-нибудь. если считается, что не пролетела, пробуют следующую величину - eps * 3 / 4. таким образом, бинарным поиском по времени, более-менее точно устанавливается момент соударения пули с припятствием.
но реальность такова, что обсчёт пуль - вообще дорогая штука, куда логичнее их обсчитать, например, рейкастом, просто выпустив луч и посмотрев, во что он попадает.
есть ещё один подход, используемый в физ.двиге bullet(с пулями из предыдущего параграфа ничего общего не имеет), где телам пересекаться вообще типа запрещено. но это "типа", честно говоря, здесь ключевое, нельзя сказать, это делает его самым физичным из всех двигов, при желании можешь почитать, что они там придумали, мне рассказывать лень, но, честно говоря, ничего гениального.
Suslik
понятие "пуля" меня пока не интересует, у меня пока стоит задача устаканить какое то кол-во шаров... интересно как устроен солвер?
на блог эрина катто загляну... но и твои мысли хочеться почитать здесь... от отмотки времени я пока откажусь...
- каким-то образом расталкивает проникшие тела.
вот это основной вопрос который меня беспокоит... мне бы описание одного рабочего способа как раздвинуть два проникших тела, чтобы при этом не возникли новые проникновения... вот это у меня в голове не укладывается...
Suslik
понятие "пуля" меня пока не интересует, у меня пока стоит задача устаканить какое то кол-во шаров... интересно как устроен солвер?
на блог эрина катто загляну... но и твои мысли хочеться почитать здесь... от отмотки времени я пока откажусь...
- каким-то образом расталкивает проникшие тела.
вот это основной вопрос который меня беспокоит... мне бы описание одного рабочего способа как раздвинуть два проникших тела, чтобы при этом не возникли новые проникновения... вот это у меня в голове не укладывается...
Suslik
- каким-то образом расталкивает проникшие тела. как это делать, много написано в блоге эрина катто на gphysics.com, но если что, я тоже могу рассказать
что то не нахожу я в блоге Эрина, как расталкивать проникшие тела, если можно прямую ссылку кинь :)
Suslik
- каким-то образом расталкивает проникшие тела. как это делать, много написано в блоге эрина катто на gphysics.com, но если что, я тоже могу рассказать
что то не нахожу я в блоге Эрина, как расталкивать проникшие тела, если можно прямую ссылку кинь :)
hellobody
Я бы все же настоятельно рекомендовал прочитать литературу по этому поводу, потому что тема-то довольно обширная, и в один абзац уложить все нюансы проблематично :)
Но просто чтобы ты понимал, как это происходит в современных движках:
для ограничений (constraints, их по-другому еще соединения/joints называют) задается ограничивающая функция C, которая должна быть равна 0, чтобы ограничение выполнялось. Т.е. например, для того чтобы сделать шарнир, нужно указать
C = x0 + R0*p0 - (x1 + R1*p1)
смысл этой формулы таков: точка на теле i задается смещением тела (xi) и поворотом вектора от нужной точки до центра масс в локальной системе координат (вектор pi, матрица ориентации Ri). Соответственно, чтобы эти точки совпадали, их координаты должны быть равны, отсюда и уравнение.
Теперь, возьмем производную:
dC/dt = dC/dx *dx/dt = J * u;
J - матрица Якоби, или матрица частных производных (получается при дифференцировании одного вектора другим - dC / dx;
в данном примере если продифференцировать и сгруппировать по скоростям:
dC/dt = d(x0 + R0*p0 - (x1 + R1*p1)) / dt = v0 - R0*p0 x w0 - v1 + R1*p1 x w1;
v/w - линейная/угловая скорость, следовательно J = ( I cross_matrix(-R0*p0) -I cross_matrix(R1*p1) )T;
), а u - вектор скоростей, которы равен:
u = (v + dt * M-1 * F(e) + dt * M-1 * Fc)
M - матрица масс, блочно-диагональная, в первом блоке m * I - линейная составляющая, во втором - тензор инерции. F(e) - внешние силы, и Fc - нужные нам ограничивающие силы, которые и заставят тело соблюдать ограничение. Теперь, подставим выражение скорости в формулу dC/dt, и перегруппируем c внесеним dt в lambda (при этом Fc = JT * lambda, здесь вектор лямбд без dt):
(J * M-1 * JT) * lambda = dC/dt - J * (v + dt * M-1 * F(e))
получилась простая СЛАУ A*x = b;
где A = J * M-1 * JT;
x = lambda - знаковые множители лагранжа, которые при умножении на транспонированную матрицу Якоби (ибо ограничивающие силы не совершают работы) и дадут нам нужные ограничивающие силы.
Проще говоря, чтобы сделать соблюдение множественных ограничений - нужно из всех них сформировать систему, и ее решить, тогда в результате у тебя будет состояние, не нарушающее ни одного ограничения, в идеале (на самом деле чаще берут не совсем точные решения во имя скорости, да и поскольку решаем в скоростях - в положениях возникают неточности и их нужно править, см. стабилизация Баумгарте или пост-стабилизация псевдо-скоростями).
Это для сцен вида цепочка из тел, связанных шарниром. В случае контакта, появляется дополнительное условие, ограничивающая сила должна препятствовать проникновению тел дальше, но не должна препятствовать их рассоединению, чтобы не было эффекта "прилипания". Для этого вводят дополнительное ограничение на вектор лямбд где нужно, и получается не СЛАУ а LCP.
Типично, для решения используется простой и нативный метод покоординатного спуска, известный как метод Гаусса-Зейделя (это для СЛАУ, для LCP его простая модификация Projected Gauss-Seidel или даже Successive Over-relaxation, это еще простая модификация PGS), его можно понять интуитивно: для одного ограничения нужно найти такие лямбды, которые прилагают силы, нужные для соблюдения телами конкретного ограничения, если искомые коэффициенты-лямбды нарушают условие (lambda > 0 здесь, но вообще - более общий случай попадания лямбд в интервал [low, high]), то просто их обрезать до нужного значения, и так пройтись по всем ограничениям (это одна итерация, и ее примерно иллюстрирует твой рисунок). Естественно, есть проблема, которую ты выше описал - пожтому нужно пройтись еще раз по всем ограничениям. С каждой итерацией мы будем потихоньку приходить к решению, когда все ограничения не нарушены. Это есть схема PGS, она проста к реализации и интуитивно понятна. Однако есть более злые итеративные методы, например метод сопряженных градиентов (это для СЛАУ, его понять уже сложнее) и точные методы, которые пытаются найти точное решение, а не постепенно приближатся к нему.
Ну конечно, после нахождения ограничивающих сил - нужно произвести интегрирование (самый простой и распространенный вариант - semi-implicit Euler, там делается v += a*dt; x += v*dt;).
Вот, самые основные принципы действия современных движков rigid-body dynamics, основанных на принципе ограничений. Но я рекомендую все же ознакомится со статьями которые указаны по ссылке, более основателен курс David Baraff.
hellobody
Я бы все же настоятельно рекомендовал прочитать литературу по этому поводу, потому что тема-то довольно обширная, и в один абзац уложить все нюансы проблематично :)
Но просто чтобы ты понимал, как это происходит в современных движках:
для ограничений (constraints, их по-другому еще соединения/joints называют) задается ограничивающая функция C, которая должна быть равна 0, чтобы ограничение выполнялось. Т.е. например, для того чтобы сделать шарнир, нужно указать
C = x0 + R0*p0 - (x1 + R1*p1)
смысл этой формулы таков: точка на теле i задается смещением тела (xi) и поворотом вектора от нужной точки до центра масс в локальной системе координат (вектор pi, матрица ориентации Ri). Соответственно, чтобы эти точки совпадали, их координаты должны быть равны, отсюда и уравнение.
Теперь, возьмем производную:
dC/dt = dC/dx *dx/dt = J * u;
J - матрица Якоби, или матрица частных производных (получается при дифференцировании одного вектора другим - dC / dx;
в данном примере если продифференцировать и сгруппировать по скоростям:
dC/dt = d(x0 + R0*p0 - (x1 + R1*p1)) / dt = v0 - R0*p0 x w0 - v1 + R1*p1 x w1;
v/w - линейная/угловая скорость, следовательно J = ( I cross_matrix(-R0*p0) -I cross_matrix(R1*p1) )T;
), а u - вектор скоростей, которы равен:
u = (v + dt * M-1 * F(e) + dt * M-1 * Fc)
M - матрица масс, блочно-диагональная, в первом блоке m * I - линейная составляющая, во втором - тензор инерции. F(e) - внешние силы, и Fc - нужные нам ограничивающие силы, которые и заставят тело соблюдать ограничение. Теперь, подставим выражение скорости в формулу dC/dt, и перегруппируем c внесеним dt в lambda (при этом Fc = JT * lambda, здесь вектор лямбд без dt):
(J * M-1 * JT) * lambda = dC/dt - J * (v + dt * M-1 * F(e))
получилась простая СЛАУ A*x = b;
где A = J * M-1 * JT;
x = lambda - знаковые множители лагранжа, которые при умножении на транспонированную матрицу Якоби (ибо ограничивающие силы не совершают работы) и дадут нам нужные ограничивающие силы.
Проще говоря, чтобы сделать соблюдение множественных ограничений - нужно из всех них сформировать систему, и ее решить, тогда в результате у тебя будет состояние, не нарушающее ни одного ограничения, в идеале (на самом деле чаще берут не совсем точные решения во имя скорости, да и поскольку решаем в скоростях - в положениях возникают неточности и их нужно править, см. стабилизация Баумгарте или пост-стабилизация псевдо-скоростями).
Это для сцен вида цепочка из тел, связанных шарниром. В случае контакта, появляется дополнительное условие, ограничивающая сила должна препятствовать проникновению тел дальше, но не должна препятствовать их рассоединению, чтобы не было эффекта "прилипания". Для этого вводят дополнительное ограничение на вектор лямбд где нужно, и получается не СЛАУ а LCP.
Типично, для решения используется простой и нативный метод покоординатного спуска, известный как метод Гаусса-Зейделя (это для СЛАУ, для LCP его простая модификация Projected Gauss-Seidel или даже Successive Over-relaxation, это еще простая модификация PGS), его можно понять интуитивно: для одного ограничения нужно найти такие лямбды, которые прилагают силы, нужные для соблюдения телами конкретного ограничения, если искомые коэффициенты-лямбды нарушают условие (lambda > 0 здесь, но вообще - более общий случай попадания лямбд в интервал [low, high]), то просто их обрезать до нужного значения, и так пройтись по всем ограничениям (это одна итерация, и ее примерно иллюстрирует твой рисунок). Естественно, есть проблема, которую ты выше описал - пожтому нужно пройтись еще раз по всем ограничениям. С каждой итерацией мы будем потихоньку приходить к решению, когда все ограничения не нарушены. Это есть схема PGS, она проста к реализации и интуитивно понятна. Однако есть более злые итеративные методы, например метод сопряженных градиентов (это для СЛАУ, его понять уже сложнее) и точные методы, которые пытаются найти точное решение, а не постепенно приближатся к нему.
Ну конечно, после нахождения ограничивающих сил - нужно произвести интегрирование (самый простой и распространенный вариант - semi-implicit Euler, там делается v += a*dt; x += v*dt;).
Вот, самые основные принципы действия современных движков rigid-body dynamics, основанных на принципе ограничений. Но я рекомендую все же ознакомится со статьями которые указаны по ссылке, более основателен курс David Baraff.
XperienS
мне никогда не нравилась матрично-математическая трактовка лямбд-якобианов. нет, это, конечно, один из вариантов, но мне больше нравится объяснение "на пальцах" а-ля те, что в презентации эрина. я и чувствую, что уже почти придумал, как можно то же самое объяснить ещё нагляднее, постараюсь изложить, как время будет.
hellobody
> что то не нахожу я в блоге Эрина, как расталкивать проникшие тела, если можно прямую ссылку кинь :)
на gphysics.com на главной странице графа "position correnction"
если вкратце, попытаюсь объяснить на твоём же примере:
у тебя неточность в переходе с пункта Б на В: как мы расталкиваем первые два шара, левый после расталкивания будет чуть левее, чем был на картинке Б. потом, когда мы вытолкнем второй из третьего, потом снова растолкнём первый и второй, первый окажется ещё чуть левее. в этом и суть итеративного поиска: вот так поочерёдно расталкивая шары, в конце концов они будут вылазить и вылазить друг из друга постепенно.
а вообще есть математически более точные методы, решающие систему уравнений в духе "чтобы первый шар вылез из второго и при этом не залез в третий", просто многие итеративные схемы решения подобных уравнений имеют именно такой физический смысл - попарного расталкивания шаров.
я, вообще говоря, не являюсь первым фанбоем бараффа и слишком большого количества теоретической физики. где можно обойтись без ненаглядной математики, я предпочитаю мыслить в терминах наглядной физики. так, например, подход бараффа и экспо - чисто математический, эрина катто - куда больше физический, а суть это - абсолютно одно и то же, математически подходы абсолютно эквивалентны, просто трактовка у проводимых операций разная.
XperienS
мне никогда не нравилась матрично-математическая трактовка лямбд-якобианов. нет, это, конечно, один из вариантов, но мне больше нравится объяснение "на пальцах" а-ля те, что в презентации эрина. я и чувствую, что уже почти придумал, как можно то же самое объяснить ещё нагляднее, постараюсь изложить, как время будет.
hellobody
> что то не нахожу я в блоге Эрина, как расталкивать проникшие тела, если можно прямую ссылку кинь :)
на gphysics.com на главной странице графа "position correnction"
если вкратце, попытаюсь объяснить на твоём же примере:
у тебя неточность в переходе с пункта Б на В: как мы расталкиваем первые два шара, левый после расталкивания будет чуть левее, чем был на картинке Б. потом, когда мы вытолкнем второй из третьего, потом снова растолкнём первый и второй, первый окажется ещё чуть левее. в этом и суть итеративного поиска: вот так поочерёдно расталкивая шары, в конце концов они будут вылазить и вылазить друг из друга постепенно.
а вообще есть математически более точные методы, решающие систему уравнений в духе "чтобы первый шар вылез из второго и при этом не залез в третий", просто многие итеративные схемы решения подобных уравнений имеют именно такой физический смысл - попарного расталкивания шаров.
я, вообще говоря, не являюсь первым фанбоем бараффа и слишком большого количества теоретической физики. где можно обойтись без ненаглядной математики, я предпочитаю мыслить в терминах наглядной физики. так, например, подход бараффа и экспо - чисто математический, эрина катто - куда больше физический, а суть это - абсолютно одно и то же, математически подходы абсолютно эквивалентны, просто трактовка у проводимых операций разная.
Suslik
> математически подходы абсолютно эквивалентны
Ну, все что ты сказал - корректно до тех пор, пока ты используешь PGS; он и имеет физический смысл попарного расталкивания шаров. Другие же методы - нет.
Я приверженец математической формулировки, потому что это исток; если же в тему не углубляться, то конечно можно ограничиться наглядностью PGS.
Правка: орфография
Suslik
> математически подходы абсолютно эквивалентны
Ну, все что ты сказал - корректно до тех пор, пока ты используешь PGS; он и имеет физический смысл попарного расталкивания шаров. Другие же методы - нет.
Я приверженец математической формулировки, потому что это исток; если же в тему не углубляться, то конечно можно ограничиться наглядностью PGS.
Правка: орфография
XperienS
да, на практике я действительно использую только пгс. но у меня абстракция солвера позволяет юзать любой метод решения, в том числе чисто матричные подходы. так вот мои эксперименты показали, что те матричные методы, что я тестил, либо показывают себя не лучше PGS(суть являются его интерпретациями), либо просто не подходят для геймдева по причиние нелинейности.
XperienS
да, на практике я действительно использую только пгс. но у меня абстракция солвера позволяет юзать любой метод решения, в том числе чисто матричные подходы. так вот мои эксперименты показали, что те матричные методы, что я тестил, либо показывают себя не лучше PGS(суть являются его интерпретациями), либо просто не подходят для геймдева по причиние нелинейности.
Suslik
у тебя неточность в переходе с пункта Б на В: как мы расталкиваем первые два шара, левый после расталкивания будет чуть левее, чем был на картинке Б.
что означает "чуть левее", поясни пожалуйста
и каким способом мы расталкиваем шары?
-один из шаров выдвигаем вдоль нормали от центра другого шара на расстояние двух радиусов? так можно делать?
http://www.gphysics.com/archives/35
не совсем то, там описывают преимущества и недостатки алгоритмов коррекции позиций вращающихся связок (если я правильно перевел), и сами алгоритмы не описаны, джойнты меня пока не интересуют...
XperienS
перевариваю...
Suslik
у тебя неточность в переходе с пункта Б на В: как мы расталкиваем первые два шара, левый после расталкивания будет чуть левее, чем был на картинке Б.
что означает "чуть левее", поясни пожалуйста
и каким способом мы расталкиваем шары?
-один из шаров выдвигаем вдоль нормали от центра другого шара на расстояние двух радиусов? так можно делать?
http://www.gphysics.com/archives/35
не совсем то, там описывают преимущества и недостатки алгоритмов коррекции позиций вращающихся связок (если я правильно перевел), и сами алгоритмы не описаны, джойнты меня пока не интересуют...
XperienS
перевариваю...
hellobody
"...что означает ..."
По очереди шары рассталкиваем. Как до эпохи исторического материализма в культовой игре Квейк. Один объект двигается, остальные замерли. Потом другой и т.д. Здесь тоже самое только парами. Т.е. картинка Б неверна, потому что третий шар ещё стоит на месте.
hellobody
"...что означает ..."
По очереди шары рассталкиваем. Как до эпохи исторического материализма в культовой игре Квейк. Один объект двигается, остальные замерли. Потом другой и т.д. Здесь тоже самое только парами. Т.е. картинка Б неверна, потому что третий шар ещё стоит на месте.
hellobody
>и каким способом мы расталкиваем шары?
в первом приближении алгоритм следующий:
берём два пересекающихся шара, нахидим, что они пересекаются на вектор d. первый выталкиваем на d/2 влево, второй - на d/2 вправо.
hellobody
>и каким способом мы расталкиваем шары?
в первом приближении алгоритм следующий:
берём два пересекающихся шара, нахидим, что они пересекаются на вектор d. первый выталкиваем на d/2 влево, второй - на d/2 вправо.
Suslik
Ну почему же: если взять случай исключительно СЛАУ, то есть например итеративный CG (Conjugate Gradients, метод Сопряженных градиентов). Его также можно сделать линейным, сходится он получше чем PGS если нужна точность (на больших количествах итераций ПГС проигрывает КГ, а вообще, математически метод сходится за N итераций, где N - количество неизвестных; однако на очень малых лучше все же ПГС использовать), а по смыслу КГ все же не является расталкиванием тел попарно. Есть также прямые методы, но они нелинейны, да.
hellobody
> джойнты меня пока не интересуют
В современной constraint-based физике, контакты - те же джоинты, только появляющиеся когда нужно, и исчезающие после разъединения тел (плюс дополнительное ограничение, которое я описал выше). Так что для того, чтобы понять работу контактов, нужно понять работу ограничений/соединений в базовом виде.
Suslik
Ну почему же: если взять случай исключительно СЛАУ, то есть например итеративный CG (Conjugate Gradients, метод Сопряженных градиентов). Его также можно сделать линейным, сходится он получше чем PGS если нужна точность (на больших количествах итераций ПГС проигрывает КГ, а вообще, математически метод сходится за N итераций, где N - количество неизвестных; однако на очень малых лучше все же ПГС использовать), а по смыслу КГ все же не является расталкиванием тел попарно. Есть также прямые методы, но они нелинейны, да.
hellobody
> джойнты меня пока не интересуют
В современной constraint-based физике, контакты - те же джоинты, только появляющиеся когда нужно, и исчезающие после разъединения тел (плюс дополнительное ограничение, которое я описал выше). Так что для того, чтобы понять работу контактов, нужно понять работу ограничений/соединений в базовом виде.
hellobody,
по вопросу расталкивания тел Суслик слишком уж упрощает объяснение, а Экспа в принципе говорит дело, но сразу глухо сыпет формулами. Попоробую сказать в двух словах. Есть такая штука, как Лагранжева динамика (см например в качестве обзора Constrained Dynamics у Бараффа http://www.cs.cmu.edu/~baraff/sigcourse/index.htm также небесполезна википедия http://en.wikipedia.org/wiki/Lagrangian_mechanics и теормех в любых формах тоже небесполезен). Столкновение есть лишь частный случай связи между двумя телами; формулировка контакта ил столкновения в виде связи приводится, например, у Кляйна (http://www.cs.ubc.ca/grads/resources/thesis/Nov02/Michael_Cline.pdf там же и вообще хороший обзор симуляции физики в терминах лагранжевой механики).
Если сказать совсем скупо, то в системе тел определяются связи как функции от координат тел, вида C(position1, position2) = 0 (связи-равенства) или C(position1, position2) >= 0 (связи-неравенства, т.ж. известные как "односторонние" связи). Теормех допускает и другие формы функций связи (например, зависящие от скорости, от времени итд), но популярные методы работают только со связями таких видов. Столкновение можно выразить как связь-неравенство. Большинство мейнстримовых методов базируется на подборе таких скоростей тел, чтобы на следующем кадре равенства и неравенства связей выполнялись для обновленных положений тел (хотя есть и позишн-бейсд подходы, и подходы, корректирующие ускорения). В таком случае каждая функция связи в любой момент представляется своей производной по координатам связанных объектов в данной точке, т.е. якобианом. Например для связи, представленной одной строкой-равенством, связывающей два тела в трехмерном пространстве, якобиан J = {C'x1 С'y1 С'z1 C'x2 С'y2 С'z2}. Если взять скалярное произведение этого якобиана и вектора скоростей связанных объектов, по правилу полной производной получится J * V = C'dxyz1xyz2 * (XYZ1XYZ2)'t = dC/dt, т.е. фактически мы выражаем скорость изменения связи, тогда как в случае выполнения условия связи она должна быть равна 0. Если не брать пока вопрос корректирования уже разъехавшихся связей, получается что скорость расхождения связи т.ж. должна быть равна 0 (справедливо для связей-равенств). Для многих связей якобиан - матрица, и требуемое условие в матричной записи J * velocity = 0. Это было условие, которое должно выполняться, а достигается оно путём приложения к телам дополнительных компенсационных сил, сил реакций связей. У Бараффа (например) доказывается, что вектор таких сил Fc = J^T * lambda, где J - тот самый якобиан, а лямбда - вектор неизвестных. Как это сводится воедино см по приведённым ссылкам или внимательнее читай посты Экспы, но в результате получается обычная система линейных уравнений если все связи равенства, или задача о линейной дополнительности (linear complementarity problem, LCP) если там есть связи-неравенства, например, столкновения. LCP - это целый мир, надо гуглить и читать статьи в коммунити на этом сайте. Но в двух словах, это проблема вида w = M*x - b; x>=0; w>=0; x dot w = 0, где М - известная матрица, b - известный вектор, x - искомый вектор неизвестных, а символ ">=" обозначает неотрицательность каждого компонента вектора. Вариантов решения лцп довольно много, но для целей игровой физики особенно хорош метод Projected Gauss Seidel, который является весьма незначительной модификацией метода Гаусса-зейделя для решения СЛАУ, в то же время есть математическое доказательство его сходимости. Есть ещё большее упрощение этого метода, которое фактически позволяет абстрагироваться от якобиана и решать проблему итеративным попарным расталкиванием объектов путём приложения импульсов определённой магнитуды, sequensial impulses. Метод полностью идентичен PGS, поэтому работает, однако он труднее оптимизируется. Гугл, гугл, гугл.
hellobody,
по вопросу расталкивания тел Суслик слишком уж упрощает объяснение, а Экспа в принципе говорит дело, но сразу глухо сыпет формулами. Попоробую сказать в двух словах. Есть такая штука, как Лагранжева динамика (см например в качестве обзора Constrained Dynamics у Бараффа http://www.cs.cmu.edu/~baraff/sigcourse/index.htm также небесполезна википедия http://en.wikipedia.org/wiki/Lagrangian_mechanics и теормех в любых формах тоже небесполезен). Столкновение есть лишь частный случай связи между двумя телами; формулировка контакта ил столкновения в виде связи приводится, например, у Кляйна (http://www.cs.ubc.ca/grads/resources/thesis/Nov02/Michael_Cline.pdf там же и вообще хороший обзор симуляции физики в терминах лагранжевой механики).
Если сказать совсем скупо, то в системе тел определяются связи как функции от координат тел, вида C(position1, position2) = 0 (связи-равенства) или C(position1, position2) >= 0 (связи-неравенства, т.ж. известные как "односторонние" связи). Теормех допускает и другие формы функций связи (например, зависящие от скорости, от времени итд), но популярные методы работают только со связями таких видов. Столкновение можно выразить как связь-неравенство. Большинство мейнстримовых методов базируется на подборе таких скоростей тел, чтобы на следующем кадре равенства и неравенства связей выполнялись для обновленных положений тел (хотя есть и позишн-бейсд подходы, и подходы, корректирующие ускорения). В таком случае каждая функция связи в любой момент представляется своей производной по координатам связанных объектов в данной точке, т.е. якобианом. Например для связи, представленной одной строкой-равенством, связывающей два тела в трехмерном пространстве, якобиан J = {C'x1 С'y1 С'z1 C'x2 С'y2 С'z2}. Если взять скалярное произведение этого якобиана и вектора скоростей связанных объектов, по правилу полной производной получится J * V = C'dxyz1xyz2 * (XYZ1XYZ2)'t = dC/dt, т.е. фактически мы выражаем скорость изменения связи, тогда как в случае выполнения условия связи она должна быть равна 0. Если не брать пока вопрос корректирования уже разъехавшихся связей, получается что скорость расхождения связи т.ж. должна быть равна 0 (справедливо для связей-равенств). Для многих связей якобиан - матрица, и требуемое условие в матричной записи J * velocity = 0. Это было условие, которое должно выполняться, а достигается оно путём приложения к телам дополнительных компенсационных сил, сил реакций связей. У Бараффа (например) доказывается, что вектор таких сил Fc = J^T * lambda, где J - тот самый якобиан, а лямбда - вектор неизвестных. Как это сводится воедино см по приведённым ссылкам или внимательнее читай посты Экспы, но в результате получается обычная система линейных уравнений если все связи равенства, или задача о линейной дополнительности (linear complementarity problem, LCP) если там есть связи-неравенства, например, столкновения. LCP - это целый мир, надо гуглить и читать статьи в коммунити на этом сайте. Но в двух словах, это проблема вида w = M*x - b; x>=0; w>=0; x dot w = 0, где М - известная матрица, b - известный вектор, x - искомый вектор неизвестных, а символ ">=" обозначает неотрицательность каждого компонента вектора. Вариантов решения лцп довольно много, но для целей игровой физики особенно хорош метод Projected Gauss Seidel, который является весьма незначительной модификацией метода Гаусса-зейделя для решения СЛАУ, в то же время есть математическое доказательство его сходимости. Есть ещё большее упрощение этого метода, которое фактически позволяет абстрагироваться от якобиана и решать проблему итеративным попарным расталкиванием объектов путём приложения импульсов определённой магнитуды, sequensial impulses. Метод полностью идентичен PGS, поэтому работает, однако он труднее оптимизируется. Гугл, гугл, гугл.
SoRRoW
> Метод полностью идентичен PGS, поэтому работает, однако он труднее
> оптимизируется.
пруф. в смысле, по большей части я с твоим постом согласен, но вот это предложение смутило. все эвристики по повышению стабильности/сходимости, которые я встречал для PGS, неплохо ложатся и на SI(constraint mix force, under-/overrelaxation, etc). что я упустил?
SoRRoW
> Метод полностью идентичен PGS, поэтому работает, однако он труднее
> оптимизируется.
пруф. в смысле, по большей части я с твоим постом согласен, но вот это предложение смутило. все эвристики по повышению стабильности/сходимости, которые я встречал для PGS, неплохо ложатся и на SI(constraint mix force, under-/overrelaxation, etc). что я упустил?
Кстати, XperienS, самой большой проблемой при объяснении этого классического подхода был вот этот момент:
>Теперь, подставим выражение скорости в формулу dC/dt, и перегруппируем c внесеним dt в lambda (при этом Fc = JT * lambda, здесь вектор лямбд без dt):
почему мы принимаем, что вектор сил, действующий в джойнтах, равен транспонированному якобиану на вектор лямбд? в объяснении SI в этом месте точно такой же трабл. эрин катто говорит, что это очевидно из интуитивных соображений, я так не считаю.
а вообще прикол, я и не знал, что якобиан появляется при дифференцировании чисто координатного ограничения C(x1, x2) = 0 по координатам. в смысле думал, что он по определению вводится как матрица чисто скоростного ограничения J * v = C
Кстати, XperienS, самой большой проблемой при объяснении этого классического подхода был вот этот момент:
>Теперь, подставим выражение скорости в формулу dC/dt, и перегруппируем c внесеним dt в lambda (при этом Fc = JT * lambda, здесь вектор лямбд без dt):
почему мы принимаем, что вектор сил, действующий в джойнтах, равен транспонированному якобиану на вектор лямбд? в объяснении SI в этом месте точно такой же трабл. эрин катто говорит, что это очевидно из интуитивных соображений, я так не считаю.
а вообще прикол, я и не знал, что якобиан появляется при дифференцировании чисто координатного ограничения C(x1, x2) = 0 по координатам. в смысле думал, что он по определению вводится как матрица чисто скоростного ограничения J * v = C
[Suslik]
Ну вообще все техники по повышению стабильности и сходимости да, легко ложатся на СИ. В принципе, наверное, если ставить перед собой такую задачу, можно сделать СИ не медленнее чем ПГС. Но имплементации, которые я встречал, имели много лишнего - например, при приложении импульсов на каждой итерации импульс приводился к центру масс, т.е. на каждой итерации возникал лишнее векторное произведение, которое достаточно сделать один раз на самом деле. Конечно никто не мешает это соптимизировать ив СИ, но в ПГСе ты сразу и сходу вынужден делать достаточно оптимальный в этом смысле код, тогда как СИ подталкивает к написанию наивного решения. В общем-то это моё субъективное восприятие. Я об этом, а не об эвристиках.
[Suslik]
Ну вообще все техники по повышению стабильности и сходимости да, легко ложатся на СИ. В принципе, наверное, если ставить перед собой такую задачу, можно сделать СИ не медленнее чем ПГС. Но имплементации, которые я встречал, имели много лишнего - например, при приложении импульсов на каждой итерации импульс приводился к центру масс, т.е. на каждой итерации возникал лишнее векторное произведение, которое достаточно сделать один раз на самом деле. Конечно никто не мешает это соптимизировать ив СИ, но в ПГСе ты сразу и сходу вынужден делать достаточно оптимальный в этом смысле код, тогда как СИ подталкивает к написанию наивного решения. В общем-то это моё субъективное восприятие. Я об этом, а не об эвристиках.
Тема в архиве.