gondolataim elsősorban játékfejlesztésről

Amióta a 1978-ban Lance Williams bemutatta a shadow mapping technikát számos továbbfejlesztési kezdeményezés látott napvilágot. Ezek közül néhány hatékonynak is bizonyult, míg a legtöbb leginkább csak elméleti jelentőségű.

De miért volt / van szükség ennek az árnyékolási módszernek a folyamatos fejlesztésére? A válasz egyszerű, mindmáig nem létezik tökéletes shadow mapping módszer vagyis olyan, amely minden jelenetben tökéletes renderelési eredményt nyújtana.

A legtöbb probléma abból ered, hogy ez a technika egy renderelés eredményeként kapott képet használ fel textúraként az árnyékok előállítására és ennek a textúrának a mérete / felbontása alapjaiban befolyásolja az ezzel a technikával elérhető minőséget (hasonlóképpen a kép "színmélysége" is befolyásoló tényező a mélységi felbontás tekintetében). Látható, hogy a shadow map főbb problémái abból erednek, hogy a felhasználása egy textúra vetítést (is) igényel! Ezt a problémát hívják perspective aliasingnak vagyis a texturának a közelre vetített része alacsony felbontásu (szögletes) míg távolodva a felbontás valamelyest javul.

Erre a problémára jelenleg két megoldást ismerek.

• Az egyik a kép felbontásának a növelése, amely azonban egy bizonyos határig lehetséges.
• A másik megoldás az adott kép optimális felhasználásán / kihasználásán alapul.

Erre a trükkre az alábbi felfedezés tesz képessé minket. A shadow mapet akkor tudjuk igazán optimálisan kihasználni, ha a megjelenített végső jeleneten az árnyékok mérete arányban van a shadow mapben tárolt árnyékok méretével. Vagyis minél távolabb van egy árnyék a kamerától annál kisebbnek látszik majd a jelenetben így elegendő kisebb méretben tárolni a shadow mapben is. Fordítva pedig, minél közelebb van valami a kamerához annál részletesebb árnyékot szeretnénk látni. Bonyolultabban fogalmazva: az a célunk, hogy a renderelt jeleneten N pixelen látszódó árnyék N-nel arányos mennyiségű texelt foglaljon el a shadow mapen ezzel csökkentve a perspective aliasingot.

Ennek a gyakorlati kivitelezése a perspective shadow mapping, a light space perspective shadow mapping, trapezoidal shadow mapping, logarithmic perspective shadow mapping, queried virtual shadow mapping, fitted virtual shadow mapping, parallel-split shadow mapping stb, melyekből (tudomásom szerint) igazán kettő vált széleskörben népszerűvé: a lispsm és a pssm.

Lássuk, hogyan nyújt a lispsm megoldást a perspective aliasingra. Egyszerűen és tömören ugy fogalmazhatnánk meg a megoldást, hogy a shadow mapen a kamerához közel eső árnyékokat "széthúzzuk" ezzel együtt a távoli árnyékokat "zsugorítjuk". Ezt a trükköt plusz egy perspektív vetítéssel éri, amely az egész technika lényegét képezi.

Ahhoz, hogy ezt a vetítést meg tudjuk tenni (elő tudjunk állítani egy vetítési mátrixot), szükségünk van egy teljes jelenet analízisre. Első nekifutásra ez kicsit félelmetesnek tűnhet. Második nekifutásra semmi mást nem jelent, csak elő kell állítanunk azon jelenet elemek listáját

• amelyek láthatók és árnyékot kapnak
• amelyek árnyékot vetnek a látható, árnyékot kapó elemekre.

Miután ezzel megvagyunk előállítjuk ezen elemek befoglaló térfogatát pontosabban elég a befoglaló test pontjait meghatározni. Itt célszerű minél nagyobb (lehető legnagyobb) pontosságra törekedni, mert a közeli árnyékok minősége ennél a lépésnél dől el(!) mivel utolsó lépésként egy perspektiv frustummal ezt a ponthalmazt fogjuk befogni. Ehhez átvisszük egy módosított fény térbe ezeket a pontokat és meghatározzuk a fénytől legtávolabbi és legközelebbi pontok távolságát. Ezen távolságok ismeretében ki tudunk számolni egy olyan virtuális poziciót, amelyből a ponthalmaz teljesen látszik.

Végezetül tehát a technika a shadow map működésén semmit nem változtat egyszerűen a vetítést teszi hatékonyabbá (akár felhasználható más textúra vetítést igénylő feladatok esetében is!). Mindössze még plusz egy mátrix transzformációt igényel vagyis gpu oldalon semmilyen változatás nem szükséges, cpu oldalon pedig némi többlet munkát bár ezen munkák egy részét mindenképp elvégezzük. A lispsm párhuzamos fényre és splot lightra is alkalmazható azonban omni fényforrásra nem! Megjegyzendő még, hogy a lispsm igen rossz eredményt produkálhat, ha nem figyelünk arra az esetre, amikor a fény vektora és nézeti vektor közel párhuzamossá válik!

Nem esett most szó sem az ún. projection aliasingról (amikor egy olyan felületre történik a vetítés, amely majdnem párhuzamos a vetítés irányával), amely szintén a textúra vetítés miatt jön létre és amelyre az itt megemlített technikák egyike sem nyújt megoldást, sem a shadow map tulajdonképpeni működéséről (depth texture, depth comparison stb).

A Quake3 bsp file-jával kapcsolatosan gondoltam írni néhány gondolatot ezekről, mivel előszeretettel használták pályaszerkesztéskor ezeket a felületeket. Eredetileg autók karosszériánának számítógépen történő tárolásához / feldolgozásához dolgozta ki Bezier 70-s évek elején. A bezier patch gyakorlatilag a b-spline 3 dimenziós kiterjesztése. Gyakorlati hasznát az adja, hogy görbült felületeket (pl. íveket és organikus elemeket) lehet vele könnyedén kezelni egy két dimenziós paramétertömb segítségével, amelyeket kontroll pontoknak hívunk. Mindössze ezek mozgatásával elérhető az egész felület módosítása.

Három alapvető elv érvényes ezekre a felületekre, hasonlóan a bezier ívekhez:

• a paramétertömb sarkait képező kontrollpontok mindig illeszkednek a felületre
• a felület folyamatos (törés nélküli)
• a felület mindig a kontroll pontok által alkotott konvex befoglaló testen belül helyezkedik el.

A legnagyobb hátránya azonban az, hogy közvetlenül(!) a mai gpukkal nem renderelhető. A legjobb megoldás ha mi magunk készítünk egy tesszelláló függvényt, amely egy ilyen felületet háromszögekkel közelít egy általunk beállított pontossági paraméter alapján. Természetesen minél nagyobb a pontosság, annál több háromszög és vertex lesz az eredmény.

A tesszelláció elve igen egyszerű: egy interpolációt vagy approximációt kell elvégezni a kontroll pontok adatai között (bizonyos terminológia az interpolációhoz a szerkesztési pontokat, míg az approximációhoz a kontroll pontokat rendeli). A pontok számától függően bi-quadratic (3x3), bi-cubic(4x4) bezier patchekről beszélhetünk (jelen példában 3x3 pontot használunk, de bármennyi kontroll pont használata lehetséges azonban ez a két eset a leggyakoribb). Ezen adatok közé tartozik többek között a pozíció is, de a műveletet elvégezhetjük textúra koordinátákra és normálokra is, amennyiben a kontroll pontok rendelkeznek velük (a normált természetesen közvetlenül a felületből is kiszámíthatjuk, de ez jóval lassabb megoldás, mint a normálok interpolálása). A tesszelláció eredménye tehát egy rács lesz legalább egy pozíció és egy vertexindex tömbbel.

A vertexindex tömb elkészítése nem igényel különösebb trükköt egyszerűen egy, rács szélességű és hosszuságú ponthalmazt kell háromszögekként indexelnünk.

A kontroll pontok approximálása ezzel szemben egy nagyobb kihívást jelentő feladat, amelyet két jól elkülöníthető algoritmusra oszhatunk fel. 

Az első, három kontroll pont közötti közelítés egy paraméterrel (tovább optimalizálható a függvény):

vec4 approximate(float t, vec4 a, vec4 b, vec4 c)
{
    float t0=1.0f - 2.0f*t + t*t; 
    float t1=2.0f*t - 2.0f*t*t;
    float t2=t*t;
    return (a*t0 + b*t1 + c*t2);
}A második függvény végzi magát a tesszellálást, amelyhez szükségünk van a kontroll pontokra és azok számára valamint arra, hogy milyen finom rácsot szeretnék végeredményül.

void tesselateBPatch(
vec4* result, int grid_width, int grid_height,
vec4 *controls, int control_width, int control_height)
{
    int size_x=control_width/2;
    int size_y=control_height/2;
    float diff_s=1.0f/grid_width;
    float diff_t=1.0f/grid_height;
    int stride=size_x*grid_width+1;
    for(int j=0;j<size_y;j++)
    {
        int patch_j=(j<size_x-1)? grid_height : grid_height+1;
        for(int i=0;i<size_x;i++)
        {
            int patch_i=(i<size_x-1)? grid_width : grid_width+1;
            int index0=2*(j*grid_width+i);
            int index1=index0+grid_width;
            int index2=index1+grid_width;
            vec4 &cp0=controls[index0++];
            vec4 &cp1=controls[index1++];
            vec4 &cp2=controls[index2++];
            vec4 &cp3=controls[index0++];
            vec4 &cp4=controls[index1++];
            vec4 &cp5=controls[index2++];
            vec4 &cp6=controls[index0++];
            vec4 &cp7=controls[index1++];
            vec4 &cp8=controls[index2++];
            vec4 *dst=result+j*grid_height*stride+ i*grid_width;
            float t=0.0f;
            for (int k=0;k<patch_j;k++,t+=diff_t)
            {
                vec4 v0=approximate(t,p0,p1,p2);
                vec4 v1=approximate(t,p3,p4,p5);
                vec4 v2=approximate(t,p6,p7,p8);
                float s=0.0f;
                for(int l=0;l<patch_i;l++,s+=diff_s)
                {
                   dst[x]=approximate(s,v0,v1,v2);
                }
                dst+=stride;
            }
        }
    }
}

A result tömbben kiszámolt vertexek a vertexindex tömbbel együtt már közvetlenül felhasználhatók rendereléshez, ütközéshez stb.

Manapság egyre kevesebb helyen használnak bezier patchet és egyéb parametrikus felületeket, helyüket lassan kiszorítja a sík felületekhez használt ún. subdivision.

Szerintem nem létezik olyan játékos, akinek az emlékei nyomokban q3 vagy q3 engine-nel készült játékkal kapcsolatos élményeket ne tartalmaznának. Joggal nevezhetjük az id software és talán a játéktörténelem egyik legsikeresebb játékának ill. engine-jének hiszen még ma is akadnak lelkes rajongók szép számmal.

A mitől vált ilyen sikeressé kérdésre mindenki megkeresheti a neki tetsző választ, de egy biztos, hogy a játék engine-nek nagy szerep jutott ebben, amelynek alappillérei a jelenet-,tér- és megjelenítési-fa. A .bsp file a legtöbb ezekhez kapcsolódó információt tárolja így hát érdemes alaposan beleásnunk magukat a részleteibe.

A .bsp fa 17-féle információt tárol valamint egy headert. Ezek nagy része grafikai (renderelési) és ütközésvizsgálathoz használt információ, a többi bsp fával kapcsolatos és játék specifikus információ.

Kezdjük ez utóbbival, mivel ez a legegyszerűbb, de a feldolgozása ennek a legkomplikáltabb lévén szöveges adatról van szó, amelyet egy script-nyelven írtak. Ennek neve entities.

A bsp fával kapcsolatos információ egy láthatósági tömb (vis_info). A file tárolja még a teret felosztó síkokat (planes), a bsp fa csomópontjait (nodes), leveleit (leaves) és a levelekhez tartozó felületek indexeit (leaf_surfaces) és a levelekhez tartozó brushok indexeit (leaf_brushes).

A grafikai adatokhoz tartoznak a vertexek (vertices), a felületek (surfaces) és a vertexindexek (indices) ill. még a modelek (model). A renderelési adatokhoz leginkább a lightmapek (lightmaps), a fényrács (lightgrid), a shaderek (shaders) és köd effektek (fogs).

Az ütközésvizsgálathoz szükséges adatok a brushes és a brushsides.

Mindenekelőtt néhány szösszenet arról, hogy mi mire való.

A shadereknek természetesen semmi közük a mai gpu shaderekhez ellenben a felületek megjelenítésére vannak hatással, mint pl. ezek tárolják a textúrákat, textura animációkat, vertex deformációt és egyéb effekteket. A köd effektek és a felületek használják ezeket viszont a bsp ezeket nem tárolja! A q3ban az árnyalás alapvetően statikus jellegű és a felületek előre elkészített árnyalási eredményét a lightmapekben tárolják a bsp file részeként, amely megegyezés szerint (ha más nem utal rá) 128*128 méretű és RGB-ben kódolja a luxeleket (mert az mindig van otthon...). Ahhoz, hogy a mozgó objektumokat megfelelően lehessen árnyalni egy fényrácsban tárolják az adott térfogatban érvényes fényteret.

A modeleket szintén nem tárolja a bsp file, hanem csak brushokat és egy bounding boxot. És hogy mi is az a brush - kissé furcsa az elnevezés hiszen ecsetet jelent miközben ütközés vizsgálathoz használják. Igazából a kettőnek csak annyi a köze egymáshoz, hogy a pályákat mintegy megrajzolják, amihez ecsetet használnak (érted...).

Tapasztalatom szerint a brushokkal ma már nem érdemes foglalkozni, hiszen manapság az ütközés vizsgálatot már egy külön fizikai engine végzi általában (persze tanulási / felfedezési célból nagyon izgalmas lehet egy ilyet implementálni).

Amiről még szó lesz az a láthatósági vizsgálat, amely ún. clustereken alapul. A bsp fa leveleit ilyenekbe szervezi a bsp compiler és a pvs-t ezek között készíti el. Ezenkívül még vannak area-k is, amelyek portálokkal vannak összekötve. Ilyen portálok általában az ajtók. A portálok használatáról azonban nem sokat tudok és azt is q3 forrásából...

Utoljára még egy fontos információ: a vertexindexek egy 4 byte-os integer tömb ill. minden egyéb referencia index is ilyen integer.

Most pedig merüljünk el az adattipusok részletes leírásában....

Elsőként a header:

struct
{
    unsigned char id[4];
    unsigned int version;
    struct
    {
        int offset;
        int length;
    }table[17];
};

az id kötelezően "IBSP", a version pedig játék függő. A 17 elemű table tárolja, hogy melyik tipusu adatot hol találjuk a fileban (a file elejétől mérve) és milyen méretű. Azt, hogy egy adatból hány darab található könnyen kiszámolhatjuk, ha a length-t elosztjuk az adott struktura méretével.

 A bsp-fához tartozó adatok:

1. A vis_info egy pvs vagyis egy meglehetősen nagy mátrix bitekből felépítve, amely azt tárolja, hogy a bsp fa egy adott levelét befoglaló clusterből mely egyéb clusterek (levelek) látszódhatnak (innen ered a neve is potentially visible set).
2. A plane egy 4 floattal leírt struktura, amely tárolja a sík normálvektorát(a,b,c) és az origótól mért távolságát(d)struct
{
    float a,b,c;
    float d;
};
3. A  node tárolja melyik sík osztja ketté és melyik 2 gyermekké osztja valamint a bounding boxát.struct
{
    int plane;
    int child_a;
    int child_b;
    int aabb_min[3];
    int aabb_max[3];
};
4. A leaf tárolja, hogy melyik cluster és portál area tartozik hozzá valamint a bounding boxát és a leafhez tartozó első surface/brush indexét és hogy hány darab surface/brush tartozik hozzá.struct
{
    int cluster;
    int area;
    int aabb_min[3];
    int aabb_max[3];
    int first_leafSurface_index;
    int num_leafSurfaces;
    int first_leafBrush_index;
    int num_leafBrushes;
};   

Grafikai adatok:

1. A vertex tárolja a 3d-s pozicióját, két, 2d-s textura koordinátát (egyik a diffúz maphez, másik a lightmaphez) egy normált és 4 byte-ot, ami egy szín RGBA komponensét jelenti.struct
{
    float position[3];
    float texcoord_diffuse[2];
    float texcoord_lightmap[2];
    float normal[3];
    unsigned char color[4];
 };

2. Talán a felület a legösszetettebb struktura, amelynek ráadásul a jelentése függ a tipusától.struct
{
    int shader_index;
    int fog_index;
    int type;
    int first_vertex;
    int num_vertex;
    int first_vertexIndex;
    int num_vertexIndex;
    int lightmap_index;
    int lightmap_corner[2];
    int lightmap_width, light_height;
    float lightmap_origin[3];
    float tangent[3];
    float bitangent[3];
    float normal[3];
    int patch_width, patch_height;
};A számunkra lényeges adatok közül az alábbi adatok egyértelműek: shader_index, lightmap_index, fog_index, type. A kavarodást a tipus fogja okozni mivel 4 féle felület tipust (legalábbis ennyiről tudok) támogat a bsp file. Ez lehet sík felület, type = 1, háromszög lista, type = 2, bezier patch, type = 3, billboard avagy flare, type = 4.
   Ezek közül az 1. és 3. eset nagyon hasonló. Mindkét esetben a bsp file vertex tömbjéből num_vertex számú különböző vertexet fogunk felhasználni (nem feltétlen megjeleníteni!) a first_vertextől kezdve. Sík felület esetében itt véget is ér a dolog hiszen num_vertex darab vertexet fogunk megjeleníteni háromszög legyezőként. 3. esetben szükségünk van még a bsp file vertex index tömbjére is, amelyből hasonlóan az előző esethez nyerhetjük ki a vertex indexeket (first_vertexIndex-től indulva num_vertexIndex-nyit) egyszerű háromszög listaként.
   Tudomásom szerint a 4. eset egy billboardolt négyzetet jelent, amit a lightmap_origin koordinátákban kell megjeleníteni.
   Utoljára hagytam a 2. típust, mert ez igényli a legtöbb átalakítást mivel ez esetben nekünk kell legenerálnunk a vertexeket is. A számoláshoz szükséges kontroll pontokat a bsp vertex tömbje tárolja, a first_vertextől kezdve.

 Végszóként még nézzük meg, hogyan is épül fel a fénytér:

struct
{
    unsigned char ambient[3];
    unsigned char diffuse[3];
    unsigned char direction[2];
};

Az itteni leírás csak az eredeti Q3 motorral készült játékok bsp file-jaihoz használható, amely azt jelenti, hogy a headerben a verziószám értéke 0x2E! Érdekesség, hogy a q3map2 alkalmazás a különböző játékok bsp file-jai között képes konvertálni.

Eye-candy vagyis hogyan tudjuk az egyszerű háromszögeket minél látványosabban megjeleníteni a képernyőn.

Nevezzük ezeket egyszerűen effekteknek, melyekből alapvetően kétféle lehet: inprocess és postprocess. A megkülönböztetés alapja az, hogy a háromszög közvetlen renderelésekor történik-e az effekt alkalmazása (inprocess) vagy a már lerenderelt, color bufferben lévő képre alkalmazzuk (postprocess) azt.

Inprocess technikák:

Elsőként tekintsük át az árnyalással kapcsolatos technikákat.

A legegyszerűbb ebből a szempontból a ma már szinte történelminek számító per-vertex árnyalás. Már itt is "extraként" emlegették a a spekulár árnyalási összetevő kiszámítását, hiszen az árnyalási egyenletet (jóval) költségesebbé teszi. Hiába nagyon régi ez az árnyalási forma nem elhanyagolható ma sem, hiszen (elméletileg) ennek használatával érhető el a legnagyobb teljesítmény valamint nincs tulzottan magas hardverigénye sem, amely lehetővé teszi, hogy az effekt használható szinte minden konfiguráción.

Az árnyalást fragmentenként is kiszámolhatjuk ebből eredően ezen technikák jóval költségesebbek. Ahhoz azonban olyan videokártya ajánlott, amiben van legalább vertex shader és "elegendő" textura unitot képes kezelni, de leginkább vertex + pixel shader kombinációja szükséges mindehhez (de pl. legelvetemültebb esetben cpuval számolhatjuk ki a fényvektorokat, texture environmenttel normalizálhatjuk a vektorokat és vehetünk skalár szorzatot belőlük, de ehhez legalább 3 textura unit szükséges és amelyik videokártya már rendelkezik ennyivel ott már várható vmilyen pixel shader is).

Miután per-fragment értékeljük ki az árnyalási egyenletet lehetőség nyílik arra is, hogy az adott felületet az árnyalás során további részletességgel gazdagítsuk. Ezt az effekt-családot hívjuk bump mappingnek, amelyben az elnevezések sokszor nem egyértelműek ill. nem egy értelemben használatosak. Három nagy csoportjuk van: tangent space bump mapping, object space bump mapping és emboss bump mapping. Ez utóbbit csak megemlítem, mert kilóg a sorból (a legolcsóbb és talán a legrégebbi bump mapping effekt, ma már alig használt, müködési és használati elve más, mint az előzőké)

Működési elvük igen egyszerű: a felület normálját avagy a fény vektort elforgatva a felületet látszólagosan egyenetlenségekkel (repedések, lyukak) tarkíthatjuk az ún. normal map segítségével. A normal mapet a height mapből, amelyet néha bump mapként is emlegetnek, állítják elő és a felület relatív magasságait tárolja.

A két módszer abban különbözik egymástól, hogy

• a tsbm, a felületre érkező fény vektorát forgatja el az un. tangent spacebe és a normal map ebben a térben tárolja a normálokat (mivel a tangent spaceben nincs értelme a negatív z-iránynak, elégséges az x,y komponenst tárolni - lásd félgömb ujraleképzés)
• az osbm, a felület normálját forgatja a model space-be és a normal map az objektum terében tárolja a normálokat

és ebből következik a nagy hátránya, hogy egy normal mapet csak egy adott modellhez lehet használni. Ezen ok miatt ma a tsbm a leginkább elterjedt (de pl. domborzat árnyalásához kitünő!!)

Természetesen ezzel a technikával az árnyalás diffúz és spekulár kompononse is kiszámítható és nagyon sok esetben - figyelembe véve a technika per-fragment voltát -létrehoznak egy un. specular mapet is (az effekt neve specular mapping), amely topológiailag megfelel a normal mapnek, de nem normálokat, hanem a felület tükröződési képességét tárolja texelenként, mivel a legtöbb felület nem minden pontja ugyanolyan mértékben veri vissza a fényt.

A következő technikák önmagukban általában nem használatosak, hanem valamelyik bump mapping technikát egészítik ki hangsúlyozva ezzel a felület részletességét.

Felületi árnyékolás, amikor a felület virtuális domborulatai árnyékot vethetnek, de természetesen csakis egymásra; ez az ún. interactive horizon mapping.

Az ún. displacement mapping technika virtuális formái vagyis amikor extra vertexek létrehozása nélkül érzékeltetjük a felület domborzatát: igen egyszerű és olcsó effekt a parallax mapping (teljes nevén parallax mapping with offset limiting) másik nevén parallax occlusion mapping, amely azonban könnyen renderelési hibákat okozhat. Jóval bonyolultabb változat a relief mapping, amely korrekt módon képes megjeleníteni a felület virtuális összetettségét pláne akkor, ha önárnyékolást is számol (amely természetesen igen-igen költséges). Mindkettő használatához szükséges height map hasonlóképpen a normal map generálásához.

Összegezve, manapság forward shadinget használva egy "fullextrás" effekt: bump mapping + specular mapping + relief mapping önárnyékkal

Ami még jön a témához:

Fresnel effekt

detail mapping, detail normal mapping 

environment mapping, environment bump mapping

multilayer material

esetleg még subsurface scattering

Nagyon sokáig gondot okozott számomra, hogy hogyan képes egy játék eltárolni, kezelni, mozgatni, "élővé" tenni nagy területeket. Számtalan 3d engine létezik a világban, de a legtöbbjük megreked a betöltök-egy-modellt-és-nyomok-rá-effektet állapotban. A szerencsésebbek egy kisebb, egy játékra alkalmas engine-ig jutnak el, de általában a folytatáshoz az egész engine ujratervezése-ujraírása lenne szükséges.

Vajon mi lehet ennek az oka; azt hiszem alapvetően két probléma merül fel ezzel a kérdéssel kapcsolatban.

Az egyik a tapasztalat hiánya, mivel aki még nem készített enginet nem valószínű, hogy tudja mi mindenre lesz majd még szüksége a későbbiekben, milyen módon lehet a kódot "legszebben" és "legjobban" megírni - magyarán, hogy három hónap mulva is megértse, hogy mit és miért úgy kódolt le ahogy ott van. Ilyenkor lehet hasznos a kommentezés.

A másik probléma, a (hosszútávú) tervezés hiánya vagyis hiába egy remek koncepció, ha az nem lesz elég gyors, nem elég általános és pár hónap múlva már gyorsabb ujraírni, mint kijavítani, mert hemzseg a bugoktól, néha itt-ott-elszáll-de-nem-tudom-miért, nálam-pedig-nem-fagyott-eddig stb.

A tapasztalatok begyűjtése az egyik leghasznosabb módja a tanulásnak, hiszen felesleges feltalálni a spanyolviaszt sokadszorra is (ami ráadásul nem 1-2 nap terméke, hanem jóval több), amikor az már régen készen van. Persze újítani mindig érdemes, de csak akkor, ha az ember biztosan tudja arról, hogy mikor lehet, mikor nem lehet azt használni és nem balladai homály takargatja az algoritmus működési elvét vagyis nem a véletlennek köszönheti a működését.

Akiket esetleg érdekel, hogy jutottam el oda, ahol most vagyok nekik szól a következő rész.

Tapasztalataim az enginem jelenetkezeléséről nagyvonalakban bevezetésként egy csipetnyi játéktörténelemmel.

Nagyon régen a 3d játékok jelenetei alapvetően 2 részre oszlottak aszerint, hogy külső, nyílt terepen vagy belső, zárt helyszíneken játszódtak-e és általában a két tipust vegyíteni nem igazán lehetett. A jelenet-típusok eme alapvető megkülönböztetése programozási, algoritmizálási és teljesítmény problémák miatt volt szükséges, mely utobbi a teljesítmény fokozatos növekedésével elvesztette jelentőségét így a kétféle helyszín vegyítése lehetségessé vált anélkül, hogy az a bizonyos "loading" felirat előkerült volna.

Az enginem első verziója brute force technikával oldotta meg a jelenetkezelést, amelynek sebességbeli hátránya elég hamar a felszínre bukkant ugyhogy lapozzunk tovább a híres-neves Quake3 .bsp pályaformátumára. A bsp sikerét mi sem bizonyítja jobban, hogy az első wolfeinstein játéktől a quake4ig bizony számos játék ezt az elvet/formátumot használta szóval nekem is kötelező volt ezt kipróbálnom.

Első menetben megelégedtem a .q3bsp geometria rendereléssel, aztán jött mellé a bsp fa felhasználása még később a pvs információk kezelése így egy teljes értékű bsp megjelenítő állt rendelkezésemre (az már csak hab a tortám, hogy még még később vagyis mostanában kezelem le a q3bspben tárolt spline-okat).

Azonban csak belső térben játszódó játék manapság már kevésbé izgalmas és ez a formátum csak kiegészítésekkel tud domborzatokat támogatni és azok sem világmegváltó-méretűek.

Következő lépésem volt tehát egy domborzat kezelő készítése. Először 128*128 méretben probálkoztam, amely reális szemmel nézve nevetségesen kicsi, de a terület nagyságával és felbontásával együtt növekedett a sebesség csökkenés is. Ekkor találtam magam szemben a terrain lod problémájával, amelyekből számos létezik, én a chunked lodnál horgonyoztam le.

Utolsó lépésként megprobáltam kiterjeszteni/egyesíteni ezt a technikát belső tér kezeléssel így jutottam el a bvh-ig.

Most pedig lássuk általában mik lehetnek az alapvető követelmények egy 3d engine-nel szemben.

1. szükséges tárolni, hogy kik/mik szerepelnek a jelenetben és közöttük milyen viszony áll fenn. Néhány példa - egy szereplő tart a kezében a fegyvert, amely rendelkezhet még extra felszereléssel; a szereplő ülhet egy járműben, amelyhez szintén tartozhat fegyver ill. a szereplőhöz is; a szereplő lángolhat esetleg meg is gyújthatja környezetét; a szereplő tagja lehet egy csapatnak stb... Ezt hívjuk jelenet-fának.
2. szükséges tárolni, hogy a jelenet részei milyen térbeli viszonyban állnak egymással. A legtöbb esetben ez a tér-fa a leghasznosabb!
3. érdemes tárolni, hogy a jelenet melyik részét milyen technikával rendereljük elkerülendő ezzel a felesleges állapotváltásokat. Azonban pl az átlátszó felületeknél erősen ajánlott. Ez a megjelenítési-fa;

A játék futása közben általában igaz az, hogy a jelenet-fa legalább egy részét mindenképp be kell járni. Például az épp aktív szereplőknek (ide tartozik legtöbbször a főszereplő is) cselekedniük kell.

A tér-fa egyik alapvető vizsgálata a frustum cull vagyis amikor az egész! jelenetet átvizsgáljuk megkeresve az összes, a frustumot metsző elemeket. De akkor is ezt használjuk, amikor meg akarjuk tudni, hogy egy adott fényforrás mely elemekre hat. Ha meg szeretnénk tudni, hogy milyen szereplők vannak a főszereplőnk körül akkor is ez lesz a segítségünkre

A frustum cullhoz szorosan kapcsolódik a megjelenítési-fa elkészítése/bejárása is. Itt választhatunk 2 lehetőség között hiszen

• vagy mindig bejárjuk az egész fát, amely renderelési technika alapján van rendezve és csak a látható elemeket rendereljük
• vagy mindig dinamikusan ujra elkészítjük a látható elemek és azok renderelési technikája alapján - én ez utobbit használom.

Tapasztalatom alapján a jelenet-fa és a megjelenítési-fa legjobb implementációi a láncolt listák (természetesen a jelenet-fából először ki kell gyűjteni az éppen aktív szereplőket), míg a tér-fa implementációjánál nagyon megfontoltnak kell lennünk! Az implementáció már önmagában is eldöntheti, hogy milyen tipusú jelenetet (külső tér/belső tér/vegyes) leszünk képes kezelni. Talán a legfontosabb kritérium, hogy a keresés hatékonysága minél jobb legyen hiszen ezt a fát többször is be fogjuk járni egy frame alatt!

1. A keresések legegyszerűbb módszere a lineáris keresés (vagyis az elemeket mindössze egy rendezetlen listába gyűjtjük), de mivel a keresés ideje az elemek számával arányos nő ezért használata nem javasolt.
2. A keresés egy hatékonyabb megoldása ha uniform gridbe (egyenletes rácsba) rendezzük a jelenetet. Ebben az esetben egy, a jelenetet teljesen befoglaló 2D v 3D rácsot készítünk, amelyek teljesen szabályos térrészekre (cellákra)osztják a jelenetet. Ezen cellákhoz (mivel a cellák méretei állandók) egyszerű osztások segítségével hozzá tudjuk rendelni a jelenet dinamikus és statikus elemeit. Hátránya, hogy nagy a tárigénye és bizonyos keresések lassuk (pl. frustum cull esetén a frustum nagyon precíz raszterizálását igényli a rácsra, hiszen egyetlen cella kihagyása is grafikailag elfogadhatlan eredményt ad) valamint lod-technikára kevésbé alkamazható.
3. A keresések leghatékonyabb módszere, ha valamilyen elv alapján rendezzük azt a halmazt, amiben a keresést végre kívánjuk hajtani. Ennek a követelménynek legjobban a körmentes összefüggő gráfok( röviden fa) felelnek meg.
   Számos fa létezik, amellyel sikeresen feloszthatjuk a teret, de alapvetően kétféle tipusuk létezik: a síkkal és térfogattal rendezők.
   
   A síkkal rendezők csoportja meghatározott síkokkal osztja fel és rendezi a teret egy fába; alapvetően 3 tipusuk létezik:
   -bsptree és ennek speciális esete a kd-tree, amely egy térrészt egy síkkal két részre oszt
   -quadtree, amely egy térrészt két síkkal négy részre oszt
   -octree, amely egy térrészt három síkkal nyolc részre oszt
   
   az osztás mélységének kritériumai jobbrészt a felhasználástól függenek:
   -a bsptreek esetén gyakori kritérium, hogy a fák levelei konvex térrészek legyenek és a térnek teljesen zártnak kell lennie (ha jól tudom); ezeket használták régen belső terekhez
   -más esetekben a cél az, hogy a levél ne tartalmazzon "túl" sok elemet a jelenetből és a fa ne is legyen tulzottan mély
   - az octree-ket leggyakrabban nagy terepek megjelenítéséhez használják
   - a quadtreeket pedig olyan helyen, ahol a "felfelé dimenzió" nincs teljesen kihasználva, ilyenek pl bizonyos rpg játékok
   Ezen fákat a számításigényük miatt a felhasználás előtt szokták elkészíteni.
   
   A térfogattal rendezők csoportja a jelenet elemeinek térben elfoglalt helye és mérete alapján rendezi őket egy fába. Ebben a fában a jelenet elemei alkotják a leveleket, míg magát a fát absztrakt térfogatok (cellák) képviselik, a fa gyökere pedig egy olyan cella, amely az egész jelenetet magába foglalja (egy adott szintbe tartozó cellák a levelék felé eső cellákat tartalmazzák, a levelektől távol eső cellák pedig őket tartalmazzák)
   Attól függően, hogy milyen térfogatokkal rendezzük a fát beszélhetünk
   -spheretreeről, mely esetében a fa elemeit gömbökkel rendezzük
   -aabbtreeről (népszerűbb nevén bvh), mely esetében a fa egyes elemét, az azt befoglaló, a világ koordinátarendszer tengelyeivel párhuzamos oldalu téglatesttel rendezzük
   -oobbtreeről, mely esetében a fa elemeit, az azt befoglaló, a fa elemének koordinátarendszerének tengelyeivel párhuzamos oldalu téglatesttel rendezzük

Számomra a bvh tűnik a legszimpatikusabbnak, hiszen jobban illeszkednek a téglatestek a gömböknél egy adott térfogatra és gyorsabban vizsgálhatóbb, mint egy a világhoz képest elforgatott téglatesösszességében. Úgy tűnik, hogy a bvh a jelenlegi legáltalánosabb és leghatékonyabb térfelosztó módszer mivel generálása jóval gyorsabb, mint bármelyik síkkal osztó fáé, nagyon gyorsan lehet benne keresni valamint  lod technikákkal könnyen kombinálható.

Összeségében tehát érdemes 3 fát karbantartanunk ahhoz, hogy egy jól működő és jól terhelhető 3d enginet kapjunk hiszen a különböző feladatok végrehajtásához rendelkezésre állnak a hatékony és specializált tároló adatszerkezetek így ezen feladatok cpu igényét a minimálisra tudjuk csökkenteni. Mindezekből kiindulva lehet gondolkozni a grafikai, fizikai, hang engineken, a játék logikai egységein valamint a mesterséges intelligencián, amelyekről majd későbbiekben írok némi zöldséget:]

-exponenciális mélység adatból lineáris mélység visszanyerése near...far tartományban:
F = (V*C+D) / -V;
F = -C + (D / -V)
F + C = D / -V
(F + C) / D = 1 / -V
D / (F + C) = -V
D / (-F - C) = V
D / (F * -2 + 1 - C) = V, mivel az F-t át kell vinni 0..1 tartományból -1..1 tartományba

,ahol C,D a frustum matrix megfelelő elemei, F a végeredmény, V a vertex eye spaceben

glsl:
float Z = gl_ProjectionMatrix[3].z/(gl_FragCoord.z * -2.0 + 1.0 - gl_ProjectionMatrix[2].z);

asm:
TEX depth, texcoord, texture[X],2D;

MAD tmp, depth, -2.0, ONE_MINUS_D;
RCP tmp, tmp.x;
MUL eye_depth, C, tmp;

-exponenciális mélység adatból lineáris mélység visszanyerése 0..1 tartományban:
glsl:
float Z= (2.0 * Near) / (Far + Near - depth * (Far - Near));

asm:

MAD depth, depth, NEAR_MINUS_FAR, NEAR_PLUS_FAR;
RCP depth, depth.x;
MUL depth, 2_TIMES_NEAR, depth.x;

-normál visszanyerése 2 komponensből (félgömb ujraleképzés):
csak pozitiv z irány és egységvektor esetén használható!!

glsl:
N.z = sqrt( 1 – N.x*N.x – N.y*N.y );

asm:

DP2 tmp.z, normal, normal;
SUB tmp.z, 1.0.z, tmp.z;
RSQ tmp.z, tmp.z;
RCP normal.z, tmp.z;


- 2 nem normalizált vektor skalár szorzata:
glsl:
float r= dot((N,L) * rsq( dot(N,N) * dot(L,L) )

asm:
DP3 tmp0, N,L;
DP3 tmp1, L,L;
DP3 tmp2, N,N;
MUL tmp3, tmp1, tmp2;
RSQ tmp3.x, tmp3.x;
MUL res, tmp0.x, tmp3.x;

-hogyan lesz 2x sebességű a depth (+stencil) only renderelés:
tilos-
-color bufferbe írni
-multisamplet bekapcsolni
-a fragment eldobás (se alpha test, se KIL)
-a fragment mélység módosítás
-használni user defined vágósíkokat

-hogyan lesz early z cull bekapcsolva:
tilos-
-a fragment eldobás (se alpha test, se KIL)
-a fragment mélység módosítás

-gpu feltétel kezelés:

if-then-else
[nv3x] mind2 ág végrehajtódik és a condition code dönti el, melyik számítás kerül a kimeneti regiszterbe
[nv40] valódi feltétel

-gpu feltétel kezelés:

for-loops, do-while
[nv3x] méretkorlát + nincs ciklus változó
[nv40] valódi ciklus  

manapság a shadow volume egyre inkább kiszorul főleg a soft shadow költséges volta miatt