Октодерево

Октодерево

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

Сферическая модель октодерева с глубиной 7

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

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

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

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

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

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

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

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

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

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

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

• Octree Quantization в Microsoft Systems Journal
• Квантизация цвета с использованием октодеревьев
• Color Quantization using Octrees in Dr. Dobb's Source Code
• Обзор октодеревьев
• Parallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library
• Generation of Octrees from Raster Scan with Reduced Information Loss, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, IASTED International conference VIIP 2001 [1]
• C++ implementation (GPL license)
• Parallel Octrees for Finite Element Applications

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

• Артем Мерец «Scart» Алгоритм Octree - теория и практика на DirectX 2. UralDev (26 февраля 2007 года). Архивировано из первоисточника 2 апреля 2012. Проверено 3 июня 2009.
• Артем Мерец «Scart» Алгоритм Octree (часть 2) 2. UralDev (5 февраля 2008 года). Архивировано из первоисточника 2 апреля 2012. Проверено 3 июня 2009.
• Джо Разбиение объектного пространства сцены путём построения octree-дерева. GameDev.ru. Архивировано из первоисточника 2 апреля 2012. Проверено 3 июня 2009.
• Octree (Дерево октантов). GameDev.ru. Архивировано из первоисточника 2 апреля 2012. Проверено 3 июня 2009.
• Алексей Игнатенко Графический процесс Геометрическое моделирование Лекция 6. Архивировано из первоисточника 2 апреля 2012. Проверено 3 июня 2009.

Для улучшения этой статьи желательно?: Проставив сноски, внести более точные указания на источники. Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.