Представление трехмерного объекта в форме октодерева является расширением подобной двухмерной схемы представления, называемыми кодированием в форме квадродерева (quadtree). Квадродеревья генерируются последовательным делением двухмерной области (обычно квадрата) на квадранты. Каждый узел квадродерева имеет четыре элемента данных - по одному на каждый квадрант области (рис. 8.63). Если все точки квадранта имеют одинаковый цвет (однородный квадрант), этот цвет ука-
Рис. 8.64. Квадратная область плоскости ху с двумя уровнями деления на квадранты и соответствующее представление в форме квадродерева
Рис. 8.65. Представление в форме октодерева квадратной области плоскости ху, содержащей одну цветную область на фоне другого цвета зывается в соответствующем элементе данных узла. Кроме того, в элементе данных устанавливается метка, определяющая, что квадрант однородный. Если, например, все точки в квадранте 2 на рис. 8.63 красного цвета, код красного цвета помещается в элемент данных 2 этого узла. В противном случае квадрант неоднородный, и он делится на подквадранты, как показано на рис. 8.64. Элемент данных в узле, соответствующем квадранту 2, теперь помечает квадрант как неоднородный и хранит указатель на следующий узел квадродерева.
В алгоритме генерации квадродерева проверяются коды цвета, присвоенные объектам выбранной двухмерной области, и соответствующим образом устанавливаются узлы квадродерева. Если все квадранты исходного пространства имеют один цвет, квадродерево содержит только один узел. Для неоднородной области плоскости последовательное деление квадрантов продолжается до тех пор, пока однородными не станут все участки разделенной области. На рис. 8.65 показано представление в форме квадродерева области, содержащей один участок сплошного цвета, отличающегося от равномерного цвета, заданного для других участков области.
Кодирование в форме октодерева позволяет существенно сэкономить требуемую память, если в области пространства имеются большие одноцветные области, поскольку один узел может представлять большую часть пространства. Кроме того, данную схему представления можно использовать для хранения кодов цвета пикселей. Для области, содержащей 2тг на 2п пикселей, представление в форме квадроде
Рис. 8.66. Куб, разделенный на нумерованные октанты, и соответствующий узел октодерева с восемью элементами данных рева содержит не более п уровней. Кроме того, каждый узел квадродерева имеет не больше четырех непосредственных потомков.
Схема кодирования в форме октодерева делит область трехмерного пространства (обычно куб) на октанты и записывает восемь элементов данных в каждом узле дерева, как показано на рис. 8.66. Отдельные подобласти после конечного этапа разбиения трехмерного пространства называются элементами объема или вокселями (voxels) по аналогии с пикселями прямоугольной области на экране дисплея. Воксель в представлении в форме октодерева хранит значения свойств для однородной подобласти пространства. Свойства объектов в трехмерной области пространства могут включать цвет, тип материала, плотность и другие физические характеристики. Например, в выбранной области пространства могут быть такие объекты, как скалы и деревья или ткани, кости и органы тела. Пустые области пространства представлены типом воксе-лей “void” (“пусто”). Как и для представления в форме квадродерева, неоднородный октант в области делится до тех пор, пока фрагменты не станут однородными. Для октодерева каждый узел может иметь от нуля до восьми непосредственных потомков.