В 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 – дерева, которое формируется следующим образом.
- Вся пространственная сцена помещается в минимально возможный, выровненный по осям координат, куб. Этот куб будет соответствовать корню дерева.
- Полученный куб делиться тремя плоскостями, параллельными координатным плоскостям, на восемь равных частей.
- Каждый из получившихся восьми кубов рекурсивно делиться еще на восемь кубов и т.д.
- В каждой ветке деление прекращается, либо когда достигается заранее определенная глубина дерева, либо когда в очередном кубе количество примитивов становится меньше заранее определенного порога.
- Примитивы сцены ассоциируются с кубами, соответствующими листьям получившегося дерева.
- При обработке примитивов, которые разбиваются секущими плоскостями, возможны варианты:
- ассоциировать разбиваемый примитив с родительским кубом;
- разбивать примитив и каждую его часть ассоциировать с соответствующим листом;
- не разбивая примитив, ассоциировать его со всеми листьями, в которые он попадает.
Недостатком второго подхода является увеличение количества примитивов в сцене, а также достаточно большая вычислительная сложность процедуры разбиения примитивов. На практике обычно используют последний подход.
Следует обратить внимание на следующие очевидные утверждения:
- Полигон будет считаться невидимым относительно Z-буфера, если ни один пиксель полигона не будет лежать ближе значения Z, уже записанного в соответствующие ячейки Z-буфера.
- Куб в пространстве будет считаться невидимым, если три его грани, обращенные к наблюдателю, будут невидимыми полигонами.
- И наконец, все дочерние ветви дерева, полученного при делении исходного пространства на подпространства, будут считаться невидимыми, если мы определим, что кубическое подпространство, ассоциируемое с данными ветвями, будет считаться невидимым.
Учитывая три вышеперечисленных условия, мы можем утверждать следующее: если куб считается невидимым на основе значений в Z-буфере, то все полигоны, которые полностью находятся в