<+«К-<О=0. (3.21).

Отсюда сразу же находится значение а. После чего оно подставляется в (3.20) и результат умножается скалярно на вектор dir, откуда получаем

'1=Л0+(Л,-^)7^Г- (3.22)

Аналогичным образом находится значение параметра t2, соот-ветствуЕощее пересечению прямой ребра и,и2.

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

Можно заметить, что если все значения концов получающихся отрезков сдвинуты на одну и ту же величину, то результат пересечения отрезков от этого не изменится. Это позволяет нам использовать вместо (3.19) упрощенную формулу

PKi=(dir,u,). (3.23)

Реализация этого алгоритма для случая произвольных выпуклых многоугольников содержится в класса Polygon3D.

Иерархические структуры

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

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

Таким образом, узел подобного дерева может быть представлен при помощи следующего класса:

Простейшие геометрические алгоритмы и структуры

class BvhNode
{
protected:
Array objects; BoundingBox box; int numChildren; BvhNode * *node;

При этом проверка какого-либо заданного объекта со всеми объектами дерева обычно начинается с корня. Если ограничивающее тело проверяемого объекта не пересекается с ограничивающим телом рассматриваемого узла, то пересечения нет и проверка на этом завершена (рис. 3.18).

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


⇐ Предыдущая| |Следующая ⇒