Введение
Структура данных дерева, в которой каждый внутренний узел имеет ровно восемь дочерних элементов, для разбиения трехмерного пространства.
Октри — это структура данных дерева, в которой каждый внутренний узел имеет ровно восемь дочерних элементов. Октри чаще всего используются для разбиения трехмерного пространства путем рекурсивного деления его на восемь октантов. Октри является трехмерным аналогом квадродеревьев. Слово образовано от "oct" (греческий корень, означающий "восемь") и "tree" (дерево). Октри часто используются в 3D-графике и 3D-игровых движках.
Для пространственного представления
Каждый узел в октре подразделяет пространство, которое он представляет, на восемь октантов. В октре на основе точек (PR-октре) узел хранит явную трехмерную точку, являющуюся "центром" подразделения для этого узла; эта точка определяет один из углов для каждого из восьми дочерних узлов. В октре на основе матриц (MX-октре) точка подразделения неявно является центром пространства, которое представляет узел. Корневой узел PR-октри может представлять бесконечное пространство, а корневой узел MX-октри должен представлять конечное ограниченное пространство, чтобы неявные центры были однозначно определены. Важно отметить, что октри отличаются от k-d деревьев: k-d деревья разделяют пространство вдоль измерения, а октри – вокруг точки. Кроме того, k-d деревья всегда двоичные, в отличие от октрей. Используя поиск в глубину, необходимо последовательно обходить узлы и отображать только необходимые поверхности.
Применение к квантованию цвета
Алгоритм цветовой квантизации с использованием октального дерева, изобретенный Гервауцем и Пургатхофером в 1988 году, кодирует данные о цвете изображения в виде октального дерева глубиной до девяти уровней. Октальные деревья используются, поскольку в системе RGB три цветовые составляющие. Индекс узла, от которого начинается ветвление на верхнем уровне, определяется формулой, использующей наиболее значащие биты красной, зеленой и синей цветовых составляющих, например, 4r + 2g + b. Следующий, более низкий уровень использует биты следующей значимости, и так далее. Менее значащие биты иногда игнорируются для уменьшения размера дерева. Алгоритм отличается высокой эффективностью использования памяти, поскольку размер дерева можно ограничить. Нижний уровень октального дерева состоит из листовых узлов, в которых накапливаются цветовые данные, не представленные в дереве; изначально эти узлы содержат отдельные биты. Если в октальное дерево введено значительно больше цветов, чем требуется для палитры, его размер можно последовательно уменьшать, находя узел нижнего уровня и усредняя его битовые данные в листовой узел, тем самым обрезая часть дерева. После завершения выборки, проход по всем ветвям дерева до листовых узлов с учетом битов на этом пути позволит получить приблизительно необходимое количество цветов.