Заметим, что изменение видимости отрезков может происходить лишь в их концах. Поэтому достаточно проанализировать взаимное расположение концов отрезков с учетом глубины. Один из вариантов такого подхода использует специальные таблицы для отслеживания концов отрезков:
таблица ребер (Edge Table), где для каждого негоризонтального ребра (горизонтальные ребра игнорируются) хранятся минимальная и максимальная у-коор динаты, л-координата, соответствующая вершине с наименьшей у-координатой,
10. Удаление невидимых линий и поверхностей шаг изменения л" при переходе к следующей строке и ссылка на соответствующую грань;
таблица граней (Facet Table), где для каждой грани помимо информации о плоскости, проходящей через эту грань, и информации, необходимой для ее закрашивания, хранится также специальный флажок, устанавливаемый в нуль при обработке очередной строки;
таблица активных ребер (Active Edge Table), содержащая список всех ребер, пересекаемых текущей сканирующей плоскостью, и проекции точек пересечения
- (л'-координаты при параллельном проектировании). Все ребра в таблице активных ребер сортируются по возрастанию х.
Для удобства определения ребер, пересекаемых текущей сканирующей плоскостью, список всех ребер обычно сортируется по наименьшей ^-координате.
Для граней, представленных на рис. 10.39, таблица активных ребер выглядит следующим образом:
|
У] |
AB, АС |
|
У2 |
AB, АС, FD, FE |
|
Уз |
AB, DE, ВС, FE |
|
У4 |
AB, DE, ВС, FE |
|
У5 |
AB, ВС, DE, FE |
Ребра из списка активных ребер обрабатываются по мере увеличения х.
При обработке линии у{ таблица активных ребер состоит только из двух ребер -AB и АС. Первым обрабатывается ребро AB, при этом флаг соответствующей грани (ABC) инвертируется. Тем самым мы "входим" в эту грань, т. е. следующая группа пикселов является проекцией этой грани.
Поскольку в данной строке пересекается лишь одна грань, то очевидно, что она является видимой и, значит, весь отрезок между точками пересечения секущей плоскости с ребрами AB и ВС необходимо закрасить в цвета этой грани. При обработке следующего отрезка флаг грани ABC снова инвертируется и становится равным нулю - мы выходим из этой грани.