Методы удаления невидимых частей сцены можно классифицировать:

1. По выбору удаляемых частей:
   удаление невидимых линий, ребер, поверхностей, объемов.
2. По порядку обработки элементов сцены:
   удаление в произвольном порядке и в порядке, определяемом процессом визуализации.
3. По системе координат:

   • алгоритмы работающие в пространстве объектов, когда каждая из N граней объекта сравнивается с остальными N-1 гранями (объем вычислений растет как N²),
   • алгоритмы работающие в пространстве изображения, когда для каждого пиксела изображения определяется какая из N граней объекта видна (при разрешении экрана M×M объем вычислений растет как M² ×N).

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

Наиболее известный ранний алгоритм - алгоритм Робертса (1963 г.). Работает с только выпуклыми телами в пространстве объектов. Каждый объект сцены представляется многогранным телом, полученным в результате пересечения плоскостей. Т.е. тело описывается списком граней, состоящих из ребер, которые в свою очередь образованы вершинами.

Вначале из описания каждого тела удаляются нелицевые плоскости, экранированные самим телом. Затем каждое из ребер сравнивается с каждым телом для определения видимости или невидимости. Т.е. объем вычислений растет как квадрат числа объектов в сцене. Наконец вычисляются новые ребра, полученные при протыкании телами друг друга.

Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату Z или глубину. При занесении очередного пиксела в буфер кадра значение его Z-координаты сравнивается с Z-координатой пиксела, который уже находится в буфере. Если Z-координата нового пиксела больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пиксела и его Z-координата заносятся в буфер, если нет, то ни чего не делается.

Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует большого объема памяти. Данные о глубине для реалистичности изображения обычно достаточно иметь с разрядностью порядка 20 бит. В этом случае при изображении нормального телевизионного размера в 768×576 пикселов для хранения Z-координат необходим объем памяти порядка 1 Мбайта. Суммарный объем памяти при 3 байтах для значений RGB составит более 2.3 Мбайта.

Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Для сокращения затрат времени нелицевые многоугольники могут быть удалены. По сути дела алгоритм с Z-буфером - некоторая модификация уже рассмотренного алгоритма заливки многоугольника. Если используется построчный алгоритм заливки, то легко сделать пошаговое вычисление Z-координаты очередного пиксела, дополнительно храня Z-координаты его вершин и вычисляя приращение dz Z-координаты при перемещении вдоль X на dx, равное 1. Если известно уравнение плоскости, в которой лежит обрабатываемый многоугольник, то можно обойтись без хранения Z-координат вершин. Пусть уравнение плоскости имеет вид:

Тогда при C не равном нулю

Найдем приращение Z-координаты пиксела при шаге по X на dx, помня, что Y очередной обрабатываемой строки - константа.

но dx = 1, поэтому

Основной недостаток алгоритма с Z-буфером - дополнительные затраты памяти. Для их уменьшения можно разбивать изображение на несколько прямоугольников или полос. В пределе можно использовать Z-буфер в виде одной строки. Понятно, что это приведет к увеличению времени, так как каждый прямоугольник будет обрабатываться столько раз, на сколько областей разбито пространство изображения. Уменьшение затрат времени в этом случае может быть обеспечено предварительной сортировкой многоугольников на плоскости.

Другие недостатки алгоритма с Z-буфером заключаются в том, что так как пикселы в буфер заносятся в произвольном порядке, то возникают трудности с реализацией эффектов прозрачности или просвечивания и устранением лестничного эффекта с использованием предфильтрации, когда каждый пиксел экрана трактуется как точка конечного размера и его атрибуты устанавливаются в зависимости от того какая часть пиксела изображения попадает в пиксел экрана. Но другой подход к устранению лестничного эффекта, основанный на постфильтрации - усреднении значений пиксела с использованием изображения с большим разрешением реализуется сравнительно просто за счет увеличения расхода памяти (и времени). В этом случае используются два метода. Первый состоит в том, что увеличивается разрешение только кадрового буфера, хранящего атрибуты пикселов, а разрешение Z-буфера делается совпадающим с размерами пространства изображения. Глубина изображения вычисляется только для центра группы усредняемых пикселов. Это метод неприменим, когда расстояние до наблюдателя имитируется изменением интенсивности пикселов. Во втором методе и кадровый и Z буфера имеют увеличенное разрешение и усредняются атрибуты пиксела, так и его глубина.

Общая схема алгоритма с Z-буфером:

· Инициализировать кадровый и Z-буфера. Кадровый буфер закрашивается фоном. Z-буфер закрашивается минимальным значением Z.

· Выполнить преобразование каждого многоугольника сцены в растровую форму. При этом для каждого пиксела вычисляется его глубина z. Если вычисленная глубина больше, чем глубина, уже имеющаяся в Z-буфере, то занести в буфера атрибуты пиксела и его глубину, иначе никаких занесений не выполнять.

· Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.

Рассмотрим теперь алгоритм с Z-буфером размером в одну строку, который представляет собой обобщение алгоритма построчной заливки многоугольника, представленный в процедурах V_FP0 и V_FP1 в приложениях. Модификация должна учесть то, что для каждой строки сканирования теперь может обрабатываться не один многоугольник.

Общая схема такого алгоритма следующая:

1. Подготовка данных.
   Для каждого многоугольника определить максимальную Y-координату.
   Занести многоугольник в группу многоугольников, соответствующую данной Y-координате.
2. Собственно заливка.

Алгоритм работает в пространстве изображения и анализирует область на экране дисплея (окно) на наличие в них видимых элементов. Если в окне нет изображения, то оно просто закрашивается фоном. Если же в окне имеется элемент, то проверяется достаточно ли он прост для визуализации. Если объект сложный, то окно разбивается на более мелкие, для каждого из которых выполняется тест на отсутствие и/или простоту изображения. Рекурсивный процесс разбиения может продолжаться до тех пор пока не будет достигнут предел разрешения экрана.

Можно выделить 4 случая взаимного расположения окна и многоугольника (рис. 0.6.49):
· многоугольник целиком вне окна,
· многоугольник целиком внутри окна,
· многоугольник пересекает окно,
· многоугольник охватывает окно.

В четырех случаях можно сразу принять решение о правилах закраски области экрана:

· все многоугольники сцены - внешние по отношению к окну. В этом случае окно закрашивается фоном;

· имеется всего один внутренний или пересекающий многоугольник. В этом случае все окно закрашивается фоном и затем часть окна, соответствующая внутреннему или пересекающему окну закрашивается цветом многоугольника;

· имеется единственный охватывающий многоугольник. В этом случае окно закрашивается его цветом.

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

В любых других случаях процесс разбиения окна продолжается. Легко видеть, что при растре 1024×1024 и делении стороны окна пополам требуется не более 10 разбиений. Если достигнуто максимальное разбиение, но не обнаружено ни одного из приведенных выше четырех случаев, то для точки с центром в полученном минимальном окне (размером в пиксел) вычисляются глубины оставшихся многоугольников и закраску определяет многоугольник, наиболее близкий к наблюдателю. При этом для устранения лестничного эффекта можно выполнить дополнительные разбиения и закрасить пиксел с учетом всех многоугольников, видимых в минимальном окне.

Первые три случая идентифицируются легко. Последний же случай фактически сводится к поиску охватывающего многоугольника, перекрывающего все остальные многоугольники, связанные с окном. Проверка на такой многоугольник может быть выполнена следующим образом: в угловых точках окна вычисляются Z-координаты для всех многоугольников, связанных с окном. Если все четыре такие Z-координаты охватывающего многоугольника ближе к наблюдателю, чем все остальные, то окно закрашивается цветом соответствующего охватывающего многоугольника. Если же нет, то мы имеем сложный случай и разбиение следует продолжить.

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

Из изложенного ясно, что важной частью алгоритма является определение расположения многоугольника относительно окна.

Проверка на то что многоугольник внешний или внутренний относительно окна для случая прямоугольных окон легко реализуется использованием прямоугольной оболочки многоугольника и сравнением координат. Для внутреннего многоугольника должны одновременно выполняться условия:

здесь	Xmin,Xmax,Ymin,Ymax	-	ребра оболочки
	Wл, Wп, Wн, Wв	-	ребра окна

Для внешнего многоугольника достаточно выполнение любого из следующих условий:

Таким способом внешний многоугольник, охватывающий угол окна не будет идентифицирован как внешний (см. рис. 0.6.50).

Проверка на пересечение окна многоугольником может быть выполнена проверкой на расположение всех вершин окна по одну сторону от прямой, на которой расположено ребро многоугольника. Пусть ребро многоугольника задано точками P1(x1,y1,z1) и P2(x2,y2,z2), а очередная вершина окна задается точкой P3(x3,y3,z3). Векторное произведение вектора P1P3 на вектор P1P2, равное (x3-x1)(y2-y1) - (y3-y1)(x2-x1) будет меньше 0, равно 0 или больше 0, если вершина лежит слева, на или справа от прямой P1P2. Если знаки различны, то окно и многоугольник пересекаются. Если же все знаки одинаковы, то окно лежит по одну сторону от ребра, т.е. многоугольник может быть либо внешним, либо охватывающим.

Вернемся к примеру 0.6.50. Такой многоугольник рассмотренными тестами не был идентифицирован ни как внутренний ни как пересекающий. Т.е. он может быть либо внешним, либо охватывающим. Для завершающей классификации может использоваться тест с подсчетом угла, рассматривавшийся ранее для определения нахождения точки внутри/вне многоугольника. В этом тесте вычисляется суммарный угол, на который повернется луч, исходящий из некоторой точки окна (обычно центра), при последовательном обходе вершин многоугольника.

Если суммарный угол равен 0, то многоугольник - внешний. Если же угол равен N×360^°, то многоугольник охватывает окно N раз. Простейшая иллюстрация этого теста приведена на рис. 0.6.51.

* - эта реализация взята из другого места, но, вроде бы, все верно ];-).

Предполагается, что экран у дисплея квадратный.
если в окне что-то есть, то алгоритм разобьет это окно.
окно разбивается на четыре одинаковых подокна.
каждый многоугольник сравнивается с каждым окном.
предполагается, что все значения заданы в системе координат экрана (пространстве изображения).
предполагается, что устранение нелицевых граней проведено до начала работы алгоритма.
Вершина - массив размером m х 3, в котором запоминаются координаты вершин всех многоугольников.
m - общее число вершин многоугольников в сцене. Предполагается, что эти вершины перечислены в порядке их обхода по часовой стрелке.
N - число многоугольников в сцене.
информация об отдельных многоугольниках запоминается в массиве.
Многоугольник размером N х 11

Многоугольник ( ,1) - указатель на первую вершину многоугольника в массиве Вершина

Многоугольник ( ,2) - число вершин многоугольника

Многоугольник ( ,3) - интенсивность света или цвет многоугольника

Многоугольник ( ,4-7) - коэффициенты a, b, c, d уравнения плоскости, несущей многоугольник

Многоугольник ( ,8-11) - габариты Xmin, Xmax, Ymin, Ymax прямоугольной объемлющей оболочки многоугольника

Push - функция, заносящая окна в стек

Pop - функция, извлекающая окна из стека

Wmax - максимальные габариты окна по х и у. Предполагается, что начало координат экрана находится в точке (0, 0)

Окно - массив размером 1x3, который содержит начало координат окна и его размер в форме (Хнач, Унач, Размер)

Внешность - флаг = 0 для пустого окна, >=1 для непустого окна

инициализировать черный фоновый цвет или интенсивность 
Фон = О 
Поместить окно размером с экран в стек 
PUSH ОКНО(0, 0, Wmax) 
while (стек не пуст) 
    взять окно из стека 
    Pop Окно(Хнач, Удач, Размер) 
    инициализировать счетчик многоугольников 
    Внешность = 0 
    Выполнить для каждого многоугольника габаритный тест с 
    прямоугольной оболочкой, чтобы найти внешние многоугольники 
    while (i <= N and внешность = О) 
        call Габарит(i, Многоугольник, Окно, Внешность) 
        i = i + 1 
    end while 
    если хотя бы один многоугольник не является внешним, то 
    разбить окно или изобразить пиксел 
    if Внешность > О then: 
        если размер окна больше пиксела, то разбить окно 
        if Размер > 1 then 
            Размер = Размер/2 
            Push Окно(Хнач + Размер, Унач + Размер, Размер) 
            Push Окно(Хнач, Унач + Размер, Размер) 
            Push Окно(Хнач + Размер, Унач, Размер) 
            Push Окно(Хнач, Унач, Размер) 
        else 
            если окно размером с пиксел, то вычислить его атрибуты 
            call Покрытие(Вершина, N, Многоугольник, Окно; Номер) 
            if Номер > 0 then 
                call Визуализация(Окно, Многоугольник (Номер, 3)) 
            else 
                Изобразить пустое окно 
                call Визуализация(Окно, Фон) 
            end if 
        end if 
    else 
        call Визуализация(Окно, Фон) 
    end if 
end while 
finish

подпрограмма реализации простого габаритного теста с 
прямоугольной оболочкой 
subroutine Габарит(i, Многоугольник, Окно; Внешность) 
вычисление габаритов окна: Хлев, Управ, Хниз, Yвepx 
Хлев  = Окно(1, 1) 
Хправ = Окно(1, 1) + Окно*) - 1 
Yниз  = Окно(1, 2) 
Yвepx = Окно(1, 2) + Окно(1, 3) - 1 
реализация тестов с прямоугольной оболочкой 
Внешность = 1 
if Многоугольник(i, 8)  > Хправ then Внешность = 0
if Многоугольник(i, 9)  < Хлев  then Внешность = 0 
if Многоугольник(i, 10) > Yверх then Внешность = 0 
if Многоугольник(i, 11) < Yниз  then Внешность = 0 
return 

подпрограмма визуализации окна 
subroutine Визуализация(окно, Интенсивность) 
Setpixe(x, у, 1) - функция визуализации пиксела, 
координаты которого (х, у), с интенсивностью I 
    for j = Окно(1, 2) to Окно(1, 2) + Окно(1, 3) - 1 
        for i = Окно(1, 1) to Окно(1, 1) + Окно(1, 3) - 1 
            Setpixe(i, j, Интенсивность) 
        next i 
    next j 
return 

подпрограмма, проверяющая, покрывает ли многоугольник центр окна 
subroutine Покрытие(Вершина, N, Многоугольник, Окно; Номер) 
считается, что многоугольник покрывает окно размером с пиксел, 
    если центр этого окна находится внутри многоугольника 
поскольку вершины многоугольника перечисляются по часовой 
    стрелке, его внутренность лежит справа от контура 
если покрывающие многоугольники не обнаружатся, то 
Номер = О 
если же найден хотя бы один покрывающий многоугольник,
то Номер будет равен номеру того из них, который видим 
    присвоить Zmax начальное значение, равное нулю. Тут предполагается, 
    что все многоугольники расположены в положительном 
    полупространстве Z >= 0 
    Zmax = 0 
    вначале предположим, что покрывающих многоугольников 
    нет 
    Номер = 0 
    установить центр окна 
    ТочкаX = Окно(1, 1) + Окно(1, 3)/2 
    ТочкаY = Окно(1, 2) + Окно(1, 3)/2 
    для каждого многоугольника 
    for i = 1 to N 
        Индекс = Многоугольник(i, 1) 
        Для каждого ребра многоугольника 
        for j = 1 to Многоугольник(i, 2) - 1 
            T1x = Вершина(Индекс, 1) 
            T1у = Вершина(Индекс, 2) 
            T2x = Вершина(Индекс + 1, 1) 
            T2y = Вершина(Индекс + 1, 2) 
            заметим, что Точка, Tl, Т2 - это сокращения для 
            идентификаторов ТочкаX, ТочкаY и т. п. 
            call Видимость(Точка, Tl, Т2; Твидимость)
            if Твидимость < 0 then 1 
            Индекс = Индекс + 1 
        next j 
        проверка относительно последнего ребра многоугольника 
        Т1х = Вершина(Индекс, 1) 
        T1у = Вершина(Индекс, 2) 
        Т2х = Вершина(Многоугольник (i, 1), 1) 
        Т2у = Вершина(Многоугольник (i, 1), 2) 
        call Видимость(Точка, Tl, Т2, Твидимость) 
        if Твидимость >= 0 then 
            call Вычислить(Вершина, i, Многоугольник, Окно; z) 
            if z > Zmax then 
                Zmax = z 
                Номер = i 
            end if 
        end if 
  1 next i 
return 

подпрограмма вычисления видимости точки
subroutine Видимость(Точка, P1, P2; Твидимость)
видимость Точка следует определить относително стороны P1-P2
Твидимость <0, если Точка невидима
           =0, если Точка лежит на  P1-P2
           >0, если Точка видима
в этой подпрограмме используется вычисление векторного произведения
Sign - функция, принимающая значения -1,0,1 в зависимости
       от того, будет ли знак ее аргумента отрицателен, 
       равен нулю или положителен
    Раб1 = (ТочкаX - P1X) * (P2Y-P1Y)
    Раб2 = (ТочкаY - P1Y)*(P2X-P1X)
    Раб3 = Раб1 - Раб2
    Твидимость = Sign(Раб3)
    return
    
подпрограмма вычисления интенсивности пиксела 
subroutine Вычислить(Вершина, i, Многоугольник, Окно; z) 
уравнение плоскости многоугольника используется для вычисления 
многоугольника, который находится ближе других к точке 
наблюдения для этого пиксела 
Мах - обозначение функции, вычисляющей максимум 
    вычисление координат х и у центра пиксела 
    Хцентр = Окно(1, 1) + Окно(1, 3)/2 
    Yцентр = Окно(1, 2) + Окно(1, 3)/2 
    определение координаты z многоугольника в центре пиксела 
    поиск ребра многоугольника, проходящего через центр пиксела 
    заметим, что многоугольник такого типа может совершенно 
    отсутствовать или появиться в качестве набора несвязанных 
    точек - например, в результате ступенчатости 
    if Многоугольник(i, 6) = 0 then 
        for j = 2 to Многоугольник(i, 2) 
            z=Max(Вершина(j, 3), Вершина(j -1, 3)) 
        next j 
    else 
        вычисление z по уравнению плоскости многоугольника 
        А = Многоугольник(i, 4) 
        В = Многоугольник(i, 5) 
        С = Многоугольник(i, 6) 
        D = Многоугольник(i, 7) 
        z = - (А * Хцентр + В * Yцентр + D)/С 
    end if 
    return 
    

В алгоритмах построчного сканирования результирующее изображение генерируется построчно причем, подобно ранее рассмотренному алгоритму построчной заливки многоугольника, используется связность соседних растровых строк изображения. Отличие состоит в том, что учитываются все, а не один многоугольник.

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

Последовательность шагов алгоритма:
· построение списка ребер,
· построение списка многоугольников,

· построение списка активных ребер - создается таблица ребер, включающая все негоризонтальные ребра многоугольников, причем элементы таблицы по значению Y-координаты отсортированы по группам.

При рассмотрении этого алгоритма предполагается, что наблюдатель находится на положительной полуоси Z, а экран дисплея перпендикулярен оси Z и располагается между объектом и наблюдателем.

Удаление невидимых (скрытых) поверхностей в алгоритме трассировки лучей выполняется следующим образом:
· сцена преобразуется в пространство изображения,

· из точки наблюдения в каждый пиксел экрана проводится луч и определяется какие именно объекты сцены пересекаются с лучом,

· вычисляются и упорядочиваются по Z координаты точек пересечения объектов с лучом. В простейшем случае для непрозрачных поверхностей без отражений и преломлений видимой точкой будет точка с максимальным значением Z-координаты. Для более сложных случаев требуется сортировка точек пересечения вдоль луча.

Ясно, что наиболее важная часть алгоритма - процедура определения пересечения, которая в принципе выполняется Rx×Ry×N раз (здесь Rx,Ry - разрешение дисплея по X и Y, соответственно, а N - количество многоугольников в сцене).

Очевидно, что повышение эффективности может достигаться сокращением времени вычисления пересечений и избавлением от ненужных вычислений. Последнее обеспечивается использованием геометрически простой оболочки, объемлющей объект - если луч не пересекает оболочку, то не нужно вычислять пересечения с ним многоугольников, составляющих исследуемый объект.

При использовании прямоугольной оболочки определяется преобразование, совмещающее луч с осью Z. Оболочка подвергается этому преобразованию, а затем попарно сравниваются знаки Xmin с Xmax и Ymin с Ymax. Если они различны, то есть пересечение луча с оболочкой (см. рис. 0.6.52)

При использовании сферической оболочки для определения пересечения луча со сферой достаточно сосчитать расстояние от луча до центра сферы. Если оно больше радиуса, то пересечения нет. Параметрическое уравнение луча, проходящего через две точки P1(x1,y1,z1) и P2(x2,y2,z2), имеет вид:

Минимальное расстояние от точки центра сферы P0(x0,y0,z0) до луча равно:

Этому соответствует значение t:

Если d2 > R2, то луч не пересекает объекты, заключенные в оболочку.

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

Наряду с вложенными оболочками для сокращения расчетов пересечений используется отложенное вычисление пересечений с объектами. Если обнаруживается, что объект пересекается лучом, то он заносится в специальный список пересеченных. После завершения обработки всех объектов сцены объекты, попавшие в список пересеченных упорядочиваются по глубине. Заведомо невидимые отбрасываются а для оставшихся выполняется расчет пересечений и отображается точка пересечения наиболее близкая к наблюдателю.

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

Для сокращения времени вычислений собственно пересечений предложено достаточно много алгоритмов, упрощающих вычисления для определенной формы задания поверхностей.

Более подробно об алгоритмах отсечения можно прочитать в соответствующей главе книги Роджерса^zip.