Октодерева представляет собой структуру данных , дерево , в котором каждый внутренний узел имеет ровно восемь детей . Октодеревья чаще всего используются для разделения трехмерного пространства путем рекурсивного деления его на восемь октантов. Октодеревья являются трехмерным аналогом квадродеревьев . Имя образовано от oct + tree , но учтите, что обычно оно пишется " octree " только с одним "t". Октодеревья часто используются в 3D-графике и в 3D- игровых движках .
Для пространственного представления [ править ]
Каждый узел в октодереве подразделяет пространство, которое он представляет, на восемь октантов . В октодереве точечной области (PR) узел хранит явную трехмерную точку , которая является «центром» подразделения для этого узла; точка определяет один из углов для каждого из восьми детей. В октодереве на основе матрицы (MX) точка подразделения неявно является центром пространства, которое представляет узел. Корневой узел октодерева PR может представлять бесконечное пространство; корневой узел октодерева MX должен представлять конечное ограниченное пространство, чтобы неявные центры были четко определены. Обратите внимание, что октодеревья - это не то же самое, что деревья k -d : деревья k -d разделяются по измерению, а октодеревья разбиваются вокруг точки. Также k-d деревья всегда бинарны, чего нельзя сказать о октодеревьях. Используя поиск в глубину, необходимо проходить узлы и просматривать только требуемые поверхности.
История [ править ]
Использование октодерева для трехмерной компьютерной графики было впервые предложено Дональдом Мигером из Политехнического института Ренсселера , описанным в отчете 1980 г. «Кодирование октодерева: новая техника для представления, манипулирования и отображения произвольных трехмерных объектов с помощью компьютера», [1] на который он имеет патент 1995 г. (с датой приоритета 1984 г. ) «Высокоскоростное создание изображений сложных твердых объектов с использованием кодирования октодерева» [2]
Обычное использование [ править ]
- Уровень детализации в компьютерной 3D-графике [3]
- Пространственная индексация
- Поиск ближайшего соседа [4]
- Эффективное обнаружение столкновений в трех измерениях
- Просмотр усеченной выбраковки
- Быстрый мультипольный метод
- Неструктурированная сетка
- Анализ методом конечных элементов
- Редкое октодерево вокселей [5]
- Оценка состояния [6]
- Установить оценку [7]
Приложение для квантования цвета [ править ]
Алгоритм квантования цвета октодерева , изобретенный Герваутцем и Пургатхофером в 1988 году, кодирует данные цвета изображения как октодерево глубиной до девяти уровней. Октодеревья используются потому, что в системе RGB есть три цветовых компонента . Индекс узла, от которого следует разветвляться на верхнем уровне, определяется формулой, в которой используются наиболее значимые биты компонентов красного, зеленого и синего цветов, например 4r + 2g + b. Следующий более низкий уровень использует значение следующего бита и так далее. Менее значимые биты иногда игнорируются, чтобы уменьшить размер дерева.
Алгоритм очень эффективен с точки зрения памяти, поскольку размер дерева может быть ограничен. Нижний уровень октодерева состоит из листовых узлов, которые накапливают данные цвета, не представленные в дереве; эти узлы изначально содержат одиночные биты. Если в октодерево вводится гораздо больше, чем желаемое количество цветов палитры, его размер можно постоянно уменьшать, отыскивая узел нижнего уровня и усредняя его битовые данные до конечного узла, сокращая часть дерева. После завершения выборки исследование всех маршрутов в дереве вплоть до листовых узлов с учетом битов на этом пути даст примерно необходимое количество цветов.
Реализация точечной декомпозиции [ править ]
Контур Примера рекурсивного алгоритма ниже ( MATLAB синтаксиса) разлагается массив 3-мерных точек в октодереве бункеров стиля. Реализация начинается с одного бина, окружающего все заданные точки, который затем рекурсивно разделяется на 8 областей октодерева. Рекурсия останавливается, когда выполняется заданное условие выхода. Примеры таких условий выхода (показаны в коде ниже):
- Когда в корзине меньше заданного количества точек
- Когда бункер достигает минимального размера или объема в зависимости от длины его краев
- Когда рекурсия достигла максимального количества подразделений
функция [binDepths, binParents, binCorners, pointBins] = OcTree ( точки ) binDepths = [ 0 ] % Инициализирует массив глубин бинов с помощью этого единственного бункера базового уровня binParents = [ 0 ] % Этот бункер базового уровня не является дочерним по отношению к другим бункерам binCorners = [ min ( points ) max ( points )] % It окружает все точки в пространстве XYZ pointBins (:) = 1 % Изначально все точки назначаются этому первому делению бина ( 1 ) % Начните деление этого первого деления функции бина ( binNo ) % Если этот лоток удовлетворяет каким-либо условиям выхода, не разделяйте его дальше. binPointCount = nnz ( pointBins == binNo ) binEdgeLengths = binCorners ( binNo , 1 : 3 ) - binCorners ( binNo , 4 : 6 ) binDepth = binDepths ( binNo ) exitConditionsMet = binPointCount < значение || мин ( binEdgeLengths ) < значение || binDepth > значение, если exitConditionsMet return ; % Выход из рекурсивной функции end % В противном случае разделите этот лоток на 8 новых суб-ячеек с новой точкой разделения newDiv = ( binCorners ( binNo , 1 : 3 ) + binCorners ( binNo , 4 : 6 )) / 2 для i = 1 : 8 newBinNo = length ( binDepths ) + 1 binDepths ( newBinNo ) = binDepths ( binNo ) + 1 binParents( NewBinNo ) = binNo binCorners ( newBinNo ) = [ один из самых 8 пар из в newDiv с minCorner или maxCorner ] oldBinMask = pointBins == binNo % Вычислить , какие точки в pointBins == binNo Теперь принадлежат newBinNo pointBins ( newBinMask ) = newBinNo % Рекурсивно разделить этот вновь созданный разделитель бинов ( newBinNo ) end
Пример цветового квантования [ править ]
Принимая полный список цветов 24-битного изображения RGB в качестве входной точки для реализации декомпозиции точек октодерева, описанной выше, следующий пример показывает результаты квантования цвета октодерева. Первое изображение является исходным (532818 различных цветов), а второе - квантованным изображением (184 различных цвета) с использованием декомпозиции октодерева, при этом каждому пикселю назначается цвет в центре окна октодерева, в которое он попадает. В качестве альтернативы, конечные цвета могут быть выбраны в центроиде всех цветов в каждом бункере октодерева, однако это добавленное вычисление очень мало влияет на визуальный результат. [8]
% Прочитать исходное изображение RGB Img = imread ( 'IMG_9980.CR2' ); % Извлечь пиксели как триплеты точек RGB pts = reshape ( Img , [], 3 ); % Создать объект декомпозиции OcTree с использованием целевой емкости бункера OT = OcTree ( pts , 'BinCapacity' , ceil (( size ( pts , 1 ) / 256 ) * 7 )); % Найти которые бункеры «листовые узлы» на объект октодерева Лифс = находке( ~ ismember ( 1 : OT . BinCount , OT . BinParents ) & ... ismember ( 1 : OT . BinCount , OT . PointBins )); % Найти центральное RGB расположение каждого листа бен binCents = средняя ( Reshape ( OT . BinBoundaries ( листья ,:), [], 3 , 2 ), 3 ); % Создайте новое "проиндексированное" изображение с цветовой картой ImgIdx = нули ( размер ( Img , 1 ), размер ( Img , 2 )); для я = 1 : длина ( листья ) pxNos = найти ( OT . PointBins == листья ( я )); ImgIdx ( pxNos ) = i ; конец ImgMap = binCents / 255 ; % Преобразование 8-битного цвета в значения MATLAB rgb % Отображение исходного 532818-цветное изображение и в результате 184-цветного изображения фигуры подзаговора (1,2,1), imshow (Img) Название ( Sprintf ( 'Оригинал% d цветного изображения' , размера ( уникальный ( PTS , 'строк' ) , 1 ))) subplot ( 1 , 2 , 2 ), imshow ( ImgIdx , ImgMap ) title ( sprintf ( 'Цветное изображение% d, квантованное по октодереву' , size ( ImgMap , 1)))
См. Также [ править ]
- Разделение двоичного пространства
- Иерархия ограничивающих интервалов
- Cube 2: Sauerbraten , трехмерный игровой движок, в котором геометрия почти полностью основана на октодеревьях.
- id Tech 6 - это трехмерный игровой движок, использующий воксели, хранящиеся в октодеревьях.
- Irrlicht Engine , поддерживает узлы сцены октодерева
- Клее проблема меры
- Линейное октодерево
- OGRE , имеет реализацию менеджера сцены октодерева
- Подмощение
- Воксель
- Quadtree
Ссылки [ править ]
- ^ Мигэр, Дональд (октябрь 1980). «Кодирование октодерева: новый метод представления, манипулирования и отображения произвольных трехмерных объектов с помощью компьютера». Политехнический институт Ренсселера (Технический отчет IPL-TR-80-111).
- ^ Мигер, Дональд. «Быстрая генерация изображений сложных твердых объектов с использованием кодирования октодерева» . УСПО . Проверено 20 сентября 2012 года .
- ^ Дэвид П. Luebke (2003). Уровень детализации 3D-графики . Морган Кауфманн. ISBN 978-1-55860-838-2.
- ^ Эльзеберг, Ян и др. « Сравнение стратегий поиска ближайшего соседа и реализаций для эффективной регистрации формы ». Журнал программной инженерии для робототехники 3.1 (2012): 2-12.
- ^ Akenine-Mo ller, Tomas; Хейнс, Эрик; Хоффман, Нэти (2018-08-06). Рендеринг в реальном времени, четвертое издание . CRC Press. ISBN 978-1-351-81615-1.
- ^ Хеннинг Эберхард, Веса Клумпп, Уве Д. Ханебек, Деревья плотности для эффективного нелинейного оценивания состояния , Труды 13-й Международной конференции по слиянию информации, Эдинбург, Соединенное Королевство, июль 2010 г.
- ^ В. Древелле, Л. Джаулин и Б. Зерр, Гарантированная характеристика исследуемого пространства мобильного робота с помощью субмарин , NOLCOS 2013.
- ^ Блумберг, Дэн С. «Цветовое квантование с использованием октодеревьев». , 4 сентября 2008 г. Проверено 12 декабря 2014 г.
Внешние ссылки [ править ]
Викискладе есть медиафайлы по теме Octrees . |
- Квантование октодерева в Microsoft Systems Journal
- Квантование цвета с использованием октодеревьев доктора Добба
- Квантование цвета с использованием октодеревьев в исходном коде доктора Добба [ постоянная мертвая ссылка ]
- Обзор квантования цвета октодерева
- Параллельная реализация алгоритма генерации октодерева, П. Соджан Лал, А. Унникришнан, К. Пулозе Якоб, ICIP 1997, IEEE Digital Library
- Генерация октодерева из растрового сканирования с уменьшенной потерей информации, П. Соджан Лал, А. Унникришнан, К. Пулозе Джейкоб, Международная конференция IASTED VIIP 2001 [1] [ постоянная мертвая ссылка ]
- Параллельные октодеревья для приложений с конечными элементами
- Видео: Использование октодерева в оценке состояния