Capsule vs AABB

Нахожусь в поисках красивого решения задачи проверки пересечения капсулы и параллелепипеда с выдачей нормали и глубины проникновения. Нашёл один вариант на http://www.geometrictools.com/, через вычисление расстояния от отрезка до граней, рёбер и углов этой, казалось бы, элементарной фигуры.
Проверил, работает, но смущает объём кода 700+ строк. На фоне моей текущей проверки Sphere vs AABB (15 строк) этот код выглядит каким-то нелепым что ли. Существуют ли более изящные алгоритмы?

GJK и его вариации, minkowsky portal refinement.

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

Если кому будет интересно, нашёл весьма полезный пепер, с его помощью реализовал столкновения различных типов объектов через Minkowski Portal Refinement, серьёзных тестов со стеком объектов ещё не проводил, но первые результаты впечатляют, хоть и есть бага с вычислением penetration depth вектора в некоторых случаях (которую решаю). Суммарно для всех типов кол-во строк кода меньше чем в той проверке случая Capsule vs AABB! :D

с MPR осторожнее. он глючит на длинных объектах

XProger
> Суммарно для всех типов кол-во строк кода меньше чем в той проверке случая
> Capsule vs AABB! :D
Даешь тесты? А то вот у меня есть сортировка:

for (int i = 0; i<size; i++)
  for (int j = 0; j<size-1; j++)
    if (item[j]<item[j+1]) swap(item[j], item[j+1]);

с малым количеством строк, но почему-то её очень редко используют :)

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

Suslik
Спасибо, походу как раз этот случай, плюс накладываются float погрешности, т.к. с double косяков с выбором вектора направления гораздо меньше вышло.

XProger
double не решает всех проблем MPR, он их просто маскирует. численная неустойчивость — основной недостаток этого метода. я всё жду решения минобрнауки, чтобы опубликовать свой диссер, у меня там как раз алгоритм, который, как и mpr, позволяет считать пересения, но так же устойчив, как gjk.

Suslik
Было бы интересно почитать. Мне пришлось полгода решения о присуждении учёной степени ждать, а затем ещё полгода прошло до получения корки. Бюрократы там весьма не торопливые )

XProger
> Что с чем сравнивать я не понял, т.к MPR покрывает даже те комбинации
> столкновений, о которых я даже не мечтал )
Скажем 1000 рандомных капсул с 1000 рандомных AABB, с кодом из другой библиотеки.

XProger
> Suslik
> Попутно наткнулся на твою статью, жаль иллюстрации слетели.
Здесь посмотри: http://web.archive.org/web/20130818061320/http://www.gamedev.ru/c… cles/?id=3127

Shurik7777
Спасибо!

Теперь борюсь с стабильностью, сперва реализовал простой если так можно выразиться солвер (по наитию) - при обнаружении коллизий моментально расталкивал объекты и пересчитывал их линейные и угловые скорости, в итоге объекты под большим весом стека вминались друг в друга, т.к. расталкивая пару объектов они въезжали в соседние... В общем решил посмотреть как умные люди делают и нарыл Baumgarte метод, который оперирует position и velocity error'ами, не уверен в верности реализации, но боксы перестали въезжать, но стали вести себя крайне нестабильно, в лежачем положении дрожат и скачут с угла на угол как при абсолютно упругом столкновении.
Сейчас копаю в сторону Projected Gauss-Seidel, т.к на форуме bullet'а пишут о его большей стабильности. Так ли это? Есть ли у метода подводные камни, а также вообще интересно к чему нынче пришёл прогресс и что модно использовать на данный момент?

Ещё интересно кто как выбирает шаг симуляции. Насколько я понимаю, разброс deltaTime также вносит свой вклад в нестабильное поведение физики. Пока режу deltaTime на интервалы в 1/60 сек накапливая хвосты в надежде, что недокрутка или недолёт объекта на < 1/60 сек в кадре не будет заметна глазу. Существуют ли другие подходы?

baumgarte — это velocity-based метод решения проникновений. как ты мог заметить, стабильностью не отличается. я писал в статье про солверы про псевдоскорости, они гораздо лучше справляются с расталкиванием и не вносят нестабильности: http://www.gamedev.ru/code/articles/?id=4706

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

Suslik
Спасибо за статью, только после прочтения остались не ясными несколько вещей:

  float b = (n1 * n1 * body1->invMass 
    + w1 * w1 * body1->InvInertia 
    + n2 * n2 * body2->invMass  
    + w2 * w2 * body2->InvInertia);

1) n1.dot(n1) и n2.dot(n2) могут быть не равны 1.0?
2) как получить float body1->InvInertia получаю как n1.dot( body1->invTensor *body1->invMass * (point - body1->pos) ), но походу ошибаюсь (invTensor - матрица)
3) при расчёте псевдо-скоростей depth принимать как квадрат глубины?
4) нужно ли учитывать угловые составляющие в уравнениях для псевдо-скоростей?

XProger
> n1.dot(n1) и n2.dot(n2) могут быть не равны 1.0?
в случае джойнтов, более сложных, чем просто контакты, могут

> как получить float body1->InvInertia получаю как n1.dot( body1->invTensor
> *body1->invMass * (point - body1->pos) ), но походу ошибаюсь (invTensor -
> матрица)
я не знаю, что ты написал, но это точно неправильно. invInertia — это линейный оператор, который при домножении слева на момент силы, даёт ускорение. в принципе если матрица поворота тела — \(R\), а тензор инерции в собственной системе координат имеет диагональный вид \(J\), то invInertia = \(RJR^-1\), при этом инвертирование в собственной системе координат делается поэлементно. по сути при умножении на момент : \(RJR^{-1}M\) ты сначала переводишь M в собственную систему координат тела, далее в собственной системе координат покомпонентно делишь получившийся вектор на соответствующие элементы главных осей тензора инерции и далее переводишь обратно в мировую систему координат.

> при расчёте псевдо-скоростей depth принимать как квадрат глубины?
какой квадрат? обычная глубина.

> нужно ли учитывать угловые составляющие в уравнениях для псевдо-скоростей?
конечно, в этом вся фишка. без угловых составляющих тела бы просто линейно расталкивались.