Теорема о разделяющей оси с несколькими полигонами?

Я пытаюсь реализовать теорему о разделяющей оси в C #. У меня есть функция, которая может рассчитать минимальный вектор перевода между двумя полигонами. Тем не менее, я не могу создать функцию, которая вычисляет минимальный вектор перевода между одним полигоном и несколькими другими полигонами. Честно говоря, я работал над этим в течение нескольких месяцев, и я не приблизился к решению и не смог найти решение в Интернете. Всегда есть несколько крайних случаев, которые не возвращают правильный результат, что приводит к ошибкам с высоким приоритетом в моей игре.

Вот общие крайние случаи, которые не работают правильно:

крайние случаи

Есть ли известное решение этой проблемы? Все, что я могу найти, это люди, говорящие «просто выполнить SAT на каждом полигоне», но это редко дает минимальный вектор перевода.

Любая помощь будет высоко ценится.

collision-detection separating-axis-theorem user40698
источник

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

Эндрю Рассел

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

Ричард Тингл

Ответы:

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

Тот факт, что ваш редактор или инструменты используют меньшие отдельные фигуры для построения уровня, не должен влиять на время выполнения.

Немного более простой подход - просто удалить «внутренние» края базовых фигур. Для вашего последнего примера между полами "floor" есть два ребра; игнорируйте их во время обнаружения столкновений.

Вы можете найти лучшие рисунки и некоторые идеи реализации, прочитав раздел 4.5 (ребра и цепочки ребер) в документации Box2D .

Шон Миддледич
источник

Использование ребер (в частности, ребер, это немного лучше с цепочками ребер) имеет главный недостаток, заключающийся в том, что физическим объектам становится очень легко проскальзывать внутри геометрии уровня.

Эндрю Рассел

@AndrewRussell: этих проблем можно избежать с помощью обычных туннельных исправлений. Убедитесь, что ваши движущиеся объекты имеют достаточно приличный объем / площадь, сохраняйте их максимальную скорость на кадр достаточно низкой, чтобы они не могли перемещаться более чем на половину своего кратчайшего размера (или делайте это несколько раз, если вам нужно, чтобы двигаться быстрее), избегайте действительно острые расщелины и тому подобное в геометрии вашего уровня, повторяйте разрешение несколько раз, пока вы не достигнете «безопасного» конечного местоположения и т. д.

Шон Миддледич