<+«К-<О=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).
В противном случае проверяется на пересечение каждый из дочерних узлов данного узла. При этом осуществляется спуск по дереву от корня к листьям. Когда проверка доходит до листа дерева, осуществляется явная проверка исходного объекта со всеми объектами, содержащимися в листе дерева. При этом мы автоматически отбрасываем все те объекты, которые «ведомо не могут иметь пересечения с рассматриваемым объектом.