Коллизии повернутых прямоугольников

Первый раз алгоритм для обнаружения коллизий между двумя повернутыми прямоугольниками я применил внезапно не в движке, а на работе.

Когда-то давно я работал над графических редактором для построения электросхем в браузере. У меня была задача реализовать авторасстановку элементов так, чтобы они не перекрывали друг друга. Каждая деталь на схеме могла сопровождаться набором картинок, изображающих изделие с разных ракурсов и чтобы пользователю редактора не нужно было все расставлять в ручную, заказчик попросил добавить автоматизацию. Также, нужно было предусмотреть функцию авторасстановки для уже существующих электросхем, для элементов, которые были расставлены неаккуратно.

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

Один из популярных алгоритмов построен на теореме о разделяющей оси (плоскости для 3D). Суть в том, что фигуры не пересекаются если существует хотя бы одна ось, при проекции на которую, полученные отрезки не пересекаются. В качестве осей часто предлагается использовать нормали к граням тестируемых многоугольников. Подробнее про реализацию можно почитать здесь если интересно.

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

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

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

Для первой ситуации нужно проверить лежит ли центр окружности в многоугольнике. Алгоритмы я находил в интернете самые разные, но выбрал тот, что мне был наиболее понятен. Для проверки из точки выпускается луч и подсчитывается сколько раз луч пересекает контур фигуры. Если четное количество раз, то точка лежит снаружи, если нечетное – внутри. Подробно на реализации останавливаться не буду, текста уже получается очень много. Кому интересно вот ссылка на статью на которую я опирался.

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

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