Алгоритм иерархического Z-буфера

Алгоритм иерархического Z-буфера

В 1993 году в качестве расширения традиционного алгоритма Z-буфера был предложен алгоритм иерархического Z-буфера (Hierarchical Z-Buffer - HZB) (Ned Greene, M. Kass, and Gary Miller. Hierarchical z-buffer visibility. Proceedings of SIGGRAPH 93, pages 231-240, 1993.). Однако его практическое использование для решения задач удаления невидимых поверхностей на компьютерах класса PC задержалось на добрый десяток лет в связи с достаточно большими требованиями к памяти и быстродействию компьютера для применения этого алгоритма на практике.

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

1. Вся пространственная сцена помещается в минимально возможный, выровненный по осям координат, куб. Этот куб будет соответствовать корню дерева.

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

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

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

5. Примитивы сцены ассоциируются с кубами, соответствующими листьям получившегося дерева.

6. При обработке примитивов, которые разбиваются секущими плоскостями, возможны варианты:

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

· разбивать примитив и каждую его часть ассоциировать с соответствующим листом;

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

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

Следует обратить внимание на следующие очевидные утверждения:

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

2. Куб в пространстве будет считаться невидимым, если три его грани, обращенные к наблюдателю, будут невидимыми полигонами.

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

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

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

1. Попадает ли он (а точнее, ассоциированный с ним кубик субпространства) в пирамиду видимости[1], если да, то

2. Видны ли грани куба, соответствующего этому узлу, и если видны, то

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

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

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

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

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

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

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

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

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

Определение видимости грани куба осуществляется следующим образом:

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

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

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

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

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

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

A (0, 0, 0), B (1, 1, -2), C (2, 0, 0), D (0, 2, -2), E (0,6, 0), F (2, 6, 0), G (1, 7, -2), H (0, 8, -2), I (0, 6, -6), L (2, 6, -6), K (1, 7, -8), J (0, 8, -8), M (6, 0, -4), N (8, 0, -4), O (7, 1, -6), P (6, 2, -8).

Будем обозначать куб пространства четверкой параметров (x, y, z, s), где (x, y, z) – координаты левой – нижней - передней вершины куба; s - длина его ребра. Под геометрическими примитивами будем понимать треугольные грани пирамид пространственной сцены. В данном случае деление ветвей дерева будем прекращать, когда в очередном кубе количество примитивов становится меньше или равно четырем.

На первом шаге алгоритма (рис. 2) вся сцена помещена в куб с параметрами (0, 0, 0, 8). Этот куб будет ассоциирован с корнем строящегося дерева. Затем (рис. 3) этот куб разбивается на восемь кубов с параметрами: (0, 0, 0, 4), (4, 0, 0, 4), (0, 4, 0, 4), (4, 4, 0, 4), (0, 0, -4, 4), (4, 0, -4, 4), (0, 4, -4, 4), (4, 4, -4, 4). И так далее… Сформированное дерево (octree) с указанием в вершинах дерева параметров связанного с ней куба субпространства и множества примитивов, лежащих внутри куба, ассоциированного с листом дерева, приведено на рис. 4. (здесь желтые вершины – листья дерева, с которыми ассоциированы примитивы пространственной сцены, голубые вершины - листья дерева, с которыми не ассоциирован ни один примитив (пустые субпространства); зеленым – транзитные вершины).

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

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

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

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

Теперь выполним рендеринг пространственной сцены с использованием построенного дерева. Будем считать, что вся пространственная сцена попадает в пирамиду видимости. Изначально Z-пирамида имеет следующий вид (рис. 6 а)) – заполнена минимальным значением координаты z пространственной сцены.

Рис. 6.

Начинаем с корня дерева (вершина (0, 0, 0, 8)). Проверяем по Z-пирамиде, видны ли грани куба (0, 0, 0, 8). Для этого анализируем самый верхний уровень Z-пирамиды, значение его равно -8, самая близкая к наблюдателю точка грани куба (0, 0, 0, 8) имеет z - координату, равную нулю. Следовательно, последовательно опускаясь по уровням Z-пирамиды, приходим к выводу, что грани куба (0, 0, 0, 8) видны. В дереве переходим к обработке вершины (0, 0, 0, 4). С помощью Z-пирамиды определяем, что грани куба (0, 0, 0, 4) видны. Поскольку обрабатываемая вершина – лист дерева, поочередно раскладываем в растр каждый из примитивов, ассоциированных с этим листом. Например, при обработке треугольника ACD находится уровень Z-пирамиды, на котором этот примитив отвечает одному пикселю (этот пиксель на рис 6 б) отмечен красной заливкой). В данном случае ближайшее значение Z примитива - треугольника ACD (z-координата точки A) находится ближе, чем значение Z в указанном пикселе, поэтому примитив отрисовывается с помощью обычного алгоритма Z-буфера и производится обновление всех уровней Z-пирамиды. Далее последовательно обрабатываем все вершины дерева, и в итоге имеем получаем Z-буфер и соответствующий ему буфер кадра, который и выводим на экран.

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

[1] По существу, попадание в пирамиду видимости означает пересечение кубом хотя бы одной из плоскостей камеры. Более подробно этот метод рассмотрен, например, на ресурсе http://www.gametutorials.com/ (пример "frustum culling tutorial").

Дата добавления: 2015-08-29