Октодерево

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

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

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

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