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[modifica | modifica wikitesto]
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[modifica | modifica wikitesto]
- 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[modifica | modifica wikitesto]
- ^ (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[modifica | modifica wikitesto]
- 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[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Albero ottale
Collegamenti esterni[modifica | modifica wikitesto]
- 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.
