У вас когда-нибудь были две прямоугольные призмы произвольного размера и размера, и вы хотели проверить, пересекаются ли они? Я знаю, что у меня есть! Просто старый AABB не поможет, так как очень плотно прилегающие прямоугольные призмы должны быть обнаружены и отклонены. Есть некоторые подлые конфигурации (например, представьте себе очень-очень маленькую прямоугольную призму, расположенную прямо над поверхностью массивной и сильно перекошенной прямоугольной призмы), которые также необходимо разузнать.

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

Итак, как это работает? Хорошо, сначала давайте подумаем о проблеме в двух измерениях. Есть 3 эскалирующих теста, которые мы можем запустить, чтобы проверить, перекрываются ли эти повернутые поля. Первый заключается в создании двух блоков, выровненных по осям, и выполнении быстрой проверки AABB в качестве широкой фазовой проверки. Второй — перебрать точки одного из ящиков и проверить перекрытие. Если в поле есть какие-либо точки, поле перекрывается. Если это неубедительно, мы проводим последний и самый дорогой тест. Во-первых, мы выбираем одно из полей, чтобы определить набор осей в любых измерениях, с которыми мы работаем. По сути, мы вращаем весь мир таким образом, что одна коробка теперь идеально выровнена с осью. Затем мы проецируем на каждую ось. Если ни одна из проекций не перекрывается, мы можем гарантировать, что прямоугольники тоже не перекрываются.

Это в значительной степени прямое попадание в третье измерение для первых двух тестов. Однако в третьем случае вместо проецирования 1D-линии из 2D-формы, как указано выше, мы проецируем 3D-форму на 2D-поверхность. Для этого мы разложим повернутую трехмерную прямоугольную призму на составные треугольники.

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

И вот мы идем! Что это было за время. Но это работает, и почти во всех случаях, которые вы только можете себе представить. Вы можете найти код Unity3D, демонстрирующий это здесь.

Первоначально опубликовано на http://lrtw.net.