Octree
Un octree è una struttura dati ad albero in cui ogni nodo può avere fino a otto figli. Gli octrees vengono spesso utilizzati per partizionare uno spazio tridimensionale suddividendolo ricorsivamente in otto ottanti.
Alcuni usi comuni degli octrees:
- indicizzazione spaziale
- efficiente rilevamento delle collisioni in 3D
- eliminando gli oggetti fuori dal cono di vista come parte di un rendering 3D
- l' osservatore di stato .
Gli octrees sono l'analogia tridimensionale dei quadtrees . Il nome è formato da octo ( οκτώ "otto", in greco) e albero ("albero", in inglese) ed è scritto octree (con una sola "t"). Ogni nodo di un ottree suddivide lo spazio che rappresenta in otto sottospazi (gli ottanti).
Nel caso di un ottree di tipo “point region” (PR), il nodo memorizza esplicitamente un punto tridimensionale che è il “centro” della suddivisione per questo nodo; il punto definisce quindi uno degli angoli di ciascuno degli otto bambini. Il nodo radice di un octree di tipo PR può rappresentare uno spazio infinito.
In un ottree di tipo "MX", il punto di suddivisione è implicitamente il centro dello spazio che il nodo rappresenta. Il nodo radice di un ottree di tipo MX deve rappresentare uno spazio finito in modo che i centri impliciti dei nodi siano ben definiti.
Applicazione per la quantizzazione del colore
L'algoritmo di quantizzazione del colore octree (in) , inventato da Gervautz e Pergathofer nel 1988, codifica i dati del colore di un'immagine come qu'octree fino a nove livelli di profondità. Gli octrees vengono utilizzati perché e ci sono tre componenti di colore nel sistema RGB .
L'indice del nodo che si estende dal livello del soffitto è determinato da una formula che utilizza i bit più significativi dei componenti rosso, verde e blu, ad esempio 4r + 2g + b. Il livello inferiore successivo utilizza i seguenti significati di bit e così via. I bit meno significativi a volte vengono ignorati per ridurre le dimensioni dell'albero.
L'algoritmo è altamente efficiente dal punto di vista del consumo di memoria poiché limita la dimensione dell'albero. Il livello del pavimento dell'ottree è costituito da nodi terminali che accumulano dati di colore non rappresentati nell'albero. Questi nodi contengono inizialmente bit singoli. Se si immettono molti più colori della tavolozza rispetto alla quantità desiderata, la sua dimensione può essere ridotta continuamente guardando oltre un nodo del pavimento e calcolando la media dei suoi bit in un nodo terminale, eliminando così varie parti dell'albero.
Terminata la fase di campionamento, otterremo approssimativamente il numero di colori richiesto percorrendo tutti i possibili percorsi dell'albero partendo dal suo nodo radice fino ai suoi nodi terminali tenendo conto, di passaggio, dei diversi bit.
Note e riferimenti
- (in) Henning Eberhardt Vesa Klumpp e Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation in Proceedings of the 13th International Conference on Information Fusion , Edinburgh , July 2010
- (fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Octree " ( vedere l'elenco degli autori ) .