17.3. АЛГОРИТМ РАЗДЕЛЕНИЯ ВИДИМЫХ И НЕВИДИМЫХ ЭЛЕМЕНТОВ СЦЕНЫ, ОСНОВАННЫЙ НА ИСПОЛЬЗОВАНИИ ТЕТРАРНОГО ДЕРЕВА
Этот алгоритм обрабатывает фрагменты изображения, соответствующие вершинам тетрарного дерева (см. разд. 6.4). Если в пределах некоторого фрагмента границы объекта отсутствуют, то цвет этого фрагмента можно определить с помощью простого упорядочения по направлению z. Именно так обстоит дело с фрагментами 11, 22, 24, 42, 44 и 33 на рис. 17.5 (эти фрагменты относятся
Рис. 17.5. (см. скан) Иллюстрация к работе алгоритма удаления невидимых линий, основанного на использовании тетрарного дерева. Жирными линиями изображены проекции границ объекта, а тонкими линиями выделены квадратные наблюдаемые фрагменты изображения, соответствующие первым трем уровням тетрарного дерева
к фону изображения). Если же на фрагменте обнаруживается граница, то он подвергается разбиению на подфрагменты посредством спуска по тетрарному дереву. На рис. 17.5 представлено разбиение, соответствующее спуску на два уровня относительно исходного разбиения изображения на фрагменты. В число однородных в результате этого разбиения попадают фрагменты 1413, 1431 и т. д. В конечном счете последовательное разбиение приводит к уровню, соответствующему отдельным пикселам. Пикселам, расположенным на границе, значение (яркость или цвет) может присваиваться в зависимости от значений соседних пикселов. Этот процесс, естественно, очень напоминает процедуру сегментации, в которой в качестве предиката однородности области используется высказывание «отсутствие границы в области». (Исторически дело обстоит как раз наоборот, см. разд. 17.8). Границы, которые не видны, устраняются автоматически, поскольку области, расположенные по обе стороны от них, имеют один и тот же цвет, а именно — цвет загораживающей поверхности.
Основная часть этого алгоритма связана с определением того, пересекается ли грань с наблюдаемым фрагментом изображения (окном). Существуют три возможности: а) грань покрывает фрагмент изображения; б) грань пересекается с фрагментом изображения или расположена внутри него; в) грань и наблюдаемый фрагмент находятся в разных частях изображения и не пересекаются (рис. 17.6). Решение можно найти, решив задачу разрезания для границ 
и фрагмента 
с помощью применения алгоритма 15.2 ко всем сторонам грани. Эту процедуру можно упростить, так как алгоритму не нужна информация о результате пересечения многоугольников — важно знать пересекаются они или нет (см. задачу 17.3).
Рис. 17.6. Иллюстрация к работе алгоритма удаления невидимых линий, основанного на использовании тетрарного дерева: допустимые случаи взаимного расположения грани и наблюдаемого фрагмента изображения; значения величины К, получаемые в результате применения процедуры 
равны двум (а), единице б) и нулю (в)
Рассмотрим процедуру 
реализующую этот метод и выдающую в качестве результата следующие значения: 2, если имеет место случай а) и грань 
покрывает фрагмент 
как показано на рис. 17.6, а; 1, если имеет место любая из двух конфигураций на рис. 17.6, б, т. е. грань 
покрывается фрагментом 
или пересекается с ним; 0, если имеет место случай в), т. е. грань
и фрагмент 
находятся на некотором расстоянии друг от друга (рис. 17.6, в).
Работа алгоритма начинается с того, что изображение разбивается на фрагменты, соответствующие листьям тетрарного дерева. Для каждого наблюдаемого фрагмента заводятся списки: список 
содержит перечень всех граней, имеющихся на изображении и могущих иметь пересечение с соответствующей вершиной (фрагментом); список М содержит те грани, которые покрывают соответствующую вершину (фрагмент). В исходном состоянии список М — пустой, а список 
содержит все грани; по окончании выполнения алгоритма пустым оказывается список 
а список М включает те грани, которые покрывают соответствующую вершину (фрагмент). При обработке каждого фрагмента алгоритм обращается к процедуре 
при изучении каждой грани, включенной в список 
(шаг 4 алгоритма 17.1). Вначале число таких граней очень велико, однако большая их часть удаляется, так как они расположены вне рассматриваемого фрагмента. Это удаление осуществляется на шаге 5. Если в результате использования процедуры 
для обработки некоторого заданного фрагмента для всех граней выдается 0, то это означает, что цвет данного фрагмента совпадает с цветом фона и больше он не будет рассматриваться (флаг 
оставляется равным 0). Если в результате применения этой процедуры выдается 2, то соответствующая грань переносится из списка 
в список М (шаг 7). Если при обработке некоторого фрагмента результатами являются только 0 и 2, то этот фрагмент также можно исключить из дальнейшего рассмотрения. Он полностью покрывается одной или несколькими гранями и его цвет совпадает, следовательно, с цветом ближайшей по отношению к наблюдателю грани. Это можно установить на основании просмотра содержания списка М на шаге 8. Если для какой-либо грани процедура дает 1, то соответствующий фрагмент необходимо подвергнуть разбиению (шаг 6). Очевидно, что всякая грань, отстоявшая на некоторое расстояние от исходного фрагмента, будет отстоять и от фрагментов, являющихся его непосредственными потомками на тетрарном дереве. Поскольку первое разбиение на более мелкие фрагменты происходит в случае, когда результатом выполнения процедуры 
является 1, то понятно, что любые изменения содержания списков 
к М связаны с отстоящими или покрытыми гранями. Следовательно, эти списки могут быть переданы непосредственным потомкам разбиваемого фрагмента на тетрарном дереве. Грань, для которой процедура выдала 1, должна остаться в списке 
для всех непосредственных потомков фрагмента 
В разд. 17.5 обсуждаются несколько изменений, которые можно использовать на этапе задания начальных условий алгоритма.
Кроме того, работу алгоритма можно ускорить, изменив шаг 4 таким образом, чтобы грань, пересекающаяся с фрагментом, сравнивалась с элементами списка М. Если оказывается, что она расположена за одним из них, то проверяемая грань больше не рассматривается.
Алгоритм 17.1. Алгоритм удаления невидимых линий, основанный на использовании тетрарного дерева
Обозначения. 
— квадратный фрагмент, соответствующий листу тетрарного дерева. Для каждого квадратного фрагмента алгоритм ведет два списка — L и М. L — список, содержащий все грани, которые могут иметь пересечение с фрагментом 
— список, содержащий грани, покрывающие фрагмент 
(это устанавливается в процессе выполнения алгоритма). Флагу 
присваивается 1 для всех квадратных фрагментов, для которых задача разделения видимых и невидимых элементов еще не решена.
(см. скан)
