Войти
ПрограммированиеФорумФизика

MPR - умный выбор начальной точки построения портала

Advanced: Тема повышенной сложности или важная.

#0
(Правка: 9:40) 9:38, 30 ноя. 2020

Доброго времени суток.

Столкнулся с необходимостью грамотного выбора начальной точки построения портала для MPR (Minkowski Portal Refinement).
Если для тел, которые имеют сходные размеры по XYZ, допустимо брать центр тела, то для некоторых случаев это неприемлимо.

Пример, бокс сталкивается со стеной, зеленая линия - это вектор проникновения, при указания начала построения портала в точке C1 (совпадает с центром стены):
Изображение

Контактная площадка не строится, бокс пролетает сквозь стену (а ведь он даже наполовину не погрузился в стену). Видео, где видна суть:

Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры


Если же выбрать центр построения портала для стены в точке C2, то все работает правильно.

Более того, если очень грамотно выбирать "центры", то это сулит неимоверный профит (по крайне мере, для этого частного случая) - даже если бокс на большой скорости пролетит сквозь стену практически насквозь - все равно он будет вытолкнут правильно:

Изображение


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


#1
(Правка: 16:38) 16:33, 28 апр. 2021

В общем случае всегда верного решения нет, т.к. MPR - это алгоритм локального поиска.
Кстати, пример с длинным и коротким боксами - классический случай, когда направление между центрами геометрий в качестве начальной догадки приводит алгоритм локального поиска к решению, сильно отличающемуся от глобального minimal translation vector.

Более-менее хорошей догадкой для MTV в конкретном случае (пара статическое-динамическое тел) может быть вектор, обратный вектору линейной скорости динамического тела (синяя стрелка на картинке). Но это при условии, что тело не очень быстро вращается. В качестве начальной точки MPR можно выбрать:

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

либо разность support-point-ов по направлению луча (получим точку на границе разности Минковского, направление от точки к origin-у будет близким к выбранному нами вектору). На картинке они - зеленые.

Points | MPR - умный выбор начальной точки построения портала

Но все алгоритмы локального поиска - это лотерея.

По факту существует лишь 2 полноценных алгоритма поиска MTV - это SAT и EPA. EPA очень страдает от проблем с вычислительной точностью, а SAT подходит только для многогранников и по факту является брутфорсом, а не алгоритмом оптимизации. За последние 20 лет ничего лучше увы так изобрести и не удалось.

#2
(Правка: 18:34) 18:33, 28 апр. 2021

Shalom
> По факту существует лишь 2 полноценных алгоритма поиска MTV - это SAT и EPA.
> EPA очень страдает от проблем с вычислительной точностью, а SAT подходит только
> для многогранников и по факту является брутфорсом, а не алгоритмом оптимизации.
> За последние 20 лет ничего лучше увы так изобрести и не удалось.
Я решил проблему за счет жутких костылей - каждое тело у меня теперь имеет свойство "круглое" или "вытянутое". В зависимости от этого свойства, соответственно, не корректируется или корректируется "центр" тела. Выглядит это в плане кода ужасающе криво, но, тем не менее, работает с достаточной для меня точностью. Иногда с некоторыми физическими артефактами, но не критичными.

#3
(Правка: 15:59) 15:53, 29 апр. 2021

MikeNew
на иллюстрации, которую ты привёл, любой локальный алгоритм поиска должен выдать правильный ответ.
для MPR начальные условия должны задаваться тремя точками (для построения портала треугольника), а не одной. поэтому ничто не мешает, например, построить кастовать по одной точке в направлениях +-X, +-Y и +-Z, чтобы из них выбрать самый подходящий начальный портал.

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

#4
(Правка: 17:08) 16:48, 29 апр. 2021

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

Что касается именно вырожденных треугольников (если я правильно понял о чем ты) - эту проблему я заметил при столкновении со сферой, из-за нее нормаль столкновения определялась неправильно. Вот только поскольку дело касалось сферы это оказалось совсем не страшно, поскольку "контактная точка" считалась правильно, а значит и нормаль можно посчитать. Других проблем от вырожденных треугольников у меня не возникало, по крайней мере таких которые бы как-то мешали.

#5
(Правка: 17:46) 17:35, 29 апр. 2021

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

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

vec3 p = ...; //любая точка за пределами CSO используется как начальное условие
while(!converged)
{
  vec3 delta = GJK(MinkowskySum(cso, -p));
  p = normalize(delta) * dot(normalize(delta), p - delta);
}

такая схема на каждой итерации кастует устойчивый и быстрый GJK, чтобы итеративно притягивать произвольную точку снаружи CSO к началу координат, гарантированно не пересекая это CSO. это делается путём последовательного проецирования точки на "самую удалённую" плоскость, которая ищется через GJK и полученная полуплоскость гарантированно полностью содержит в себе CSO, поэтому при проекции мы его гарантированно не пересечём. можно доказать, что эта схема монотонно сходится к некоторому локальному минимуму. на практике она сходится к нему не просто быстро, а очень быстро, потому что каждый GJK каст стартует с симплекса, на котором закончил предыдущий каст, а если локальный минимум был найден на прошлом кадре, то не понадобится больше 1 GJK каста. короче, я не видел описания этой схемы литературе, хотя алгоритм достаточно очевидный, поэтому наверняка его кто-то до меня придумал, но у меня весь destruction на нём работал, включая случаи со злыми геометриями вроде палок и длинных катающихся эллипсоидов.

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