Hvad er et Octree?
En octree er en digital træstruktur, der bruges til at skabe tredimensionelle (3D) og polygonale kreationer, mest til spilindustrien. I octree-strukturen har hver intern knude enten ingen børn eller otte børn - intet imellem - og hver barneknud er i stand til at indeholde farveinformation for den rødblå-grønne (RGB) farveprofil. Hele strukturen starter som en terning, og tomme interne terninger bruges til kollisionsinformation. Denne struktur er meget hukommelseseffektiv, fordi der findes en relativt lille mængde data i hvert barn, og træet kan begrænses i størrelse.
Når en model er lavet til et videospil, skal den have information om tekstur og farve og skal være i stand til at kollidere med andre modeller. En af de strukturer, der bruges i denne branche, er octree. Nogle gange kaldes et oct træ, dette navn betyder betydningen af tallet otte i denne træstruktur. Som at lave træstrukturer, har octree forældre og børn knudepunkter. I modsætning til andre træer er der meget lidt variation i, hvor mange børneknuder der kan laves fra forælderen.
Hver forælder kan indeholde enten otte noder eller ingen. Begge terningstyper er vigtige for at skabe en fuldstændig gengivet model. De mest intensive terninger er dem med otte knudepunkter. Hver intern knude inkluderer information om farve og tekstur, så modellen kan have et kompliceret udseende. For eksempel, hvis modellen er et træ, skal hver af de interne knudepunkter indeholde en brun farve til bagagerummet og skraveringsinformation for at skabe en realistisk struktur.
Mens terningerne med otte knudepunkter er vigtige for en octree, er de tomme terninger lige så vigtige. Hele strukturen starter som en stor tom terning, som andre mindre terninger kan bo i. Denne terning sammen med andre tomme terninger bruges primært til kollisionsinformation. For eksempel, hvis en model støder på denne model, fortæller de tomme terninger modellen, at den ikke kan gå videre, fordi den skaber en kollision.
Det er intensivt at oprette en ordentlig model med en octree, og meget information går ind i den, men selve strukturen bruger hukommelsen meget effektivt. En af grundene hertil er, at selvom der er meget kodning, er informationen bare information om farve og tekstur og dermed temmelig lille. En anden grund er, at træet har forskellige niveauer, der indeholder unødvendige data, og hvis beskæres, kan hukommelsen skaleres endnu mere.