15.3. Исключение сравнений по глубине. Оболочки

В некоторых алгоритмах, чтобы избежать ненужных сравнений между объектами, используются экранные оболочки, введенные в гл. 4 для исключения лишних отсечений. На рис. 15.3 показаны два трехмерных многоугольника, их проекции, а также прямоуголь­ные оболочки, окружающие проекции. Оболочки в этом случае не пересекаются и, следовательно, не надо проверять, не перекрыва­ются ли ребра одного многоугольника с ребрами другого.

чтобы выяснить, например, перекрываются ли два многоугольника в направлении z. На рис. 15.5 показано, как в таком случае исполь­зуются оболочки; здесь оболочкой является бесконечная область, ^ограниченная минимальным и максимальным значениями г для каждого многоугольника. Перекрытие по оси z отсутствует, если

Во всех этих случаях наиболее сложным является нахождение самих оболочек. Их можно определить, просматривая снова список вершин координат и фиксируя наибольшие и наименьшие значения по каждой координате.

Предположим, что многоугольники были подвергнуты преобра­зованию, описываемому матрицей М (разд. 15.2). Тогда проециро­вание на плоскость ху выполняется тривиально путем установки z=0 для каждой вершины. Если бы это преобразование не приме­нялось, для построения проекции потребовалось бы деление на г.

Если прямоугольные оболочки перекрываются, имеет место один из двух случаев (показанных на рис. 15.4): либо проекции много­угольников также перекрываются (случай а), либо этого не происхо­дит (случай б). В обоих случаях для более подробного анализа тре­буются дополнительные сравнения. В случае б с их помощью будет установлено, что на самом деле два многоугольника не перекры­ваются: пересечение оболочек в некотором смысле оказалось «лож­ной тревогой».

Можно воспользоваться оболочками, как в гл. 9, для окружения самих многоугольников, а не их проекций — в этом случае оболоч­ки становятся пространственными. С другой стороны, их можно применить для указания границ в пределах одного измерения,