Octree

Un octree (dal latino octo 'otto' e dall'inglese albero 'albero' ) è una struttura di dati in informatica . Un octree è un albero radicato i cui nodi hanno ciascuno otto discendenti diretti o nessun discendente.

Gli Octrees sono utilizzati principalmente in computer grafica per suddividere gerarchicamente insiemi di dati tridimensionali. La radice rappresenta tutti i dati, ogni altro nodo rappresenta un ottante dei dati del suo diretto predecessore. Questo li rende adatti per l'attuazione della strategia divide et impera .

Gli octree possono essere visti come estensioni di alberi binari e quadtree : gli alberi binari suddividono i dati unidimensionali, i quadtree bidimensionali e gli octree tridimensionali; Occasionalmente, una generalizzazione a dati di qualsiasi dimensione è chiamata N-Tree . Un'altra versione più generalizzata, dove le dimensioni non sono fisse, è il B-tree .

utilizzo

Schema di un polpo. A sinistra la suddivisione del volume cubico, a destra l'octree risultante.

L'esempio seguente illustra l'uso più comune di un octree, ovvero per la struttura uniforme di uno spazio dati a forma di cubo: La radice sta per l'intero cubo. Il cubo è diviso in otto cubi più piccoli - gli ottanti - e ogni successore della radice rappresenta uno di essi. Ciascuno di questi cubetti più piccoli viene a sua volta tagliato in otto cubetti ancora più piccoli, e così via. La suddivisione di un cubo parziale termina quando non è possibile o non è necessaria un'ulteriore divisione.

Il volume originale non deve essere a forma di cubo, ma può anche essere generalmente cuboide. È anche possibile dividere i volumi in parti disuguali. Di norma, nei nodi vengono memorizzate ulteriori informazioni sui nodi subordinati. Quindi contiene z. Ad esempio, ogni nodo della forma speciale min-max-octree ha il minimo e il massimo del seguente sottoalbero, che consente ricerche efficienti.

Ulteriori campi di applicazione

Le aree generali di applicazione per i polpi sono:

• Rappresentazione dell'immagine
• Indicizzazione spaziale (es. nei sistemi informativi geografici )
• Raggruppamento di particelle in dinamica molecolare / simulazioni DEM
• Rimozione della superficie nascosta dei dati del terreno
• Rilevamento delle collisioni nei giochi per computer 3D
• Splatting gerarchico
• Risoluzione adattiva di equazioni differenziali, ad es. B. corpi deformabili
• Stima dello stato

Forme speciali

Vuoto-Non-Vuoto-Octree

Il valore empty o non-empty è memorizzato in ogni nodo in un octree vuoto-non vuoto . Vuoto indica che il volume di dati rappresentato dal nodo non contiene dati che valga l'elaborazione; non vuoto indica di conseguenza che il volume di dati associato deve essere elaborato. Normalmente il vuoto è anche il criterio di terminazione della suddivisione; Poiché il volume di dati associato non contiene più informazioni interessanti, non vale la pena suddividerlo ulteriormente.

Min-Max-Octree

Schema di un octree min-max. Ogni nodo contiene il minimo (in alto) e il massimo (in basso) del suo sottoalbero. Quando si cerca il valore 3, devono essere cercati solo i volumi di dati dei nodi contrassegnati in giallo.

Il minimo e il massimo del sottoalbero del nodo sono memorizzati in un min-max-octree in ogni nodo. Min-Max-Octrees sono quindi adatti per ricerche efficienti basate sull'esempio degli alberi binari. Il sottoalbero di un nodo viene cercato solo se il valore cercato è compreso tra il minimo e il massimo del nodo. In questo modo, parti dell'albero possono essere tralasciate e la ricerca può essere accelerata.

Per il caso particolare che il minimo e il massimo siano gli stessi in un nodo, la ricerca nel sottoalbero può anche essere omessa, perché l'intero sottoalbero del nodo contiene il valore che stai cercando. Normalmente, il caso di minimo uguale a massimo è anche il criterio di terminazione per la suddivisione, cioè il volume di dati associato non viene ulteriormente suddiviso.

Ad esempio, gli octree min-max vengono utilizzati nella grafica del volume per accelerare l' algoritmo del cubo in marcia . Qui vengono cercati tutti i sottocubi dell'octree che contengono un dato valore di soglia. Questo valore di soglia è una densità del materiale per la quale deve essere estratta un'isosuperficie dai dati voxel.

Campi tensoriali

Da un punto di vista matematico, gli octree sono particolarmente adatti per strutturare campi tensoriali . Una griglia voxel con valori grigi, ad esempio, è un campo tensoriale di ordine zero come campo scalare , una griglia voxel con tre valori di colore secondo lo schema RGB e un componente alfa è un campo tensoriale di primo ordine come campo vettoriale .

link internet

Evidenze individuali

1. ↑ Martin Seiler et al., A Threefold Representation for the Adaptive Simulation of Embedded Deformable Objects in Contact , Journal of WSCG, Pilsen, Repubblica Ceca, febbraio 2010.
2. ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edimburgo, Regno Unito, luglio 2010. (PDF; 3.2 MB)