Буфер глубины (depth buffer). Удаление невидимых поверхностей и линий. Использование z-буфера в DirectX

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

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

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

"… Из переписки с 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. Введение

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

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

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

Доминирующими технологиями для просчета видимости являются 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 расширяла возможности использования только объектной когерентности, и эти модифицированные алгоритмы показывали вполне приемлемые результаты . Переходная когерентность очень редко использовалась на практике, но для ряда случаев все же есть несколько методик. Если все объекты являются выпуклыми и остаются неподвижными во время движения самой камеры, то существуют некоторые закономерности в процессе изменения видимости самих объектов. Алгоритм трассирования в состоянии отследить и использовать эти закономерности. С другой стороны, если камера является неподвижной, то тогда лучи, которые не попадают под влияние движущихся объектов, могут быть легко определены, и их можно взять из процесса обработки предыдущего кадра. Но мы по-прежнему не видим ни одного метода, способного извлечь выгоду из когерентности изображения, ввиду того, что каждый пиксель просчитывается независимо от состояния соседних. Существуют, однако, алгоритмы эвристического предсказания результатов ray tracing на конкретный пиксель по текущему состоянию соседних , однако мы и здесь не получаем гарантированного решения по использованию когерентности изображения при ray tracing.

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

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

С целью более эффективного использования объектной когерентности в архитектурных моделях Airey , а в дальнейшем Teller и Sequin предложили предварительно разбить модели на отдельные ячейки и просчитать для них 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 и эффективной рендеризации объемных наборов данных . С некоторыми, и очень важными модификациями, большинство методов из вышеперечисленных работ можно применить к 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-пирамиде. Если значение из пирамиды находится ближе, мы знаем, что полигон невидим в данном квадранте.

* не кажется ли вам это знакомым? HyperZ ?… :)

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

References

S. M. Rubin and T. Whitted. A 3-dimensional representation for fast rendering of complex scenes. Computer Graphics, 14(3):110-1 16, July 1980.
A. Glassner. Space subdivision for fast ray tracing. IEEE CG&A, 4(10):15-22, Oct. 1984.
D. Jevans and B. Wyvill. Adaptive voxel subdivision for ray tracing. Proc. Graphics Interface "89 , 164-172, June 1989.
T. Kay and J. Kajiya. Ray tracing complex surfaces. Com-puter Graphics, 20(4):269-278, Aug. 1986.
M. Kaplan. The use of spatial coherence in ray tracing. In Techniques for Computer Graphics, etc., D. Rogers and R. A. Earnshaw, Springer-Verlag, New York, 1987.
H. Hubschman and S. W. Zucker. Frame to frame coherence and the hidden surface computation: constraints for a convex world. ACM TOG, 1(2):129-162, April 1982.
D. Jevans. Object space temporal coherence for ray trac-ing. Proc. Graphics Interface "92 , Vancouver, B.C., 176- 183, May 11-15, 1992.
A. Glassner. Spacetime ray tracing for animation. IEEE CG&A, 8(3):60-70, March 1988.
J. Chapman, T. W. Calvert, and J. Dill. Spatio-temporal coherence in ray tracing. Proceedings of Graphics Interface "90 , 196-204, 1990.
S. Badt, Jr. Two algorithms for taking advantage of temporal coherence in ray tracing The Visual Computer, 4:123-132, 1988.
B. Garlick, D. Baum, and J. Winget. Interactive viewing of large geometric databases using multiprocessor graphics workstations. SIGGRAPH "90 Course Notes: Parallel Algo-rithms and Architectures for 3D Image Generation, 1990.
J. Airey. Increasing update rates in the building walkthrough system with automatic model-space subdivision. Techni-cal Report TR90-027, The University of North Carolina at Chapel Hill, Department of Computer Science, 1990.
J. Airey, J. Rohlf, and F. Brooks. Towards image realism with interactive update rates in complex virtual building environ-ments. ACM SIGGRAPH Special Issue on 1990 Symposium on Interactive 3D Graphics, 24(2):41-50, 1990.
S. Teller and C. Sequin. Visibility preprocessing for interac-tive walkthroughs. Computer Graphics, 25(4):61-69, 1991.
S. Teller and C. Sequin. Visibility computations in polyhedral three-dimensional environments. U.C. Berkeley Report No. UCB/CSD 92/680, April 1992.
D. Meagher. Efficient synthetic image generation of arbitrary 3-D objects. Proc. IEEE Conf. on Pattern Recognition and Image Processing, 473-478, June 1982.

Ned Green , Apple Computer, U.C. Santa Cruz
Michael Kass and Gavin Miller , Apple Computer

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

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

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

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

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

1-й случай

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

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

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

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

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

2-й случай

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

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

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

3-й случай

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

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

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

рис.3

рис. 4

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

рис. 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 6.3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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