Un octree è una struttura ad albero digitale utilizzata per creare creazioni tridimensionali (3D) e poligonali, principalmente per l’industria dei giochi. Nella struttura octree, ogni nodo interno non ha figli o otto figli – niente in mezzo – e ogni nodo figlio è in grado di contenere informazioni sul colore per il profilo colore rosso-blu-verde (RGB). L’intera struttura inizia come un cubo e i cubi interni vuoti vengono utilizzati per le informazioni sulle collisioni. Questa struttura è molto efficiente in termini di memoria, perché in ogni figlio è contenuta una quantità relativamente piccola di dati e l’albero può avere dimensioni limitate.
Quando un modello è realizzato per un videogioco, deve avere informazioni sulla trama e sul colore e deve essere in grado di entrare in collisione con altri modelli. Una delle strutture utilizzate in questo settore è il polpo. A volte chiamato albero di ottobre, questo nome indica l’importanza del numero otto in questa struttura ad albero. Come le strutture ad albero make, l’octree ha nodi padre e figlio. A differenza di altri alberi, c’è poca varietà nel numero di nodi figli che possono essere creati dal genitore.
Ogni genitore può includere otto nodi o nessuno. Entrambi i tipi di cubo sono importanti nella creazione di un modello completamente renderizzato. I cubi più intensivi sono quelli con otto nodi. Ogni nodo interno include informazioni sul colore e sulla trama, quindi il modello può avere un aspetto complesso. Ad esempio, se il modello è un albero, ciascuno dei nodi interni deve includere un colore marrone per il tronco e informazioni sull’ombreggiatura per creare una trama realistica.
Mentre i cubi con otto nodi sono importanti per un octree, i cubi vuoti sono altrettanto importanti. L’intera struttura inizia come un grande cubo vuoto, che altri cubi più piccoli possono abitare. Questo cubo, insieme ad altri cubi vuoti, viene utilizzato principalmente per le informazioni sulle collisioni. Ad esempio, se un modello urta questo modello, i cubi vuoti diranno al modello che non può avanzare, perché crea una collisione.
La creazione di un modello adeguato con un octree è impegnativa e contiene molte informazioni, ma la struttura stessa utilizza la memoria in modo molto efficiente. Una ragione per questo è che, mentre c’è molta codifica, le informazioni sono solo informazioni sul colore e sulla trama e, quindi, piuttosto piccole. Un’altra ragione è che l’albero ha diversi livelli che contengono dati non necessari e, se tagliati, la memoria può essere ulteriormente ridotta.