Oktalno stablo

Oktalna stabla su stabla kod kojih svaki unutrašnji čvor ima tačno 8 dece. Oktalna stabla se najčešće koriste za rekurzivno deljenje trodimenzionog prostora na oktante, kao i u trodimenzionalnoj računarskoj grafici i trodimenzionim pokretačima igara.

Oktalna stabla za predstavljanje prostora uredi

Svaki čvor u oktalnom stablu deli prostor na osam oktanata. Svaki čvor čuva tačku u tri dimenzije koja predstavlja „centar“ dela koji predstavlja taj čvor. Ta tačka definiše jedan od ćoškova za svako od njegove osmoro dece. U stablima zasnovanim na matricama (MX stabla), ova tačka je implicitno centar deljenog prostora, tako da MX stabla mogu da predstavljaju samo konačan prostor, dok to ne važi ѕa ostala oktalna stabla. Primetimo da oktalna stabla nisu ista kao i K-D stabla. K-D stabla dele prostor preko jedne dimenzije i uvek su binarna, dok oktalna to rade oko tačke i uvek su oktalna. Korišćenjem pretrage u dubinu čvorovi će se pomerati, a samo potrebne površine će biti vidljive.

Istorija uredi

Korišćenje oktalnih stabala u trodimenzionalnoj računarskoj grafici je razvio Donald Meger (engl. Donald Meagher), što je opisano u izveštaju iz 1980. godine Šifrovanje oktalnih stabala: Nova tehnika reprezentacije, manipulacije i prikazivanja proizvoljnog trodimenzionog objekta računarom (engl. Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer).^[1] On poseduje patent iz 1995. sa imenom Generisanje slika kompleksnih čvrstih objekata korišćenjem šifrovanja oktalnim stablima (engl. High-speed image generation of complex solid objects using octree encoding).^[2]

Česte upotrebe oktalnih stabala uredi

Trodimenzionalna računarska grafika^[3]
Prostorno indeksiranje
Pretraživanje najbližeg suseda^[4]
Efikasno detektovanje kolizije u trodimenzionom prostoru
Detektovanje nevidljivih površina
Nestruktuirana mreža
Analiza konačnog elementa
Spars Vokselovo oktalno stablo
Procena položaja^[5]
Procena seta^[6]

Upotreba u kvantifikovanju boja uredi

Algoritam za kvantifikovanje boja pomoću oktalnih stabala, koga su izmislili Gervauc (engl. Gervautz) i Purgatofer (engl. Purgathofer) 1988. godine, šifruje podatke o boji slike kao oktalno stablo i do devet nivoa duboko. Koriste se oktalna stabla zato što postoje tri komponente boja u RGB sistemu, a $2^{3}=8$ . Indeks čvora iz kojeg će se grananje vršiti na gornjem nivou je određeno formulom koja koristi najbitnije bitove komponente crvene, zelene i plave boje, na primer 4r + 2g + b. Sledeći niži nivo koristi sledeći bit po težini, i tako dalje. Bitovi manje težine se nekad zanemaruju da bi se smanjila veličina stabla.

Algoritam je veoma memorijski efikasan zato što se veličina stabla može ograničiti. Najniži nivoi oktalnog stabla se sastoje od listova koji sadrže podatke o boji koja se ne nalazi u stablu; ovi čvorovi inicijalno sadrže pojedinačne bitove. Ako se unese mnogo više boja u oktalno stablo, njegova veličina se može još smanjiti traženjem čvora iz najnižeg dela (čvor koji nije list) i nalaženjem proseka njegovih bitova i bitova listova i na taj način odsecanjem delova stabla. Nakon završenog biranja uzorka, pretraživanjem svih puteva od korena do listova će kao rezultat dati potreban broj boja.

Reference uredi

^ Meagher, Donald (oktobar 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. Pristupljeno 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). Arhivirano iz originala (PDF) 03. 03. 2016. g. Pristupljeno 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.

Literatura uredi

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

Spoljašnje veze uredi

[1] Meagher, Donald (oktobar 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. Pristupljeno 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). Arhivirano iz originala (PDF) 03. 03. 2016. g. Pristupljeno 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]