Kiirtejälitus

**Kiirtejälitus** (inglise keeles *ray tracing*) on kiirte väljasaatmisel põhinev algoritm peidetud pindade määramiseks või kolmemõõtmeliste objektide nähtavuse väljaselgitamiseks ühe punkti suhtes ruumis. Kiirtejälituse all peetakse silmas ka selle protsessi laiendatud versioone, kus arvutatakse kiirte edasine tee ka pärast nende pinnaga lõikumist.

Suurt kasutust leiab kiirtejälitus 3D-arvutigraafikas. Kiirtejälituse algoritm võimaldab 3D-stseenide kujutamist. Stseenis olevaid valgusolusid aitab kalkuleerida kiirte tee simuleerimine kiirtejälituse meetodi läbi.

## Kiirtejälituse juured ja tähendus
Enne kiirtejälituse arengut koosnes 3D-arvutigraafika põhiliselt nippidest, mille kaudu üritati matkida objektide valgustatust. Kiirtejälitus oli esimene selle aja algoritm, millel oli ka füüsikaline alus.

Esimene kiirtejälitusmeetodit rakendav pilt arvutati välja Ameerika Ühendriikide Marylandi Ülikoolis 1960. aastal. Väljaarvutatud pilt kuvati ostsilloskoobi ekraanil. Kiirtejälituse algoritmi peamisteks väljatöötajateks loetakse tihti Arthur Apple, Robert Goldstein ja Robert Nagel, kes selle algoritmi 1960. aastate lõpus avaldasid. Teised kiirtejälitusega tegelevad teadlased olid Herb Steinberg, Marty Cohen ja Eugen Troubetskoy.
Kiirtejälitus põhineb geomeetrilisel optikal, kus valgust käsitletakse kiirekimbuna. Kiirtejälituse käigus kasutatavad meetodid olid juba palju varem rakendust leidnud, näiteks läätsede tootmisel. Tänapäeval rakendavad paljud renderdid (arvutiprogrammid piltide loomiseks 3D-tseenide põhjal) kiirtejälitust, kombineerides seda vajaduse korral muude meetoditega.

Lihtsamad kiirtejälituse vormid võtavad arvesse vaid otsest valgustatust, st otse valgusallikalt langevat valgust. Pärast kiirtejälituse kasutuselevõttu arvutigraafikas on seda edasi arendatud. Täiuslikumad kiirtejälituse vormid võtavad arvutustes arvesse ka selle valguse, mis peegeldub muudelt objektidelt. Sel juhul saab rääkida mõistest *global illumination* (otsetõlkes 'globaalne valgustatus').

Kiirtejälituse ühte lihtsamat vormi kirjeldatakse ka mõistega *raycasting*. Osaliselt võidakse neid kahte mõistet kasutada ka sünonüümidena.

## Tööpõhimõte
Rastergraafikal põhineva pildi loomist 3D-stseeni põhjal nimetatakse renderdamiseks, visualiseerimiseks või pildisünteesiks. Sellele eelneb stseeni loomine modelleerimisprogrammide abil.

Stseenikirjeldusse sisestatakse järgmised andmed:
* primitiivide, näiteks kerade või hulknurkade asukoht stseenis;
* lokaalse valgustuse mudel ja selle parameetrid, mis määravad stseenis olevate objektide värvi ja materjali;
* stseeni valgusallikad.

Lisaks sellele määratakse kiirtejälituse puhul ka silma ja pilditasandi asukoht, mille abil määratakse stseenist loodava pildi perspektiiv. Silm on kui virtuaalne kaamera, mis paikneb mingis stseeni punktis. Pilditasand on virtuaalne nelinurk, mis paikneb silmast teatud kaugusel. Rasterpildile omaselt on pilditasand jaotatud punktideks, mis kujutavad lõpp-pildi üksikpiksleid.

### Peidetud alade arvutamine
Kiirtejälitus on esmalt protsess, et määrata objektide nähtavus vaatleja suhtes. Selline põhimõte on üsna lihtne.

Kiirtejälitus töötab andmestruktuuriga, mida nimetatakse **kiireks**. Iga piksli jaoks arvutatakse välja kiire suund silma ja talle vastava pilditasandi punkti abil. Seejärel arvutatakse iga kiire jaoks välja lõikepunkt vaateväljas paiknevate primitiivide suhtes. Selle protsessi käigus arvutatakse välja ka objekti kaugus silmast. "Võitjaks" kuulutatakse lõikumispunkt, mis oli silmale kõige lähemal, ja ülejäänud lõikumispunktid klassifitseeritakse lähima objekti poolt varjatuks.

Meetod, mille käigus saadetakse silmpunktist välja kiiri, meenutab objektiivita kaamerat – see on nagu valguskindel kast, milles on väike auk. Kiirtejälituse käigus on aga augu ja filmi asukoht vahetuses. Sarnaselt kaameraga määrab ka kiirtejälituse puhul valgusava ja filmi vaheline kaugus fookuskauguse, mille põhjal stseeni töödeldakse.

Kuna kiired väljuvad silmast ja mitte valgusallikast, nagu looduses, räägitakse vahel ka *backwards ray tracing*'ust. Kiirtejälitus tegeleb küsimusega, kust valgus tuleb. Mõningates publikatsioonides on seda meetodit nimetatud ka *eye ray tracing'uks* või *forward ray tracing'uks*.

### Lõikumispunkti väljaselgitamine
Eespool mainitud meetod keha ja kiire lõikumispunktide määramiseks on kiirtejälituse meetodi tuum. Lõikumispunkti väljaselgitamiseks kasutatavaid teste annab rakendada hulgaliselt erinevate geomeetriliste kujundite peal. Lisaks kolmnurkadele ja keradele on võimalik neid teste rakendada ka silindritel, kuupidel, punktpilvedel või isegi fraktalitel.

Kerade puhul on lõikumispunkti väljaarvutamine küllalt lihtne ja kiire protsess, mis selgitab konkreetse kujundi populaarsust kiirtejälitusel põhinevate renderdite testpiltidel. Siiski lubavad paljud renderdid tänapäeval primitiividena (baas ehitusjupid) vaid kolmnurki, millest vajalikke objekte kokku ehitatakse.

Uuemal ajal on olnud võimalik kasutada ka keerukamaid geomeetrilisi põhimõtteid, näiteks NURBS-i. Eeliseks on suurendatud täpsus, kuna pinnad ei koosne vaid kolmnurkadest. Tagajärjeks on samas pikemad töötlusajad, kuna lõikumispunkte on vaja arvutada keerukate valemitega. NURBS-ile omast täpsust on küll võimalik saavutada ka kolmnurkadega, samas nõuab see aga väga suure hulga kolmnurkade käsitlemist, mis omakorda pikendab töötlusaega.

### Varjutamine
Lähima primitiivi määramise protsessi käigus leitakse lisaks lõikepunktile ja kaugusele silmast ka primitiivi pinnanormaal. Nõnda on olemas vajalik informatsioon, et määrata silmpunkti peegelduva "valguskiire" värv. Selle käigus kasutatakse ka stseenis paiknevate valgusallikate kirjeldatud omadusi. Kõik arvutused põhinevad lokaalse valguse mudelil, mis on võimeline simuleerima materjalide olemust. Seda pilditöötluse osa, mis tegeleb värviedastusega, nimetatakse varjutajaks.

### Näitekood
Lihtsama kiirtejälitusel põhineva programmi loomine ei ole kuigi töömahukas. Pseudokoodis saab vajalikke põhimõtteid kirjeldada nii:

 Funktsioon **Pildi_töötlemine**
    Kiir.Allikas = Silmpunkt
    **For every** (x,y)-Rastergraafika pikslid
        Kiir.suund = [Pilditasandil asuva punkti 3D-koordinaadid] − Silmpunkt
        Värv (x,y)-Pixel = *Värv_suunast*(kiir)

 Funktsioon **Värv_suunast**(kiir)
    Lõikepunkt := *Lähim_lõikepunkt*(kiir)
    **If** Lõikepunkt.võitja = (False):
        Värv_suunast := *Värv_taust*
    **Else:**
        Värv_suunast := *Värv_lõikepunktist*(kiir, lõikepunkt)

 Funktsioon **Lähim_lõikepunkt**(kiir)
    MaxKaugus := ∞
    Lõikepunkt.võitja := (False)
    **For every** primitiiv steenis
        Lõikepunkt := *Testi_primitivi*(primitiv, kiir)
        **If** Lõikepunkt.kaugus 'uga oma maksimumi saavutas. Alles hiljem seati arenduses siht protsessi ajavajaduste vähendamiseks ilma, et kvaliteet selle käigus langeks.

### Vari

Kiirtejälitusalgoritmi paindlikkuse tõttu on võimalik valguskiiri lisaks silmpunktile välja saata ka ruumi muudest punktidest. Seda demonstreeris 1968. aastal Arthur Apple ja näitas, et seda meetodit saab rakendada varjude simuleerimiseks.

Pinna suvaline punkt asub just siis varjus, kui tema ja valgusallika vahel objekt paikneb. Seda saab kindlaks teha, kui saata silmast tulnud kiire lõikepunktist välja kiir valgusallikasse et näha, kas uus väljasaadetud kiir mingi objektiga lõikub. Kui nõnda juhtub, asub lõikepunkt varjus ning silmpunkti kiire heleduseks määratakse 0. Vastasel juhul leiab aset tavaline varjutamine.
### Rekursiivne kiirtejälitus
Kiirtejälitust saab rakendad lihtsatele, valgust mitteläbilaskvate, kehadele ka läbipaistvatele ja peegelduvate kehadele. Sellel puhul saadetakse lõikepunktist välja uusi valguskiiri. Peegelduvate pindade puhul on vaja välja arvutada peegeldumisseaduste põhjal uue kiire suund ning välja saata vastav peegelduskiir.

Valgust läbilaskvate objektide puhul saadetakse välja kiir vastavalt Snelli-Descartesi seadusele, seekord objekti sisse. Üldiselt peegeldavad läbipaistvad objektid osa valgusest tagasi. Murdunud ja peegeldunud valguse värve annab arvutada Fresneli valemitega. Selliseid kiiri nimetatakse sekundaarkiirteks.

Kuna sekundaarkiired võivad tabada ka muid objekte, kutsutakse esile algoritm rekursiivselt, et võimaldada mitmekordne valguse peegeldumine ja valguse murdumine. Kogu protsessi hierarhilist ülesehitust kutsutakse ka töötluspuuks (inglise keeles *render-tree*).

Rekursiivse kiirtejälituse töötasid välja Kay ja Whitted 1980. aastatel.

Rekursiivse kiirtejälituse puhul näeb pseudokoodis kirjutatud varjuti välja nii:

 Funktsioon **Värv_Lõikepunktis**(Kiir, Lõikepunkt)
    **If** Lõikepunkt.Võitja.Materjal = peegelduv **or** läbipaistev
        Peegeldav_Osa := *Fresnel*(Kiir, Lõikepunkt)
        Värv := Peegeldav_Osa × *Värv_Suunast*(Peegeldumiskiir)
               + Murdunud_Osa × *Värv_Suunast*(Murdumiskiir)
    **Else:**
        Värv := 0
        For every Valgusallikas
            Varjukiir := Valgusallikas.Positsioon – Lõikepunkt.Positsioon
            VarjuLõikepunkt := *Lähim_Lõikepunkt*(Varjukiir)
            If VarjuLõikepunkt.Võitja = Valgusallikas
                Värv := Värv + *Otsene_Valgustus*(Kiir, Valgusallikas)
    Värv_Lõikepunktis := Värv

Ülejäänud programmi osad võivad jääda samaks, nagu nad lihtsa kiirtejälituse puhul olid. Siin näidatud funktsioon *Värv_Suunast* võib esile kutsuda funktsiooni *Värv_Lõikepunktis*, millega tuleb esile funktsiooni rekursiivne olemus.

### Difuusne kiirtejälitus
Rekursiivne kiirtejälitus võimaldab lisaks valguse murdumisele ja valguse peegeldumisele ka teravate varjude simulatsiooni. Reaalsuses on siiski valgusallikatel olemas mõõtmed, mis varjud pehmeks ja uduseks muudavad.

See efekt, nagu ka sakitõrje (inglise keeles *antialiasing*), läikivad peegeldused, jne. lasevad ennast difuusse kiirtejälitusega (inglise keeles *distributed ray tracing*) abil simuleerida. Selle kohta publitseeris von Cook aastal 1984 paberi. Meetodi idee seisneb ühe kiire asemel mitme kiire väljasaatmises ning nende kiirte värviinformatsiooni keskmise väljaarvutamises. Nõnda on võimalik luua näiteks pehmeid varje. Protsessi miinuseks on müra, mis tekib, kui liiga vähe kiiri välja saadetakse. On siiski olemas meetodeid, nt *importance sampling*, mis müra vähendab.

### ''Path tracing'' ja ''light tracing''
Difuusne kiirtejälitus võimaldab küll simuleerida paljusid efekte, kuid see ei ole võimeline simuleerima globaalset valgustatust koos efektidega, näiteks difuusne interreflektsioon ja kaustikefektid (läbi valguskiirte koondamise tekkivad valged valguslaigud). See on põhjustatud tõsiasjast, et difuusse kiirtejälituse puhul tekivad sekundaarsed kiired vaid valguse peegeldumise ja murdumise korral, mitte aga difuussete objektidega kokkupuutel.

1986. aastal avalikustatud publikatsioonis kirjeldas James Kajiya töötlemisvõrrandit, mis lõi matemaatilise aluse globaalsele valgustatusele.  Ühe kiire "heledus" defineeritakse nõnda radiomeetriliselt korrektselt kui kiiretihedust. Kaijya näitas, et globaalse valgustuse jaoks peab iga pind välja saatma sekundaarseid kiiri. Lisaks näitas ta, et *render-tree* ei tööta piisavalt efektiivselt, kuna palju tööressurssi kulub suurtes hierarhiasügavustes arvutamise peale, ning on parem, kui välja saadetakse vaid üks kiir. Seda meetodit tuntakse tänapäeval nimetusega *path tracing*, kuna valguskiir otsib endale silmpunktist teed läbi stseeni. *Path tracing*'ul on matemaatiliselt ja füüsikaliselt paindumatu struktuur.

Kui *path tracing*'u käigus difuusse pinna poolt välja saadetud sekundaarkiir tabab valgusallikat otse, ignoreeritakse selle heledusosa. Heledusastet arvutatakse hoopis varjukiirte põhjal. Alternatiivselt võidakse otsest valgustatust arvutada nii, et välja saadetakse vaid üks sekundaarkiir, ja kui see tabab valgusallikat, tagastatakse tolle valgustihedus. Kumb kahest mudelist efektiivsem on sõltub pinna lokaalsest valgusmudelist ja jälgitava objekti nurgast valgusallika suhtes.  Eksisteerib ka kontseptuaalselt lihtsama *path tracing*'u variant *adjoint photon tracing*, kus varjukiiri välja ei saadeta.

Kuigi *path tracing* on võimeline simuleerima globaalset valgustust, väheneb tolle efektiivsus väikeste valgusallikate puhul. Selle all kannatab eriti kaustik ja tolle peegeldused, kuna välja saadetakse väga vähe kiiri. Seetõttu kasutatakse tihti teisi, *path tracing*'ul põhinevaid meetodeid või edasiarendusi.

*Light ray tracing* on haruldane versioon kiirtejälitusest, kus selle asemel, et valguskiiri silmast välja saata, saadetakse kiired välja valgusallikast. Pikslid, mida pilditasandil tabatakse, värvitakse vastavalt kiire omadustele. Nõnda on võimalik täpselt simuleerida kaustikaid aga teiste efektide simuleerimine kannatab ebaefektiivsuse all, kuna paljud kiired pilditasandit lihtsalt ei taba.

### Ülevaade

## Viited