формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.
Объем вычислений для любого алгоритма, работающего в объектном пространстве, и сравнивающего каждый объект сцены всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов. Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселов в системе координат экрана, растет теоретически, как n*N. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N - число пикселов. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n<N. Теоретически большинство алгоритмов следует реализовывать в объектном пространстве. Однако на практике это не так. Дело в том, что алгоритмы, работающие в пространстве изображения, более эффективны потому, что для них легче воспользоваться преимуществом когерентности при растровой реализации.
АЛГОРИТМ ПЛАВАЮЩЕГО ГОРИЗОНТА
Алгоритм плавающего горизонта чаще всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде
F(X, Y, Z) = 0
Подобные функции возникают во многих приложениях в математике, технике, естественных науках и других дисциплинах.
Предложено много алгоритмов, использующих этот подход. Поскольку в приложениях в основном интересуются описанием поверхности, этот алгоритм обычно работает в пространстве изображения. Главная идея данного метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат X, Y или Z.
Например, пусть указанные параллельные плоскости определяются постоянными значениями Z. Функция F(X, Y, Z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности
Y = f(X, Z) или X = g(Y, Z),
где z постоянно на каждой из заданных параллельных плоскостей. Предполагается, что полученные кривые являются однозначными
функциями независимых переменных. Если спроецировать полученные кривые на плоскость Z = 0, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости Z=const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты X в пространстве изображения определяется соответствующее значение Y. Алгоритм удаления невидимой линии заключается в следующем:
Если на текущей плоскости при некотором заданном значении X соответствующее значение Y на кривой больше значения Y для всех предыдущих кривых при этом значении X, то текущая кривая видима в этой точке; в противном случае она невидима.
Реализация данного алгоритма достаточно проста. Для хранения максимальных значений Y при каждом значении X используется массив, длина которого равна числу различимых точек (разрешению) по оси X в пространстве изображения. Значения, хранящиеся в этом массиве,
представляют собой текущие значения "горизонта". Поэтому по мере рисования каждой очередной кривой этот горизонт "всплывает". Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.
Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых. Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алгоритм будет считать их невидимыми. Нижняя сторона поверхности делается видимой, если модифицировать этот алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго массива, длина которого равна числу различимых точек по оси X в пространстве изображения. Этот массив содержит наименьшие значения Y для каждого значения X. Алгоритм теперь становится таким:
Если на текущей плоскости при некотором заданном значении X соответствующее значение Y на кривой больше максимума или меньше минимума по Y для всех предыдущих кривых при этом X, то текущая кривая видима. В противном случае она невидима.
В изложенном алгоритме предполагается, что значение функции, т. е. Y, известно для каждого значения X в пространстве изображения. Однако, если для каждого значениях нельзя указать (вычислить) соответствующее ему значение Y, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений Y между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов. Если видимость кривой меняется, то метод с такой простой интерполяцией не даст корректного результата. Необходимо решать задачу о поиске точек пересечения сегментов текущей и предшествующей кривых.
АЛГОРИТМ РОБЕРТСА
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий. Это математически элегантный метод, работающий в объектном пространстве. Алгоритм прежде всего удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть или части, если таковые есть, экранируются этими телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет теоретически как квадрат числа объектов. Это в сочетании с ростом интереса к растровым дисплеям, работающим в пространстве изображения, привело к снижению интереса к алгоритму Робертса. Однако математические методы, используемые в этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно использовать для иллюстрации некоторых важных концепций. Наконец, более поздние реализации алгоритма, использующие предварительную приоритетную сортировку вдоль оси Z и простые габаритные или минимаксные тесты, демонстрируют почти линейную зависимость от числа объектов.
В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. В этом алгоритме выпуклое многогранное тело с плоскими гранями должно представляться набором пересекающихся плоскостей. Уравнение произвольной плоскости в трехмерном пространстве имеет вид
aX+bY+cZ+d = 0
31
Вматричной форме этот результат выглядит так:
++
[X Y Z 1]¦а¦ = 0 ¦b¦ ¦с¦ ¦d¦
+ +
или
T
[X Y Z 1][Р] = 0
T
где [Р] = [a b c d] представляет собой плоскость. Поэтому любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей, т. е.
++
[V]= ¦а1 a2 ... аn¦ ¦b1 b2 ... bn¦ ¦с1 c2 ... сn¦ ¦d1 d2 ... dn¦
++
где каждый столбец содержит коэффициенты одной плоскости. Напомним, что любая точка пространства представима в однородных координатах вектором [S] =[Х Y Z 1].
T
Более того, если точка [S] лежит на плоскости, то [S][Р] = 0. Если же [S] не лежит на плоскости, то знак этого скалярного произведения показывает, по какую сторону от плоскости расположена точка. В алгоритме Робертса предполагается, что точки, лежащие внутри тела, дают положительное скалярное произведение.
Ниже приводится эффективная реализация алгоритма Робертса. Этот алгоритм делится на три этапа. На первом этапе каждое тело анализируется индивидуально с целью удаления нелицевых плоскостей На втором этапе проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков. На третьем этапе вычисляются отрезки, которые образуют новые ребра при протыкании телами друг друга. В данном алгоритме предполагается, что тела состоят из плоских полигональных граней, которые в свою очередь состоят из ребер, а ребра - из отдельных вершин. Все вершины, ребра и грани связаны с конкретным телом.
Удаление нелицевых плоскостей
Для каждого тела в сцене:
Сформировать многоугольники граней и ребра, исходя из списка вершин тела.
Вычислить уравнение плоскости для каждой полигональной грани тела.
Проверить знак уравнения плоскости:
Взять любую точку внутри тела, например усреднив координаты его вершин.
Вычислить скалярное произведение уравнения плоскости и точки внутри тела.
Если это скалярное произведение < 0, то изменить знак уравнения этой плоскости.
Сформировать матрицу тела.
Умножить ее слева на матрицу, обратную матрице видового преобразования, включающего перспективу.
Вычислить и запомнить габариты прямоугольной объемлющей обо-
лочки преобразованного объема: Xmax, Xmin, Ymax, Ymin. Определить нелицевые плоскости:
Вычислить скалярное произведение пробной точки, лежащей в бесконечности, на преобразованную матрицу тела.
Если это скалярное произведение < 0, то плоскость невидима. Удалить весь многоугольник, лежащий в этой плоскости. Это избавляет от необходимости отдельно рассматривать невидимые линии, образуемые пересечением пар невидимых плоскостей.
Удаление из каждого тела тех ребер, которые экранируются всеми остальными телами в сцене:
Если задано только одно тело, то алгоритм завершается. Сформировать приоритетный список этих тел:
Провести сортировку по Z. Сортировка производится по максимальным значениям координаты Z вершин преобразованных тел. Первым в упорядоченном списке и обладающим наибольшим приоритетом будет то тело, у которого минимальное среди максимальных значений Z. В используемой правой системе координат это тело будет самым удаленным от точки наблюдения, расположенной в бесконечности на оси Z.
Для каждого тела из приоритетного списка:
Проверить экранирование всех лицевых ребер всеми другими телами сцены. Тело, ребра которого проверяются, называется пробным объектом, а тело, относительно которого в настоящий момент производится проверка, называется пробным телом. Естественно, что нужно проверять экранирование пробного объекта только теми пробными телами, у которых ниже приоритеты.
Провести проверки экранирования для прямоугольных объемлющих оболочек пробного объекта и пробного тела:
Если Xmin(пробное тело) > Xmax(пробный объект) или Xmax(пробное тело) < Xmin(пробный объект) или Ymin(пробное тело) > Ymax(пробный объект) или Ymax(пробное тело) < Ymin(пробный объект),
то пробное тело не может экранировать ни одного ребра пробного объекта. Перейти к следующему пробному телу. В противном случае:
Провести предварительные проверки протыкания, чтобы увидеть, не протыкается ли пробное тело пробным объектом и существует ли возможность частичного экранирования первого последним.
Сравнить максимальное значение Z у пробного объекта с минимальным значением Z у пробного тела.
Если Zmax(пробный объект) < Zmin(пробное тело), то протыкание невозможно. Перейти к следующему телу. В противном случае:
Проверить видимое протыкание.
Если Zmax(пробный объект) > Zmax(пробное тело), то пробный объект может проткнуть переднюю грань пробного тела.
Установить флаг видимого протыкания для последующего использования. Занести проткнутое тело в список протыканий.
Если Xmax(пробный объект) > Xmin(пробное тело) или Xmin(пробный объект) < Xmax(пробное тело),
то пробный объект может проткнуть бок пробного тела.
Установить флаг видимого протыкания для последующего использования. Занести тело в список протыканий.
32
Если Ymax(пробный объект) > Ymin(пробное тело) или Ymin(пробный объект) < Ymax(пробное тело),
то пробный объект может проткнуть верх или низ пробного тела.
Установить флаг видимого протыкания для последующего использования. Занести проткнутое тело в список протыканий.
Если список протыканий пуст, то устанавливать флаг протыкания не надо.
Провести проверки экранирования ребер:
Вычислить S и D для ребра, где S =[X1,Y1,Z1,1] -
начальная точка, D = [X2-X1,Y2-Y1,Z2-Z1,1] - нап-
равление ребра.
Вычислить векторные произведения P=S[VT], Q=D[VT], W=G[VT] для каждой плоскости, несущей грань пробного тела. Здесь G - вектор точки наблюдения, T - матрица размером 4х4 видового преобразования (например, при переносе единичного куба с центром в начале координат на три единицы в положительном направлении оси X:
[T]= 1 0 0 0 0 1 0 0 0 0 1 0
3 0 0 1 ).
Проверка полной видимости. Если ребро полностью видимо, то перейти к следующему ребру. Сформиро-
вать уравнения Hj = Pj+tQj+aWj = 0 (0<=t<=1, a>=0), где j - номер столбца в матрице тела, и решить их, объединяя попарно и включив в систему уравнения границ t = 0 и t = 1. Если установлен флаг видимого протыкания, то в систему надо включить и уравнение границы a = 0. Запомнить точки протыкания. В противном случае границу a = 0 не учитывать.
Для каждой пары (t, a), являющейся решением, проверить выполнение условий 0<=t<=1, a >= 0 и Hj > 0 для всех других плоскостей. Если эти условия выполнены, то найти tmaxmin (максимальное среди минимальных) и tminmax (минимальное среди максимальных).
Вычислить видимые участки отрезков и сохранить их для последующей проверки экранирования телами с более низкими приоритетами.
Определить видимые отрезки, связывающие точки протыкания:
Если флаг видимого протыкания не установлен, перейти к процедуре визуализации.
Если точек протыкания не обнаружено, перейти к процедуре визуализации.
Сформировать все возможные ребра, соединяющие точки протыкания, для пар тел, связанных отношением протыкания. Проверить экранирование всех соединяющих ребер обоими телами, связанными отношением протыкания.
Проверить экранирование оставшихся соединяющих ребер всеми прочими телами сцены. Запомнить видимые отрезки.
АЛГОРИТМ ВАРНОКА
Основные идеи, на которые опирается алгоритм Варнока обладают большой общностью. Они основываются на гипотезе о способе об-
работки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым, в качестве примера рассмотрим поверхность стола, на которой нет ничего, кроме вазы с фруктами. Для восприятия цвета, фактуры и других аналогичных характеристик всей поверхности стола много времени не нужно. Все внимание сосредоточивается на вазе с фруктами. В каком месте стола она расположена? Велика ли она? Из какого материала сделана: из дерева, керамики, пластика, стекла, металла? Каков цвет вазы: красный, синий, серебристый; тусклый или яркий и т. п.? Какие фрукты в ней лежат: персики, виноград, груши, бананы, яблоки? Каков цвет яблок: красный, желтый, зеленый? Есть ли у яблока хвостик? В каждом случае, по мере сужения сферы интереса, возрастает уровень требуемой детализации. Далее, если на определенном уровне детализации на конкретный вопрос нельзя ответить немедленно, то он откладывается на время для последующего рассмотрения. В алгоритме Варнока и его вариантах делается попытка извлечь преимущество из того факта, что большие области изображения однородны, например поверхность стола в приведенном выше примере. Такое свойство известно как когерентность, т. е. смежные области (пикселы) вдоль обеих осей X и Y имеют тенденцию к однородности.
Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом. Устранение лестничного эффекта можно реализовать, доведя процесс разбиения до размеров, меньших, чем разрешение экрана на один пиксел, и усредняя атрибуты подпикселов, чтобы определить атрибуты самих пикселов.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма Варнока каждое окно разбивалось на четыре одинаковых подокна.
АЛГОРИТМ РАЗБИЕНИЯ КРИВОЛИНЕЙНЫХ ПОВЕРХНОСТЕЙ
Многие объекты описываются криволинейными поверхностями, например самолеты, корабли, автомобили, мебель и т. п. Полигональные аппроксимации таких поверхностей не всегда дают адекватные представления, например силуэтные линии выглядят не как непрерывные кривые, а как состоящие из отдельных коротких отрезков прямых. Кэтмул предложил для визуализации криволинейных поверхностей алгоритм типа алгоритма разбиения Варнока. Хотя сам Кэтмул использовал этот алгоритм для поверхностей, заданных бикубическими элементами, он обладает общностью, достаточной для применения его к любым криволинейным поверхностям. В отличие от алгоритма Варнока, который рекурсивно разбивал пространство изображения, алгоритм Кэтмула рекурсивно разбивает поверхность. Простейшее описание этого алгоритма таково:
Рекурсивно разбивать поверхность на элементы до тех пор, пока проекция каждого элемента на пространство изображения не
33
будет покрывать не более одного центра пиксела.
Вычислить атрибуты поверхности в этом пикселе и изобразить его.
Чтобы убедиться в том, что криволинейный элемент покрывает ровно один центр пиксела, если поверхность не слишком искривлена, обычно бывает достаточно его полигональной аппроксимации. Процесс разбиения завершается, когда появляются элементы, которые не покрывают ни одного центра пиксела. Атрибуты этих элементов присваиваются ближайшим к ним центрам пикселов. Те элементы поверхности, которые проецируются за пределы окна видимости, разумеется отбрасываются. Элементы, которые пересекают ребра окна видимости, разбиваются дальше до тех пор, пока не станет очевидным вопрос об их расположении относительно окна.
Эффективность этого алгоритма зависит от эффективности метода разбиения криволинейной поверхности. Кэтмул предложил один метод для разбиения бикубических элементов. Коэн Лич и Ризенфельд предложили более общий метод для поверхностей, заданных В-сплай- нами.
АЛГОРИТМ, ИСПОЛЬЗУЮЩИЙ Z-БУФЕР
Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм
впространстве изображения. Идея Z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пиксела в пространстве изображения, Z-буфер - это отдельный буфер глубины, используемый для запоминания координаты Z или глубина каждого видимого пиксела
впространстве изображения. В процессе работы глубина или значение Z каждого нового пиксела, который нужно занести в буфер кадра, сравнивается с глубиной того пиксела, который уже занесен в Z-буфер. Если это сравнение показывает, что новый пиксел расположен впереди пиксела, находящегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, производится корректировка Z-буфера новым значением Z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по X и Y наибольшего значения функции
Z(X, Y).
Главное преимущество алгоритма - его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в Z-буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.
Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат Z значений, то можно использовать Z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (X, Y); обычно бывает достаточно 20 бит. Буфер кадра размером 512х512х24 бит в комбинации с Z-буфером размером 512х512х20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для Z-буфера и связанной с ним аппаратуры.
Альтернативой созданию специальной памяти для Z-буфера является использование для этой цели оперативной или массовой памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на 4, 16 или больше квадратов или полос. В предельном варианте можно использовать Z-буфер размером в одну строку развертки. Для последнего случая имеется интересный алгоритм построчного сканирования. Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование Z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из квадратов или полос, может значительно сократить этот рост.
Другой недостаток алгоритма Z-буфера состоит в трудоемкости
ивысокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания. Поскольку алгоритм заносит пикселы в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания пикселы могут заноситься в буфер кадра в некорректном порядке, что ведет к локальным ошибкам.
Хотя реализация методов устранения лестничного эффекта, основывающихся на префильтрации, в принципе возможна, практически это сделать трудно. Однако относительно легко реализуются методы постфильтрации (усреднение подпикселов). В методах устранения лестничного эффекта, основывающихся на постфильтрации, сцена вычисляется в таком пространстве изображения, разрешающая способность которого выше, чем разрешающая способность экрана. Поэтому возможны два подхода к устранению лестничного эффекта на основе постфильтрации. В первом используется буфер кадра, заданный в пространстве изображения, разрешение которого выше, чем у экрана,
иZ-буфер, разрешение которого совпадает с разрешением экрана. Глубина изображения вычисляется только в центре той группы подпикселов, которая усредняется. Если для имитации расстояния от наблюдателя используется масштабирование интенсивности, то этот метод может оказаться неадекватным.
Во втором методе оба буфера, заданные в пространстве изображения, имеют повышенную разрешающую способность. При визуализации изображения как пикселная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512х512х24 бита, использующее Z-буфер размером 20 бит на пиксел, разрешение которого повышено в 2 раза по осям X и Y и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 мегабайт памяти. Более формальное описание алгоритма Z-буфера таково:
Заполнить буфер кадра фоновым значением интенсивности или цвета.
Заполнить Z-буфер минимальным значением Z.
Преобразовать каждый многоугольник в растровую форму в произвольном порядке.
Для каждого Пиксел(X, Y) в многоугольнике вычислить его глу-
бину Z(X,Y).
Сравнить глубину Z(X,Y) со значением Z буфер(X,Y), хранящимся в Z-буфере в этой же позиции.
Если Z(X,Y) > Z буфер(X,Y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заме нить Z буфер(X,Y) на Z(X,Y).
В противном случае никаких действий не производить.
34
В качестве предварительного шага там, где это целесообразно, применяется удаление нелицевых граней.
Если известно уравнение плоскости, несущей каждый многоугольник, то вычисление глубины каждого пиксела на сканирующей строке можно проделать пошаговым способом. Напомним, что уравнение плоскости имеет вид
aX + bY + сZ + d = 0
Отсюда Z = - (аX+ bY+d)/c <> 0.
Для сканирующей строки Y = const. Поэтому глубина пиксела на этой строке, у которого X1 = X + dX, равна
Z1 - Z = -(аX1 + d) /с + (aX + d) /с = а(X - X1) /с
или
Z1 = Z - (a/с) * dX Но dX = 1, поэтому Z1 = Z - (а/с).
Алгоритм, использующий Z-буфер, можно также применить для построения сечений поверхностей. Изменится только оператор сравнения:
Z(X,Y) > Z буфер(X,Y) and Z(X,Y) < Zсечения
где Zсечения - глубина искомого сечения. Эффект заключается в том, что остаются только такие элементы поверхности, которые лежат на самом сечении или позади него.
АЛГОРИТМЫ, ИСПОЛЬЗУЮЩИЕ СПИСОК ПРИОРИТЕТОВ
При реализации всех обсуждавшихся алгоритмов удаления невидимых линий и поверхностей устанавливались приоритеты, т. е. глубины объектов сцены или их расстояния от точки наблюдения. Алгоритмы, использующие список приоритетов, пытаются получить преимущество посредством предварительной сортировки по глубине или приоритету. Цель такой сортировки состоит в том, чтобы получить окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на расстоянии от точки наблюдения. Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друг друга. Тогда можно записать все элементы в буфер кадра поочередно, начиная с элемента, наиболее удаленного от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далеких элементах в буфере кадра. Поэтому задача об удалении невидимых поверхностей решается тривиально. Эффекты прозрачности можно включить в состав алгоритма путем не полной, а частичной корректировки содержимого буфера кадра с учетом атрибутов прозрачных элементов.
Для простых элементов сцены, например для многоугольников, этот метод иногда называют алгоритмом художника, поскольку он аналогичен тому способу, которым художник создает картину. Сначала художник рисует фон, затем предметы, лежащие на среднем расстоянии, и, наконец, передний план. Тем самым художник решает задачу об удалении невидимых поверхностей, или задачу видимости, путем построения картины в порядке обратного приоритета.
Ньюэл М., Ньюэл Р. и Санча предложили специальный метод сортировки для разрешения конфликтов, возникающих при создании списка приоритетов по глубине.
Алгоритм Ньюэла - Ньюэла - Санча для случая многоугольников:
Сформировать предварительный список приоритетов по глубине, используя в качестве ключа сортировки значение Zmin для каждого многоугольника. Первым в списке будет многоугольник с минимальным значением Zmin. Этот многоугольник лежит дальше всех от точки наблюдения, расположенной в бесконечности на положительной полуо-
си Z. Обозначим его через Р, а следующий в списке многоугольник - через Q.
Для каждого многоугольника Р из списка надо проверить его отношение с Q.
Если ближайшая вершина Р (Pzmax) будет дальше от точки наблюдения, чем самая удаленная вершина Q (Qzmin), т.е. Qzmin >= Рzmax, то никакая часть Р не может экранировать Q. Занести Р в буфер кадра.
Если Qzmin < Pzmах, то P потенциально экранирует не только Q, но также и любой другой многоугольник типа Q из списка, для которого Qzmin < Рzmах - тем самым образуется множество [Q]. Однако Р может фактически и не экранировать ни один из этих многоугольников. Если последнее верно, то Р можно заносить в буфер кадра. Для ответа на этот вопрос используется серия тестов, следующих по возрастанию их вычислительной сложности. Эти тесты ниже формулируются в виде вопросов. Если ответ на любой вопрос будет положительным, то Р не может экранировать [Q]. Поэтому Р сразу же заносится в буфер кадра. Вот эти тесты:
Верно ли, что прямоугольные объемлющие оболочки Р и Q не перекрываются по X?
Верно ли, что прямоугольные оболочки Р и Q не перекрываются по Y?
Верно ли, что Р целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения?
Верно ли, что Q целиком лежит по ту сторону плоскости, несущей Р, которая ближе к точке наблюдения?
Верно ли, что проекции Р и Q не перекрываются?
Каждый из этих тестов применяется к каждому элементу [Q]. Если ни один из них не дает положительного ответа и не заносит Р в буфер кадра, то Р может закрывать Q.
Поменять Р и Q местами, пометив позицию Q в списке. Повторить тесты с новым списком.
Если сделана попытка вновь переставить Q, значит, обнаружена ситуация циклического экранирования. В этом случае Р разрезается плоскостью, несущей Q, исходный многоугольник Р удаляется из списка, а его части заносятся в список. Затем тесты повторяются для нового списка. Этот шаг предотвращает зацикливание алгоритма.
Взятые вместе, первые два из приведенных выше вопросов образуют обычный габаритный тест для прямоугольных оболочек. Поскольку многие сцены не являются квадратными, то прямоугольные объемлющие оболочки будут с большей вероятностью перекрываться в одном из двух возможных направлений. Когда многоугольники преимущественно горизонтальны или вертикальны, то использование одного из этих двух тестов оказывается более эффективным. В алгоритме в той форме, в которой он записан выше, предполагается, что ширина сцены больше ее высоты, т. е. многоугольники преимущественно являются горизонтальными. Если высота сцены больше ее ширины, то тесты следует поменять местами. Если же сцена является квадратной или ее структура изоморфна, то порядок применения этих тестов не имеет значения.
АЛГОРИТМ ПОСТРОЧНОГО СКАНИРОВАНИЯ, ИСПОЛЬЗУЮЩИЙ Z-БУФЕР
Одним из простейших алгоритмов построчного сканирования, ко-
35