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

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

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

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

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

Историја[уреди]

Коришћење окталних стабала у тродимензионалној рачунарској графици је развио Доналд Мегер (енгл. Donald Meagher), описано у извештају из 1980. године: Шифровање окталних стабала: Нова техника репрезентације, манипулације и приказивања произвољног тродимензионог објекта рачунаром[1] (енгл. Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer). Он поседује патент из 1995. са именом Генерисање слика комплексних чврстих објеката коришћењем шифровања окталним стаблима[2] (енгл. High-speed image generation of complex solid objects using octree encoding).

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

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

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

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

Референце[уреди]

  1. ^ Meagher, Donald (October 1980). „Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer“. Rensselaer Polytechnic Institute (Technical Report IPL-TR-80-111). 
  2. ^ Meagher, Donald. „High-speed image generation of complex solid objects using octree encoding“. USPO Приступљено 20. 9. 2012.. 
  3. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.
  4. ^ V. Drevelle, L. Jaulin and B. Zerr, Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings, NOLCOS 2013.

Спољашње везе[уреди]