Иерархические структуры можно строить и на основе разбиения пространства (картинной плоскости): каждая клетка исходного разбиения разбивается на части (которые, в свою очередь, также могут быть разбиты, и т. д. При этом каждая клетка разбиения соответствует узлу дерева).
Удаление невидимых поверхностей
Иерархии (как и разбиение пространства) позволяют достаточно легко и просто производить частичное упорядочение граней. В результате получается список граней, практически полностью упорядоченный, что дает возможность применить специальные методы сортировки.
Помимо упорядочения граней, иерархические структуры позволяют производить быстрое и эффективное отсечение граней, не удовлетворяющих каким-либо поставленным условиям.
Рассмотрим основные методы удаления невидимых поверхностей.
Метод трассировки лучей Наиболее естественным методом для определения видимости граней является метод трассировки лучей (вариант, используемый только для определения видимости, без отслеживания отраженных и преломленных лучей обычно называется ray casting). В данном методе для каждого пиксела картинной плоскости определяется ближайшая к нему грань, для чего через этот пиксел выпускается луч, находятся все точки его пересечения с гранями и среди них выбирается ближайшая.
Данный алгоритм можно представить следующим образом:
for all pixels
for all objects compare zОдним из преимуществ этого метода является простота, универсальность (он может легко работать не только с полигональными моделями; возможно использование Constructive Solid Geometry - CSG) и возможность совмещения определения видимости с расчетом цвета пиксела.
Еще одним несомненным плюсом метода является большое количество методов оптимизации, позволяющих работать с сотнями тысяч граней и обеспечивающих временные затраты порядка О (Clog и), где С - общее количество пикселов на экране, а п - общее количество объектов в сцене. Более того, существуют методы, обеспечивающие практическую независимость временных затрат от количества объектов.
Метод z-буфера