Удаление невидимых поверхностей и линий. Удаление невидимых граней

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм, использующий 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).

Рис. 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-буфер. Отличительной особенностью алгоритма является его простота. Алгоритм работает в пространстве изображения. Основные шаги алгоритма следующие:

• заполнить буфер кадра фоновым значением интенсивности или цвета, 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

Дата создания: 2010-03-18 14:07:57
Последний раз редактировалось: 2012-03-01 02:48:07

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

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

На рисунке а объект нарисован неправильно. Здесь мы видим "внутренности " (задние треугольники) модели. Именно так рисовались все наши объекты до сих пор. На рисунке б показан правильно нарисованный объект. Собственно, наша задача в сегодняшнем уроке - научиться рисовать треугольники в правильном порядке.

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

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

Сортировка треугольников

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

Самый простой случай - когда треугольники расположены параллельно проекционной плоскости:

На рисунке а - вид сверху, на рисунке б - конечное изображение. В данном случае очень легко определить порядок треугольников:
1. Нужно взять z значение любых вершин обоих треугольников.
2. Отсортировать (например, с помощью метода пузырька) треугольники по z значению.
3. Вывести треугольники в порядке уменьшения z: сначала будут выведены дальние треугольники, затем ближние.

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

Самое главное здесь: треугольники сортируются по z-значению, а затем выводятся в зависимости от z-значения: от самого большого, к самому маленькому.

Существуют более сложные случаи расположения треугольников, где простая сортировка выдаст неверный результат:

Расположение треугольников, показанное на этой картинке маловероятно в реальных ситуациях, но тем не менее этот случай стоит рассмотреть. Здесь нельзя просто воспользоваться сортировкой по z координатам. Чтобы правильно отобразить эти треугольники, их придётся разрезать на более мелкие. Сделать это не так-то просто.

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

Буфер глубины в DirectX

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

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

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

После преобразования в проекционную плоскость (это не совсем плоскость, скорее это половина куба), значения вершин по x и y расположены между -1 и 1. Значения z находятся на отрезке от нуля до единицы.

Как мы выяснили в прошлом уроке, далее происходит переворачивание картинки (умножение y координаты всех вершин на -1) и "растягивание" картинки по вертикали и горизонтали до размера окна. После этого x и y координаты всех вершин будут находиться в диапазоне от нуля до ширины/высоты. Заметьте, здесь x, y координаты уже будут целыми числами (в проекционной плоскости они были дробными), потому что это уже координаты пикселей в окне. Нельзя обращаться к пикселям как 25,5 или 126,0023, только 25 или 126. В данный момент ещё не существует никаких треугольников, только вершины, которые описывают эти треугольники. При этом координаты z этих вершин всё это время остаются неизменными - они расположены на отрезке .

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

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

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

Программные и аппаратные вычисления (Software and hardware rendering)

Когда в методе IDirect3D9::CreateDevice мы указываем второй параметр как D3DDEVTYPE_HAL, это значит что растеризация (а вместе с ней и все вычисления связанные с буфером глубины), будет выполняться аппаратно. Если передаётся D3DDEVTYPE_REF, то вычисления будут производиться программно.

Чем отличаются программные вычисления от аппаратных? Центральный процессор компьютера может производить любые вычисления (на самом деле большую часть времени процессор занят выполнением простейших арифметических операций). Когда мы в программе "Камера" самостоятельно производили преобразования, все вычисления происходили программно, т.е. для этого была написана специальная программа (функции multiplication и transformation). Затем эту программу выполнял центральный процессор. Но в DirectX есть возможность производить преобразования аппаратно. Для этого нужно задать матрицы преобразования через SetTransform. При программных вычислениях всё делает центральный процессор. При аппаратных, вычислениями занимается отдельное физическое устройство, специально созданное для данной конкретной задачи. Но тут есть одна проблема: если в видеокарте нет аппаратной поддержки какой-нибудь функции (например, z-буфера или преобразований), то всё придётся делать центральному процессору программно.

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

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

Использование z-буфера в DirectX

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

В структуре D3DPRESENT_PARAMETERS для z-буфера выделено два поля:

BOOL EnableAutoDepthStencil; D3DFORMAT AutoDepthStencilFormat;

Первое поле позволяет включить (enable) использование буфера глубины для данного устройства. Второй флаг задаёт формат буфера глубины. В настоящее время в буфере глубины вместе хранятся и z-буфер и трафаретный (stencil) буфер. О трафаретном буфере мы будем говорить позже.

Форматы буфера глубины могут быть следующими (это не все форматы):
D3DFMT_D16_LOCKABLE
16-битный замыкаемый буфер глубины.
D3DFMT_D32
32-битный буфер глубины.
D3DFMT_D15S1
16-битный буфер глубины. 15 бит - на канал z-буфера, 1 бит на канал трафаретного буфера.
D3DFMT_D24S8
32-ухбитный буфер глубины. 24 бита - z-буфер, 8 бит - трафаретный буфер.
D3DFMT_D24X8
32-ухбитный буфер глубины. 24 бита - z-буфер, 8 бит не используется.
D3DFMT_D24X4S4
32-битный буфер глубины. 24 бита - z-буфер, 4 бита не используется, 4 бита - трафаретный буфер.

Мы будем использовать D3FMT_D24S8. Пока что канал трафаретного буфера будет пустовать. Теперь заполнение структуры D3DPRESENT_PARAMETERS будет выглядеть так:

D3DPRESENT_PARAMETERS pp; ZeroMemory(&pp,sizeof(pp)); pp.BackBufferWidth = 500; pp.BackBufferHeight = 500; pp.BackBufferFormat = D3DFMT_X8R8G8B8; pp.BackBufferCount = 1; pp.MultiSampleType = D3DMULTISAMPLE_NONE; pp.SwapEffect = D3DSWAPEFFECT_DISCARD; pp.hDeviceWindow = hWnd; pp.Windowed = true; pp.EnableAutoDepthStencil = 1; pp.AutoDepthStencilFormat = D3DFMT_D24S8; pp.Flags = D3DPRESENTFLAG_LOCKABLE_BACKBUFFER;

При создании фоновой и основной поверхности, Direct3D создаст и буфер глубины. При этом количество элементов в фоновой/основной поверхности равно количеству элементов в буфере глубины. Больше ничего делать не нужно, DirectX всё остальное сделает за нас. Единственное, каждый кадр необходимо очищать буфер глубины (так же как и фоновый буфер). Для этого используется уже знакомый нам метод Clear:

HRESULT Clear(DWORD Count, CONST D3DRECT * pRects, DWORD Flags, D3DCOLOR Color, float Z, DWORD Stencil);

Третий параметр - набор флагов: D3DCLEAR_STENCIL, D3DCLEAR_TARGET, D3DCLEAR_ZBUFFER. Так как нам нужно очищать фоновый буфер и буфер глубины, то указывать мы будем два последних флага. Предпоследний аргумент - значение z, которым будут проинициализированы все элементы z-буфера. Сюда нужно передавать максимальное значение z-буфера - единицу. Теперь пример вызова метода Clear:

Dev->Clear(0, NULL, D3DCLEAR_TARGET | 3DCLEAR_ZBUFFER, D3DCOLOR_XRGB(255,255,255), 1.0f, 0);

Вот и всё.

Состояния рендеринга z-буфера

Для управления поведением z-буфера доступно несколько типов состояний:

D3DRS_ZENABLE
Позволяет включить/выключить z-буфер. Возможны три варианта: D3DZB_FALSE - z-буфер выключен, D3DZB_TRUE - z-буфер включён, D3DZB_USEW - вместо z-буфера использовать w-буфер. По умолчанию используется состояние в зависимости от значения поля EnableAutoDepthStencil структуры D3DPRESENT_PARAMETERS.

D3DRS_ZWRITEENABLE
Тип состояния разрешает запись в z-буфер. По умолчанию установлено TRUE. Если установлено значение FALSE, то пикселю будут тестироваться на значение z, но запись новых значений в z-буфер запрещена. Практически никогда не используется.

D3DRS_ZFUNC
Этот тип состояний позволяет изменить способ, каким сравниваются пиксели. По умолчанию значение z пикселя сравнивается со значением z буфера глубины, и если у пикселя z-значение меньше или равно, то в z-буфер записывается новое значение. В данном случае используется значение D3DCMP_LESSEQUAL (less - меньше, equal - равно). Т.е. данный тип состояний позволяет изменить функцию сравнения значений глубины пикселя и z-буфера. Кроме D3DCMP_LESSEQUAL другие значения практически никогда не используются на практике.

w-буфер и z-буфер

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

Для решения этой проблемы использовался w-буфер. Т.е. вместо z координаты проверялась однородная. Не во всех видеокартах есть поддержка w-буфера. Сейчас, когда в большинстве случаях используется 24-битные или даже 32-ухбитные z-буферы, использовать w-буфер не имеет смысла.

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

Как мы выяснили, z-буфер требует довольно больших вычислительных мощностей. В реальных программах z-буфер обязательно должен создаваться аппаратно. Но не все видеокарты поддерживают все форматы буфера глубины. Например, моя видеокарта не поддерживает D3DFMT_D32. В DirectX есть возможность проверить, какие форматы буфера глубины (и других поверхностей) поддерживает видеокарта. Для этого используется метод IDirect3D9::CheckDeviceFormat. Этот метод нужно вызывать до заполнения структуры D3DPRESENT_PARAMETERS:

HRESULT CheckDeviceFormat(UINT Adapter, D3DDEVTYPE DeviceType, D3DFORMAT AdapterFormat, DWORD Usage, D3DRESOURCETYPE RType, D3DFORMAT CheckFormat);

UINT Adapter
Первый параметр указывает, какой графический адаптер будет проверяться. Здесь возможны разные значения, если на компьютере расположено больше одной видеокарты. Мы будем передавать 0 или D3DADAPTER_DEFAULT (это одно и то же).

D3DDEVTYPE DeviceType
Тип устройства. Практически всегда передаётся D3DDEVTYPE_HAL. Этот тип устройства говорит, что будет проверяться аппаратная поддержка.

D3DFORMAT AdapterFormat
Формат вывода изображения адаптера. Сюда передаётся формат фоновой/основной поверхностей.

DWORD Usage
Параметр, указывающий, каким образом используется поверхность, формат которой проверяется. Так как мы проверяем буфер глубины, то передавать нужно D3DUSAGE_DEPTHSTENCIL. Другие возможные значения вы можете посмотреть в документации: Direct3D Reference → Constants → D3DUSAGE.

D3DRESOURCETYPE RType
Тип ресурса. Мы проверяем поверхность (буфер глубины - это поверхность), поэтому значение будет D3DRTYPE_SURFACE. Другие значения D3DRESOURCETYPE можно посмотреть в справке: Direct3D Reference → Enumerations → D3DRESOURCETYPE.

D3DFORMAT CheckFormat
Формат, который нужно проверить.

Вот пример проверки аппаратной поддержки формата D3DFMT_D24S8:

HRESULT hr = 0; hr = CheckDeviceFormat(D3DADAPTER_DEFAULT, D3DDEVTYPE_HAL, D3DFMT_X8R8G8B8, D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_SURFACE, D3DFMT_D24S8); if (hr != S_OK) { // формат не поддерживается }

Если формат не поддерживается, то функция вернёт значение отличное от S_OK.

Ещё одно замечание по поводу S_OK. Когда мы проверяли ввод в DirectInput, для проверки успешного выполнения функции мы использовали константу DI_OK. В Direct3D есть своя константа, которая проверяет успешное завершение функции - D3D_OK. Все три константы: S_OK, DI_OK, D3D_OK - имеют одно и то же значение - ноль. Можно использовать любую.

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

Заключение

Сегодня мы познакомились с двумя способами вывода треугольников в правильном порядке.

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

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

На сегодня всё. До скорой встречи.