Формирование прямоугольных экстентов осуществляется рекурсивно, потому что прямоугольный экстент Булева дерева может быть образован из прямоугольных экстентов его дочерних узлов. Как рассматривалось ранее, для форм прямоугольный экстент может быть сформирован без рекурсии, посредством нахождения «облака точек» для объекта в мировых координатах и построения вокруг этого облака выровненного параллелепипеда. Для каждого типа формы существует свой метод makeBoxExtentO. Каждый такой метод строит прямоугольный экстент, сохраняет его вместе с объектом и возвращает этот экстент для использования другими объектами. Например, для класса UnionBool можно использовать следующую подпрограмму:

Cuboid UnionBool :: makeBoxExtentO {
Cuboid 1ft - left->makeBoxExtent(): Cuboid rt - right->makeBoxExtent(); Cuboid tmp:

tmp.left - minOft.left.rt.left); // form the union // формируем объединение

tmp.top - max(lft.top.rt.top);

etc. for the other four values // и так далее для остальных четырех значений

worldBoxExtent - tmp: // store it in the object // сохраняем его в объекте

return tmp;
}

На предварительном этапе можно было бы вызывать метод makeBoxExtentO для каждого объекта из списка объектов. Когда же этот метод вызывается для Булева объекта, то он создает и сохраняет прямоугольные экстенты как для корневого узла дерева, так и для каждого внутреннего узла.

Создание сферических экстентов Сферические экстенты в мировых координатах строятся примерно таким же способом, как и прямоугольные. Как уже обсуждалось ранее, для форм определяется облако точек в мировых координатах, а сферический экстент - это сфера, наиболее плотно охватывающая это облако. Что касается Булевых объектов, то нам необходимо определиться, как формировать сферический экстент для объединения, разности и пересечения двух объектов.

14.13. Резюме

mm

Для случая разности все просто: используется сферический экстент самого левого объекта. Такой экстент не будет очень плотным, но он подойдет. Можно было бы принять такой же выбор для пересечений, поскольку в случае пересечения очень трудно вычислить истинный сферический экстент. Для объединений, возможно, проще всего объединить облака точек для левого и правого объектов, после чего образовать вокруг получившегося облака одну сферу.

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