Алгоpитм z buffer


Содержание

Удаление невидимых граней. Алгоритм z-буфера

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

Главное преимущество алгоритма — его простота. Кроме того, этот алгоритм решает задачу об удалении невидимых поверхностей и делает тривиальной визуализацию пересечений сложных поверхностей. Сцены могут быть любой сложности. Поскольку габариты пространства изображения фиксированы, оценка вычислительной трудоемкости алгоритма не более чем линейна. Поскольку элементы сцены или картинки можно заносить в буфер кадра или в 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-буфер (стр. 1 из 2)

Разработать программу, реализующую алгоритм удаления невидимых линий и поверхностей методом Z-буфера.

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

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

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

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

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

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

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

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

Во втором методе оба буфера, заданные в пространстве изображения, имеют повышенную разрешающую способность. При визуализации изображения как пикселная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512 * 512 * 24 бита, использующее z-буфер размером 20 бит на пиксел, разрешение которого повышено в 2 раза по осям x и y и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 мегабайт памяти.

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

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

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

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

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

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

если z(x, y) > Zбуфер(x, y), то записать атрибут этого многоугольника (интенсивность, цвет и т. п.) в буфер кадра и заменить Zбуфер(x, y) на z(x, y);

в противном случае никаких действий не производить.

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

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

ax + by + cz + d = 0

z = -(ax + by + d)/c <> 0.

Для сканирующей строки y = const. Поэтому глубина пиксела на этой строке, у которого x1 = x + Dх, равна

z1 — z = -(ax1 + d)/c + (ax + d)/с = a(x — x1)/c или


Но Dx = 1, поэтому z1 = z — (a/c).

Дальнейшей иллюстрацией алгоритма послужит следующий пример.

Пример. Алгоритм, использующий z-буфер. Рассмотрим многоугольник, координаты угловых точек которого равны P1(10, 5, 10), P2(10, 25, 10), P3(25, 25, 10), P4(25, 5, 10) и треугольник с вершинами P5(15, 15, 15), P6(25, 25, 5), P7(30, 10, 5). Треугольник протыкает прямоугольник, как показано на рис. 21.1. Эти многоугольники нужно изобразить на экране с разрешением 32 * 32, используя простой буфер кадра с двумя битовыми плоскостями. В этом буфере фон обозначен через 0, прямоугольник — через 1, а треугольник — через 2. Под z-буфер отводится 4 битовых плоскости размером 32 * 32 бит. Таким образом, содержимое z-буфера окажется в диапазоне от 0 до 16. Точка наблюдения расположена в бесконечности на положительной полуоси z, как показано на рис. 21.1b.

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Напомним, что в левом нижнем углу находится пиксел (0, 0).

Используя метод Ньюэла, получаем уравнение плоскости треугольника 3x + y + 4z — 120 = 0.

Алгоритм использующий 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 отсекающего, то такой многоугольник по крайней мере частично экранирует отсекающий многоугольник. Следовательно, результат предварительной сортировки по глубине ошибочен. Многоугольник, нарушивший порядок, выбирается новым отсекающим многоугольником. Отсечению подлежат многоугольники из внутреннего списка, причем старый отсекающий многоугольник теперь сам будет подвергнут отсечению новым отсекающим многоугольником. Подчеркнем, что новый отсекающий многоугольник является копией исходного многоугольника, а не его остатка после первого отсечения. Использование копии неотсеченного многоугольника позволяет минимизировать число разбиений.

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

Алгоритм, использующий Z буфер.

Алгоритм работает в пространстве изображения.

Буфер кадра (регенерации) используется для заполнения атрибутов (интенсивности) каждого пикселя в пространстве изображения.

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

  1. Простота. Сцены могут быть любой сложности
  2. Элементы сцены не нужно сортировать
  1. Большой объём памяти
  2. Трудоёмкость устранения лестничного эффекта
  3. Трудоёмкость реализации эффектов прозрачности
  1. Заполнение буфера кадра фоновый значением интенсивности (цвета).
  2. Заполнение Z — буфера минимальным значением Z .
  3. Преобразование каждого многоугольника в растровую форму в произвольном порядке.
  4. Вычисление для каждого пикселя с координатами (x, y), принадлежащего многоугольнику, его глубины Z(x, y).
  5. Сравнение глубины Z(x, y) со значением Zбуф(x, y), хранящимся в Z-буфере для пикселя теми же координатами(x, y). Если Z(x, y)>Zбуф(x, y), то записать атрибут очередного многоугольника в буфер кадра и Zбуф(x, y) заменить на значение Z(x, y).
Илон Маск рекомендует:  CSS-градиент

Замечание
Алгоритм, использующий Z -буфер, можно применять для построения разрезов поверхностей. В этом случае изменяется только операция сравнения глубины пикселя со значением, занесенным в буфер: [Z(x, y) > Zбуф (x, y)] и (Z(x, y

Алгоритм, использующий список приоритетов (алгоритм Художника)

В основе алгоритма способ изображения сцены от дальних объектов к ближним.

  1. Отсортировать многоугольники сцен в кадре в порядке возрастания Z
  2. Построить самый дальний многоугольник, если он не экранирует другие другие многоугольники (Zmax(A) Zmin(Q). Если на один из тестов даётся + ответ, P заносится в буфер кадра (P не экранирует Q). Если все -, то P и Q меняются местами, позиция Q помечается, тесты повторяются снова. Если вновь попытка менять местами, то P разрезается плоскостью, несущей Q, исходный многоугольник удаляется из списка, а его части заносятся в список. Тесты повторяются снова.
    1. верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по X? по Y?
    2. верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения
    3. верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая расположена ближе к точке наблюдения
    4. верно ли, что проекции P и Q не перекрываются

Для 3,4 можно проверять функцией f=Ax+By+Cz+D, где A, B, C – коэффициенты пробной плоскости U. В f подставляются координаты вершин испытуемого многоугольника W. Если знаки f для вершин совпадают и + или =0, то W находится с дальней стороны от плоскости U. Если знаки совпадают и отрицательны или равны 0, то W расположен с ближней стороны от U.

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

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

  1. Подготовка информации
    a) Для каждого многоугольника определить самую верхнюю сканирующую строку, которую он пересекает.
    b) Занести многоугольник в группу y, соответствующую этой сканирующей строке
    c) Запомнить для каждого многоугольника: Δy – число строк, пересекающих этот многоугольник, список рёбер многоугольника, коэффициенты A, B, C, D уравнения плоскости многоугольника, визуальные атрибуты многоугольника
  2. Решение задачи удаления невидимых поверхностей
    a) Инициализировать буфер кадра дисплея
    b) Для каждой сканирующей строки
  1. Инициализировать буфер кадра размером с одну сканирующую строку, заполнив его фоновым изображением
  2. Инициализировать Z-буфер размером с одну сканирующую строку значением Zmin
  3. Проверить необходимость добавления в список активных многоугольников (САМ)
    новых многоугольников
  4. Если было добавление многоугольника в САМ, то добавить в САР соответствующие рёбра новых многоугольников
  5. Если произведено удаление какого-либо элемента из пары рёбер САР, то проверить необходимость удаления всего многоугольника из САМ. Если он остаётся, то проверить необходимость удаления другого ребра из этой пары – если его удалять не нужно, то доукомлектовать пару (добавив недостающее левое или правое ребро)
    c) В САР должна храниться следующая информация:
    1) Xл – пересечение левого ребра с текущей сканирующей строкой
    2) ΔXл – приращение Xл в интервале между соседними сканирующими строками
    3) ΔYл – число сканирующих строк, пересекаемых левым ребром
    4) Xп, ΔXп, ΔYп
    5) ΔZх=-A/C для C≠0 (иначе ΔZх=0) – приращение по Z вдоль сканирующей строке
    6) ΔZy=-B/C для C≠0 (иначе ΔZy=0) – приращение по Z в интервале между соседними сканирующими строками
    d) Для каждой пары ребёр многоугольника из САР выполнить:
    1) Извлечь
    2) Инициализировать Z значением Zл
    3) Для каждого пикселя Xл≤X≤Xп вычислить Z(x,y=const). Z1=Zл, . Zk=Zk-1+ ΔZх
    4) Если Z()>Zбуф(), то Zбуф=Z и занести атрибуты многоугольника в буфер кадра
    e) Записать буфер кадра сканирующей строки в буфер кадра дисплея
    f) Скорректировать САР
    1) ΔYл—, ΔYп—
    2) Xл=Xл+ΔXл, Xп=Xп+ΔXп
    3) Zл=Zл+ΔZхΔX+ΔZy
    4) Если ΔYл

Дата добавления: 2020-01-14 ; просмотров: 92 ; ЗАКАЗАТЬ РАБОТУ

Иерархический Z-буфер

Преамбула

Поводом для перевода данной статьи послужил новый графический чипсет от ATI Radeon 256, а именно, примененная в нем технология HyperZ, позволяющая, по утверждениям самой ATI, при тактовой частоте в 200 Мгц достичь магической цифры — 1.5 Гигатекселей в секунду (при положенных на данной частоте 1.2 Gtex). Что это — новый прорыв в области трехмерной графики или реализация уже изобретенных идей? Сама ATI это тщательно скрывает, а между тем, большинство аналитиков и специалистов в области дизайна графических чипсетов сходятся на мысли, что данный 20%-ный прирост производительности получается за счет применения Z-буфера с уменьшенным разрешением и выделения высвобождающихся ресурсов на другие нужды. Вот что написал по этому поводу Eric Haines, автор переживающей второе издание книги Real-Time rendering (http://www.realtimerendering.com)

«… Из переписки с Peter Glazkowsky, который изучает графические чипы всю свою жизнь, вырисовывается следующее:

HyperZ работает на тайловой основе, т.е на основе разбиения экрана на квадратные фрагменты. Radeon вырисовывает полигон сначала в обычном порядке, затем в тайловом, и если тайл полностью закрывает собой полигон, то он отбрасывается и исключается из дальнейшей обработки. Это простой, но очень эффективный трюк, так как сюжет большинства трехмерных игр разыгрывается в сценах, содержащих стены, потолки и т.д. ATI сообщает, что такой подход экономит до 20% времени при рендеризации.

Что это означает? А скорее всего то, что алгоритм сохраняет значение только самого «удаленного» значения Z из всего тайла ( например, 8х8 пикселей, какой именно размер использует ATI, я не знаю), и при рендеризации полигона вычисляется его ближайшее значение для каждого тайла, который он перекрывает. И если выясняется, что это ближайшее значение находится дальше самого удаленного для тайла, то мы сразу выбрасываем этот полигон. Он нам больше не нужен, т.к. мы его просто не видим. Участок стены покрывает часть экрана размером 8х8, тогда все, что находится за этим участком, будет отсечено всего одной операцией сравнения, вместо традиционного исследования всех 64 пикселей один за другим.

Мне кажется, что в течение времени мы периодически будем встречать объявления о реализации вещей, подобных этим, по мере того, как все больше и больше функций графического конвейера будет реализовываться в hardware. Так, несколько лет назад, мы могли слышать, что HP Visualize fx позволяет рендеризовать проекции трехмерных кубических подпространств, содержащих в себе элементы геометрии сцены. В действительности, проекции этих подпространств на экран, конечно же, не выводились, но спроецированные грани мы могли проверить Z-буфером на видимость. CPU затем мог сказать нам, является ли проверяемый куб видимым, и если нет, то разом отпадала необходимость заниматься просчетом тех полигонов, которые содержались в этом подпространстве. «

А между тем, идея применения Z-буфера с низким разрешением была разработана уже давно. Z-пирамида — яркий тому пример. Впрочем, как и алгоритм отсечения невидимой геометрии при помощи кубических подпространств, содержащих эту геометрию. Алгоритм, реализующий сразу оба таких подхода, называется Hierarchical Z-buffer. Был впервые разработан для рендеризации сцен большой геометрической сложности, описан в далеком 1993 и опробован на мощнейших тогда системах на базе SGI Crimson Elan и Titan.

«Зачем мне читать такое старье?» — спросите вы.

Потому что то, что проектировалось в 1993 году исключительно для дорогостоящих графических станций, сейчас вполне доступно для реализации на нынешних PC. Этот материал не потерял актуальности. И специфические реализации тех времен только сейчас находят свое применение в системах, ориентированных на массового пользователя.

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


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

  • Object spaceобъектное пространство, определяет совокупность всех объектов в сцене, оно трехмерно и описывается тремя координатами: X — ширина, Y — высота, Z — глубина.
  • Image spaceотображаемое пространство (пространство изображения), проекция трехмерного пространства на двумерную плоскость (экран), описывается двумя координатами X, Y и адресуется попиксельно.
  • Interactive graphicинтерактивная компьютерная графика. Термин очень широко используется в зарубежных компьютерных кругах и подразумевает под собой совокупность используемых методов проектирования объектного пространства и его отображения с таким расчетом, чтобы дискретность вывода окончательных кадров анимации была незаметна человеческому глазу.
  • Renderingрендеризация, в общем смысле — процесс просчета трехмерной модели или примитива на двумерную плоскость. Рендеризация совсем не означает непосредственный вывод на экран, так как рендеризация чаще всего осуществляется в определенный буфер памяти для дальнейшей работы с ним.

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

Общее

Алгоритмы определения видимости объектов прежде всего должны а) быстро отсечь большую часть невидимой геометрии модели(объекта) и б) эффективно утилизовать пространственную и, по возможности, переходную когерентность (взаимосвязь) между растеризуемыми изображениями. Ray casting с пространственным делением отлично подходит под пункт а), но слабо удовлетворяет критерию б). Scan conversion (отсечение при растеризации) с традиционным базовым Z-буфером хорошо реализует б), но не подходит под критерий а). В данной статье мы опишем иерархический алгоритм Z-buffer scan-conversion, который реализует оба критерия одновременно. Это метод использует две иерархических структуры данных, полученных в результате:

  • рекурсивного деления объектного пространства на 8 подпространств (object space octree).
  • создания Z-пирамиды в отображаемом пространстве для акселерации растеризации.

Полученные две структуры данных делают возможным быстро отсекать невидимую геометрию и, в то же время, визуализировать видимую со скоростью получаемой при scan conversion. При анимации данный алгоритм позволит использовать переходную когерентность (взаимосвязь) между кадрами. Этот метод наиболее подходит для сцен с высокой геометрической сложностью и значительной глубиной и в некоторых случаях позволяет достичь скорости просчета на несколько порядков выше традиционного Z-buffer scan conversion.

1. Введение

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

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

  1. Когерентность в объектном пространстве: во многих случаях однократное вычисление позволит определить видимость целого набора рядом расположенных объектов.
  2. Когерентность в отображаемом двумерном пространстве: очень часто однократное вычисление позволяет определить видимость объекта, покрывающего определенный набор пикселей на экране.
  3. Переходная когерентность — информация о видимости объектов в одном кадре, зачастую может быть использована для ускорения просчетов в следующем кадре.

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

Доминирующими технологиями для просчета видимости являются Z-buffer scan conversion и ray tracing. Т.к. алгоритмы, использующие Z-буфер, не очень эффективно работают с частично прозрачными поверхностями, поэтому мы ограничим обсуждение моделями, состоящими из непрозрачных поверхностей. В случае применения таких моделей для определения видимости нам достаточно луча, направленного из камеры до поверхности, таким образом, мы остановимся только на алгоритмах Z-буферизации и ray casting (тот же ray tracing, только без учета вторичного луча).

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

Традиционные методы трассировки луча (ray tracing или ray casting), наоборот, используют когерентные связи в объектном пространстве, реализуя некоторого рода пространственное деление. Луч из глаз наблюдателя (или камеры) проходит через структуру поделенного пространства, пока не коснется первой видимой поверхности. Как только луч достиг поверхности, уже нет необходимости рассматривать остальные поверхности в подпространствах, расположенных за первой поверхностью по ходу луча. Таким образом, мы исключаем из дальнейшей обработки значительное количество геометрии. В этом контексте мы получили значительное преимущество по сравнению с традиционным Z-буфером, но не использовали когерентность в отображаемом пространстве и переходные взаимосвязи между кадрами. Здесь нужно заметить, что в алгоритмах основанных на трассировке лучей все же вполне возможно утилизовать переходные когерентные связи, но реализовать когерентность в отображаемом пространстве (image space coherence) представляется очень и очень сложной задачей.

В нашем случае мы представляем алгоритм, который объединяет в себе силы сразу двух (ray casting и Z-buffering) алгоритмов. Для утилизации когерентных связей в объектном пространстве мы будем использовать рекурсивное деление пространства на 8 подпространств. Реализацию когерентности в пространстве изображения возложим на Z-buffer scan conversion, усовершенствованный при помощи Z-пирамиды, которая позволит нам очень эффективно отсекать невидимые части геометрии сцены. И наконец, для использования переходной когерентности в качестве стартовой точки начала всего алгоритма для каждого кадра мы будем использовать уже просчитанную видимую геометрию из предыдущего кадра. Представляемый алгоритм не сложен для реализации и применим для полигонных наборов любой сложности. И чем сложнее использованная геометрия в сцене и чем выше разрешения конечного изображения, тем заметнее будет разница в скорости просчетов по сравнению с традиционными алгоритмами.

Во второй части статьи мы дадим оценку уже проведенным исследованиям и разработкам по ускорению работы алгоритмов ray-tracing и scan conversion. В части 3 мы разработаем структуры данных утилизирующих когерентность в объектном и отображаемом пространствах, а также между соседними кадрами. В части 4 мы опишем реализацию и покажем полученные результаты для некоторых сложных моделей содержащих сотни миллионов полигонов.

2. Предыдущие наработки

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

Основная масса наработок в области ray tracing расширяла возможности использования только объектной когерентности, и эти модифицированные алгоритмы показывали вполне приемлемые результаты [1, 2, 3, 4, 5]. Переходная когерентность очень редко использовалась на практике, но для ряда случаев все же есть несколько методик. Если все объекты являются выпуклыми и остаются неподвижными во время движения самой камеры, то существуют некоторые закономерности в процессе изменения видимости самих объектов. Алгоритм трассирования в состоянии отследить и использовать эти закономерности. С другой стороны, если камера является неподвижной, то тогда лучи, которые не попадают под влияние движущихся объектов, могут быть легко определены, и их можно взять из процесса обработки предыдущего кадра. Но мы по-прежнему не видим ни одного метода, способного извлечь выгоду из когерентности изображения, ввиду того, что каждый пиксель просчитывается независимо от состояния соседних. Существуют, однако, алгоритмы эвристического предсказания результатов ray tracing на конкретный пиксель по текущему состоянию соседних [10], однако мы и здесь не получаем гарантированного решения по использованию когерентности изображения при ray tracing.

При реализации алгоритмов Z-buffer (и алгоритмов scan conversion вообще) возникает совершенно противоположная проблема. Обычная растеризация с применением Z-буфера в подавляющем большинстве случаев связана с необходимостью предварительного просчета каждого полигона, и только после этого можно непосредственно перейти к самой растеризации посредством scan conversion, при которой последовательно обновляются все задействованные пиксели. Эта схема, сама по себе, прекрасно утилизирует когерентность изображения, поэтому необходимо задуматься только над объектной и переходной когерентностью.

Одним из доступных решений по использованию объектной когерентности в алгоритмах Z-буферизации является использование пространственного деления на подпространства с целью усечения (culling) модели до такого состояния, чтобы остались только полигоны, попадающие в поле видимости (viewing frustum), определяемое углом наблюдения камеры и ее положением. Этот подход дает значительное ускорение в вычислениях, но все же утилизирует только малую часть когерентных связей в объектном пространстве, в случае, когда модель имеет сложную геометрию по Z-координате. В моделях архитектуры, например, большая часть геометрии спрятана за стенами комнат, хотя и в пределах viewing frustum.

С целью более эффективного использования объектной когерентности в архитектурных моделях Airey [12, 13], а в дальнейшем Teller и Sequin [15] предложили предварительно разбить модели на отдельные ячейки и просчитать для них potentially visible set (PVS) — потенциально видимый набор полигонов из каждой из ячеек. При рендеризации изображения из любой точки зрения, находящейся внутри ячейки, рассматривались только полигоны, входящие в PVS.

* чуть позже данный метод получил дальнейшее развитие и реализовывался в виде предварительного просчета BSP (binary set of polygons) дерева для всей сцены.

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

3. Hierarchical Visibility (применение иерархических структур данных в алгоритме определения видимости)

Иерархический Z-буфер в своей реализации использует octree spatial subdivision — рекурсивное деление пространства на восемь подпространств — для активного использования объектной когерентности; Z-пирамиду для утилизации когерентности изображения и список ранее видимых (в предыдущем кадре) подпространств. В то время, как максимальный выигрыш в производительности мы можем достичь только в случае одновременного использования всех трех иерархических структур, object space octree и Z-pyramid могут применяться отдельно друг от друга. И независимо от того, применяем мы их вместе или раздельно, мы можем достичь эффекта традиционного Z-буфера, только уже со значительно меньшей вычислительной нагрузкой.

3.1 Деление пространства на восемь (object-space octree)

Древовидная структура, получающаяся в результате рекурсивного деления пространства на восемь подпространств, использовалась ранее для ускорения ray tracing и эффективной рендеризации объемных наборов данных [16]. С некоторыми, и очень важными модификациями, большинство методов из вышеперечисленных работ можно применить к Z-buffer scan conversion. В результате мы получим алгоритм, который позволяет достичь производительности в несколько десятков раз выше при его применении на моделях, имеющих сложную геометрию и простирающихся глубоко в «глубь экрана».

Для того, чтобы быть максимально понятыми, для начала введем несколько соглашений. Относительно Z-буфера, полигон будет считаться невидимым, если ни один пиксель полигона не будет лежать ближе значения Z, уже записанного в соответствующую позицию Z-буфера. Аналогично, куб в пространстве будет считаться невидимым, если три его грани, обращенные к наблюдателю, будут невидимыми полигонами. И наконец, все дочерние ветви дерева (octree), полученного при делении пространства, будут считаться невидимыми, если мы определим, что кубическое подпространство, ассоциируемое с данными ветвями, будет считаться невидимым. С учетом этих определений, мы можем сформулировать следующее условие, позволяющее нам комбинировать 2D Z-буфер с делением пространства на кубические субпространстве: если куб считается невидимым на основе значений в Z-буфере, то все полигоны, которые полностью находятся в данном кубическом субпространстве, тоже будут невидимыми. Что нам это дает? А то, что если мы методом scan conversion просчитаем грани определенного субпространства из состава octree и определим, что все пиксели этого куба находятся позади соответствующих значений в Z-буфере, то можем смело игнорировать всю геометрию находящуюся внутри данного куба.

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

*в общем случае, (octree) — дерево рекурсивного деления пространства на восемь подпространств — формируется следующим образом. Вся сцена помещается в минимально возможный, выровненный по осям координат, куб. Этот куб будет являться базовым (root) и соответствовать началу(корню) дерева. Дальнейшая процедура является рекурсивной по сути и начинается с проверки содержащихся в данном кубе примитивов, и если их количество меньше определенного порогового значения, то процедура ассоциирует данный примитив с этим кубом и заканчивает рекурсию. Если нет, то с кубом ассоциируется любой примитив, который пересекает хотя бы одну из двух плоскостей, виртуально делящих куб на восемь равных подпространств, и производится деление куба этими двумя плоскостями. В результате этого мы получим восемь новых дочерних кубиков с размером сторон 1/2 от размеров родительского куба. Эти восемь кубиков будут представлять первую ветвь дерева. Полученные кубы снова проверяются на соответствие содержащихся в них примитивов определенному пороговому количеству, и, если необходимо, каждый не удовлетворивший условию куб будет снова поделен на восемь меньших кубиков(подпространств), означающих собой появление новых, дочерних ветвей у родительской ветви и т.д. Этот процесс будет продолжаться до тех пор, пока каждый из кубов не будет содержать примитивов меньше, чем пороговое значение, или пока рекурсия не достигнет своего самого глубокого уровня.

Закончив с формированием дерева, мы рекурсивно выполняем следующую процедуру: начиная с базового (root) куба, мы проверяем, попадает ли данный куб в поле зрения (viewing frustum), если НЕТ — на этом и закончим, если же ДА, то методом scan conversion для граней определяем видимость данного куба. Если куб не видим — заканчиваем, если видим — то рендеризуем геометрию, ассоциированную с данным кубом, а затем переходим к его дочерним ветвям (меньшим по размерам кубам) и последовательно выполняем вышеприведенную процедуру, но уже для этих ветвей.

Базовый алгоритм имеет несколько характеристик, на которые надо обратить особое внимание. Первое: он рендеризует ту геометрию, которая содержится только в видимых кубах (видимых ветвях дерева). При этом часть просчитанных примитивов может быть полностью невидимой, но все они считаются «видимыми частично». Частично видимыми мы их будем называть исходя из следующих соображений: всегда найдется такая точка в пространстве, в которой данный полигон станет полностью видимым, и эта точка будет находиться не дальше, чем длина диагонали куба, содержащего данный полигон. Это значительное преимущество по отношению к обычному усечению геометрии под поле зрения камеры (culling to the viewing frustum). В дополнение к этому, наш алгоритм не тратит время на ненужные ветви дерева разбиений, так как он посещает только те ветви, родительские структуры которых — видимы. Что еще более важно, наш алгоритм никогда не посещает одни и те же ветви дважды. А этот недостаток присущ алгоритмам ray tracing, где корень дерева посещается каждый раз для каждого нового пикселя, а другие ветви могут повторно посещены десятки тысяч раз. Как результат, наш базовый алгоритм осуществляет culling гораздо более эффективно.

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

3.2. Z — пирамида отображаемого пространства


Дерево делений объектного пространства (object space octree) позволяет нам отсечь значительную долю невидимой геометрии со скоростью, присущей scan conversion для граней кубических подпространств, из состава octree. Так как кубические пространства могут занимать значительную площадь в пересчете на пиксели, то такой вариант применения scan conversion может оказаться очень «дорогим» удовольствием.

*здесь надо иметь в виду, что реально сами кубы на экран не растеризуются, а растеризуются только примитивы, содержащиеся в этих кубах. А результаты проведенного scan conversion для кубов используются только для выяснения, видим он или нет, т.е. растеризовать ассоциированную с ним геометрию или пропустить.

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

*По сути, Z-пирамида очень напоминает собой пирамиду текстур с mip- levels.

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

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

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

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

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

Если мы не можем определить, что полигон невидим хотя бы в одном из квадрантов, мы переходим на следующий, еще более точный уровень пирамиды для этого квадранта и пытаемся снова. В конце концов, мы сможем сказать, что полигон или полностью невидим, или мы дойдем до самого точного уровня пирамиды и найдем единичный видимый пиксель. Т.е. мы или отбросим полигон, или «нарисуем» один из пикселей этого полигона. Когда мы таким образом найдем все видимые пиксели, мы скажем, что произвели hierarchical scan conversion

Потенциальная проблема с окончательным алгоритмом определения заключается в том, что может быть очень «дорого» вычислять ближайшее значение Z полигона для конкретного квадранта.

* Возвращаясь к HyperZ, можно предположить, что ATI, вероятнее всего, вынуждена была постараться и реализовать это «дорогое вычисление» аппаратно.

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

3.3. Переходная когерентность

Зачастую, когда мы просчитываем проекцию сложной модели на двумерную плоскость с использованием object-space octree, только малая часть кубических подпространств из состава octree остается видимой. Если мы начинаем просчитывать следующий кадр анимации, то можно с большой вероятностью утверждать, что большинство кубов, видимых в предыдущем кадре, будет видимо и в следующем. Некоторые из видимых кубов станут невидимыми, а некоторые — наоборот, но когерентность между соседними кадрами в большинстве анимаций достаточно велика, и только небольшое количество кубов изменит свой статус при переходе между соседними кадрами (если, конечно, не произошла полная смена всей сцены). С помощью нашего иерархического алгоритма мы реализуем и эту зависимость. Создав первый кадр, мы создадим и сохраним перечень видимых кубов из него в виде списка (temporal coherence list). Перейдя к формированию следующего, перед тем, как с самого начала запустить наш иерархический алгоритм для нового кадра, мы проведем рендеризацию геометрии, содержащейся в подпространствах из нашего списка. Кубы, геометрию из которых мы уже просчитали, пометим как «rendered». На базе получившегося в результате этой операции Z-буфера создадим начальную Z-пирамиду. Теперь, запустив в работу наш алгоритм, при достаточной когерентности между кадрами мы затратим значительно меньше времени на работу алгоритма, т.к. большая часть геометрии уже будет рендеризована. Потребуется значительно меньше циклов рекурсий на выявление невидимых кубов из состава octree и полигонов геометрии. В заключение нам необходимо обновить список видимых кубов в соответствии с новым кадром. Как мы увидим в четвертой части статьи, использование переходной когерентности может значительно ускорить просчеты окончательного изображения.

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

4. Практическая реализация и результаты

Наша первая реализация иерархического алгоритма определения видимости создана на базе стандартного, портируемого С-кода. При этом scan conversion был реализован полностью программно. Наш код использовал object-space octree, Z-pyramid в отображаемом пространстве и список переходной когерентности (temporal coherence list). Даже для относительно простых моделей наш чисто «софтверный» алгоритм оказался быстрее традиционного алгоритма определения видимости на базе Z-буфера. Для сложных моделей увеличение скорости просчетов было более чем заметным.

Для тестирования алгоритма мы сконструировали модуль в виде офисной комнаты, состоящий из более, чем 15000 полигонов, а затем размножили данный модуль в 3D-пространстве. Каждый модуль имел в своем составе лестничный блок с большим проемом, так что мы могли видеть часть обстановки на соседних этажах. Ни одна из стен офисного модуля не простиралась непосредственно до потолка, поэтому из определенной точки мы могли видеть обстановку и мебель из соседних модулей на том же самом этаже.

Ожидалось, что для простых моделей с малым количеством полигонов на единицу глубины сцены наш иерархический алгоритм определения видимости (hierarchical visibility algorithm) будет несколько медленнее, чем традиционные, ввиду нагрузки при просчете видимости подпространств octree и поддержания Z-пирамиды. Для проверки данного предположения мы произвели финальную рендеризацию нашим методом единичного офисного модуля, описанного выше (15000 полигонов) из точки, позволяющей видеть максимум геометрии. Время на рендеризацию окончательного изображения 512х512 пикселей составило 1.52 секунды, в то время как традиционный scan conversion потребовал 1.30 секунды. Налицо 17%-ное отставание от традиционных способов. Далее мы рендеризовали три модуля, выстроенных друг за другом в глубину (45000 полигонов). Время обработки составило 3.05 секунды для обоих алгоритмов, показывая, что данный уровень геометрической сложности является пороговым (для текущей геометрической модели). Иерархический алгоритм затратил 5.17 секунды для рендеризации окончательного изображения набора из девяти модулей, в то время когда традиционный метод потратил на это уже 7.16 секунды.

Конечно, истинная область применения иерархических алгоритмов — это модели большой и исключительно большой сложности. Для демонстрации возможностей алгоритма мы сконструировали некоторое подобие здания, состоящее из 33 размноженных в пространстве, исходных офисных модулей. Общее количество полигонов в модели достигло 538 миллионов! В нашем случае 59.7 миллионов полигонов лежало в поле viewing frustum. Проверке на видимость подверглись 1746 сформированных подпространств (кубов) из состава octree, из них 27 процентов было отброшено сразу, грани 687 кубов были иерархически scan converted, в результате чего мы отбросили почти 73% полигонов, попадающих в поле захвата камеры (viewing frustum). После таких упрощений нам осталось только 83000 полигонов, из которых 41200 были обращены к камере (это около 0.000076 от исходной модели). В результате визуализация окончательного изображения описанной нами модели заняла всего лишь 6.45 секунды на рабочей станции SGI Crimson Elan. Визуализация этой же модели с использованием традиционного Z-буфера, но с применением его аппаратной версии на Crimson Elan, заняла приблизительно 1 час 15 минут. А при программной реализации нам наверняка потребовалось бы не менее суток.

Как видим, выигрыш представляемый новым алгоритмом колоссален.

4.2. Использование графических акселераторов

В дополнение к полностью «софтверной» версии нашего алгоритма мы попробовали немного видоизменить наши методы с целью возможности применить доступные на настоящий момент коммерческие графические акселераторы. Результатом наших исследований был вывод: на текущий момент использовать графические акселераторы для реализации части нашего алгоритма очень проблематично. И вот по каким, вроде бы совершенно незначительным причинам: эффективное использование когерентности объектного пространства возможно в том случае, если мы, используя scan conversion функции акселератора, очень быстро сможем определить, является ли конкретный пиксель видимым. К сожалению, протестированные нами акселераторы или вообще не смогли дать ответ на наш запрос, или возвращали результат в течение миллисекунд. А это слишком долго. Конечно, вполне естественно ожидать определенную задержку от графического конвейера, но «железо», спроектированное и готовое отвечать на такие «вопросы», должно давать ответ в течение микросекунд.

Мы попробовали реализовать деление пространства на подпространства (object space octree) на рабочей станции Kubota Pacific Titan 3000 с акселератором графики на базе Denali GB. Denali поддерживал нестандартный вызов из графической библиотеки, позволяющий определить, видимы или нет пиксели определенного набора полигонов, на основании информации из текущего Z- буфера. Мы использовали этот вызов (имевший название «Z query») для определения видимости octree cubes. Быстрота возвращения результата очень зависела от размера проекции куба на экран (если бы мы его действительно визуализировали на экран), и порой требовалось до нескольких миллисекунд. Наши дальнейшие тесты показали, что на выполнение подобных запросов тратилось до 36% времени. Это недопустимо много, чтобы считать применение акселератора эффективным.

И все же использование текущих акселераторов с типовым аппаратным Z-буфером оказалось возможным. Стандартный аппаратный Z-буфер был применен для реализации переходной когерентности в нашем алгоритме. При этом был использован своеобразный софтхард гибрид нашего алгоритма. Object space octree и иерархический scan conversion с Z -пирамидой реализовывались программно (in software), а геометрия из списка видимых подпространств (temporal coherence list) рендеризовалась аппаратно (in hardware). И вот как это выглядело. Первый кадр полностью визуализировался программно. Далее уже аппаратно производилась рендеризация геометрии из списка. Затем мы считывали из акселератора полученное двумерное изображение и сформированный Z-буфер, из которого формировали Z-пирамиду, и опять переключались на software. Так, при наличии определенной взаимосвязи между кадрами значительная часть нового кадра просчитывалась на акселераторе, и это давало чувствительный прирост в производительности. В среднем, время, потраченное на вычисления, сокращалось в 1.5 — 2 раза. Так, например, при реализации анимации, представляющей собой виртуальную прогулку по нашему зданию, каждый новый кадр просчитывался значительно быстрее самого первого. Так, на Crimson Elan использование temporal coherence (переходной когерентности между кадрами) позволило сократить время создания кадра до 3.96 секунды, по сравнению с 6.45 сек при отключенной возможности использования temporal coherence.

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

5. Заключение

Учитывая то, что все более и более сложная геометрия моделей и трехмерных сцен становится все чаще и чаще используемой в компьютерной графике, становится очевидным, что для получения максимальных результатов необходимо научиться использовать когерентность и сцены и изображения. Здесь мы представили первый в индустрии алгоритм, который одновременно утилизирует три вида когерентности: object space coherence, image-space coherence и temporal coherence. Алгоритм был реализован на практике и доказал свою эффективность на модели с более, чем полумиллиардом полигонов.

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

* с учетом изложенного в конце преамбулы к данной статье, будем очень надеяться, что новый Radeon 256 от ATI будет свободен от указанных недостатков :)

Благодарности

Особая благодарность Frank Crow и Advanced Technology Group компании Apple Computer за помощь в проведении исследований. Также мы благодарны Mike Toelle, Avi Bleiweiss, Helga Thorvaldsdottir и Mike Keller из Kubota Pacific Corporation за помощь в проведении тестирования наших алгоритмов на рабочей станции Titan.

Электронный учебник по компьютерной графике

Компьютерная графика


4.6. Алгоритм, использующий Z-буфер

Алгоритм, использующий Z-буфер

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

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

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

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

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

Алгоритм использующий z буфер

Удаление невидимых линий.ppt

Алгоритм использующий z буфер » src=»https://present5.com/presentation/3/43035132_145890731.pdf-img/43035132_145890731.pdf-1.jpg» alt=»> Алгоритм использующий z буфер » /> Алгоритм использующий z буфер

Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы» /> Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. Алгоритмы, работающие в oбъектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность. Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.

15.5. Алгоритм, использующий z-буфер

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

1. Вычисление глубины многоугольника z(x, у) в точке (х, у).

2. Если г(х, у) меньше, чем значение z-буфера в позиции (х, у), то

а) г(х, у) заносится в элемент (х, у) z-буфера и

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

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

Весь процесс представляет собой не более чем поиск среди мно­жества пар <zi(x, у), Vi(x, у)> для заданных х и у с целью найти минимальное гг. При успешном поиске минимальное из встретив­шихся значений z помещается в z-буфер для каждой позиции (х, у). Очередность появления объектов на экране определяется упорядо­ченностью, с которой обрабатываются многоугольники, т. е. они могут изображаться не обязательно в направлении от переднего плана к заднему или от заднего к переднему.

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

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

решается относительно этой переменной

kТеперь, если в точке (х, у) в уравнении (15.6) получается значение Zi, то в точке (х+Дх, у)

Отношение А/С является постоянным, а Дх=1, поэтому, если -задана глубина в точке (х, у), для вычисления глубины в точке (#-Н, у) требуется выполнить лишь одно вычитание.

15.6. Алгоритмы построчного сканирования

Эти алгоритмы разработаны Уайли, Ромни, Эвансом и Эрдалом [516], Букнайтом [52, 53] и Уоткинсом [487]. Они функционируют в пространстве изображения, причем образ в них генерируется по­строчно. Ниже описан общий подход, который с некоторыми ва­риациями используется в названных выше алгоритмах.

Этот подход является расширением алгоритма преобразования многоугольника в растровую форму, описанного в разд. 11.7. Раз­личие заключается в том, что в этом случае мы имеем дело не с одним многоугольником, а сразу со всеми многоугольниками, определяю­щими объект. На первом шаге создается таблица ребер (ТР), со­держащая все негоризонтальные ребра многоугольников. Элементы ТР отсортированы по группам на основе меньшей у-координаты каждого ребра, а внутри групп — в зависимости от величины тан­генса угла наклона. Эти элементы содержат:

1) х-координату крайней точки ребра с меньшей у-координатой;

2) «/-координату другой крайней точки ребра;

3) приращение Ал: координаты х, используемое для перехода от каждой сканирующей строки к следующей (Ах обратно тангенсу

угла наклона ребра);

4) идентификатор многоугольника, указывающий, какому много­угольнику принадлежит данное ребро.

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

1) коэффициенты уравнения плоскости;

2) информация о закраске или цвете многоугольника;

3) булева переменная (флаг), определяющая положение внутри/ вне многоугольника. (Она используется при обработке сканирующей строки; вначале этой переменной присваивается значение false.)


На рис. 15.9 показаны проекции двух треугольников на пло­скость ху; невидимые линии изображены пунктиром. В отсортиро­ванной ТР для этой фигуры содержатся элементы для АВ, AC, FD, FE, СВ и DE. В ТМ входят элементы для ABC и DEF.

На третьем шаге создается таблица активных ребер (ТАР), ко­торая применялась в разд. 11.7; эта таблица всегда упорядочена по возрастанию координаты х. К тому времени, когда алгоритм дойдет до сканирующей строки у—а, ТАР будет содержать АВ и АС в ука­занном порядке. Ребра рассматриваются в направлении слева на­право. Приступая к обработке АВ, инвертируем прежде всего флаг внутри/вне треугольника ABC. Тогда флаг примет значение true и, следовательно, мы окажемся «внутри» треугольника, который необходимо рассмотреть Теперь, поскольку мы находимся внутри только одного треугольника, последний должен быть видимым и, следовательно, на интервале от ребра А В до следующего ребра АС в ТАР будет вестись закраска, требуемая для треугольника ABC. При прохождении этого ребра флаг ABC меняет значение на false, и, следовательно, мы теперь не находимся «внутри» ни одного из треугольников. Поскольку АС является последним ребром в ТАР, обработка сканирующей строки завершается. В ТАР вносятся изме­нения из ТР, она снова упорядочивается по х и производится пере­ход к обработке следующей строки.

Когда встретится сканирующая строка t/=p\ в отсортированной ТАР будут находиться АВ, AC, FD и F£. Обработка продолжа­ется в основном так же, как прежде. Со сканирующей строкой пересекаются два треугольника, но мы в каждый момент будем находиться «внутри» только одного из них.

Больший интерес представляет сканирующая строка i/=V-При входе в ABC флаг треугольника становится равным true. На интервале от точки входа до следующего ребра DE ведется закраска, требуемая для ABC. В точке пересечения с DE флаг DEF также устанавливается в true, и, следовательно, мы будем находиться «внут­ри» сразу двух треугольников (полезно иметь отдельный список многоугольников, флаги внутри/вне которых принимают значение true, а также счетчик, показывающий сколько многоугольников находится в списке). Очевидно, что теперь нам надо решить, какой из треугольников расположен ближе к наблюдателю — ABC или DEF. Определение производится путем вычисления значений z из уравнений плоскости для обоих треугольников при у=у и при х, задаваемом пересечением строки у=7 с ребром DE. Эта величина х содержится в элементе для DE в ТАР. В нашем примере треуголь-ник DEF имеет меньшую координату z и поэтому мы его видим. Таким образом, правило закраски DEF действует на всем интервале : вплоть до пересечения с ребром ВС, где флаг ABC примет значение false, после чего интервал снова будет «внутри» только одного тре­угольника DEF. Поэтому правило закраски, установленное для DEF, продолжает действовать вплоть до пересечения с ребром FE. На рис. 15.10 показано соотношение между двумя треугольниками

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

Предположим, что за треугольниками ABC и DEF находится большой многоугольник GHIJ (рис. 15.11). Тогда, если при дви­жении вдоль строки z/=Y, мы пересечем ребро СВ, будем все еще находиться «внутри» многоугольников DEF и GHIJ и,следовательно, вычисления, связанные с определением глубины, будут произво­диться снова. Этих затрат процессорного времени можно избе­жать, если предположить, что многоугольники не могут проникать друг в друга (при моделировании реальных объектов такое допуще­ние вполне приемлемо). Из этого предположения вытекает, что соотношение глубин между DEF и GHIJ после выхода из ABC изме­ниться не может, и, мы, следовательно, будем продолжать оставаться «внутри» DEF. Поэтому при выходе из закрываемого многоуголь­ника глубину можно не вычислять, ее требуется определять только в том случае, если мы выходим из закрывающего многоугольника.

На рис. 15.12 показаны проникающие друг в друга треуголь­ники. Чтобы правильно использовать алгоритм, введем в рассмот­рение ложное ребро ML и тем самым разобьем треугольник KLM на KLLM и L‘ММ’. Кроме того, можно модифицировать алгоритм и при обработке сканирующей строки на ней определять точку проникновения.

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

рис. 15.9, где для обеих сканирующих строк у—^ и у=7+1 види­мыми являются интервалы от АВ до DE и от DE до FE.

На рис. 15.9 когерентность по глубине теряется при переходе от (/=Y+1 к У=7+2, поскольку в ТАР меняется взаимная упорядо­ченность ребер DE и СВ (эта ситуация в алгоритме должна быть предусмотрена). Поэтому видимыми станут другие интервалы, в нашем случае от АВ до СВ и от DE до FE. Хзмлин и Джир [210] показали, как иногда может сохраняться когерентность по глубине, даже если меняется порядок хождения ребер в ТАР.

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

Алгоритм, использующий z-буфер

Читайте также:

  1. Метод z-буфера
  2. Простой протокол, использующий KDC

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

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

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

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

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

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

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

Во втором методе оба буфера, заданные в пространстве изображения, имеют повышенную разрешающую способность. При визуализации изображения как пикселная информация, так и глубина усредняются. В этом методе требуются очень большие объемы памяти. Например, изображение размером 512 * 512 * 24 бита, использующее z-буфер размером 20 бит на пиксел, разрешение которого повышено в 2 раза по осям x и y и на котором устранена ступенчатость методом равномерного усреднения, требует почти 6 мегабайт памяти.

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

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

Если известно уравнение плоскости, несущей каждый многоугольник, то вычисление глубины каждого пиксела на сканирующей строке можно проделать пошаговым способом. Напомним, что уравнение плоскости имеет вид:
ax + by + cz + d = 0
z = -(ax + by + d)/c <> 0.

Для сканирующей строки y = const. Поэтому глубина пиксела на этой строке, у которого x1 = x + Dх, равна
z1 — z = -(ax1 + d)/c + (ax + d)/с = a(x — x1)/c или
z1 = z — (a/c)Dx.
Но Dx = 1, поэтому z1 = z — (a/c).

Дальнейшей иллюстрацией алгоритма послужит следующий пример.

Пример. Алгоритм, использующий z-буфер. Рассмотрим многоугольник, координаты угловых точек которого равны P1(10, 5, 10), P2(10, 25, 10), P3(25, 25, 10), P4(25, 5, 10) и треугольник с вершинами P5(15, 15, 15), P6(25, 25, 5), P7(30, 10, 5). Треугольник протыкает прямоугольник, как показано на рис. 21.1. Эти многоугольники нужно изобразить на экране с разрешением 32 * 32, используя простой буфер кадра с двумя битовыми плоскостями. В этом буфере фон обозначен через 0, прямоугольник — через 1, а треугольник — через 2. Под z-буфер отводится 4 битовых плоскости размером 32 * 32 бит. Таким образом, содержимое z-буфера окажется в диапазоне от 0 до 16. Точка наблюдения расположена в бесконечности на положительной полуоси z, как показано на рис. 21.1b.

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Напомним, что в левом нижнем углу находится пиксел (0, 0).

Используя метод Ньюэла, получаем уравнение плоскости треугольника 3x + y + 4z — 120 = 0.

Значит, глубина треугольника в любой его точке задается уравнением z = -(3x + у — 120)/4.

Для последовательных пикселов, лежащих на сканирующей строке z1 = z — 3/4.


Вычисление пересечений сторон треугольника со сканирующими строками развертки с учетом соглашения о половине интервала между соседними сканирующими строками дает следующие пары координат (25.2, 24.5), (25.5, 23.5), (25.8, 22.5), (26.2, 21.5), (26.5, 20.5), (26.8, 19.5), (27.2, 18.5), (27,5, 17.5), (27.8, 16.5), (28.2, 15.5), (28.5, 14.5), (28.8, 13.5), (29.2, 12.5), (29.5, 11.5), (29.8, 10.5) для строк от 24 до 10. Напомним, что активируется тот пиксел, у которого центр лежит внутри или на границе треугольника, то есть при x1 Zбуфер(x, y) and z(x, y)

| следующая лекция ==>
Метод z-буфера | Алгоритмы, использующие список приоритетов

Дата добавления: 2014-01-03 ; Просмотров: 273 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

Алгоритм Варнока

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

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

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

Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма каждое окно разбивалось на четыре одинаковых подокна. Многоугольник, входящий в изображаемую сцену, по отношению к окну будем называть (рис. 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- буфер в произвольном порядке, их не нужно предварительно сортировать по приоритету глубины. Поэтому экономится вычислительное время, затрачиваемое на сортировку по глубине.

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

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

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

В целом алгоритм выглядит так:

  1. Заполнить буфер кадра фоновым значением цвета.
  2. Заполнить Z -буфер минимальным значением z (глубины) .
  3. Преобразовать изображаемые объекты в растровую форму в произвольном порядке.
  4. Для каждого объекта:

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

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

4.3. Если Z- \text<буфер>(x,y)» style=»display: inline; «>, то занести атрибуты пикселя в буфер кадра и заменить . В противном случае никаких действий не производить.

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

Илон Маск рекомендует:  Mfc под колпаком или создание mfc приложения без app wizard
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL