Алгоритм, использующий список приоритетов, может работать

-49-

как в об»ектном пространстве, так и в пространстве изображе­ния. Формирование списка приоритетов ведется в об»ектном пространстве, а результат заносится в буфер кадра в терминах пространства изображения. При этом необходимо произвести масш­табирование (переход из пространства мировых координат в пространство экранных координат).

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

6.5. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ Z-БУФЕР Данный алгоритм удаления невидимых поверхностей является одним из простейших. Этот алгоритм работает в пространстве изображения. Здесь обобщается идея о буфере кадра. Буфер кадра используется для заполнения атрибутов (интенсивности) каждого пиксела в пространстве изображения. Наряду с буфером кадра вводится Z-буфер, представляющий собой специальный буфер глу­бины, в котором запоминаются координаты Z (глубина) каждого видимого пиксела в пространстве изображения.

В процессе работы глубина (значение координаты Z) каждого нового пиксела, который надо занести в буфер кадра, сравнивает­ся с глубиной того пиксела, который уже занесен в Z-буфер. Если

-50-

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

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

Главный недостаток алгоритма - большой об»ем требуемой памяти. Буфер кадра совместно с Z-буфером требует около 1,5 мегабайт памяти (при разрешающей способности 640*480 пикселов, 8 битах для хранения цвета пиксела и 32 битах для хранения глубины).

Один из путей решения этой проблемы - использование внешней памяти, но это может существенно замедлить работу. Другой путь экономии памяти - использование Z-буфера размером в одну стро­ку (алгоритм построчного сканирования).

Еще два недостатка данного алгоритма - трудоемкость устра­нения лестничного эффекта и невозможность реализации эффектов

-51 -

прозрачности.

Формально описать алгоритм можно следующим образом:

1. Заполнение буфера кадра фоновым значением интенсивности
(цвета).

2. Заполнение Z-буфера минимальным значением Z.

3. Преобразование каждого многоугольника в растровую форму
в произвольном порядке.

4. Вычисление для каждого пиксела с координатами (х,у),
принадлежащего многоугольнику, его глубины Z(x,y).

5. Сравнение глубины Z(x,y) со значением Zбyф(x,y), храня­
щимся в Z-буфере для пиксела с теми же координатами (х,у):

если Z(x,y)>Zбyф(x,y), то записать атрибут очередного мно­гоугольника в буфер кадра и гбуф(х,у) заменить на значение Z(x,

У).

Предварительно для выпуклых многогранников целесообразно удалить нелицевые грани (выполнить первый этап алгоритма Ро-бертса).

Для вычисления глубины каждого пиксела на сканирующей строке можно поступить следующим образом: уравнение плоскости, несущей многоугольник, имет вид Ax+By+Cz+D=0.

Отсюда при С<>0 Z=-(Ax+By+D)/C. Для сканирующей строки y=const, глубина пиксела, для которого xl=x+ х, равна: Ax+By+D Ax A

zl=............................ = z- - х

С   С  С

Поскольку х=1, Tozl=z-A/C. Если же О=0, то плоскость многоугльника параллельна оси Z. (Для наблюдателя такой много-

-52-

угольник вырождается в линию). Глубина пиксела, являющегося пе­ресечением сканирующей строки с ребром многоугольника, вычисля­ется следующим образом. Сначала определяются ребра грани, вер­шины которых лежат по разные стороны от сканирующей строки (одна из вершин ребра может в крайнем случае лежать на скани­рующей строке), так как только в этом случае сканирующая стро­ка пересекает ребро. Затем из найденных точек пересечения вы­бирается ближайшая к наблюдателю. Глубина точки пересечения определяется из соотношения _У3-у2

z3=z2 +      (z2-zl)

y2-yl где (yl,zl) и (y2,z2) - координаты вершин проекции ребра

на плоскость YOZ; (y3,z3) - координаты проекции точки пересечения на ту же

плоскость. Уравнение проекции ребра

z-z2 y-y2

z2-zl y2-yl

Уравнение проекции плоскости y=const (у-уЗ).

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

где Zpasp - глубина искомого разреза. В этом случае оста-

-53-

ются только элементы поверхности, которые лежат на плоскости разреза или позади нее.

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

1=Т*1о

Т=( 1 -(4piD+M))exp(-S * 1),

где I - интенсивность пиксела, Т - коэффициент прозрачности,

D,M - коэффициенты диффузного и зеркального отражения, S - коэффициент поглощения, 1 - путь луча в рассматриваемом слое, 1о - текущее содержимое ALFA-буфера. (коэффициент прозрачности должен быть близок к 1).

Ограничение на величину коэффициента прозрачности Т поз­воляет не учитывать относительное расположение прозрачных по­верхностей и вычислять результирующую интенсивность пиксела в линейном приближении.

В заключение можно отметить, что эксплуатационные характе-

-54-

ристики алгоритма с Z-буфером остаются практически постоянными, т.к. с ростом числа многоугольников в видимом об»еме уменьшает­ся число пикселов, покрываемых одним многоугольником.

6.6. АЛГОРИТМ ПОСТРОЧНОГО СКАНИРОВАНИЯ

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

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

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