В отличие от алгоритма Робертса, Варнок в 1968 г. предложил алгоритм, работающий не в объектном пространстве, а в пространстве образа. Он также нацелен на изображение многогранников, а главная идея его основана на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. Так, например, рассматривая помещение, в котором имеется только картина на стене, мы быстро осматриваем стены, пол и потолок, а затем все внимание сосредоточиваем на картине. В свою очередь, на этой картине, если это портрет, мы бегло отмечаем фон, а затем более внимательно рассматриваем лицо изображенного персонажа, в особенности глаза, губы. Как правило, достаточно детально рассматриваются еще и руки и с чуть меньшим вниманием - одежда.

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

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

Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма каждое окно разбивалось на четыре одинаковых подокна. Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть (рис. 6.3)

  • внешним , если он целиком находится вне окна;
  • внутренним , если он целиком расположен внутри окна;
  • пересекающим , если он пересекает границу окна;
  • охватывающим , если окно целиком расположено внутри него.


Рис. 6.3.

Теперь можно в самом общем виде описать алгоритм.

Для каждого окна:

  1. Если все многоугольники сцены являются внешними по отношению к окну, то оно пусто; изображается фоновым цветом и дальнейшему разбиению не подлежит.
  2. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему внутренним, то окно заполняется фоновым цветом, а сам многоугольник заполняется своим цветом.
  3. Если только один многоугольник сцены имеет общие точки с окном и является по отношению к нему пересекающим, то окно заполняется фоновым цветом, а часть многоугольника, принадлежащая окну, заполняется цветом многоугольника.
  4. Если только один многоугольник охватывает окно и нет других многоугольников, имеющих общие точки с окном, то окно заполняется цветом этого многоугольника.
  5. Если существует хотя бы один многоугольник, охватывающий окно, то среди всех таких многоугольников выбирается тот, который расположен ближе всех многоугольников к точке наблюдения, и окно заполняется цветом этого многоугольника.
  6. В противном случае производится новое разбиение окна.

Шаги 1–4 рассматривают ситуацию пересечения окна только с одним многоугольником. Они используются для сокращения числа подразбиений. Шаг 5 решает задачу удаления невидимых поверхностей. Многоугольник, находящийся ближе всех к точке наблюдения, экранирует все остальные.

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

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

Алгоритм Вейлера-Азертона

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

  1. Предварительная сортировка по глубине.
  2. Отсечение по границе ближайшего к точке наблюдения многоугольника, называемое сортировкой многоугольников на плоскости.
  3. Удаление многоугольников, экранируемых более близкими к точке наблюдения многоугольниками.
  4. Если требуется, то рекурсивное разбиение и новая сортировка.

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

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

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

  1. Рекурсивно разбивается поверхность до тех пор, пока проекция элемента на плоскость изображения не будет покрывать не больше одного пикселя.
  2. Определить атрибуты поверхности в этом пикселе и изобразить его.

Эффективность такого метода, как и алгоритм Варнока, зависит от эффективности разбиений. В дальнейшем этот алгоритм был распространен на сплайновые поверхности.

Метод Z-буфера

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

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

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

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

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

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

Предполагается следующая последовательность шагов:

14.Особенности проекций гладких отображений

1-й случай

Заданная поверхность плоскость, описываемая уравнением Z = X и проектируемая на плоскость X = 0 (рис. 1).

Записав ее уравнение в неявном виде X-Z=0, Вектор L , вдоль которого осуществляется проектирование, имеет координаты

Вычислим координаты нормального вектора:

Скалярное произведение этих двух векторов отлично от нуля:

Тем самым вектор проектирования и нормальный вектор рассматриваемой поверхности не перпендикулярны ни в одной точке. Отметим, что полученная проекция особенностей не имеет.

2-й случай

Заданная поверхность параболический цилиндр с уравнением Z = X2 или, что то же, X2 - Z = 0. Нормальный вектор ортогонален вектору проектирования L в точках оси Y. Это вытекает из того, что .

Здесь, в отличие от первого случая, точки плоскости X = 0 разбиваются на три класса: к первому относятся точки (Z > 0), у которых два прообраза (на рис. 2 этот класс заштрихован); ко второму те, у которых прообраз один (Z = 0);

к третьему классу относятся точки, у которых прообразов на цилиндре нет вовсе. Прямая X = 0, Z = 0является особой. Вдоль нее векторы N ρ и L ρ ортогональны. Особенность этого типа называется складкой .

3-й случай

Рассмотрим поверхность, заданную уравнением X 3 + XY - Z = 0.

Пусть Y = 1 . Тогда Z = X 3 + X (рис. 3).

При Y = 0 имеем: Z = X 3 (рис. 4).

рис.3

рис. 4

Наконец, при Y = 1 получаем: Z = X 3 - X (рис. 5).

рис. 5

Построенные сечения дают представление обо всей поверхности. Поэтому нарисовать ее теперь уже несложно (рис. 6).

16.Растровая развертка отрезка

Для горизонтальных, вертикальных и наклоненных под углом 45°. отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пиксели труднее. Общие требования к изображению отрезка:

· концы отрезка должны находиться в заданных точках;

· отрезки должны выглядеть прямыми,

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.

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

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

· отрезок аппроксимируется набором пикселей и лишь в частных случаях вертикальных, горизонтальных и отрезков под 45  они будут выглядеть прямыми

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

Алгоритмы генерации отрезка:

1) Цифровой дифференциальный анализатор. Решается дифференциальное уравнение вида dY/dX = Py/Px, где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X. При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения. В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов. Получаемые значения X i , Y i преобразуются в целочисленные значения координаты очередного подсвечиваемого пикселя либо округлением, либо отбрасыванием дробной части. Генератор векторов, использующий этот алгоритм, имеет тот недостаток, что точки могут прописываться дважды, что увеличивает время построения. Кроме того из-за независимого вычисления обеих координат нет предпочтительных направлений и построенные отрезки кажутся не очень красивыми.

2) Алгоритм Брезенхема. Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации. Брезенхем предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки. Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

3) Модифицированный алгоритм Брезенхема. Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пикселя пропорционально площади пикселя, попавшей внутрь многоугольника.

Одной из уникальных характеристик растрового графического устройства является возможность представления сплошных областей. Генерацию сплошных областей из простых описаний ребер или вершин будем называть растровой разверткой сплошных областей, заполнением многоугольников или заполнением контуров. Для этого можно использовать несколько методов, которые обычно делятся на 2 категории: растровая развертка и затравочное заполнение.

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

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

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

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

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

Рисунок 8.8 Схема работы алгоритма.

Схема, иллюстрирующая работу алгоритма приведена на рис. 8.8.

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

Алгоритм требует большого объема памяти, так как информацию о глубине нужно обрабатывать с достаточно большой точностью. Буфер цвета размером 1024х768х24 бит в комбинации с z-буфером глубиной 20 бит требуют около 5 мегабайт памяти. Уменьшение требуемой памяти достигается разбиением пространства изображения на несколько частей (квадратов или полос). Если использовать z -буфер размером в одну строку развертки то мы получим интересный алгоритм построчного сканирования . Поскольку каждый элемент сцены обрабатывается много раз, то сегментирование z-буфера, вообще говоря, приводит к увеличению времени, необходимого для обработки сцены. Однако сортировка на плоскости, позволяющая не обрабатывать все многоугольники в каждом из сегментов, значительно сокращает вычислительные затраты.

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

4.11. ИНТЕРВАЛЬНЫЙ АЛГОРИТМ ПОСТРОЧНОГО СКАНИРОВАНИЯ

В алгоритме построчного сканирования с использованием z-буфера глубина многоугольника вычисляется для каждого пиксела на сканирующей строке. Количество вычислений глубины можно уменьшить, если использовать понятие интервалов, впервые введенных в алгоритме Ваткинса. На рис. 1, а показано пересечение многоугольников сцены со сканирующей плоскостью. Решение задачи удаления невидимых поверхностей сводится к выбору видимых отрезков в каждом из интервалов, полученных путем деления сканирующей строки проекциями точек пересечения ребер.

Из рисунка видно, что возможны только три варианта:

Рис. 8.9. Интервалы для построчного сканирования.

Интервал пуст, как, например, интервал 1 на рис. 8.9.а). – представляющие интервал пиксели имеют цвет фона.

Интервал содержит лишь один отрезок, как, например, интервалы 2 и 4 на рис. 8.9.а. - изображаются атрибуты многоугольника, соответствующего отрезку.

Интервал содержит несколько отрезков, как, например, интервал 3 на рис. 8.9.а). В этом случае вычисляется глубина каждого отрезка в интервале. Видимым будет отрезок с максимальным значением г. В этом интервале будут изображаться атрибуты видимого отрезка.

Если многоугольники не могут протыкать друг друга, то достаточно вычислять глубину каждого отрезка в интервале на одном из его концов. Если два отрезка касаются, но не проникают в концы интервала, то вычисление глубины производится в середине интервала, как показано на рис. 8.9 б) . Для интервала 3 вычисление глубины, проведенное на его правом конце, не позволяет принять определенное решение. Реализация вычисления глубины в центре интервала дает уже корректный результат.

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

АЛГОРИТМ ВАРНОКА

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

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

Рисунок 8.10 Схема разбиения окна в алгоритме Варнока

При достижении предела разрешения в окне обычно оказывается один приксел (при устранении лесничного эффекта и в некоторых других случаях разбиение может продолжаться и далее. Цвет пикселя определяется взвешиванием окраски его частей). Для выяснения видимости окна так же находятся ближайший из охватывающих многоугольников и многоугольников границам которых принадлежит этот пиксел. Схема нескольких начальных разбиений окна при обработке алгоритмом Варнока простой сцены, представлена на рис 8.10. При первом разбиении подокно 1а оказалось пустым, остальные три подокна потребовали дальнейшего разбиения. Разбиение окна 1в (порядок рассмотрения подокон не важен. Мы просматриваем подокна слева направо, сверху вниз) также дает четыре подокна. Окно 2а пустое, оно может быть заполнено цветом фона. Окно 2b также требует разбиения. Основываясь на данной схеме разбиения окна, при разрешении экрана 1024*1024, мы достигаем предела разрешения экрана после десяти разбиений (1024 = 2 10).

Рисунок 8.11 Разбиение окна на основе прямоугольной оболочки многоугольника.

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

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

· Расширение понятия простого содержимого окна (для него принимается решение о видимости без подразбиений). Для этого, рассматриваются возможные расположение многоугольника относительно окна и вводятся понятия внутреннего, внешнего, пересекающего и охватывающего многоугольника. На основе этих понятий вводятся правила обработки окон с простым содержанием. Примером может служить следующее правило: если в окне находится только один внутренний многоугольник, и у окна нет охватывающих многоугольников то площадь окна вне многоугольника закрашивается цветом фона а сам многоугольник заполняется соответствующим ему цветом;

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

АЛГОРИТМ ВЕЙЛЕРА-АЗЕРТОНА

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

· Предварительная сортировка по глубине (по Zmax).

· Сортировка многоугольников на плоскости.

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

· Если требуется, то рекурсивное подразбиение и окончательная сортировка, для устранения всех неопределенностей.

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

Рисунок 8.12. Тестовый пример.

В качестве отсекающего многоугольника используется копия первого многоугольника из предварительного списка приоритетов по глубине. Вводятся два списка: внутренний и внешний На основе сортировки на плоскости все многоугольники отсекаются по границам отсекающего многоугольника. Сортировка на плоскости или ху –сортировка это двумерная операция пересечения проекций отсекающего и отсекаемого многоугольников. Части отсекаемых многоугольников, попадающие внутрь внутри отсекающего, заносятся во внутренний список. Многоугольники или части многоугольников оставшиеся вне отсекающего образуют внешний список. Результат первой сортировки сцены приведенной на рисунке 8.12 показан на рис. 8.13

Рисунок 8.13 Сортировка на плоскости.

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

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


©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-20

Буфер глубины (Z-buffer, depth buffer) - двумерный массив данных, дополняющий двумерное изображение, где для каждого пикселя (фрагмента) изображения сопоставляется «глубина» (расстояние от наблюдателя до поверхности изображаемого объекта).

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

Буфер глубины может иметь различную разрядность данных:

  • 16 бит. Устаревший формат с невысокой точностью. На современных видеокартах используется редко, например для рендера в текстуру глубины на картах АТИ Радеон 9***, которые не поддерживают получения данных буфера глубины более высокой разрядности.
  • 24 бита. Можно сказать, стандартный тип данных буфера глубины, в основном используется он.
  • 32 бита. Формат ещё более высокой точности, но совершенно не распространён, не стоит рассчитывать на его поддержку.

Если для отрисовки нужен буфер трафарета, то данные для него будут расположены вместе с данными буфера глубины. Например, при использовании 24-битного буфера глубины на один фрагмент изображения будет приходиться 32 бита данных (не считая цвета), 8 бит которых будут представлять данные буфера трафарета.

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

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

Действие Название в Название в Название в
false D3D10_COMPARISON_NEVER D3DCMP_NEVER GL_NEVER
Znew < Zold D3D10_COMPARISON_LESS D3DCMP_LESS GL_LESS
Znew == Zold D3D10_COMPARISON_EQUAL D3DCMP_EQUAL GL_EQUAL
Znew <= Zold D3D10_COMPARISON_LESS_EQUAL D3DCMP_LESSEQUAL GL_LEQUAL
Znew > Zold D3D10_COMPARISON_GREATER D3DCMP_GREATER GL_GREATER
Znew != Zold D3D10_COMPARISON_NOT_EQUAL D3DCMP_NOTEQUAL GL_NOTEQUAL
Znew >= Zold D3D10_COMPARISON_GREATER_EQUAL D3DCMP_GREATEREQUAL GL_GEQUAL
true D3D10_COMPARISON_ALWAYS D3DCMP_ALWAYS GL_ALWAYS

Где Znew значение глубины фрагмента и Zold предыдущее значение глубины.
Функция сравнения устанавливается функциями IDirect3DDevice::SetRenderState(D3DRS_ZFUNC, func) в DirectX, и glDepthFunc(func) в OpenGL. Также для работы следует включить тест глубины функциями IDirect3DDevice::SetRenderState(D3DRS_ZENABLE, true) в DirectX, и glEnable(GL_DEPTH_TEST) в OpenGL.

После того как тест пройден, новое значение записывается в буфер глубины. В некоторых алгоритмах требуется отключить данный шаг. Это делается вызовами IDirect3DDevice::SetRenderState(D3DRS_ZWRITEENABLE, false) или glDepthMask(false); значение по умолчанию - true.

Полученное значение z" затем нормализуется в диапазон , где 0 - у ближней плоскости отсечения, и 1 - у дальней.
Значения глубины точки не находятся в линейной зависимости от расстояния до камеры. Значения у ближней плоскости расположены очень плотно, а с увеличением дальности к дальней плоскости отсечения всё более редко. По этой причине нужно следить за расстояниями, на которых вы ставите плоскости отсечения: ближнюю плоскость не стоит ставить слишком близко! В противном случае можно получить множество артефактов изображения вдали, в особенности z-fighting, когда небольшое изменение ракурса камеры может изменить видимость близко расположенных треугольников.

Что такое Буфер глубины (Z-buffer)?


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

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

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

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

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

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

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

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

4. Для каждого объекта:

· Для каждого пикселя образа вычислить его глубину .

· Сравнить глубину со значением глубины, хранящимся в Z-буфере в этой же позиции.

· Если , то занести атрибуты пикселя в буфер кадра и заменить . В противном случае никаких действий не производить.

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

где - глубина искомого сечения.

Методы приоритетов (художника, плавающего горизонта)

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

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

Пусть поверхность задана уравнением

В качестве картинной плоскости выберем плоскость . В области задания функции на осях координат построим сетку узлов:

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

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

Рис. 7.4. Простое каркасное изображение с поверхности

Рис. 7.5. Каркасное изображение диагональными ребрами

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

На самом деле мы будем рисовать четырехугольник и одну диагональ. В процессе рисования нам понадобятся два целочисленных массива: (нижний горизонт) и (верхний горизонт) размерностью, соответствующей горизонтальному размеру экрана в пикселях. Они нужны для анализа видимости участков изображаемых отрезков. Сначала мы инициализируем верхний горизонт нулем, а нижний - максимальным значением вертикальной координаты на экране. Каждая выводимая на экран точка может закрывать другие точки, которые "скрываются за горизонтом". По мере рисования нижний горизонт "опускается", а верхний "поднимается", постепенно оставляя все меньше незакрытого пространства. В отличие от метода художника, здесь мы продвигаемся от ближнего угла к дальнему. Теперь опишем алгоритм подробнее.