Удаление невидимых ребер

После первого этапа удаления нелицевых отрезков необходимо выяснить, существуют ли такие отрезки, кото­рые экранируются другими телами в картинке или в сцене. Для этого каждый оставшийся отрезок или ребро нужно сравнить с другими телами сцены или картинки.

Возможны следующие случаи:

¨ Грань ребра не закрывает. Ребро остается в списке ребер.

¨ Грань полностью закрывает ребро. Ребро удаляется из списка рассматриваемых ребер.

¨ Грань частично закрывает ребро. В этом случае ребро разбивается на не­сколько частей, видимыми из кото­рых являются не более двух. Само ребро удаляется из списка рассматриваемых ребер, но в список проверяемых ребер добавляются те его части, которые данной гранью не закрываются.

Для оптимизации используется приоритетная сортировка (z -сортировка) и простого ми­нимаксного или габарит­ного с прямоугольной объемлющей оболочкой тестов позволяет удалить целые группы или кластеры отрезков и тел. Например, если все тела в сцене упорядочены в некотором приоритетном списке, использующем значения z ближайших вершин для представления расстояния до наблюдателя, то никакое тело из этого списка, у которого ближайшая вершина находится дальше от наблюдателя, чем самая удаленная из концевых точек ребра, не может закрывать это ребро. Более того, ни одно из оставшихся тел, прямоугольная оболочка которого расположена пол­ностью справа, слева, над или под ребром, не может экранировать это ребро. Использование этих прие­мов значи­тельно сокращает число тел, с которыми нужно сравнивать каждый отрезок или ребро. Рис. 5.10. иллюстрирует работу алгоритма.

Рис. 4.10 Результат работы алгоритма Робертса