Октално стабло

Лево: Рекурзивно дељење коцке на октанте. Десно: Одговарајуће октално стабло.

Октална стабла су стабла код којих сваки унутрашњи чвор има тачно 8 деце. Октална стабла се најчешће користе за рекурзивно дељење тродимензионог простора на октанте, као и у тродимензионалној рачунарској графици и тродимензионим покретачима игара.

Октална стабла за представљање простора

Сваки чвор у окталном стаблу дели простор на осам октаната. Сваки чвор чува тачку у три димензије која представља „центар“ дела који представља тај чвор. Та тачка дефинише један од ћошкова за свако од његове осморо деце. У стаблима заснованим на матрицама (MX стабла), ова тачка је имплицитно центар дељеног простора, тако да MX стабла могу да представљају само коначан простор, док то не важи ѕа остала октална стабла. Приметимо да октална стабла нису иста као и К-Д стабла. К-Д стабла деле простор преко једне димензије и увек су бинарна, док октална то раде око тачке и увек су октална. Коришћењем претраге у дубину чворови ће се померати, а само потребне површине ће бити видљиве.

Историја

Коришћење окталних стабала у тродимензионалној рачунарској графици је развио Доналд Мегер (Шаблон:Јез-енгл), што је описано у извештају из 1980. године Шифровање окталних стабала: Нова техника репрезентације, манипулације и приказивања произвољног тродимензионог објекта рачунаром (Шаблон:Јез-енгл). Он поседује патент из 1995. са именом Генерисање слика комплексних чврстих објеката коришћењем шифровања окталним стаблима (Шаблон:Јез-енгл).

Честе употребе окталних стабала

• Тродимензионална рачунарска графика
• Просторно индексирање
• Претраживање најближег суседа
• Ефикасно детектовање колизије у тродимензионом простору
• Детектовање невидљивих површина
• Неструктуирана мрежа
• Анализа коначног елемента
• Спарс Вокселово октално стабло
• Процена положаја
• Процена сета

Употреба у квантификовању боја

Алгоритам за квантификовање боја помоћу окталних стабала, кога су измислили Гервауц (Шаблон:Јез-енгл) и Пургатофер (Шаблон:Јез-енгл) 1988. године, шифрује податке о боји слике као октално стабло и до девет нивоа дубоко. Користе се октална стабла зато што постоје три компоненте боја у RGB систему, а $2^3=8$. Индекс чвора из којег ће се гранање вршити на горњем нивоу је одређено формулом која користи најбитније битове компоненте црвене, зелене и плаве боје, на пример 4r + 2g + b. Следећи нижи ниво користи следећи бит по тежини, и тако даље. Битови мање тежине се некад занемарују да би се смањила величина стабла.

Алгоритам је веома меморијски ефикасан зато што се величина стабла може ограничити. Најнижи нивои окталног стабла се састоје од листова који садрже податке о боји која се не налази у стаблу; ови чворови иницијално садрже појединачне битове. Ако се унесе много више боја у октално стабло, његова величина се може још смањити тражењем чвора из најнижег дела (чвор који није лист) и налажењем просека његових битова и битова листова и на тај начин одсецањем делова стабла. Након завршеног бирања узорка, претраживањем свих путева од корена до листова ће као резултат дати потребан број боја.

Литература

• Шаблон:Cite book

Спољашње везе

• Дневник Microsoft-а о квантизацији окталних стабала
• Квантизација боја користећи октална стабла
• Преглед квантизације боја користећи октална стабла
• Паралелна имплементација генерацијског алгоритма помоћу окталних стабала, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE дигитална библиотека
• C++ имплементација (GPL лиценца) Шаблон:Wayback
• Паралелно октално стабло за апликације са коначним елементима Шаблон:Wayback
• Коцка 2: Sauerbraten - игрица писана у Cube 2 покретачу игара (покретач који интензивно користи октална стабла)
• Ogre - тродимензиони објектно оријентисани покретач игара са менаџером сцена имплентираним помоћу окталних стабала (MIT лиценца)
• Dendro: паралелна мултимрежа за мрежу окталних стабала (MPI/C++ имплементација)