Albero ottale

Un albero ottale (spesso indicato con il termine inglese octree) è una struttura di dati ad albero in cui ogni nodo interno ha esattamente otto figli. Gli alberi ottali sono spesso usati per partizionare uno spazio tridimensionale suddividendolo ricorsivamente in otto ottanti. Sono l'analogo tridimensionale degli alberi quadramentali. La parola octree deriva da oct (radice greca che significa "otto") + tree (albero in inglese). Gli alberi ottali sono spesso usati nella grafica 3D e nei motori di gioco 3D.

Storia

L'uso di alberi ottali per la computer grafica 3D è stato introdotto da Donald Meagher al Rensselaer Polytechnic Institute, e descritto in un rapporto del 1980 intitolato "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer". Donald Meagher detiene un brevetto del 1995 (con priority date 1984): "High-speed image generation of complex solid objects using octree encoding", ovvero "Generazione di immagini ad alta velocità di oggetti solidi complessi utilizzando la codifica octree".^[1]

Usi comuni

Livello di dettaglio nel rendering nella computer grafica 3D ^[2]
Indicizzazione spaziale
Nearest neighbor search ^[3]
Rilevamento di collisioni efficiente in tre dimensioni
Determinazione della superficie nascosta
Fast multipole method
Griglie non strutturate
Metodo degli elementi finiti
Sparse voxel octree ^[4]
State estimation ^[5]
Set estimation ^[6]

Note

^ (EN) High-speed image generation of complex solid objects using octree encoding, su Google Patents. URL consultato il 22 agosto 2023.
^ David P. Luebke, Level of Detail for 3D Graphics, Morgan Kaufmann, 2003, ISBN 978-1-55860-838-2.
^ (EN) Jan Elseberg, Stéphane Magnenat, Roland Siegwart e Andreas Nüchter, Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration (PDF), su researchgate.net, gennaio 2012. URL consultato il 22 agosto 2023 (archiviato dall'url originale il 27 novembre 2022). Journal of Software Engineering for Robotics 3.1 (2012): 2-12.
^ (EN) Tomas Akenine-Mo ̈ller, Eric Haines e Naty Hoffman, Real-Time Rendering, Fourth Edition, CRC Press, 6 agosto 2018, ISBN 978-1-351-81615-1.
^ 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), su isas.uka.de. URL consultato il 12 gennaio 2022 (archiviato dall'url originale il 3 marzo 2016).
^ V. Drevelle, L. Jaulin and B. Zerr, Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings, NOLCOS 2013. (PDF).

Voci correlate

Partizionamento dello spazio binario
Cube 2: Sauerbraten, un motore di gioco 3D in cui la geometria è quasi interamente basata sugli alberi ottali
id Tech 6 è un motore di gioco 3D che utilizza voxel archiviati in alberi ottali
Irrlicht Engine, supporta i nodi della scena basati su alberi ottali
OGRE, ha un'implementazione del gestore della scena basato sugli alberi ottali
Voxel
Albero quadramentale

Altri progetti

Wikimedia Commons

Wikimedia Commons contiene immagini o altri file su Albero ottale

Collegamenti esterni

Octree Quantization in Microsoft Systems Journal, su microsoft.com. URL consultato il 12 gennaio 2022 (archiviato dall'url originale il 5 giugno 2014).
(EN) Quantizzazione del colore usando octree in Dr. Dobb's, su ddj.com.
(EN) Panoramica sulla quantizzazione del colore tramite alberi binari, su web.cs.wpi.edu.
Parallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library, su ieeexplore.ieee.org.
Parallel Octrees for Finite Element Applications (PDF), su sc07.supercomputing.org (archiviato dall'url originale il 3 marzo 2016).
Video: Use of an octree in state estimation, su youtube.com.