Проверка столкновений: Minkowski Separating Axis Theorem

Что такое столкновения и зачем нужна эта теорема?

Представь, что в твоей игре есть два объекта — например, герой и враг. Чтобы понять, столкнулись ли они, нужно проверять их пересечение. Самый простой способ — использовать bounding boxes (ограничивающие прямоугольники) и проверять их перекрытие. Но что, если объекты сложной формы? Здесь на помощь приходит Minkowski Separating Axis Theorem (SAT) — элегантный математический способ проверки столкновений между выпуклыми фигурами.

🎯 Запомни: SAT работает только с выпуклыми фигурами. Выпуклая фигура — это такая, у которой нет «впадин». Все отрезки, соединяющие любые две точки внутри фигуры, лежат внутри неё.

Примеры выпуклых фигур: квадрат, круг, треугольник, правильный многоугольник. Невпуклые (вогнутые) фигуры нужно разбивать на выпуклые части для использования SAT.

Суть теоремы: ось разделения

Основная идея проста: если две выпуклые фигуры не пересекаются, между ними можно провести прямую линию (или гиперплоскость в 3D), которая их разделит. Более того, эту линию можно выбрать так, чтобы она была перпендикулярна одной из сторон фигур или одной из осей их «разности».

📘 Простыми словами: Если найдётся хотя бы одна ось (направление), на которую спроецированы фигуры, и их проекции не перекрываются, то фигуры не пересекаются. Если же на всех осях проекции перекрываются, то фигуры столкнулись.

Разность Минковского: волшебный трюк

SAT тесно связана с понятием разности Минковского. Не пугайся этого термина! Это просто способ «вычитать» одну фигуру из другой.

Представь две фигуры A и B. Их разность Минковского определяется так:

A ⊖ B = { a - b | a ∈ A, b ∈ B }

Где ∈ означает «принадлежит» фигуре.

Ключевое наблюение: две фигуры A и B пересекаются тогда и только тогда, когда начало координат (точка 0,0) содержится в их разности Минковского A ⊖ B.

✨ Визуализация: Если представить, что ты обводишь фигуру B вокруг фигуры A, разность Минковского — это область, которую покрывает центр фигуры B. Если центр B (начало координат) находится внутри этой области — есть столкновение!

Алгоритм проверки столкновений с помощью SAT

Вот пошаговый алгоритм для 2D:

1. Найди потенциальные оси разделения:
   • Нормали (перпендикуляры) всех рёбер первой фигуры
   • Нормали всех рёбер второй фигуры
2. Для каждой оси:
   1. Спроецируй все вершины первой фигуры на эту ось
   2. Спроецируй все вершины второй фигуры на эту ось
   3. Найди минимальную и максимальную точки проекций для каждой фигуры
   4. Проверь, перекрываются ли интервалы проекций
3. Если на какой-то оси интервалы не перекрываются — фигуры не пересекаются, можно прекращать проверку.
4. Если интервалы перекрываются на всех осях — фигуры пересекаются.

Практический пример: два треугольника

Давай рассмотрим простой пример с двумя треугольниками.

Условие задачи:

Есть два треугольника:

• Треугольник A с вершинами: (1, 1), (3, 1), (2, 3)
• Треугольник B с вершинами: (2, 2), (4, 2), (3, 4)

Определить, пересекаются ли они, используя SAT.

Решение:

1. Найдём рёбра и нормали для треугольника A:

• Ребро 1: (1,1)-(3,1) → вектор (2,0) → нормаль (0,1) или (0,-1)
• Ребро 2: (3,1)-(2,3) → вектор (-1,2) → нормаль (2,1) или (-2,-1)
• Ребро 3: (2,3)-(1,1) → вектор (-1,-2) → нормаль (-2,1) или (2,-1)

2. Найдём рёбра и нормали для треугольника B:

• Ребро 1: (2,2)-(4,2) → вектор (2,0) → нормаль (0,1) или (0,-1)
• Ребро 2: (4,2)-(3,4) → вектор (-1,2) → нормаль (2,1) или (-2,-1)
• Ребро 3: (3,4)-(2,2) → вектор (-1,-2) → нормаль (-2,1) или (2,-1)

3. Потенциальные оси разделения: (0,1), (2,1), (-2,1), (0,-1), (-2,-1), (2,-1)

4. Проверим ось (0,1):

• Проекция A: min=1, max=3
• Проекция B: min=2, max=4
• Интервалы [1,3] и [2,4] перекрываются [2,3]

5. Проверим ось (2,1):

• Проекция A: min=1*2+1*1=3, max=3*2+1*1=7
• Проекция B: min=2*2+2*1=6, max=4*2+2*1=10
• Интервалы [3,7] и [6,10] перекрываются [6,7]

6. Проверим ось (-2,1):

• Проекция A: min=1*(-2)+1*1=-1, max=3*(-2)+1*1=-5
• Проекция B: min=2*(-2)+2*1=-2, max=4*(-2)+2*1=-6
• Интервалы [-5,-1] и [-6,-2] перекрываются [-5,-2]

Поскольку на всех проверенных осях проекции перекрываются, треугольники пересекаются.

💡 Совет: На практике нужно нормализовать оси (привести к длине 1) для корректного сравнения проекций, но в этом примере мы опустили этот шаг для простоты.