Удаление невидимых поверхностей
но*. (Полезно вырезать из картона несколько образцов граней и поэкспериментировать с их различными ориентациями.) Ситуация на рис. 13.6, в еще более сложна: грани А и В проникают друг в друга. В данном случае алгоритм беспечного художника бездумно нарисует грань В поверх грани Л.
Рис. 13.6. Упорядочивание граней по глубине Таким образом, алгоритм беспечного художника не в состоянии определить, какая часть одной грани закрывает другую. Недопустимо просто рисовать грани целиком одну поверх другой на основе единственного критерия, такого как максимальная глубина. В разделе «Алгоритм сортировки по глубине» мы исправим алгоритм художника путем выполнения дополнительных проверок участвующих в нем граней. Усовершенствованный алгоритм работает правильно, однако он значительно сложнее, чем исходный.
Практические упражнения
13.3.1. Есть ли перекрывание?
Покажите, что одна грань не обязательно закрывает другую, даже если их лг- иу-экстенты перекрываются.
13.3.2. Когда алгоритм беспечного художника работает?
Укажите класс сеток, для которого данный алгоритм работает для любой точки зрения на единственный объект. (Например, работает ли он в случае выпуклых объектов?) Какое условие приводит к краху алгоритма для объектов, не принадлежащих к этому классу?
13.3.2. HSR с использованием деревьев двоичного разбиения пространства Элегантный метод удаления невидимых поверхностей основан на применении деревьев двоичного разбиения пространства (binary-space partition - BSP) [Fuchs, 69, Fuchs, 70]. На предварительном этапе полигоны из массива faces [] особым образом организовываются в структуру данных двоичного дерева, когда определенные грани разбиваются на две части, й при рисовании сцены с корректно удален13.3. HSR-методы со списками приоритетов_809
ными невидимыми поверхностями нужно методично «обойти» такое дерево. BSP-дерево обходится (is traversed) путем поочередного посещения каждого его узла (в определенном порядке) и рисования грани, обнаруженной в этом узле.