Алгоритм Z-буфера

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

void PPZB(x,y,z){ if (z<ZBuffer[y][x]) { ZBuffer[y][x]=z; PP(x,y); } }

Как правило, расчет глубины осуществляется при растеризации очередной грани, т.о. этот алгоритм удаления невидимых поверхностей, практически не требует дополнительных вычислений и выполняется за время O(N). Из-за своей простоты, он хорошо подходит для реализации на графических акселераторах. Тем не менее, алгоритм требует растеризовать все грани в сцене, тогда, как большинство из них могут быть полностью невидимыми, поэтому, как правило, в дополнение к нему используют какие-то дополнительные алгоритмы отброса заведомо невидимых объектов и граней. Кроме того, здесь тоже можно использовать когерентность. Например, если построить вокруг группы граней AABB и проверить по Z-буферу, виден ли он (проверить, все соответствующие ему пикселы, не занося значения в Z-буфер). Если он невиден, то и грани внутри него не видны.

Опять же лучше построить иерархию описывающих тел. Например, описать вокруг всех граней в сцене AABB, затем рекурсивно разбивать его на 8 частей, до тех пор, пока в количество полигонов в текущем AABB не станет достаточно малым, чтобы дальнейшее деление не имело смысла. Получится дерево, узлы – AABB, листья – AABB со списком полигонов в них. Далее, берется начальный AABB дерева (корневой), проверяется на попадание в пирамиду зрения, затем проверяется по Z-буферу, если оказывается, что он виден – тоже самое проделывается для каждого из восьми дочерних AABB. В конце концов, выводятся полигоны в листьях дерева. Важным является порядок обхода дочерних AABB, сначала выводятся ближайшие к наблюдателю, а затем более дальние. Порядок определяется положением наблюдателя относительно плоскостей, разделяющих родительский AABB на дочерние (как в BSP). Выгода от рисования от ближних к дальним в том, что отрисованные ближние грани будут закрывать дальние.

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

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

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

Для алгоритма Z-буфера можно использовать совершенно различные параметры, характеризующие глубину. Обычно используются либо координата Z (проекция точки на ось вглубь экрана OZ), либо обратная ей величина 1/Z. Обратную величину можно линейно интерполировать вдоль экрана при перспективном проектировании. Более подробно об этом будет рассказано в лекции, посвященной закрашиванию и наложению текстур. Чтобы сохранить увеличение значения в Z-буфере с увеличением расстояния до объекта, используют величину 1-k/Z.

Из-за того, что размер и точность чисел ограничен, необходимо наложить некоторые условия на глубину. Обычно, глубина хранится в виде целого числа, принимающего значения [0..ZBmax]. Тогда, если глубна характеризуется Z- координатой, значение для Z-буфера рассчитывается по формуле V(Z)=Z/Zmax* ZBmax. Цена младшего разряда (дискретность) d для числа V будет Zmax/ZBmax (500/65536~0.01). Для обратной величины V(Z)=(1-k/Z)* ZBmax. Здесь k вычисляется исходя из Zmin. ZV=0 => k=Zmin. Цена младшего разряда не постоянна V(Z+d)-V(Z)=1 => d=Z*Z/(k*ZBmax-Z) = Z*Z/(Zmin*ZBmax-Z). С увеличением Z цена возрастает, и максимальная цена будет в Zmax (500*500/(0.1*65535-500)=41), а минимальная в Zmin (d=Zmin/(ZBmax-1))=0.1/65536=1e-6), это значит, что последние объекты в последних 40 метрах будут иметь одинаковое значение глубины. Чтобы избежать этого выбирают меньшие Zmax и большие Zmin(100,1=>0.15). Либо увеличение разрядной сетки (до 24-х или 32-х разрядов (500,0.1,24 => 500*500/0.1*16000000=0.15)).

В общем случае алгоритм Z-буфера не позволяет работать с полупрозрачными объектами. Обычно их выводят после вывода непрозрачных, в порядке от дальних к ближним, проверяя Z-буфер. Но можно несколько модифицировать и сам алгоритм, для этого в каждом пикселе добавляется упорядоченный по глубине список прозрачных пикселей. Если в обычном Z-буфере каждому пикселу соответствует пара (С,Z), где C-цвет, Z-глубина, то в модифицированном - (С,Z,t,next), где t-степень прозрачности, next – указатель на следующий элемент в списке. Сначала строится Z-буфер, а затем рисуются все пиксели со списками от дальнего элемента к ближнему.

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

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