A raycasting hasonlóan a raytracing-hez, képzeletbeli, a szemlélőtől kiinduló sugarak segítségével dönti el egy-egy sík láthatóságát, és építi fel a képet. A kettő fogalom között azért nagy különbség van. A raytracing minden egyes pixelt egy kibocsátott sugár segítségével határoz meg, míg a raycasting egy képernyőoszlophoz rendel egy sugarat, és oszloponként építi fel a képet. Ebből következően a raycasting sokkal gyorsabb, kevésbé általános, nem olyan szép, viszont realtime jól számolható. A kevésbé általános alatt azt értem, hogy a modellezett tér sok sajátosságát kihasználja. A falak mindig merőlegesek a padlóra és a mennyezetre, amik vízszintesek. Ezt a technikát először a mára már legendává vált Wolf3D-ben láthattuk, de még számos követte (Doom, Dark Forces, …). A manapság hódító Quake persze ennél sokkal többet, és máshogy tud, de elégedjünk meg most a régi alapokkal.

Kezdjük a technikából következő korlátozásokkal (azért itt, ott lehet rajtuk segíteni).

  • A falak merőlegesek a padlóra
  • A falak kocka (téglatest) egységekből állnak
  • A nézőpontot csak oldalirányban tudjuk forgatni. (jobbra, balra)
  • A padló mindig sík
Építsünk fel egy teret.

A tér egy mátrixon van felépítve (grid map). A mátrix elemeihez rendelt érték jelzi, hogy az illető helyen mi van.
Legegyszerűbb, ha most csak a falakat jelöljük.

Mielőtt össze-vissza kavarnánk a koordinátarendszerben, először döntsük el, mi merre nő, hol van a nulla fok, és merre forog. Bárhogyan is határozunk, a lényeg, hogy következetesen tartsuk hozzá magunkat. Szóval a továbbiakban ez a nyerő koordinátarendszer a grid map-en:
 

A következő lépés a raycasting jellemzőinek meghatározása.

Legfontosabb a látómező (Field Of View). Az embernek 100 fok körüli látómezeje van, ez a keskeny monitoron elég bénán nézne ki. Általában ennél jóval kevesebbre, 60 fok körülire szokták választani. Számoljunk ennyivel. A raycasting során csak a látómezőn belül indítunk sugarakat, a szemlélő felől:

A nézőpont magasságát is meg kell határozni (a játékos magasságát), akkor a legegyszerűbb, ha a falak magasságának a felével számolunk, ekkor ugyanolyan messze van a plafon, mint a padló. Végül szükségünk van leképezési síkra. Ez az a sík, ahová leképezzük az általunk látott teret. Ez a képernyő síkja, legyen 320X200-as.

A későbbi számolások során a a térben a pixel-t tekintjük egy egységnek, a grid map-en pedig egy grid egység az egység. Ezekből már ki tudjuk számolni a szemlélő és a leképezési sík távolságát.

Tehát a szemlélő távolsága a leképezési síktól X*tan(FOV/2), ahol X a leképezési sík szélessége, FOV, pedig a látómező (Field Of View, ezután FOV-al jelölve mindig). Ha mind a 320 képernyőoszlopra bocsátunk ki sugarat (márpedig ez a raycasting lényege), akkor FOV/X, azaz 60/320 fokonként kell sugarat indítanunk.

A kép felépítése

A képet, amint eddig is kiderült, oszlopról oszlopra építjük fel. A 0. oszlopra lesz leképezve a legbaloldalibb sugár. Mivel a középső sugárnak a szöge a nézet szöge (Angle of View, továbbiakban AOV), tehát az a szög, amerre a játékos néz, ezt a sugarat kell a leképezési sík közepére leképezni (160.-dik oszlopra). Az első sugár (legbaloldalibb)  szöge AOV, mínusz a látótér fele. A 319. oszlopra pedig a legjobboldalibb sugár, AOV plusz a látótér fele. A sugarakat a teret felépítő mátrixon (Grid-en) eregetjük:

Mivel AOV=135 fok (Erre nézünk) az első sugár szöge 135 fok -60 fok/2 (AOV-FOV/2), az utolsóé 135+60/2(AOV+FOV/2), a középsőé pedig 135 (AOV).

A kép felépítéséhez szükséges lépések:

  1.  Meghatározzuk az első sugár szögét. AOV-FOV/2.
  2. A 0. Képernyőoszloptól az utolsóig (nálunk ez 319 )
    A. Elindítjuk a sugarat a Grid-en (Cast a ray, innen a név).
    B. Falkeresés. A sugár hossza elvileg végtelen, addig megyünk, amíg nem találunk valami tereptárgyat. (Falat)
    C. Ha megtaláltuk a falat, akkor a távolságát kiszámoljuk, eltároljuk, szükség lesz rá.
    D. Kirajzoljuk a megtalált fal egy képernyőoszlopát. Az oszlop kezedét és végét a távolságból számoljuk ki.
    E. Hozzáadjuk a sugár szögéhez a növekményt, hogy a következőre lépjünk. Ez esetünkben 60/320 (FOV/X).
A sugár igazi számolása, (húzása) a falkeresésnél történik, itt visszük a sugarat egészen addig, amíg nem találunk falat. A sugár számolása lépésközökkel megy, hasonlóan egy texture mapping-hez. Mivel egy Grid egy egység falat jelent a modellben, nem csak a sugár által metszett Grid koordinátákra lesz szükségünk, de azt is tudnunk kell, hogyan metszette a sugár a grid egységet. Hiszen a falak kockákból állnak, meg kell különböztetni, hogy szemben, vagy oldalt metszette a sugár.

A metszés keresése ezért két nekifutásban történik. Először a grid-en soronként lépünk, tehát minden sorban megkeressük a sugár által metszett grid-et. Ekkor a szemben metszett grideket (horizontális metszés) találjuk meg. Másodszorra, pedig oszloponként haladva keresünk, ekkor az oldalt metszett gridek (vertikális metszés) fognak kijönni. Tehát először az Y lépésköz lesz 1 a griden, másodszor az X.

Vertikális metszések keresése

Ha az első metszés koordinátáit kiszámoljuk, utána ezekhez csak Xd-t és Yd-t kell adni, hogy megtudjuk a következő metszés helyét.

A programban persze nem akarunk lebegőpontosan számolni, ezért felszorzott grid koordinátákkal (Fixpontosan) számolunk. Praktikusan kettő valamelyik hatványával szorzunk, mondjuk 64, 128, vagy 256. Az a legpraktikusabb, ha a grid map szélességével szorzunk fel, ekkor a tömb indexelésénél (gridmap[Y*mapXsize,X]) nem kell még egyszer szorozni az Y koordinátát. Ez legyen most 64 (26). Ekkor a lépésközöket is felszorozva kell kiszámolni. A nézőpont (játékos helye Px, Py) is már felszorzott koordinátákban legyen megadva.

Algoritmus:

  1. Az első metszéspont megkeresése.
  2. Lépésközök kiszámolása. (Xd, Yd)
  3. Megnézni a grid-en, hogy a metszéspontnál van-e fal
  4. Ha van, ki kell számolni a távolságát, és kilépni
  5. Lépésközök hozzáadása a metszéspont koordinátákhoz, így megkapjuk a következőt.
  6. Vissza 3.-ra
A képletek az elején bemutatott koordinátarendszerben működnek. Ha másfele növekszik az X, vagy az Y, avagy máshol van a nulla fok, a képletek értelemszerűen átalakítandóak.
 
Először az első metszés koordinátáit kell kiszámolnunk. Ehhez tudnunk kell, hogy mi a sugár iránya. A sugár szögéből ki lehet találni.
Ha a sugár szöge 0, vagy 180, akkor nem kell semmit csinálni, hiszen biztos hogy a sugár horizontális, így vertikálisan nem fog metszeni semmit. Egyébként:

Az első metszés koordinátái:
Y0:
Ha az irány lefelé mutat: Y0=(Py div 64)*64+64 (Ha a<360 és  a>180)
Ha felfelé megy a sugár:  Y0=(Py div 64)*64-1 (Ha a>0 és a<180??)

A képletek kicsit légből kapottnak tűnhetnek, nézzük meg őket. A Py egészosztása 64-el visszaadja az igazi grid koordinátát (64-el fel volt szorozva). Ha ez megvan szorozzuk vissza 64-el, ezzel biztos hogy eltüntettük a fixpontos szám törtrészét. Assembly-ben járatosak egy AND utasítással is le tudják maszkolni ezeket a biteket. Ha a sugár felfelé megy, akkor kivonunk egyet az eredményből. Ezt azért tesszük, mert kivonás nélkül ugyanannak a grid egységnek a legtetejére mutatna, ahonnan indultunk, nekünk a következő grid egység legalja kell, hiszen az ott lévő illetve nem lévő falra vagyunk kíváncsiak. Ha a sugár lefelé megy, akkor 64-et hozzáadunk, mert így fog a koordináta a játékos alatti grid egység legtetejére mutatni.

X0 (az első metszés x koordinátája):
X0=Px+(Py-Y0)/tan(a).

Itt nem kell törődni a sugár irányával, hiszen a képletben már szerepel a meredeksége (tan(???.

A lépésközök felszorozva
Ha a sugár lefelé irányul: Yd=+64
Ha a sugár felfelé irányul: Yd=-64
Xd=-Yd/ tan(a)
Mivel az Y tengely felfelé csökken, -1-el szorozunk, hogy az X tengelyen jó irányba haladjunk.

A következő metszés koordinátáit mindig a lépésközök hozzáadásával kapjuk:

X1=X0+Xd, X2=X1+Xd, … Xuj=Xrégi+Xd
Y1=Y0+Yd, Y2=Y1+Yd,…. Yuj=Yrégi+Yd

Addig megyünk, amíg nincs fal. Tehát 64X64-es gridmap-en: GridMap[(Y AND $FFC0) +(X SHR 6)]<>WALL
Az AND utasítás lemaszkolja az alsó 6 bitet, ezen volt a fixpontos szám törtrésze. Ezzel 64*Y-t kapunk, ami kell az indexeléshez. A SHR utasítás visszaosztja a felszorzott X-et 64-el. Kevésbé gyakorlottak GridMap[(Y div 64)*64+(X div 64)] -et is használhatnak.


Ha a sugár szöge 90, vagy 270 fok akkor kiléphetünk, egy függőleges vonalnak nincs vízszintes metszése.

Az algoritmus ugyanaz, mint a vertikális keresésnél, csak itt mások a képletek:
Az első metszés koordinátái:
Ha a sugár balra irányul: X0=(Px div 64)*64-1 (Ha a>90 és a<270)
Ha a sugár jobbra irányul: X0=(Px div 64)*64+64 (Ha 0<a<90 vagy 360>a>270)
Az egyel való csökkentés, és a 64-el való növelés ugyanolyan logika alapján megy, mint az előbb.
Y0=Py+(Px-X0)*tan(a)
A lépésközök 64-el felszorozva:
Ha a sugár balra irányul: Xd=-64  (Ha a>90 és a<270)
Ha a sugár jobbra irányul: Xd=+64  (Ha 0<a<90 vagy 360>a>270)
Yd=-Xd*tan(a)

A két eljárás által szolgáltatott faltávolság közül a kisebbet kell választani, az a fal látszik, hiszen az van közelebb.
A fal távolságának meghatározása:


Persze Pitagoras tétellel is meg lehetne adni, de egyszerűbb a szögfüggvényes, mert azokat ki lehet gyűjteni táblázatba. Az ABS abszolútértéket jelent, szükség van rá, hiszen a távolság nem szokott negatív lenni.
Az a probléma ezekkel a képletekkel, hogy a sugár hosszát adják meg a metszéspontig, a kirajzoláshoz nekünk meg a mélységi távolsága kellene (Z koordinátája). Ha ezeket az értékeket használjuk a leképezéshez, előjön az un. halszem effektus.

Halszem effektus

Ha az eddigi távolságot használjuk, a látómező szélére eső dolgok sokkal messzebbinek látszanak, mint a látómező közepén lévőek. Így amolyan nagyítóeffekt szerű képet kapunk. Az eddig példának használt gridmap, amelyen egyetlen egyenes fal van, szemből valahogy így nézne ki:

Állítólag a hal is így lát, innen a név. (Honnan tudják?)
Ha ezt ki akarjuk küszöbölni, korrekciót kell csinálnunk:

Ha a szögfüggvényeket kigyűjtjük tömbbe, akkor egyetlen szorzással megoldható a korrekció.

A falak leképezése

Ha tudjuk a fal távolságát, akkor már ki is tudjuk rajzolni. A falaknak legyen konstans magasságuk, így megkönnyítjük a dolgunkat. A fal tetejét és alját kell kiszámolnunk a képernyőoszlopra, ha megvan csak meghúzzuk a függőleges vonalat.

A fal tetejének és aljának kiszámolása:

Hasonló háromszögek alapján felírható:

Fal képének magassága                      Fal magassága ---------------------------------------- = ----------------------------- A leképezési sík és a szemlélő távolsága   A fal távolsága a szemlélőtől

A leképezési sík és a szemlélő távolságát már kiszámoltuk, (277) a fal konstans magassága legyen 64, a fal távolságát pedig jelöljük Z-vel. Ez természetesen a korrekció utáni távolság. H-val jelöljük a leképezett fal magasságát. Ekkor:

H=64*Z/277

Mivel tudjuk, hogy a szemlélő magassága a fal magasságának fele, a fal közepe a leképzési sík felénél lesz (100. sor). Ezért a fal teteje az éppen cast-olt  képernyőoszlopon: SartY=100-H/2
A fal alja : EndY=100+H/2

Kitöltjük a StartY és EndY között a képernyőoszlopot a fal színével, és már meg is vagyunk az adott oszloppal. Jöhet a következő, falkeresés, távolság számolás, kirajzolás…

Ez persze nem szép, nincsenek textúrák a falakon, nincs árnyékolás, sőt még padló és plafon sincs, meg nincsenek ajtók, meg nem lő senki….
De azért az alapok megvannak.

A letölthető forráskód Free Pascal-ra született, a Borland nem fogja lefordítani. Egyébként igyekszem belőle tradíciót csinálni, pascal-ban többen tudnak mint C-ben, a Free Pascal meg bárhol hozzáférhető.

Szóval Folyt. Köv. a következő számban. Lesz textúra, padló, mennyezet, egy kis árnyékolás, meg ami sikerül.