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".
Usi comuni Livello di dettaglio nel rendering nella computer grafica 3D Indicizzazione spaziale Nearest neighbor search Journal of Software Engineering for Robotics 3.1 (2012): 2-12. Rilevamento di collisioni efficiente in tre dimensioni Determinazione della superficie nascosta Fast multipole method Griglie non strutturate Metodo degli elementi finiti Sparse voxel octree State estimation Set estimation
Note
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
Collegamenti esterni
Categoria:Alberi (strutture dati)