Иерархический 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-пирамиде. Если значение из пирамиды находится ближе, мы знаем, что полигон невидим в данном квадранте.

* не кажется ли вам это знакомым? 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

• [1] 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.
• [2] A. Glassner. Space subdivision for fast ray tracing. IEEE CG&A, 4(10):15-22, Oct. 1984.
• [3] D. Jevans and B. Wyvill. Adaptive voxel subdivision for ray tracing. Proc. Graphics Interface '89 , 164-172, June 1989.
• [4] T. Kay and J. Kajiya. Ray tracing complex surfaces. Com-puter Graphics, 20(4):269-278, Aug. 1986.
• [5] 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.
• [6] 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.
• [7] D. Jevans. Object space temporal coherence for ray trac-ing. Proc. Graphics Interface '92 , Vancouver, B.C., 176- 183, May 11-15, 1992.
• [8] A. Glassner. Spacetime ray tracing for animation. IEEE CG&A, 8(3):60-70, March 1988.
• [9] J. Chapman, T. W. Calvert, and J. Dill. Spatio-temporal coherence in ray tracing. Proceedings of Graphics Interface '90 , 196-204, 1990.
• [10] S. Badt, Jr. Two algorithms for taking advantage of temporal coherence in ray tracing The Visual Computer, 4:123-132, 1988.
• [11] 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.
• [12] 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.
• [13] 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.
• [14] S. Teller and C. Sequin. Visibility preprocessing for interac-tive walkthroughs. Computer Graphics, 25(4):61-69, 1991.
• [15] S. Teller and C. Sequin. Visibility computations in polyhedral three-dimensional environments. U.C. Berkeley Report No. UCB/CSD 92/680, April 1992.
• [16] D. Meagher. Efficient synthetic image generation of arbitrary 3-D objects. Proc. IEEE Conf. on Pattern Recognition and Image Processing, 473-478, June 1982.