Введение в дискретно-ориентированные многогранники для задачи определения столкновений

Введение в дискретно-ориентированные многогранники для задачи определения столкновений

354
ПОДЕЛИТЬСЯ

Обнаружение столкновений (collision detection) виртуальных объектов является достаточно важной частью для задач визуализации.

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

Чтоб облегчить подобные вычисления и не создавать проверку конкретно меж примитивами визуализации (что занимает наибольшее время) были выдуманы технологии ограничивающих размеров (bounding volume), которые разрешают обрисовывать объекты визуализации таковым образом, чтоб проверка на столкновения занимала не такие значимые ресурсы хотя и при маленький утраты точности.
Иными словами, ограничивающие объемы — это обыкновенные геометрические фигуры куда вписываются наиболее сложные объекты.

Bounding volumes
Более нужные ограничивающие объемы:
— Сфера (Sphere).
— Ограничивающий параллелепипед выровненный по координатным осям (Axis-aligned bounding boxes — AABB, уж простите за перевод).
— Объектно-направленный ограничивающий параллелепипед (Object-oriented bounding boxes — OBB)
— Дискретно-направленные многогранники. (Discrete oriented polytopes — k-DOPs)
— и остальные.

Рис 1. Обзор BV.

k-DOP
Каждый из их имеют ряд плюсов и недочетов, но остановимся на k-DOP.

Доходчиво о BV. Рис 2.

Дискретно-направленные многогранники — это заблаговременно известное количество ограничивающих плоскостей и их ориентации. K в заглавии обрисовывает количество таковых плоскостей.
По сущности AABB — это личный вариант k-DOP. К примеру, двухмерный 4-DOP является обыденным квадратом, описывающим некоторый также двухмерный объект.

Двухмерный AABB является таковым же квадратом, как и 4-DOP.
А трехмерный AABB является таковым же кубом, как и 6-DOP.

Но k-DOP так же может применять большее количество плоскостей. И, как было сказано, ориентация таковых плоскостей выбирается заблаговременно и не изменяется.

Ориентации плоскостей определяют через вектора направления, составляющие нормалей которых ограничены обилием {-1, 0, 1}.

К примеру, для обыденного квадрата нужно 4 плоскости с направлениями: (0, 1), (1, 0).
Тут описаны направления 2-ух плоскостей, но которые ограничивают квадрат снизу, сверху, слева и справа. Хотя всего плоскостей 4, потому бывает пишут еще так: (0, ±1), (±1, 0)

Данные нормали разрешают серьезно облегчить вычисления.

Структура
Два значения на одну плоскость, что в итоге выходит достаточно просто обрабатывать и хранить. k-DOP описывается всего только минимальными и наивысшими интервалами (slabs) либо дистанциями.

Интервалы в k-DOP. Рис 3.

Означает будет нужно 2 (k/2) малых и 2 наибольших значений. К примеру для квадрата, как мы запомнили, нужно 4 плоскости (k=4).

Рис 4. 8-DOP описывающий треугольник.

На рисунке №4 треугольник с координатами (3, 1), (5, 4), (1, 5) описан с помощью 8-DOP, т. е. восьмью плоскостями и с векторами направления (1, 0), (0, 1), (1, 1), (1, -1).
Давайте посчитаем интервалы, описывающие этот многогранник.

Берем первую плоскость с направлением (1, 0) и умножаем на координаты:
3*1 + 1*0 = 3
5*1 + 4*0 = 5
1*1 + 5*0 = 1

Малое значение тут 1, а наибольшее 5.
Плоскость (1, 0) определяется значениями 1 и 5.
Для плоскости (0, 1) такие же значения 1 и 5.
Для (1, 1) — 4 и 9.
Для (1, -1) — -4 и 2.

Проверка на пересечение
Раз по последней мере одна плоскость не пересекается, то вся структура также не пересекается.

Лишь раз все интервалы/плоскости пересекаются, тогда пересекается сама структура k-DOP. Но следует увидеть, что описываемый объект может и не пересекаться.
Потому говориться, раз k-DOP структуры 2-ух объектов сталкиваются (collide), то их описываемые объекты могут сталкиваться.

bool overlapped(const KDop& a, const KDop& b, unsigned k)
{
for (unsigned i = 0; i < k / 2; ++i)
{
if (a.min[i] > b.max[i] || a.max[i] < b.min[i])
{
return false;
}
}

return true;
}
Иерархии ограничивающих размеров (Bounding Volume Hierarchy)
Как выяснилось, внедрение ограничивающих размеров дозволяет упростить проверку на столкновения, но теряет незначительно в точности.
Потому для обычных объектов, чтоб исключить не нужные проверки, тестируют поначалу их ограничивающие объемы, как AABB либо k-DOP, а опосля уже перебегают на примитивы.
Но при трудно структурированных объектов используют иерархии ограничивающих размеров. Нередко это просто бинарные деревья, где ноды определяют какой-то объект либо часть объекта, ограниченный каким-то объемом.

Дерево объектов. Рис 5.

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

Традиционно создание дерева происходит одним методом из 3-х.

(top down method) К примеру пока объекты не закончатся либо пока не выполнится какое-то условие. Непростой объект (рутовая нода) делится на наименее сложные (дочерние ноды).

Обыкновенные объекты (ноды) объединяются в наиболее сложные пока не остается один непростой рутовый объект (bottom up method).

Либо добавление объекта в уже сформированное дерево (insertion method).

При сбалансированном таком дереве сложность поиска равна трудности остальных сбалансированных бинарных деревьях поиска — O(logN).

Более увлекательный вопросец каким же методом разделять объект на дочерние.
Аспект сопоставления частей объекта, чтоб помещать в левое либо правое поддерево могут различаться.
Более обычным является обычное деление места пополам: все объекты с координатами выше определенной идут в правое поддерево, все другие в левое.

Также может быть подсчет среднего значения, к примеру по избранной оси.
Либо хоть каким иным методом. Либо построение медианы.

Другое абстрактное дерево объектов. Рис 6.

Поиск коллизий
Поиск столкновений на 2-ух иерархических структур, в свою очередь, тоже может быть реализован различными методами.

Чтоб проверить на пересечения 2-ух объектов, нужно просто сделать дерево (BVH-tree) на каждый объект, где нода описывает свою часть объекта через какой-то ограничивающий размер.

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

Дерево рекурсии сравнения объектов. Рис 7.

Иллюстрации и информация
Real-Time Collision Detection, Volume 1. — Треугольничик и нужный абзац про многогранники. 1. Christer Ericson.
— Экскаватор, кролик и совершенно просто про коллизии, иерархии. 2. Bounding Volume Hierarchies for Collision Detection. Hamzah Asyrani Sulaiman and Abdullah Bade.
3. Кратко и тезисно про главные вопросцы иерархических структур ограничивающих размеров. Johannes Mezger. — Дерево и интервалы многогранников. Collision Handling in Dynamic Simulation Environments: Bounding Volume Hierarchies.
Game Programming. Introduction To Collision Detection — Титульное завлекалово и шедевр с человечками. Rolf Lakaemper. Обычный обзор по определению коллизий. 4.
5. Пример обычный реализации поиска пересечений либо коллизий с помощью BVH дерева и дискретно-нацеленных многогранников. habrahabr.ru