Конгер Д.
Физика для разработчиков компьютерных игр
стр. 253

ВЫРОВНЕННЫЕ ПО ОСЯМ ОГРАНИЧИВАЮЩИЕ БЛОКИ И ОРИЕНТИРОВАННЫЕ ОГРАНИЧИВАЮЩИЕ БЛОКИ

Если ограничивающие блоки достаточно точны для вашей игры, они могут работать очень быстро. В играх чаще всего используются ограничивающие блоки двух типов. Первый - это выровненные по осям ограничивающие блоки (axis-aligned bounding boxes - ААВВ).

Чаще всего ААВВ хранятся в специальной структуре данных, называемой октальным деревом (octree). Преимущество ААВВ в том, что их ребра всегда параллельны осям х, у, z глобальной системы координат. Поэтому, проверяя есть ли столкновение, программа просто проверяет координаты х, у, z точки столкновения - попадают ли они в границы ААВВ? Такие проверки выполняются быстро.

Что такое октальные деревья?

Во всех обсуждениях методов обнаружения столкновений всегда упоминаются октальные деревья (octree). Эти деревья отличаются от других типов деревьев. Например, в бинарных деревьях у каждого узла может быть один левый и один правый дочерний узел, поэтому такое дерево легко изобразить на плоскости - это фактически 20-структуры. Октальные деревья -это ЗЭ-структуры.

Представьте себе, что мы разрезали лазером ЗЭ-фигуру на прямоугольные блоки. Предположим, что все блоки остаются на своих местах. Собственно говоря, мы поделили пространство, в котором находилась фигура, на прямоугольные блоки. А теперь проиндексируем блоки так, чтобы они образовали древовидную структуру. В дереве будет указатель на каждый блок. Собственно говоря, дерево предоставит способ быстро переходить от одного блока к другому, соседнему блоку в 3D. Именно для этого предназначены октальные деревья.

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

Другой тип ограничивающих блоков - ориентированные (oriented bounding boxes - ОВВ). Как и в ААВВ, в ОВВ помещаются части ограничиваемого твердого тела. ОВВ размещаются так, чтобы как можно теснее ограничить эти части. Однако в отличие от ААВВ, ОВВ размещаются в локальной системе координат тела и вращаются, перемещаются и масштабируются вместе с этим телом.

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

Новости
Исследование: Треть населения Земли играют в видеоигры
Специалисты компании NewZoo провели исследование и пришли к выводу, что треть населения Земли или 2,3 млрд человек играют в видеоигры.
Антивирусы и облачные сервисы портят сохранения Dark Souls Remastered
Вчера комьюнити-менеджер Bandai Namco под ником Izmar подтвердил проблему в Steam, посоветовав ограничить доступ антивирусов и других программ вроде облачных сервисов Google и Amazon к файлам ремастера Dark Souls.