Рис. 8.27. Перемещение наблюдателя относительно объектов сцены
8.9.3. 4-арное и 8-арное деревья Поскольку в качестве плоскостей разбиения в ходе формирования бинарных деревьев разделения пространства используются плоскости многоугольников, эти плоскости могут иметь произвольную ориентацию. Но расчет положения точки относительно произвольной плоскости занимает довольно много времени, учитывая то огромное количество точек, которые нужно обработать при построении дерева. Справиться с этой проблемой позволяет использование 8-арных (octree) и 4-арных (quadtree) деревьев, поскольку при их построении используются разделяющие плоскости, параллельные координатным. Рассмотрим эти типы деревьев применительно к двухмерному пространству (рис. 8.28).
Предположим, что изображение состоит из пикселей только двух цветов - черных и белых, - которые сформированы каким-то алгоритмом отображения трехмерной сцены. Чтобы сохранить сцену, это изображение нужно поместить в двоичный массив. Но можно поступить и по-другому, учитывая согласованность в расположении групп пикселей. Можно провести две прямые, как на рис. 8.29, и разделить всю область на четыре квадранта. Обратите внима-
Иерархические графические модели
ниє - один квадрант заполнен только белыми пикселями, а в остальных есть пиксели и того и другого цвета. Поскольку один квадрант полностью состоит из пикселей белого цвета, то этот цвет можно назначить всему квадранту. Три остальных квадранта придется опять разделить и продолжать операцию рекурсивно с каждым из них таким же образом, пока в результате последовательных разбиений не окажется, что какая-либо из областей полностью заполнена пикселями одного цвета. Вся информация сохраняется в дереве, которое получило название 4-арного (quadtree). Уровни такого дерева соответствуют последовательным разбиениям, а каждый узел имеет четырех потомков (рис. 8.30).
Рис 8.30. 4-арное дерево Поскольку при формировании 4-арного дерева мы разбиваем пространство линиями, параллельными осям координат, то эта процедура выполняется быстрее по сравнению с аналогичным разбиением в процессе формирования бинарного дерева. Не менее существенно и то, что 4-арное дерево требует для хранения описания изображения меньшего объема памяти.