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.

A sinistra: suddivisione ricorsiva di un cubo in ottanti. A destra: l'albero ottale corrispondente.

StoriaModifica

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 comuniModifica

NoteModifica

Voci correlateModifica

Collegamenti esterniModifica

  Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica