1. Bounding Volume
Intro
Очень простая идея, которая очень сильно ускоряет процесс поиска коллизий - это использование ограничивающих объемов. Те мы ассоциируем фигуру с его упрощенным представлением. Если не пересекаются ограничивающие объемы, то и сами фигуры не будут пересекаться.
Таких видов объемов много. Для ленивых, которые не хотят читать весь список, переходите сразу на AABB. Они чаще всего используются.
Bounding Sphere
Bounding sphere - это сфера, которая ограничивает оригинальный объект. Ее плюс в том что нужно мало данных для хранения и ее не нужно перестраивать при повороте объекта.
Для определения коллизий boundings sphere редко используются. Вот например они используются для потимизации рендера в Three.js
Выглядят эти сферы как-то так:
Для простейших форм, посчитать такие сферы, достаточно просто. Но для вогнутых фигур посчитать оптимальную сферу, уже сложнее. Для этого есть 2 популярных алгоритма.
BS по AABB
Строим ограничивающий прямоугольник (AABB): Ищем минимальную и максимальную координату объекта по каждой оси. и по AABB строим сферу. Это самый простой способ, но часто не оптимальный. Например, для форм близких к треугольнику, сфера будет сильно отличаться от описанной около треугольника.
Алгоритм Риттера
Делаем два прохода по всем вершинам объекта:
- Находим минимальную и максимальные точки по каждой оси. Считаем центр сферы как среднее арифметическое между минимальной и максимальной точкой. А диаметр сферы как максимальное расстояние между точками.
- Второй раз проходимся по всем точкам объекта и увеличиваем радиус сферы, чтобы она описывала все вершины объекта.
Автор статьи говорит, что максимальная ошибка этого алгоритма 5 процентов.
OBB
Oriented bounding box - это прямоугольник, который ограничивает оригинальный объект, но может быть повернут в пространстве. Если фигура обладает известными осями симметрии, то OBB можно достаточно просто построить, но в общем случае это сложная задача.
AABB
Axis-aligned bounding box - это прямоугольник, который ограничивает оригинальный объект и выровнен по осям координат.
Супер простая идея, которая чаще всего встречается почти всех движках bullet, jolt и box2d
Выглядит это как-то так:
Существует несколько способов генерации AABB. И это всегда трейдофф между скоростью и точностью.