A CIKK TARTALMA
BSP fák használata

BSP fák

A BSP fa használata a kép felépítése során

"Bounding Box" módszer
BSP fák használata

Az első részben megtudtuk, hogyan lehet egy falat kirajzolni, mozogatni, forgatni a pályát.
A program a kép felépítését nagyon egyszerűen oldotta meg, minden falat megpróbált kirajzolni. Ami leképezés után a képernyőn kívülre esett azt nem rajzolta ki. Mivel össze-vissza rajzoljuk ki a falakat, eg
ész biztosan előfordul, hogy a közelebbit rajzoljuk ki először, majd ezt felülírjuk egy távolabbival. Így nem helyesek a takarási viszonyok, ezért Z bufferelni is kell. Ez a módszer egy nagyobb pálya esetén nem járható út.

Az lenne az igazi, ha a falak távolság szerint volnának rendezve. Ekkor megtehetnénk, hogy először a legtávolabbit rajzoljuk ki, utoljára a legközelebbit. Ha egy pálya több ezer falból áll, akkor nem jó ötlet minden frame-re újra sorbarendezni az összes falat. Ezen kívül még mindig nem tudnánk, hogy a több ezer fal közül melyik az a pár, amit valóban ki kell majd rajzolni. Mi lehet a megoldás?

BSP fák

Magyarul Binary Space Partitioning. A módszer nem egyszerű, de igen hasznos. Maga az elv elég általános, több területen is használják, most csak azt szeretném bemutatni, ami egy Doom stílusú játékhoz szükséges.

A lényege az, hogy egy fában eltároljuk a falak (poligonok) egymáshoz viszonyított helyzetét. Hogy a bal vagy a jobb oldalán vannak-e egy másiknak. Egy nagyon leegyszerűsített példával próbálnék indítani. A pálya:

A betűvel jelzett vonalak a falak. Azért van nyíl az egyik végükön, mert vektorként kell felfognunk őket. Így tudjuk értelmezni, hogy egyik fal a másik jobb illetve bal oldalán van. Mivel egy falat a két végpontjával határozunk meg, a fal vektora a kezdőpontjából a végpontba mutat.

Egy BSP fa erre a pályára valahogy így néz ki:

Többféle fa is leírja ugyanazt a pályát, és ezek a fák nem is hasonlítanak egymáshoz.

A fa minden csomópontja egy fal a pályán, minden, ami a baloldali ágban van az a faltól balra van, ami a jobboldali mellékágban van, az jobbra van. A csomópontokat "node" -nak is hívják, a mellékágakat "subtree" -nek. . A fa felépítése során azokat a falakat elvágjuk, amik nincsenek teljes terjedelmükkel a fában felettük lévő jobb, illetve bal oldalán. (Így keletkeztek h1,h2,b1,b2.) A fa felépítéséről majd később, most csak annyit jegyezzünk meg, hogy a felépítés során új falak keletkeznek. A fa végződései (levelei "terminal node") több falat is tartalmazhatnak. Ezek a falak azért kerülhettek egymás mellé, mert egymással konvex alakzatot alkotnak, nincs olyan nézőpont, ahonnan takarnák egymást. Egymás után kirajzolhatóak anélkül, hogy takarási hibát követnénk el.

A BSP fa használata a kép felépítése során

Képzeljük el, hogy az X-en (ld. fenti ábra) állunk. Vajon milyen sorrendben kellene kirajzolni a falakat? Induljunk el a fán.

Mivel "e" bal oldalán állunk, először a jobb oldali ágat kell végigjárnunk, itt vannak a messzebb lévő falak, ezeket akarjuk először kirajzolni. Tehát elindulunk a jobb oldalon. Megtaláljuk a következő csomópontot. Ez azt mondja, hogy "f" fal. Mivel az "f" jobb oldalán állunk, a bal oldali ágba megyünk le. Itt megtaláljuk, hogy "g,h2", és nincs tovább. Tehát először ezeket kell kirajzolni.

Írjuk fel : g,h2

Mivel nem tudunk tovább menni, ugorjunk vissza az "f" csomópontra. Már megvannak a legtávolabbi falak, most már felírhatjuk az "f"-et is. Ha ez megvan, keressük meg a közelebbi falakat is, tehát induljunk el a jobb ágon. Itt azt találjuk, hogy "d,c,b2". Tehát eddig a kirajzolási sorrend:

g,h2,f,d,c,b2

Ez megvan, ugorjunk vissza. Visszaértünk az "e"- hez. Mivel az "e" által takart falakat már mind megtaláltuk, felírhatjuk a listára az "e"-t is. A bal ágból jövünk, menjünk le a jobb ágon is, itt lesznek a közelebbiek. Itt az van, hogy "h1,a,b1"

A sorrend: g,h2,f,d,c,b2,h1,a,b1

Azokat a falakat persze nem kell kirajzolni, amik mögöttünk vannak (negatív a Z-jük). Tehát, ha történetesen felfelé néztünk, megkapjuk, hogy : g,h2,f,d,c,b2,h1,b1.

A fa ilyen módú bejárása egyszerűen megoldható egy rekurzív eljárással. Az eljárás pszeudokódja (kb):
 

vector player ;a néző térképbeli pozíciójastructure node ;egy csomópont leírása           vector vertex1,vertex2 ;a fal kezdő és végpontja           node left_subtree,right_subtree ;jobb és baloldali                                           ;mellékág           mapwall wall ;a fal adatai a kirajzoláshoz           bool terminal ;végződés-e           mapwall treminal_walls[maxwall] ;a végződésben több fal                                         ;is lehet endstruct recurse(node)     if node.terminal         ;vége a fának, a falakat berakjuk a listába          addtolist(node.terminal_walls)          return     endif     if left(node.vertex2-node.vertex1,player-node.vertex1)         ;balra vagyunk a faltól, ezért a jobb oldali ágon megyünk          le          recurse(node.right_subtree)          ;a takart falak megvannak, most már berakhatjuk őt is          addtolist(node.wall)         ;és most lemegyünk a bal ágon is, itt vannak a közelebbi         ;falak          recurse(node.left_subtree)     else          ;jobbra vagyunk a faltól, ezért a bal ágon megyünk le          ;először          recurse(node.left_subtree)          addtolist(node.wall)         ;és most lemegyünk a jobb ágon is, itt vannak a közelebbi          ;falak          recurse(node.right_subtree)     endif     return end recurse

Egy kérdés merülhet fel, hogyan működik a "left" függvény, és miért vonogatjuk ki a vektorokat egymásból a paraméter-megadásnál. A "left" eljárás két vektorról tudja eldönteni, hogy egyik a másiknak bal vagy jobb oldalán van. A fal vektora a kezdőpontból a végpontba mutató vektor. Ezt úgy kapjuk meg, hogy a kezdőpont vektorát kivonjuk a végpont vektorából. Két vektor különbsége az a vektor, ami a kivonandó végpontjától a kisebbítendő végpontjába mutat. Így vertex2-vertex1 a fal vektora. Ugyanezen megfontolásból vonjuk ki a nézőpontból a fal kezdőpontját, megkapjuk a fal kezdőpontjából a nézőpont felé mutató vektort.

A "left" függvény már igen egyszerű. (hogy honnan a képlet, azt ne firtassuk…):

Bool left(vector a, vector b)        Return ( a.x*b.y-b.x*a.y>0 ) End left

Egyébként az itt alkalmazott képlet negatív értéket ad eredményül, ha jobbra van "b" "a"-tól, nullát pedig akkor, ha egy vonalban vannak.

Ez eddig működne ugyan, de semmivel sem jobb, mintha találomra rajzolgatnánk a falakat, mivel mindig bejárjuk az egész fát, és az összes falat beletesszük a kirajzolandó falak listájába. Csak más sorrendben, attól függően, hogy hol van a nézőpont (hol állunk a pályán).

"Bounding Box" módszer

Ha a fát használni akarjuk, egy kis finomítást kell végeznünk. A fa minden csomópontjára (és leveleire is) meg kell határoznunk egy "bounding box"-ot. Ez egy olyan téglalap, amibe beleférnek a csomópont alatti egész részfa által tartalmazott vonalak.

Tehát a legfelső csomópont az "e" "bounding box"-a az egész pályát tartalmazni fogja, mert az alatta lévő fa az egész pálya. A "d,c,b2" csomópont (levél) "bounding box"-a csak egy akkora téglalap, amibe belefér mindhárom fal.

Ábra:


Szóval a színeket kell összepárosítani.

Ha megvannak ezek a téglalapok, csak meg kell vizsgálni, hogy metszik-e a látómezőnket, ha igen, csak akkor kell tovább kibontani azt az ágat.

Az L a legelső (legbaloldalibb) kibocsátott sugár, az R a legjobboldalibb. (ld. raycasting) Ez a két vektor határozza meg a látómezőnket.

Lássuk a példát. Most lefelé nézünk. Az elv ugyanaz, mint eddig.

Elindulunk a fa csúcsán. Megnézzük, hogy a látómező metszi-e (vagy befoglalja -e) a csomópont bounding box-át. Mivel a fa elején vagyunk, a hozzá tartozó téglalap az egész pálya. Egész biztos, hogy metsszük. Mivel az "e" bal oldalán vagyunk, először a jobb oldali mellékágat kell megnéznünk(itt vannak a távolabbi falak). A jobb oldali mellékágban megtaláljuk az "f"-et. Megnézzük a bounding box-át. A látómezőnk nem metszi, tehát NEM kell tovább kibontani ezt az ágat. Visszamegyünk, berakjuk "e"-t a kirajzolandó falak listájába. Megnézzük a bal oldali ágat. A felirat "h1,a,b1", ennek metsszük a bounding boksz-át, tehát berakjuk a listába.

A lista: e,h1,a,b1

Ez még nem az igazi. Egy olyan fal is belekerült a listába, ami mögöttünk van, azaz egyáltalán nem is arra nézünk. Mivel ismerjük a látómezőnket, megkérdezhetjük magunktól: "vajon arrafelé nézek?"

Ez a kérdés matematikailag egy kicsit bonyolultabb.

Ha egy fal bal oldalán állunk és a látómező jobb szélső vektora a falnak jobbra van, akkor a fal felé nézünk. Ha egy fal jobb oldalán állunk, és a látómező bal szélső vektora a fal bal oldalán van, akkor is a fal felé nézünk. Hogy hogyan tud egyik vektor a másik jobb, illetve bal oldalán lenni? Úgy, hogy egy végpontra hozzuk őket.

Tehát az ábrán a látómező legjobboldalibb vektora a fal vektorához képest jobbra van. Így felé nézünk. A már megismert "left" függvénnyel: left(vertex2-vertex1,R).

Ahol vertex1 a fal kezdőpontja, vertex2 a fal végpontja, R a jobboldali sugár. A függvény hamisat fog visszaadni, mivel az R vektor jobbra van a fal vektorához képest.

Tehát meg tudjuk kérdezni, hogy a fal felé nézünk-e. Az előző pozícióban így az eljárás:

Elindulunk a fa tetején. "e"-től balra vagyunk, tehát a jobb oldali ágon mennénk le először. De mivel tudjuk, hogy nem "e" felé nézünk, nem vagyunk arra kíváncsiak, hogy milyen falakat takar az "e". Nem kell lemennünk a bal ágba, sőt az "e"-t sem kell beraknunk a kirajzolandó élek listájába, mivel nem felé nézünk. Lemegyünk a jobb ágon, és hamar azt az eredményt kapjuk, hogy a kirajzolandó falak: h1,a,b1.

És valóban ezeknek a falaknak van esélyük arra, hogy látsszanak.

Egy igazán nagy pályán a módszer sokkal látványosabb lenne. Azért itt is 10 falból hetet könnyedén kiszűrt. Csak hármat kell leképezni, és azokat kirajzolni, amik a képernyőre esnek.

Ez pszeudokódban:
 

vector player ;a néző térképbeli pozíciója vector left_sightline ;a látómező lebbaloldalibb sugara vector right_sightline ;a látómező legjobboldalibb sugarastructure node ;egy csomópont leírása vector   vertex1,vertex2 ;a fal kezdő és végpontja node   left_subtree,right_subtree ;jobb és baloldali mellékág mapwall  wall ;a fal adatai a kirajzoláshoz bool  terminal ;végződés-e mapwall  treminal_walls[maxwall] ;a végződésben több fal is lehet bounding_box box endstruct recurse(node) ;Ha nincs benne a látómezőben, akkor kihagyjuk   if not BoxInCone(left_sightline,right_sightline,node.box) return if node.terminal   ;vége a fának, a falakat berakjuk a listába   addtolist(node.terminal_walls)   return endif if left(node.vertex2-node.vertex1,player-node.vertex1)   ;balra vagyunk a faltól   ;ha a fal felé nézünk, csak akkor nézzük meg a takart (jobboldali) falakat if  not left(node.vertex2-node.vertex1,right_sightline) ;a fal felé nézünk, a jobb oldali ágon megyünk le recurse(node.right_subtree)    ;a takart falak megvannak, most már berakhatjuk őt is addtolist(node.wall)    endif ;és most lemegyünk a bal ágon is, itt vannak a közelebbi falak recurse(node.left_subtree) else   ;ha a fal felé nézünk, csak akkor nézzük meg a takart (baloldali) falakat if left(node.vertex2-node.vertex1,left_sightline)   ;jobbra vagyunk a faltól, ezért a bal ágon megyünk le először    recurse(node.left_subtree)    addtolist(node.wall)   endif ;és most lemegyünk a jobb ágon is, itt vannak a közelebbi falak recurse(node.right_subtree) endif return end recurse

A "ConeInBox" függvény igazat ad vissza, ha az elsőként megadott két vektor által megadott mező metszi, vagy bentfoglalja a téglalapot. Hogyan tudjuk ezt eldönteni.

Nézzük azokat az eseteket, amikor igazat kell a függvénynek visszaadni, azaz messzi, vagy bentfoglalja a látómező a téglalapot.

Mikor van egy pont a két vektor között? Ha az egyiknek a jobb oldalán van, a másiknak pedig a bal oldalán. Ha mindkét vektornak ugyanazon oldalán van, akkor a kettőn kívül helyezkedik el.

A két esetet figyelembe véve a függvény:

Bool ConeInbox(vector L,vector R, box B) ;ha bármelyik sarka belóg, azaz a két vektor különböző ;oldalán van, akkor igazzal tér vissza If (s1R=left(R,B.P1))!=left(L,B.P1) or    (s2R=left(R,B.P2))!=left(L,B.P2) or    (s3R=left(R,B.P3))!=left(L,B.P3) or    (s4R=left(R,B.P4))!=left(L,B.P4) return true; ;ha bármelyik kettő másik oldalon van, akkor is metsszük if s1R!=s2R or s2R!=s3R or s3R1=s4R or s4R!=s1R return true return false; End ConeInBox

Azzal kell vigyáznunk, hogy ha a téglalap a vektorok kezdőpontja mögött van, akkor hibás eredményt kaphatunk. Ez viszont nem fordulhat elő, ha megvizsgáljuk a fa bejárása során, hogy a fal felé nézünk-e.

Ha már tudjuk, hogyan kell bejárni a fát, csak a felépítését kell megismernünk. Ezt csak egyszer a program elején kell megtennünk, sőt az sem katasztrófa, ha már BSP faként van elmentve a pálya.

Na de ezt majd a következő alkalommal. Szóval folyt köv.