Kaptam pár érdeklődést, hogy mégis mi is az az octree, illetve a quadtree? (Emailt még mindig nem küldött senki, pedig ott a címünk!)

Végül beláttam, hogy egyáltalán nem egyértelmű, hogy mi is ez a két fogalom, illetve, ezzel együtt kitérek arra is (szerintem legalábbis) érdekes témára, miszerint hogyan is néz ki az optimalizálás  (bizonyos mértékig, persze, mielőtt Gizmo bántalmazna).

Tehát, elsőnek is, egy kis belátás a kulisszák mögé, vagyis hogyan jelenít meg a számítógép (vagyis a videokártya) bármiféle képet.

Informatikában, és grafikában a legalapvetőbb egység (megjelenítés terén) a háromszög, vagyis, ahogy hívni szokás, a poligon. Minden, amit csak látsz a monitoron, poligonokból épül fel, tehát háromszögekből. Miért jó ez, miért éppen háromszög? Erre elég egyszerű a válasz: egy háromszög MINDIG egy síkot határoz meg, tehát olyan háromszöget nem fogsz találni, ami esetleg púpos lenne, így tökéletes a színezésre, illetve a textúrák megjelenítésére. Illetve, háromszögből szinte mindent ki lehet rakni. Egyedüli kivétel a kör, illetve a körnek az elemei, de kellő mennyiségű háromszög felhasználásával nagyon szépen lehet közelíteni a kört is.

Remélem, ez érthető, de legalábbis elképzelhető volt, haladjunk tovább. Hogyan mondjuk meg a gépnek, hova akarunk háromszöget?

Ehhez első lépésként készítünk egy adathalmazt (leggyakrabban egy tömböt) ami meghatározza a háromszög pontjait a 3D térben. (Ezek x,y,z tengelyen meghatározott pontok, vagyis Vector3, egészen pontosan 3 darab). Eddig semmi bonyolult nem történik (nyugi, későbbiekben sem fog, maximum annak tűnik). Na igen, de mégis hogyan lesz 3 darab pontból egy háromszög?

Ha megvannak a háromszögeink, akkor van több fajta lehetőségünk is, hogy ezekkel a pontokkal mit akarunk kezdeni. Ügyebár a gépünk számára egyelőre csak átadunk számokat, hármas csoportokban. A legegyszerűbb technika az, ha azt mondjuk a gépnek, hogy ezek a pontok egy lista elemei: tehát hármas csoportokban alkotják a háromszögeket. Ekkor fogja a gép az első három pontot, rajzol belőle egy háromszöget, fogja a következő hármat, újabb háromszög... És így tovább, amíg el nem fogy a lista. Miért jó ez? Azért jó, mert egyszerű. Kevés memóriaigénye van, és még kevesebb számítás igény.

S miért rossz? Mert sok memóriát igényel olyan testek esetében, ahol egy pont több háromszöget is meghatároz. (Képzeljünk el egy kockát, amit háromszögekből állítunk fel! Minden csúcspont legalább hat háromszögben lesz benne, tehát 6x annyi adat kell, mint amennyi logikusan szükséges lenne.)

Mi erre a megoldás? A következő technika: az indexelés. Ami eléggé egyszerű szintén: meghatározod az előző példában írt kockát: meghatározzuk a csúcspontokat, EGYSZER mindegyiket. Tehát van 8 darab pontunk. Ez sokkal jobb, mint az előző 48 pont. Na igen, de honnan tudja a gép, hogy melyik háromszög melyik pontból áll? Erre valóak az indexek (amíg natúr int típusú számok egy tömbben) amelyek meghatározzák, hogy az adott pontokat felhasználva hogyan épülnek fel a háromszögek. Tehát, az első felépül a 1,3,6 pontból. Ezzel szépen levehetjük a rendszerigényt, és sokkal kevesebb adatból elérhetjük ugyanazt, bár ez csak akkor működik, ha sok pont érintkezik, különben fölösleges.

Ezenkívül még van pár technika, de a mi dolgunk szempontjából elég lesz ez a kettő, a többi végülis ennek a különböző variációja.

Oké, tehát megvannak a pontjaink, a videokártya azt is tudja, hogy melyik pont hova kerül. Akkor mi a gondom már megint?

Az a probléma, hogy a képernyő 2 dimenziós. Nekünk meg háromdimenziós pontjaink vannak, tehát ezeket le kell képezni 2D felületre. Ezt a részt nem ecsetelgetném nagyon, mert ez viszont bonyolult: a lényeg az, hogy létrehozunk egy mátrixot (a mátrixok voltaképpen egy 4x4-es számtömbök, amelyek meghatározzák a transzformációkat), amivel a pontjainkat beszorozva megkapjuk, hogy azok valójában hol is vannak, illetve, hogyan torzulnak (hiszen grafikában a valóságosnak tűnő "távolság" nem több, csupán a pontok eltorzítása, kb mint amit a festők használnak, a 3D kép leképezése 2D képpé.)

Na, ezzel akkor meg is lennénk, remélem, érthető volt valamennyire :) Tehát minden, amit a képernyőn látunk (a legegyszerűbb kockától kezdve a Crysis 2 modellekig) így jelenik meg.

Na, és akkor én miért is meséltem el ezt a sok zagyvaságot, amikor a Quadtree-t kellett volna elmesélnem? Azért tettem, ugyanis a Quadtree ebbe a folyamatba illeszkedik, és nagyban segíti a gyorsaságát, illetve azt, hogy lehetséges legyen jóval nagyobb terület eltárolását, és megjelenítését, amit egyébként a gép képességei lehetővé tesznek.

Tehát, a Quadtree dióhéjban: egy eljárás, ami fog egy területet, és négy részre osztja. Majd fogja a részeket, és ezeket is négy részre osztja. Ezt az eljárást addig folytatja, amíg el nem éri azt a minimum értéket, aminél kisebb node (vagyis faág ez esetben) már nem lehet.

És akkor egy kis technikai infó megint: amikor egy textúrát rá akarunk feszíteni egy háromszög csoportra, akkor belefutunk egy olyan problémába, hogy szegény gépnek egyszerre csak 1 textúrát tudunk átadni (Vagyis különböző eszközökkel meg lehet oldani, hogy többet, csak akkor a hívás egyre bonyolultabb lesz, arról nem is beszélve, hogy minden lehetséges számot külön-külön le kell programozni, és ha esetleg növelném, akkor azt is újra...). Tehát, van egy rakat háromszögünk, és 1 darab textúránk. Ez néhány esetben elég, a játékok legnagyobb részében viszont nem. Mi erre a megoldás? Fogjuk, és nem egy adagban küldjük le a háromszögeket a videokártyának, hanem darabokban, vagyis leküldjünk az első 12-tőt (erre kerül az 'A' textúra) majd a másodikat, erre megy a 'B' és így tovább.

Ez nagyon egyszerűnek hangzik, akkor miért nem ezt használom, a további szövegelés helyett? Azért, mert itt is két lehetőség van: vagy egyesével elküldöm az adott textúrához tartozó falat, aztán a következőt, majd megint a következőt... Ez túl sokáig tartana, tehát kis pályák esetén még kivitelezhető, de nagyobb méretekben (10+ textúra, több tízezer poligon) esetében rendkívül nagy teljesítménybeli romlás következik be.

Illetve, a videokártya azt szereti, ha kap egy nagy adag feladatot, és azon csámcsoghat, békében nyugodtan (és félelmetesen gyorsan). Viszont nyűgös lesz, ha folyton kicsi adagokat adunk neki, és akkor elkezd lassan dolgozni, hiszen a feladat váltás számára sokáig tart. (Tehát, a fő különbség a CPU és GPU között: a CPU általános feladatokat végez, ezeket viszonylag "lassan", viszont rendkívül gyorsan képes feladatot váltani, míg a GPU specializált feladatot lát el, ezeket félelmetesen gyorsan megoldja, viszont elképesztően lassan vált a feladatok között).

Vagy pedig, írok egy algoritmust, ami elsőnek összeszedegeti a falakat, amik azonos textúrát használnak, majd ezeket egy nagyobb csomagban küldöm le. Na, ez a technika kellemes kompromisszum a lehetőségek között: kellőképpen gyors, és nem terheli a rendszer fölöslegesen. Tehát meg is van a megoldás!

Csak éppen megint nem ilyen egyszerű. Ugyanis ez a kereső algoritmus nagy területek esetében túl sok ideig tart, és már megint ugyanott vagyunk, csak most a kutatás emészti fel a rendszer és processzor időt. Hát, akkor mi a megoldás?

Hát az, ami miatt elkezdtem ez az egészet, vagyis a Quadtree. Írtam, hogy négy részre osztjuk a terepet, négy fő ágra. Amikor elkezdődik a kutatás, elsőnek megnézzük, hogy ebből a négy fő ágból mit lát a kamera. Tehát, legrosszabb esetben kapásból felére redukáltuk a számításigényt, ami több milliárd művelet esetén rendkívül tetemes nyereség, de inkább mondhatom azt, hogy a negyedére (a leggyakoribb esetben.). Igen ám, de a Quadtree ágaival is elvégezzük, egyre mélyebbre haladva, folyton megkeresve azokat a háromszögeket, amiket éppen aktuálisan használunk, tehát csak és kizárólag azokkal a területekkel foglalkozunk, amik beleesnek a kamera látószögébe.

Képletesen szólva: képzeljük el, hogy az adatunk egy valódi fa! Na, most közelítsünk rá a kameránkkal erre a fára. Egészen addig, amíg csak két levelet látunk. Quadtree nélkül, hiába nem látjuk a fa többi részét, csak a két levelet, azt is tudnunk kéne, hol van, és hogyan néz ki a többi levél. Quadtree-vel viszont csak és kizárólag azt a két levelet fogjuk látni, és csak azzal kell foglalkozni, ami a látószögünkben van.

Így a szükséges számításigényt nem csak, hogy a negyedére, de akár 400-500%-al is csökkenthetjük, ami csodás eredmény, hiszen így már akármekkora (a memória kapacitásáig, vagy, még nagyobb pálya esetén a merevlemez kapacitásáig) pályát megjeleníthetünk!

Tehát, ez volna a Quadtree. Az octree, amit eredetileg használni akartam, ugyanez, csak 3D-s világban, tehát alulra-fölülre is feloszlik, vagyis 8 darab területre osztja fel a pályát. Mint probléma, rendkívül érdekes, és mint eljárás, elképesztően zseniális. A quadtree nélkül jóformán egyetlen játék sem lenne képes akkora területet megjeleníteni, amiket ma látunk a játékokban. Persze, ez csak a fő, nyers technika, ezt még milliónyiképpen lehet finomítani, állítani. De már így is túlszaladtam a kereten.

Köszönöm a figyelmet, remélem, annyira érdekes volt, mint amennyire engem érdekel :D