Построение прямоугольных экстентов Как целесообразно определить прямоугольный экстент для СБС-узла? (Мы имеем в виду, конечно, прямоугольные экстенты в мировых координатах, поскольку у Булева объекта версия в базовых координатах отсутствует.) Предположим, что узел представляет объект А орг В, где А и В - формы, а орг - один из Булевых операторов. Прямоугольный экстент (бокс) для этого объекта должен охватывать весь объект, так что мы должны быть уверены, что луч проходит мимо объекта, если он проходит мимо экстента. Форма объекта может быть достаточно сложной (например, пересечение кругового тора с деформированным кубом), так что будет очень трудно найти самый прилегающий выровненный параллелепипед автоматически, без большого объема вычислений.
Рассмотрим простейший подход и создадим прямоугольный экстент объекта I орг /? из прямоугольного экстента £(!) объекта I и прямоугольного экстента £(/?) объекта /?. Для различных операторов прямоугольный экстент определяется различно:
Введение в трассировку лучей
1. Union (объединение). В качестве прямоугольного экстента берем выровненный параллелепипед, охватывающий одновременно объекты E(L) и E(R). Это эквивалентно E(E(L)uE(R)). (Вопросы. Всегда ли данное выражение равно E(L\jR)7 Не будет ли эффективнее тестировать объекты E(L) и E(R) раздельно? Если луч проходит мимо обоих раздельных экстентов, то обязательно ли он проходит мимо объекта LuR?)
2. Intersection (пересечение). Возьмем в качестве прямоугольного экстента пересечение объектов E(L) и E(R). Пересечение двух выровненных параллелепипедов всегда является также выровненным параллелепипедом, причем его компоненты (left, top, right, bottom, front, back) вычисляются просто. (Как?) (Вопрос. Вы уверены, что луч пройдет мимо объекта LnR, если он проходит мимо объекта E(L)nE(R)?) Экстент вида E(L)nE(R) вероятнее всего будет достаточно плотно прилегать к объекту, если экстенты объектов I и R являются плотными. (Почему?)
3. Difference (разность). В качестве прямоугольного экстента возьмем просто E(L). Это подход с большим запасом, поскольку мы отказываемся от использования преимуществ для того случая, когда разность L-R значительно меньше, чем объект I: может быть, объект R отсекает у I очень много пространства. Однако выполнять более подробный анализ было бы слишком дорого.