Как разрешить столкновения сложных фигур с помощью SAT?

16

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

Чтобы разрешить столкновения между сложными (невыпуклыми) формами, я думал о некоторой сложной форме, которая состоит из нескольких выпуклых многоугольников. Если столкновение происходит в широкой фазе (например, окружность против круга или AABB против AABB), столкновение будет разрешено путем проверки каждого многоугольника в составной фигуре и каждого многоугольника в другой составной фигуре.

Интересно, каков лучший способ отделить объекты? Наивным подходом было бы просто взять вектор с наибольшей величиной и использовать его для разделения. На следующем рисунке это будет V 2

SAT пример 1

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

СБ пример 2

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

СБ пример 3

Здесь мы будем бесконечно повторяться между состоянием слева и состоянием справа.

Итак, чтобы задать актуальный вопрос здесь: каков разумный подход к этой проблеме? Я предполагаю, что использование составных полигонов для сложных форм является разумной идеей, но мне действительно интересно, как в этом случае следует разрешать коллизии? Как определить тупик, как показано на третьем изображении?

bummzack
источник
Можете ли вы уточнить, для чего вы хотите использовать вектор?
Будет
@Will Вектор должен использоваться для разрешения столкновения, чтобы формы больше не перекрывались. Таким образом, я мог переместить желтый объект по результирующему вектору, и эти два объекта больше не будут сталкиваться.
bummzack

Ответы:

7

Я думаю, что вы, возможно, пытаетесь вставить квадратный ключ в круглое отверстие, применяя SAT таким, какой вы есть, здесь. Очевидно, что он не предназначен для вогнутых и вогнутых столкновений, и, хотя я рекомендую ваши усилия по его адаптации для этой цели, есть соображения, которые делают это маловероятным.

Реализм

Угловой импульс и его побочные эффекты - вот название игры здесь.

Порядок точек контакта важен для реалистичного разрешения столкновений. В реальном мире одна из этих точек всегда будет бить раньше другой. И только в эмуляции этого порядка контактов и результатов каждого «подчинения», представленного этим, вы можете ожидать реалистичного результата в симуляции. Это, в первую очередь, одна из причин, по которой вы разбиваете свою вогнутую поверхность на выпуклую - она ​​позволяет кусочно определить, какая часть ударила первой. Конечно, это также можно подражать в соответствии с моим комментарием под заголовком "Менее реализм".

Ваши выпуклые приборы объединяются, чтобы придать объекту как его контур, так и его центр тяжести (и, конечно, в более сложных симуляциях каждый прибор также может по-разному влиять на плотность). Причина, по которой я упоминаю об этом, заключается в том, что при реалистическом разрешении столкновений вам придется рассчитывать не только линейный, но и угловой импульс, следуя каждому «подчиненному столкновению» ваших контактных точек. Это не так просто, как базовое «раздвигание», которое вы применяете с помощью SAT.

Это полностью меняет природу вашей проблемы, потому что, как вы видите, бессмысленно получать и пытаться использовать 2 или более точек контакта, потому что на самом деле это только первое, что имеет значение. После того, как вы разрешили первое с точки зрения линейного и углового импульса, вам нужно будет пересчитать для дальнейших столкновений, потому что ориентации каждого объекта будут изменены. В дополнение к этому, обнаружение каждого отдельного контакта на этом этапе может потребоваться или не потребоваться на этом же этапе - в зависимости от синхронизации между контактами, когда первая точка контакта объектов касается, применяется последующий линейный и угловой импульс, второй касание точки соприкосновения и так далее.

Меньше реализма

Конечно, если вы совсем не заинтересованы в определении углового импульса, то лучшее, что вы можете сделать с SAT, по сути, будет именно тем, что вы сделали бы, если бы вы обернули эти многоугольники в выпуклые, используя что-то вроде сканирования Грэма: раздвигание с помощью одного разделяющего вектор. Другими словами, как вы продемонстрировали, нет смысла пытаться разрешить три вектора в тандеме. Это самое большое в этой группе.

РЕДАКТИРОВАТЬ в ответ на ваш вопрос

Что вам нужно сделать, если вы хотите упрощенный подход, заключается в следующем:

  • Определите правильное направление смещения. Это проще всего сделать выпуклой оболочкой каждого и определением нормалей к разделительной оси.

  • Теперь вам нужно определить величину смещения . Почему мы не можем просто использовать величину, заданную SAT? Потому что, если вы подумаете об этом, глубины взаимопроникновения будут потенциально больше для выпуклых корпусов, чем для их совмещенных вогнутых корпусов - подумайте о двух E с зубьями друг в друге! Как вы сделали выше, найдите все точки контакта для данного шага, но найдите их параллельно нормали оси, потому что это правильное направление смещения. Теперь определите, какой из этих параллельных векторов перекрытия самый длинный. Переместитесь на это, откажитесь от остальных и перейдите к следующему физическому шагу.

инженер
источник
Я думаю, я понимаю, что вы имеете в виду. Таким образом, в сценарии «меньшего реализма» я не просто оценил бы (самые короткие) векторы, заданные SAT для отдельных полигонов, но мне также пришлось бы рассмотреть другие (более крупные) перекрытия, а в худшем случае использовать выпуклую оболочку?
Bummzack
Смотрите (последнее) редактировать.
инженер