Октри

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

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

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

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

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

История [ править ]

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

Общее использование [ править ]

Применение к квантованию цвета [ править ]

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

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

Реализация точечной декомпозиции [ править ]

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

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

function   [binDepths, binParents, binCorners, pointBins] = OcTree  (  points  )  binDepths   =   [  0  ]       % Инициализировать массив глубин ячеек с помощью этого единственного интервала базового уровня  binParents   =   [  0  ]      % Этот интервал базового уровня не является дочерним элементом другого bins  binCorners   =   [  min  (  points  )   max  (  points  )]   % Он окружает все точки в пространстве XYZ  pointBins  (:)   =   1      % Первоначально все точки назначаются этому первому  разделителю интервала  (  1  )             % Начинаем деление этого первого интервала  с функцией   деления  (  binNo  )  % Если этот интервал соответствует каким-либо условиям выхода, не делите его дальше.  binPointCount   =   nnz  (  pointBins   ==   binNo  )  binEdgeLengths   =   binCorners  (  binNo  ,   1  :  3  )   -   binCorners  (  binNo  ,   4  :  6  )  binDepth   =   binDepths  (  binNo  )  exitConditionsMet   =   binPointCount  <  значение   ||   min  (  binEdgeLengths  )   <   значение   ||   binDepth   >   значение  , если   exitConditionsMet      return  ;   % Выход из рекурсивной функции,  конец  % В противном случае разделите этот интервал на 8 новых подотделов с новой точкой разделения  newDiv   =   (  binCorners  (  binNo  ,   1  :  3  )   +   binCorners  (  binNo  ,   4  :  6  ))   /   2  for   i   =   1  :  8      newBinNo   =   длина  (  binDepths  )   +   1      binDepths  (  newBinNo  )   =   binDepths  (  binNo  )   +   1      binParents  (  newBinNo  )   =   binNo      binCorners  (  newBinNo  )   =   [  одна   из   8     пар  newDiv   теперь   % Вычислить, какие точки в pointBins == binNo   с   minCorner   или   maxCorner  ]      oldBinMask   =   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  ));  объекта октодерева  % Найдите, какие ячейки являются «листовыми узлами» на листьях   =   find  (  ~  ismember  (  1  :  OT  .  BinCount  ,   OT  .  BinParents  )   &   ...      ismember  (  1  :  OT  .  BinCount  ,   OT  .  PointBins  ));  % Найдите центральное местоположение RGB каждого листового контейнера  binCents   =   mean  (  reshape  (  OT  .  BinBoundaries  (  Leafs  ,:),   [],   3  ,   2  ),   3  );   % Создать новое «индексированное» изображение с картой цветов  ImgIdx   =   нули  (  размер  (  Img  ,   1  ),   размер  (  Img  ,   2  ));  для   i   =   1  :  длина  (  листья  )      pxNos   =   find  (  OT  .  PointBins  ==  листы  (  i  ));      ImgIdx  (  pxNos  )   =   я  ;  конец  ImgMap   =   binCents   /   255  ;   % Преобразование 8-битного цвета в значения MATLAB rgb   184-цветного изображения  (  % Отобразите исходное 532818-цветное изображение и результирующий подграфик  1  ,  2   ,  1   )  ,   imshow  (  Img  )  title  (  sprintf  (  'Исходное цветное изображение %d'  ,   размер  (  уникальный  (  pts  ,  'rows'  ),   1  )))  подграфик  (  1  ,   2  ,   2  ),   imshow  (  ImgIdx  ,   ImgMap  )  заголовок  (  sprintf  (  'Цветное изображение %d, квантованное по октодереву'  ,   размер  (  ImgMap  ,   1  ) ))

См. также [ править ]

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

Ссылки [ править ]

^ Мигер, Дональд (октябрь 1980 г.). «Октри-кодирование: новый метод представления, манипулирования и отображения произвольных трехмерных объектов на компьютере». Политехнический институт Ренсселера (Технический отчет IPL-TR-80-111).
^ Мигер, Дональд. «Высокоскоростная генерация изображений сложных твёрдых объектов с использованием октодерева» . УСПО . Проверено 20 сентября 2012 г.
^ Дэвид П. Любке (2003). Уровень детализации 3D-графики . Морган Кауфманн. ISBN 978-1-55860-838-2 .
^ Эльсеберг, Ян и др. « Сравнение стратегий и реализаций поиска ближайшего соседа для эффективной регистрации формы ». Журнал разработки программного обеспечения для робототехники 3.1 (2012): 2-12.
^ Акенине-Мёллер, Томас; Хейнс, Эрик; Хоффман, Нати (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание . ЦРК Пресс. ISBN 978-1-351-81615-1 .
^ Хеннинг Эберхардт, Веса Клампп, Уве Д. Ханебек, Деревья плотности для эффективной нелинейной оценки состояния , Материалы 13-й Международной конференции по объединению информации, Эдинбург, Великобритания, июль 2010 г.
^ В. Древель, Л. Жолен и Б. Зерр, Гарантированная характеристика исследуемого пространства мобильного робота с использованием грунтового покрытия , NOLCOS 2013.
^ Блумберг, Дэн С. «Квантование цвета с использованием октодеревьев». , 4 сентября 2008 г. Проверено 12 декабря 2014 г.

Внешние ссылки [ править ]

Квантование октодерева в 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] ^{[ постоянная мертвая ссылка ]}
Параллельные октодеревья для приложений конечных элементов
Видео: Использование октодерева при оценке состояния

[1] Мигер, Дональд (октябрь 1980 г.). «Октри-кодирование: новый метод представления, манипулирования и отображения произвольных трехмерных объектов на компьютере». Политехнический институт Ренсселера (Технический отчет IPL-TR-80-111).

[2] Мигер, Дональд. «Высокоскоростная генерация изображений сложных твёрдых объектов с использованием октодерева» . УСПО . Проверено 20 сентября 2012 г.

[Luebke2003-3] Дэвид П. Любке (2003). Уровень детализации 3D-графики . Морган Кауфманн. ISBN 978-1-55860-838-2 .

[4] Эльсеберг, Ян и др. « Сравнение стратегий и реализаций поиска ближайшего соседа для эффективной регистрации формы ». Журнал разработки программного обеспечения для робототехники 3.1 (2012): 2-12.

[5] Акенине-Мёллер, Томас; Хейнс, Эрик; Хоффман, Нати (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание . ЦРК Пресс. ISBN 978-1-351-81615-1 .

[6] Хеннинг Эберхардт, Веса Клампп, Уве Д. Ханебек, Деревья плотности для эффективной нелинейной оценки состояния , Материалы 13-й Международной конференции по объединению информации, Эдинбург, Великобритания, июль 2010 г.

[7] В. Древель, Л. Жолен и Б. Зерр, Гарантированная характеристика исследуемого пространства мобильного робота с использованием грунтового покрытия , NOLCOS 2013.

[8] Блумберг, Дэн С. «Квантование цвета с использованием октодеревьев». , 4 сентября 2008 г. Проверено 12 декабря 2014 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Древовидные структуры данных
Поиск деревьев ( динамические наборы / ассоциативные массивы )	2–3 2–3–4 АА (а, б) АВЛ Б B+ Б* Б ^х ( Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов ( Наклон влево ) Красно-черный козел отпущения Распространение Т Треп УБ Сбалансированный по весу
Кучи	Двоичный Биномиальный Мостовая долина д -и Фибоначчи Левый Сопряжение Наклонный бином Перекос от Эмде Боас Слабый
Пытается	Cтрие C-trie (сжатый ADT) Хэш Радикс Суффикс Троичный поиск X-быстрый Y-быстро
пространственных данных Деревья разделения	Мяч БК БСП Декартовский Гильберт Р. k -d ( неявный k -d ) М Метрика MVP Октри PH Приоритет Р Четырехместный Р Р+ Р* Сегмент вице-президент Х
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние Хэш-календарь iDistance К-и Левый ребенок, правый брат Связать/вырезать Лог-структурированное слияние Меркле ПК Диапазон SPQR Вершина