Co je Octree?
Octree je digitální stromová struktura slouží k vytvoření tří-dimenzionální (3D) a polygonální výtvory, většinou pro herní průmysl. Ve struktuře oktree nemá každý vnitřní uzel žádné děti ani osm dětí - mezi nimi nic - a každý podřízený uzel je schopen uchovávat barevné informace pro červeno-modro-zelenou barvu (RGB). Celá struktura začíná jako jedna krychle a pro informace o kolizi se používají prázdné vnitřní krychle. Tato struktura je velmi efektivní z hlediska paměti, protože v každém dítěti je uloženo relativně malé množství dat a velikost stromu může být omezena.
Když je model vytvořen pro videohru, musí mít informace o struktuře a barvě a musí být schopen srážet se s jinými modely. Jednou ze struktur používaných v tomto odvětví je octree. Tento název, který se někdy nazývá osmičkový strom, označuje význam čísla osm v této stromové struktuře. Stejně jako struktury stromových struktur má i oktree nadřazené a podřízené uzly. Na rozdíl od jiných stromů existuje velmi malá rozmanitost v tom, kolik dětských uzlů lze vytvořit z rodiče.
Každý rodič může obsahovat osm uzlů nebo žádný. Oba typy krychlí jsou důležité při vytváření plně vykresleného modelu. Nejintenzivnější jsou kostky s osmi uzly. Každý vnitřní uzel obsahuje informace o barvě a struktuře, takže model může mít složitý vzhled. Například v případě, že model je strom, každý z vnitřních uzlů musí obsahovat hnědou barvu do kufru a informace o stínování vytvořit realistické textury.
Zatímco kostky s osmi uzly jsou důležité pro octree, prázdné kostky jsou stejně důležité. Celá struktura začíná jako jedna velká prázdná kostka, kterou mohou obývat další menší kostky. Tato krychle se spolu s dalšími prázdnými kostkami používá především pro informace o kolizi. Například, jestliže jeden model narazí do tohoto modelu, prázdné kostky řekne model, který nemůže postoupit, protože vytváří kolizi.
Vytvoření správného modelu s octree je intenzivní, a velké množství informací jde do něj, ale samotná konstrukce velmi efektivně využívá paměť. Jedním z důvodů je to, že i když tam je hodně kódování, informace je jen barvu a strukturu informací, a tudíž poměrně malý. Dalším důvodem je, že strom má různé úrovně, které přidržují nepotřebných dat, a pokud prořezané, paměť může být zmenšen ještě víc.