В этом случае необходимо многоугольник Р разрезать плоскостью, несущей Q, на две части. При этом исходный многоугольник Р удаляется из списка, а две его новые части включаются в список на соответствующие места, и тесты повторяются для нового списка.
Для разбиения многоугольника вдоль линии пересечения несущих эти многоугольники плоскостей можно использовать алгоритм Сазерленда-Ходжмена (если отсекатель выпуклый) или алгоритм Вейлера-Азертона в общем случае. Многоугольник Q используется как отсекатель. Многоугольник Р разбивается на два новых. Для нахождения точек пересечения ребер многоугольника Р с отсекателем Q можно использовать алгоритм Кируса-Бека [ ].
-49-
как в об»ектном пространстве, так и в пространстве изображения. Формирование списка приоритетов ведется в об»ектном пространстве, а результат заносится в буфер кадра в терминах пространства изображения. При этом необходимо произвести масштабирование (переход из пространства мировых координат в пространство экранных координат).
Данный алгоритм может применяться и для удаления невидимых линий (каркасная модель изображения). При этом в буфер кадра заносятся атрибуты, соответствующие цвету фона. При разложении многоугольника в растр его ребрам присваиваются атрибуты, отличающиеся от цвета фона, а все внутренние пикселы получают цвет фона. В этом случае новый многоугольник, закрывающий ранее рассмотренный многоугольник, при разложении в растр «сотрет» ребра предыдущего многоугольника (они будут закрашены цветом фона).
6.5. АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ Z-БУФЕР Данный алгоритм удаления невидимых поверхностей является одним из простейших. Этот алгоритм работает в пространстве изображения. Здесь обобщается идея о буфере кадра. Буфер кадра используется для заполнения атрибутов (интенсивности) каждого пиксела в пространстве изображения. Наряду с буфером кадра вводится Z-буфер, представляющий собой специальный буфер глубины, в котором запоминаются координаты Z (глубина) каждого видимого пиксела в пространстве изображения.
В процессе работы глубина (значение координаты Z) каждого нового пиксела, который надо занести в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в Z-буфер. Если
это сравнение показывает, что новый пиксел расположен ближе к наблюдателю, чем пиксел, уже находящийся в буфере кадра, то новый пиксел заносится в буфер кадра. Помимо этого производится корректировка 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 - глубина искомого разреза. В этом случае оста-
ются только элементы поверхности, которые лежат на плоскости разреза или позади нее.
Для построения прозрачных поверхностей может применяться модифицированный вариант 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, а в буфер кадра заносится фоновое значение интенсивности.
-55-
екцией каждого многоугольника на плоскость XOY (если эти пересечения существуют). Пересечения образуют пары, поэтому в интервале между концами пар глубина многоугольника сравнивается с глубиной, содержащейся в Z-буфере. Если глубина рассматриваемого пиксела многоугольника больше значения из Z-буфера, то рассматриваемый многоугольник будет текущим видимым. Атрибуты этого многоугольника заносятся в буфер кадра в текущую позицию, одновременно корректируется и Z-буфер. После обработки всех многоугольников сцены буфер размером в одну строку содержит решение задачи об удалении невидимых поверхностей для данной сканирующей строки. Содержимое буфера кадра может выводиться на экран.