Октри

Октри
Тип	Дерево
Изобретенный	1980
Изобретён	Дональд Мигер
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск О(логН+К) О(логН+К) Вставлять О (логН) О (логН) Удалить О (логН) О (логН) Пик О (логН) О (логН) Пространственная сложность Космос НА) НА)

Слева: Рекурсивное деление куба на октанты . Справа: соответствующее октодерево.

Октри — это древовидная структура данных , в которой каждый внутренний узел имеет ровно восемь дочерних элементов . Октрины чаще всего используются для разделения трехмерного пространства путем рекурсивного разделения его на восемь октантов. Октри-деревья — это трёхмерный аналог квадродеревьев . Слово происходит от октябрь (греческий корень, означающий «восемь») + дерево . Октри часто используются в 3D-графике и движках 3D-игр .

Для пространственного представления

Каждый узел в октанте делит пространство, которое он представляет, на восемь октантов . В октадереве точечной области (PR) узел хранит явную трехмерную точку , которая является «центром» подразделения для этого узла; точка определяет один из углов для каждого из восьми детей. В октодереве на основе матрицы (MX) точка подразделения неявно является центром пространства, которое представляет узел. Корневой узел октодерева PR может представлять бесконечное пространство; корневой узел окт-дерева MX должен представлять конечное ограниченное пространство, чтобы неявные центры были четко определены. Обратите внимание, что октодеревья — это не то же самое, что k -d деревья : k -d деревья разбиваются по измерению, а октодеревья разбиваются вокруг точки. Кроме того, деревья k -d всегда являются двоичными, чего нельзя сказать о окт-деревьях. При использовании поиска в глубину необходимо пройти узлы и просмотреть только необходимые поверхности.

История

Впервые использование октодеревьев для трехмерной компьютерной графики было предложено Дональдом Мигером из Политехнического института Ренсселера и описано в отчете 1980 года «Кодирование октодерева: новый метод представления, манипулирования и отображения произвольных трехмерных объектов с помощью компьютера». на что он имеет патент 1995 года (с датой приоритета 1984 года ) «Высокоскоростное создание изображений сложных твердых объектов с использованием кодирования октодерева».

Общее использование

• Уровень детализации в компьютерной 3D-графике.
• Пространственная индексация
• Поиск ближайшего соседа
• Эффективное обнаружение столкновений в трех измерениях
• Просмотр отсечения усеченного конуса
• Быстрый мультипольный метод
• Неструктурированная сетка
• Конечно-элементный анализ
• Разреженное октодерево вокселей
• Оценка состояния
• Установить оценку

Применение к квантованию цвета

октодерева Алгоритм квантования цвета , изобретенный Герваутцем и Пургатхофером в 1988 году, кодирует данные цвета изображения в виде октодерева глубиной до девяти уровней. Октрины используются потому, что $2^{3}=8$ есть три цветовых компонента и в системе RGB . Индекс узла, от которого требуется ответвление на верхнем уровне, определяется по формуле, в которой используются старшие биты компонентов красного, зеленого и синего цвета, например 4r + 2g + b. Следующий более низкий уровень использует значение следующего бита и так далее. Менее значимые биты иногда игнорируются, чтобы уменьшить размер дерева.

Алгоритм отличается высокой эффективностью использования памяти, поскольку размер дерева может быть ограничен. Нижний уровень октодерева состоит из конечных узлов, которые накапливают данные о цвете, не представленные в дереве; эти узлы изначально содержат одиночные биты. Если в окт-дерево введено гораздо больше цветов палитры, чем желаемое, его размер можно постоянно уменьшать, находя узел нижнего уровня и усредняя его битовые данные до конечного узла, отсекая часть дерева. После завершения выборки исследование всех маршрутов в дереве вплоть до конечных узлов, принимая во внимание биты на этом пути, даст примерно необходимое количество цветов.

Реализация точечной декомпозиции

В приведенном ниже примере схемы рекурсивного алгоритма ( синтаксис MATLAB ) массив трехмерных точек разлагается на ячейки в стиле октодерева. Реализация начинается с единого интервала, окружающего все заданные точки, который затем рекурсивно подразделяется на области из 8 октодеревьев. Рекурсия останавливается, когда выполняется заданное условие выхода. Примеры таких условий выхода (показаны в коде ниже):

• Когда ячейка содержит меньше заданного количества точек
• Когда контейнер достигает минимального размера или объема в зависимости от длины его краев.
• Когда рекурсия достигла максимального количества подразделений

function [binDepths, binParents, binCorners, pointBins] = OcTree(points)

binDepths = [0]     % Initialize an array of bin depths with this single base-level bin
binParents = [0]    % This base level bin is not a child of other bins
binCorners = [min(points) max(points)] % It surrounds all points in XYZ space
pointBins(:) = 1    % Initially, all points are assigned to this first bin
divide(1)           % Begin dividing this first bin

function divide(binNo)

% If this bin meets any exit conditions, do not divide it any further.
binPointCount = nnz(pointBins == binNo)
binEdgeLengths = binCorners(binNo, 1:3) - binCorners(binNo, 4:6)
binDepth = binDepths(binNo)
exitConditionsMet = binPointCount<value || min(binEdgeLengths) < value || binDepth > value
if exitConditionsMet
    return; % Exit recursive function
end

% Otherwise, split this bin into 8 new sub-bins with a new division point
newDiv = (binCorners(binNo, 1:3) + binCorners(binNo, 4:6)) / 2
for i = 1:8
    newBinNo = length(binDepths) + 1
    binDepths(newBinNo) = binDepths(binNo) + 1
    binParents(newBinNo) = binNo
    binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]
    oldBinMask = pointBins == binNo
    % Calculate which points in pointBins == binNo now belong in newBinNo
    pointBins(newBinMask) = newBinNo
    % Recursively divide this newly created bin
    divide(newBinNo)
end

Пример квантования цвета

Взяв полный список цветов 24-битного изображения RGB в качестве входных данных для реализации точечного разложения октодерева, описанной выше, в следующем примере показаны результаты квантования цвета октодерева. Первое изображение является исходным (532818 различных цветов), а второе — квантованным изображением (184 различных цвета) с использованием разложения октодерева, где каждому пикселю присваивается цвет в центре ячейки октодерева, в которую он попадает. Альтернативно, окончательные цвета могут быть выбраны в центроиде всех цветов в каждом интервале октодерева, однако это добавленное вычисление очень мало влияет на визуальный результат.

% Read the original RGB image
Img = imread('IMG_9980.CR2');
% Extract pixels as RGB point triplets
pts = reshape(Img, [], 3);
% Create OcTree decomposition object using a target bin capacity
OT = OcTree(pts, 'BinCapacity', ceil((size(pts, 1) / 256) * 7));
% Find which bins are "leaf nodes" on the octree object
leafs = find(~ismember(1:OT.BinCount, OT.BinParents) & ...
    ismember(1:OT.BinCount, OT.PointBins));
% Find the central RGB location of each leaf bin
binCents = mean(reshape(OT.BinBoundaries(leafs,:), [], 3, 2), 3);
 
% Make a new "indexed" image with a color map
ImgIdx = zeros(size(Img, 1), size(Img, 2));
for i = 1:length(leafs)
    pxNos = find(OT.PointBins==leafs(i));
    ImgIdx(pxNos) = i;
end
ImgMap = binCents / 255; % Convert 8-bit color to MATLAB rgb values
 
% Display the original 532818-color image and resulting 184-color image 
figure
subplot(1, 2, 1), imshow(Img)
title(sprintf('Original %d color image', size(unique(pts,'rows'), 1)))
subplot(1, 2, 2), imshow(ImgIdx, ImgMap)
title(sprintf('Octree-quantized %d color image', size(ImgMap, 1)))

См. также

• Разделение двоичного пространства
• Иерархия граничных интервалов
• Cube 2: Sauerbraten , игровой 3D-движок, в котором геометрия почти полностью основана на октодеревьях.
• id Tech 6 — это 3D-игровой движок, использующий вокселы, хранящиеся в октодеревьях.
• Irrlicht Engine , поддерживает узлы сцены октодерева.
• Проблема меры Клее
• Линейное октодерево
• OGRE имеет реализацию менеджера сцен октодерева.
• Мощение
• Воксель
• Четырехдерево

Внешние ссылки

• Квантование октодерева в Microsoft Systems Journal
• Квантование цвета с использованием октодеревьев в Dr. Dobb's
• Обзор квантования цвета Octree
• Соян Лал, П.; Унникришнан, А.; Пулос Джейкоб, К. (1998). «Параллельная реализация алгоритма генерации октодерева» . Материалы Международной конференции по обработке изображений 1998 г. ICIP98 (Кат. № 98CB36269) . Том. 3. С. 1005–1009. дои : 10.1109/ICIP.1998.727419 . ISBN  0-8186-8821-1 . S2CID   195863788 .
• Генерация октодеревьев из растрового сканирования с уменьшенной потерей информации, П. Соян Лал, А. Унникришнан, К. Пулос Джейкоб, Международная конференция IASTED VIIP 2001 [1]
• Параллельные октодеревья для приложений конечных элементов
• Видео: Использование октодерева при оценке состояния