Проверка на пересечение двух OBB

Одним из распространенных классов ограничивающих тел (bounding volume) являются прямоугольные параллелепипеды (bounding box).

При этом встречаются два типа прямоугольных параллелепипедов - AABB (Axis-Aligned Bounding Box) и OBB (Oriented Bounding Box).

Первый тип (AABB) использует ребра, параллельные осям координат. За счет этого заметно упрощаются все операции над такими ограничивающими телами. Однако это же и ограничивает свободу и приводит к появлению явно неоптимальных ограничивающих тел (рис 1).

Рис 1. Пример неудачного использования AABB.

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

Рассмотрим реализацию для OBB одной из базовых операций - проверки двух OBB на пересечение. Существует теорема (separating axis theorem), утверждающая, что два OBB не пересекаются тогда и только тогда, когда существует такая прямая l, что проекции этих OBB на нее не пересекаются (рис 2).

Рис 2. Теорема о разделяющей прямой.

На самом деле нет никакой необходимости проверять все возможные прямые (направления), достаточно лишь проверить всего лишь 15 направлений. Пусть каждый из OBB (A и B) задается своим центром (C_A и C_B), набором из трех ортонормированных векторов и размерами от центра.

Тогда достаточно проверить в качестве направления l разделяющей прямой 6 векторов, задающих ребра обоих OBB (a₁,...b₃) и все их попарные векторные произведения [a_i,b_j], т.е. всего 15 направлений.

Начать лучше всего с самого простого случая - векторов a₁,...b₃, так как для них проверки получаются значительно проще.

Рис 3. Проверка на пересечение проекция на прямую с направлением l.

Пусть задано произвольное единичное направление l. Тогда достаточно сравнить модуль (t,l) (расстояние между проекциями на l точек C_A и C_B) и r_A+r_B. Справедливы следующие формулы:

Пусть l = a_k. Тогда

Тогда соответствующие 6 проверок примут следующий вид

Здесь через r_i,j обозначены элементы следующей матрицы:

Пусть теперь l = [a₁,b₁]. Тогда воспользуемся равенством

Отсюда легко получаем, что

Тогда соответствующая проверка (первая из последних 9) примет следующий вид:

Аналогично записываются и оставшиеся 8 проверок. Если хотя бы для одной из проверок неравенство не выполнено, что данные OBB пересекаются. Если же все 15 неравенств выполнены, то пересечения нет.

Построение OBB по набору точек

Пусть у нас задан набор точек p₁,p₂,...,p_n и нужно по ним построить содержащую их OBB. Фактически задача сводится к нахождению центра C и трех ортонормированных векторов a₁,a₂,a₃, задающих направления ребер.

В качестве центра обычно берется среднее арифметическое из всех точек:

После этого строится так называемая матрица ковариации M, собственные вектора которой и используются в качестве направлений для ребер: