Albero ottale

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
A sinistra: suddivisione ricorsiva di un cubo in ottanti. A destra: l'albero ottale corrispondente.

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.

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]

  1. ^ (EN) High-speed image generation of complex solid objects using octree encoding, su Google Patents. URL consultato il 22 agosto 2023.
  2. ^ David P. Luebke, Level of Detail for 3D Graphics, Morgan Kaufmann, 2003, ISBN 978-1-55860-838-2.
  3. ^ (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.
  4. ^ (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.
  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), su isas.uka.de. URL consultato il 12 gennaio 2022 (archiviato dall'url originale il 3 marzo 2016).
  6. ^ 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]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica