Kas yra Octree?

Oktras yra skaitmeninė medžio struktūra, naudojama trimačiams (3D) ir daugiakampiams kūriniams kurti, dažniausiai žaidimų pramonei. Oktrinėje struktūroje kiekvienas vidinis mazgas neturi vaikų arba aštuonių vaikų – nieko tarp jų – ir kiekvienas antrinis mazgas gali saugoti raudonos-mėlynos-žalios (RGB) spalvų profilio spalvų informaciją. Visa struktūra prasideda kaip vienas kubas, o tušti vidiniai kubai naudojami informacijai apie susidūrimą. Ši struktūra labai taupo atmintį, nes kiekviename vaike yra santykinai mažas duomenų kiekis, o medžio dydis gali būti ribotas.

Kai modelis yra sukurtas vaizdo žaidimui, jis turi turėti tekstūros ir spalvų informaciją ir turėti galimybę susidurti su kitais modeliais. Viena iš šioje pramonėje naudojamų struktūrų yra oktras. Kartais vadinamas okto medžiu, šis pavadinimas reiškia aštuonių skaičių šioje medžio struktūroje. Kaip ir medžio struktūros, oktre yra pirminiai ir antriniai mazgai. Skirtingai nuo kitų medžių, labai mažai skiriasi tai, kiek vaikų mazgų galima padaryti iš tėvų.

Kiekvienas iš tėvų gali turėti aštuonis mazgus arba nė vieno. Abu kubo tipai yra svarbūs kuriant visiškai pateiktą modelį. Intensyviausi kubai yra tie, kuriuose yra aštuoni mazgai. Kiekviename vidiniame mazge yra informacijos apie spalvą ir tekstūrą, todėl modelis gali atrodyti sudėtingai. Pavyzdžiui, jei modelis yra medis, kiekviename vidiniame mazge turi būti ruda kamieno spalva ir šešėlinė informacija, kad būtų sukurta tikroviška tekstūra.

Nors kubeliai su aštuoniais mazgais yra svarbūs oktrei, tušti kubeliai yra tokie pat svarbūs. Visa struktūra prasideda kaip vienas didelis tuščias kubas, kuriame gali gyventi kiti mažesni kubeliai. Šis kubas kartu su kitais tuščiais kubeliais pirmiausia naudojamas informacijai apie susidūrimą. Pavyzdžiui, jei vienas modelis atsitrenks į šį modelį, tušti kubai modeliui praneš, kad jis negali judėti pirmyn, nes sukelia susidūrimą.

Tinkamo modelio su oktre kūrimas yra intensyvus, į jį patenka daug informacijos, tačiau pati struktūra labai efektyviai naudoja atmintį. Viena iš priežasčių yra ta, kad nors kodavimo yra daug, informacija yra tik spalvos ir tekstūros informacija, todėl ji yra gana maža. Kita priežastis yra ta, kad medis turi skirtingus lygius, kuriuose saugomi nereikalingi duomenys, o apkarpius atmintį galima dar labiau sumažinti.