Просмотр кода страницы Октодерево

[[Файл:Octree.png|thumb|right|300px|Октодерево]]
[[Файл:Octree2.png|thumb|right|300px|Слева: Рекурсивное разделение куба на октанты. Справа: Соответствующее октодерево.]]
[[Файл:Esfera octree.png|thumb|right|300px|Сферическая модель октодерева с глубиной 7]]

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

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

== Общее использование октодеревьев ==
* {{нп3|Пространственная индексация|Пространственная индексация|en|Spatial index}}
* Эффективное [[обнаружение столкновений]] в трёхмерном пространстве
* {{нп3|Определение скрытых поверхностей|Определение скрытых поверхностей|en|Hidden surface determination}}
* [[Быстрый метод мультиполей]]
* [[Неструктурированная сетка]]
* [[Метод конечных элементов]]
* [[Трассировка лучей]]

== Применение для квантования цвета ==
{{нет ссылок в разделе|дата=27 августа 2020}}
Алгоритм октодерева для {{нп3|Квантование цвета|квантования цвета|en|Color quantization}}, изобретённый Гервауцем и Пургатхофером в 1988 году, кодирует данные о цвете изображения как октодерево с девятью уровнями в глубину. Использование октодерева объясняется тем, что <math>2^3 = 8</math> и в системе [[RGB]] есть три компоненты цвета. Данный алгоритм очень эффективен по отношению к использованию памяти, потому что размер дерева может быть ограничен. Нижний (базовый) уровень октодерева состоит из узловых листьев ({{lang-en|leaf nodes}}), которые накапливают данные о цвете, которые не представлены в дереве; эти узлы первоначально содержат единичные биты. Если в октодерево введено намного большее количество цветовой палитры, чем желательное, то размер октодерева может непрерывно сокращаться, ведя поиск узла на нижнем (базовом) уровне и составляя в среднем его битовые данные в узловой лист, сокращая часть дерева. Как только осуществление выборки закончено, в дереве исследуются все маршруты по направлению вниз к узловым листьям, принимая во внимание биты по пути поиска. Этот процесс приведёт к приблизительному количеству требуемых цветов.

== Использование октодеревьев в конкретных приложениях ==
{{список примеров|дата=2016-10-30}}
* [[Urho3D]] —  [[Свободное ПО|свободный]] [[игровой движок]].
* [[Sauerbraten]] — [[компьютерная игра]], которая использует [[игровой движок]] [[Cube 2]], который использует октодеревья.
* [[OGRE]] — [[Свободное ПО|свободный]] объектно-ориентированный [[графический движок]], в котором присутствует менеджер сцен, использующий октодеревья ({{lang-en|Octree Scene Manager}})
* [http://www.cc.gatech.edu/csela/dendro/html/index.html Dendro] — параллельная мультисеточная библиотека для вычислений методом конечных элементов, использующая октодерево (MPI/C++ реализация)
* [[FLASH]] - пакет кодов для численного моделирования астрофизических процессов от Чикагского университета.

== Внешние ссылки ==
'''Англоязычные источники'''
* [https://web.archive.org/web/20140605161956/http://www.microsoft.com/msj/archive/S3F1.aspx Octree Quantization в Microsoft Systems Journal]
* [http://www.ddj.com/184409805 Квантизация цвета с использованием октодеревьев]
* [ftp://66.77.27.238/sourcecode/ddj/1996/9601.zip Color Quantization using Octrees in Dr. Dobb's Source Code]{{Недоступная ссылка|date=Октябрь 2018 |bot=InternetArchiveBot }}
* [http://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html Обзор октодеревьев]
* [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=727419 Parallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library]
* [https://dblp.uni-trier.de/db/conf/viip/viip2001.html#LalUJ01 Generation of Octrees from Raster Scan with Reduced Information Loss, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, IASTED International conference VIIP 2001] [http://www.actapress.com/catalogue2009/proc_series13.html#viip2001]{{Недоступная ссылка|date=Октябрь 2018 |bot=InternetArchiveBot }}
* [http://nomis80.org/code/octree.html C++ implementation (GPL license)]
* [http://sc07.supercomputing.org/schedule/pdf/pap117.pdf Parallel Octrees for Finite Element Applications] {{Wayback|url=http://sc07.supercomputing.org/schedule/pdf/pap117.pdf |date=20160303224709 }}
'''Русскоязычные источники'''
* {{cite web|url=http://www.uraldev.ru/articles/id/6|title=Алгоритм Octree - теория и практика на DirectX|author=Артем Мерец «Scart»|publisher=[[UralDev]]|datepublished=2007-02-26|accessdate=2009-06-03|pages=2|archiveurl=https://www.webcitation.org/66cMz4589?url=http://www.uraldev.ru/articles/id/6|archivedate=2012-04-02|deadlink=no}}
* {{cite web|url=http://www.uraldev.ru/articles/id/20|title=Алгоритм Octree (часть 2)|author=Артем Мерец «Scart»|publisher=[[UralDev]]|datepublished=2008-02-05|accessdate=2009-06-03|pages=2|archiveurl=https://www.webcitation.org/66cN0L5JJ?url=http://www.uraldev.ru/articles/id/20|archivedate=2012-04-02|deadlink=no}}
* {{cite web|url=http://www.gamedev.ru/articles/?id=30114|title=Разбиение объектного пространства сцены путём построения octree-дерева|author=Джо|publisher=[[GameDev.ru]]|datepublished=|accessdate=2009-06-03|archiveurl=|archivedate=|deadlink=no}}
* {{cite web|url=http://www.gamedev.ru/terms/Octree|title=Octree (Дерево октантов)|author=|publisher=[[GameDev.ru]]|datepublished=|accessdate=2009-06-03|archiveurl=|archivedate=|deadlink=no}}
* {{cite web|url=http://courses.graphicon.ru/files/courses/cg3/2008/lectures/lect06_08.pdf|title=Графический процесс Геометрическое моделирование <small>Лекция 6</small>|author=Алексей Игнатенко|publisher=|datepublished=|accessdate=2009-06-03|archiveurl=https://www.webcitation.org/66cN2wYud?url=http://courses.graphicon.ru/files/courses/cg3/2008/lectures/lect06_08.pdf|archivedate=2012-04-02|deadlink=yes}}

{{Внешние ссылки}}
{{Деревья (структуры данных)}}

[[Категория:Деревья (структуры данных)]]