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

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

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

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

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

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

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

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

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

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

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

Референце[уреди | уреди извор]

^ Meagher, Donald (октобар 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).
^ Meagher, Donald. „High-speed image generation of complex solid objects using octree encoding”. USPO. Приступљено 20. 9. 2012.
^ Luebke, David P. (2003). Level of detail for 3D graphics. Morgan Kaufmann Publishers. ISBN 978-1-55860-838-2. OCLC 928694719.
^ Elseberg, Jan, et al. "Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration." Journal of Software Engineering for Robotics 3.1 (2012): 2-12.
^ „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.” (PDF). Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 18. 04. 2014.
^ V. Drevelle, L. Jaulin and B. Zerr, Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings, NOLCOS 2013.

Литература[уреди | уреди извор]

Luebke, David P. (2003). Level of detail for 3D graphics. Morgan Kaufmann Publishers. ISBN 978-1-55860-838-2. OCLC 928694719.

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

[1] Meagher, Donald (октобар 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] Luebke, David P. (2003). Level of detail for 3D graphics. Morgan Kaufmann Publishers. ISBN 978-1-55860-838-2. OCLC 928694719.

[4] Elseberg, Jan, et al. "Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration." Journal of Software Engineering for Robotics 3.1 (2012): 2-12.

[5] „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.” (PDF). Архивирано из оригинала (PDF) 03. 03. 2016. г. Приступљено 18. 04. 2014.

[6] V. Drevelle, L. Jaulin and B. Zerr, Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings, NOLCOS 2013.

[1]

[2]

[3]

[4]

[5]

[6]