Помощь по Теле2, тарифы, вопросы

Это один из простейших алгоритмов удаления невидимых поверхностей. Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения.

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

Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона координат z значений, то можно использовать z-буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (x, y) ; обычно бывает достаточно 20 бит. Буфер кадра размером 512*512*24 бит в комбинации с z-буфером размером 512*512*20 бит требует почти 1.5 мегабайт памяти.

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

Формальное описание алгоритма z-буфера:

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

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

Оптимизация алгоритма

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

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

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

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

Основной недостаток алгоритма - большой объем требуемой памяти. Если сцена подвергается видовому преобразованию и отсекается до фиксированного диапазона значений координат z , то можно использовать z -буфер с фиксированной точностью. Информацию о глубине нужно обрабатывать с большей точностью, чем координатную информацию на плоскости (х, y) ; обычно бывает достаточно 20-ти бит. Буфер кадра размером 512´512´24 бит в комбинации с z -буфером размером 512´512´20 бит требует почти 1.5 мегабайт памяти. Однако снижение цен на память делает экономически оправданным создание специализированных запоминающих устройств для z -буфера и связанной с ним аппаратуры.

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

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

Формальное описание алгоритма z -буфера таково:

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

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

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

4. Для каждого Пиксель (x,y ) в многоугольнике вычислить его глубину z (x,y ).

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

Если z (х,у ) > Zбуфер (х,у ), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер (х,у ) на z (х,у ). В противном случае никаких действий не производить.

На псевдокоде алгоритм можно представить так:

for all covered pixels

compare z

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

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

(x a , y, z a)

(x 1 , y 1 , z 1 )

(x, y, z)

(x 2 , y 2 , z 2 )

(x 3 , y 3 , z 3 )

(x b , y, z b)

Рис. 8.11. Сканирующая строка по грани

Для рисунка y меняется от y 1 до y 2 и далее до y 3 , при этом для каждой строки определяется x a , z a , x b , z b :

x a = x 1 + (x 2 - x 1)× ;

x b = x 1 + (x 3 - x 1)× ;

z a = z 1 + (z 2 - z 1)× ;

z b = z 1 + (z 3 - z 1)× .

На сканирующей строке x меняется от x a до x b и для каждой точки строки определяется глубина z :

z = z a + (z b - z a )×

Реализация алгоритма вдоль сканирующей строки позволяет совместить алгоритм z -буфера с алгоритмами растровой развертки ребер и алгоритмами закраски грани.

Проиллюстрируем работу алгоритма на примере для рис. 8.12.

Рис. 8.12. Протыкающий треугольник

В начале в буфере кадра и в z -буфере содержатся нули. После растровой развертки прямоугольника содержимое буфера кадра будет иметь вид

Содержимое z -буфера таково:

При обработке треугольника преобразование его в растровую форму и сравнение по глубине дает новое значение буфера кадра:

Новое содержимое z -буфера таково.

Буфер глубины (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)?

В отличие от алгоритма Робертса, Варнок в 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 для сцены. Если необходимо то удалить не лицевые грани;
• растеризовать каждый многоугольник сцены (порядок произволен);
• для каждой точки многоугольника с координатами (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