Октодерево ( дерево октантов , восьмеричное дерево , англ. octree ) — тип древовидной структуры данных , в которой у каждого внутреннего узла ровно восемь «потомков». Восьмеричные деревья чаще всего используются для разделения трёхмерного пространства, рекурсивно разделяя его на восемь ячеек. Октодеревья являются трёхмерными аналогами квадродеревьев . Англоязычное название «octree» сформировано из oct + tree и обычно пишется как «octree», а не «octtree».

Представление пространства октодеревом

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

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

• (англ.) (
• Эффективное обнаружение столкновений в трёхмерном пространстве
• (англ.) (
• Быстрый метод мультиполей
• Неструктурированная сетка
• Метод конечных элементов
• Трассировка лучей

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

Алгоритм октодерева для (англ.) ( , изобретённый Гервауцем и Пургатхофером в 1988 году, кодирует данные о цвете изображения как октодерево с девятью уровнями в глубину. Использование октодерева объясняется тем, что ${\displaystyle 2^{3}=8}$ и в системе RGB есть три компоненты цвета. Данный алгоритм очень эффективен по отношению к использованию памяти, потому что размер дерева может быть ограничен. Нижний (базовый) уровень октодерева состоит из узловых листьев ( англ. leaf nodes ), которые накапливают данные о цвете, которые не представлены в дереве; эти узлы первоначально содержат единичные биты. Если в октодерево введено намного большее количество цветовой палитры, чем желательное, то размер октодерева может непрерывно сокращаться, ведя поиск узла на нижнем (базовом) уровне и составляя в среднем его битовые данные в узловой лист, сокращая часть дерева. Как только осуществление выборки закончено, в дереве исследуются все маршруты по направлению вниз к узловым листьям, принимая во внимание биты по пути поиска. Этот процесс приведёт к приблизительному количеству требуемых цветов.

Использование октодеревьев в конкретных приложениях

Список примеров в этой статье не основывается на авторитетных источниках , посвящённых непосредственно предмету статьи. Добавьте ссылки на источники , предметом рассмотрения которых является тема настоящей статьи (или раздела) в целом, а не отдельные элементы списка. В противном случае список примеров может быть удалён.

• — свободный игровой движок .
• — компьютерная игра , которая использует игровой движок Cube 2 , который использует октодеревья.
• OGRE — свободный объектно-ориентированный графический движок , в котором присутствует менеджер сцен, использующий октодеревья ( англ. Octree Scene Manager )
• — параллельная мультисеточная библиотека для вычислений методом конечных элементов, использующая октодерево (MPI/C++ реализация)
• - пакет кодов для численного моделирования астрофизических процессов от Чикагского университета.

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

Англоязычные источники

• (недоступная ссылка)
• (недоступная ссылка)
• от 3 марта 2016 на Wayback Machine

Русскоязычные источники

• Артем Мерец «Scart». (неопр.) 2. (26 февраля 2007). Дата обращения: 3 июня 2009. 2 апреля 2012 года.
• Артем Мерец «Scart». (неопр.) 2. (5 февраля 2008). Дата обращения: 3 июня 2009. 2 апреля 2012 года.
• Джо. (неопр.) . GameDev.ru . Дата обращения: 3 июня 2009.
• (неопр.) . GameDev.ru . Дата обращения: 3 июня 2009.
• Алексей Игнатенко. (неопр.) . Дата обращения: 3 июня 2009. Архивировано из 2 апреля 2012 года.