Kiirtejälitus

Kiirtejälitus^[1] (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.

Kiirtejälituse abil saadud pilt

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.^[2] Kiirtejälituse algoritmi peamisteks väljatöötajateks loetakse tihti Arthur Apple, Robert Goldstein ja Robert Nagel, kes selle algoritmi 1960. aastate lõpus avaldasid.^[3][4][5] Teised kiirtejälitusega tegelevad teadlased olid Herb Steinberg, Marty Cohen ja Eugen Troubetskoy.^[6] 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.

Kiirtejälituse põhimõte

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.^[7] 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 < MaxKaugus :
           MaxKaugus := Lõikepunkt.kaugus
           Lõikepunkt.võitja := Primitiv
   Lähim_lõikepunkt := lõikepunkt

Iga kiirtejälitaja, ükskõik millist kiirtejälgimisega seotud meetodit rakendades, jälgib sarnast struktuuri, mis sisaldavad veel lõikepunktidest (Testi_primitivi) ja varjutajat (Värv_Lõikepunktis).

Võimekus

Kiirendusmeetodid

Esimese kiirt tabava primitiivi määramiseks võib, nagu ülevaltoodud näitekoodis, testida kiirt iga stseenis oleva primitiivi suhtes. Samas pole see enamasti vajalik, kui on teada, et osad primitiivid ei paikne kiire läheduses ja seega on võimatu, et nad kiirega pihta saavad. Lõikepunktide väljaarvutamiseks on kiirtejälituse meetodi puhul töötluse kõige aeganõudvam protsess ja seetõttu on tähtis arvutustesse kaasata nii vähe primitiive, kui võimalik, et säästa arvutusaega.

Kiirendusmeetodite käigus jaotatakse stseen mingite süsteemide järgi automaatselt alamtükkideks. Nendesse alamtükkidesse grupeeritakse sealpaiknevad primitiivid. Kui kiir saadetakse stseeni läbima, ei arvutata tema lõikumist kogu stseeni suhtes, vaid hoopis alamtükkide suhtes, mida ta läbib. Nõnda peab lõikumispunktide arvutustesse kaasama vaid alamtükkides paiknevad primitiivid ja mitte kogu stseeni informatsioon.

Kiire liikumine läbi vokselvõrgustiku

Kiirtejälituse jaoks on välja arendatud mitmeid selliseid kiirendusmeetodeid. Näited alajaotussüsteemidest on näiteks vokselvõrgustik, BSP-puud ja bounding volumes, mis primitiive ümbritsevad ja stseeni osadeks jagavad. Samuti on võimalik eespool mainitud meetodeid kombineerida. Animatsioonide jaoks on välja töötatud sarnaseid kiirendusmeetodeid.

Ükski kiirendusmeetod pole universaalselt optimaalne. Efektiivsusaste sõltub suurel määral siiski stseenist. Samas vähendavad kiirendusmeetodid stseeni üleüldist töötlusaega väga suurel määral ja võimaldavad kiirtejälitus algoritmi praktiliselt rakendada. K-dimensioonilistel puudel baseeruvad kiirendusmeetodid on enamus mitteanimeeritud stseenide jaoks üks efektiivsemaid tehnikaid, kuna seda on heuristikat kasutades veelgi optimeerimisvõimalusi.^[8][9] On ka kindlaks tehtud, et stseeni ajaline keerukus on logaritmilises sõltuvuses temas paiknevate primitiivide hulgaga.

On näidatud, et tänapäevaste arvutite puhul pole kiirtejälituse pudelikaelaks mitte protsessor, vaid hoopis mälule ligipääsu kiirus. Vahemälu hoolika majandamise abil on võimalik algoritmi märgatavalt kiirendada. Samuti saab kasutada protsessorite SIMD-arhitektuuri, mis võimaldab paralleelseid arvutusi ning spetsiaalselt optimeeritud eraldusskeeme. Sedasi on võimalik üheaegselt jälgida mitmeid "pakettidesse" kokkuseotud kiirepuntraid. Seda põhjusel, et enamik silmpunktist väljasaadetud kiiri on üksteisega väga sarnased ja nad tabavad tihti sama objekti. SSE käsustikega saadakse korraga testida nelja kiire lõikumist objekti suhtes. Spetsiaalsete riistvaralahendustega on võimalik ka suuremaid, üle 1000 kiirt sisaldavaid pakette, jälgida. Kahjuks kaotavad vahemälu- ja SIMD-optimeeringud enda ajaeelise komplitseeritumate kiirtejälitusmeetodite kasutamisel.

Veel on võimalik kogu kiirtejälitus protsess paralleliseerida. Selle realiseerimine on küllalt lihtne, kui anda konkreetsele protsessorile/arvutile pildi erinevaid juppe töötlemiseks. Paralleliseerimisega toimetulekuks on vaja vaid mõningaid optimeerimismeetodeid kohandada.

Mälutarve

Kiirtejälituse protsess ise palju mälu ei tarvita. Küll aga hõivab palju mälu hoopis stseen – keerukamad stseenid võivad koosneda miljonitest primitiividest, mille maht võib ulatuda gigabaitideni. Lisaks sellele peab arvesse võtma ka kiirendusmeetodite mäluvajadust. Kuna väga suured stseenid korraga arvuti mällu ei mahu, on vajalik lehekülgede saalimine.

Suuremate ja keerukamate objektide puhul, mis esinevad stseenis mitmekordselt ja erinevad vaid positsiooni ja suuruse poolest (näiteks mets), pole kogu geomeetriat vaja korduvalt mällu salvestada. Läbi eksemplaarimise (inglise keeles instancing) on võimalik kokku hoida palju salvestusruumi, kuna objekt laaditakse mällu vaid üks kord.

Edasiarendused

Üks kiirtejälituse meetodi edukuse põhjuseid on tema edasiarenduspotentsiaali rohkus. Eelpoolkirjeldatud algeline metoodika pildisünteesi jaoks ei ole enam tänapäevastele nõudlustele vastav. Tõusva arvutusvõimsuse ja füüsikast ammutatud inspiratsiooni abil (esmalt optika ja radiomeetria) on loodud mitmeid edasiarendusi ja variatsioone, millest mõned siis lühidalt kirjeldatud on.

Üleüldiselt kehtib, et iga edasiarendusega tõuseb võimalik kvaliteet, aga ka vajaminev ajakulu, mis path tracing'uga oma maksimumi saavutas. Alles hiljem seati arenduses siht protsessi ajavajaduste vähendamiseks ilma, et kvaliteet selle käigus langeks.

Vari

Lichtquelle – valgusallikas; Shattenwerfer – varjuheirja; Shattenstrahl – varjukiir; Strahl – kiir

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.^[10][11]

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.^[12] 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.

Globaalse valgustuse näide

1986. aastal avalikustatud publikatsioonis kirjeldas James Kajiya töötlemisvõrrandit, mis lõi matemaatilise aluse globaalsele valgustatusele. ^[13] Ü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.

Visualiseeritud Causics Photon Map

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. ^[14] 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

Kiirtejälitusmeetod	Vari	Valguspeegeldused ja -murdumised	Valgustus	Näitepilt
Ainult peidetud pindade määramine	Ei	Ei	Ei
Varjude simulatsioon (ainult ühe varjukiirega)	Ainult kõvad varjud	Ei	Ainult otsene valgustus
Rekursiivne kiirtejälitus	Ainult kõvad varjud	Ainult peegeldavatel pindadel	Ainult otsene valgustus või peegeldus
Difuusne kiirtejälitus	Täielik	Ainult peegelduvate/läikivate pindade puhul	Ainult otsene valgustus või peegelduv/läikiv peegeldus
Path Tracing	Täielik	Täielik	Täielik (globaalne valgustatus)

Viited

1. [http://vallaste.ee Vallaste e-teatmik "ray tracing"]
2. Terrence Masson: CG 101: A Computer Graphics Industry Reference. S. 267. Digital Fauxtography 2007, ISBN 0-9778710-0-2
3. Arthur Appel: Some Techniques for Shading Machine Renderings of Solids. In Proceedings of the Spring Joint Computer Conference 1968. S. 37–45. AFIPS Press, Arlington
4. Mathematical Applications Group, Inc.: 3-D Simulated Graphics Offered by Service Bureau. Datamation 13, 1 (Feb. 1968): 69, ISSN 0011-6963
5. Robert Goldstein, Roger Nagel: 3-D Visual Simulation. Simulation 16, 1 (Jan. 1971): 25–31, ISSN 0037-5497
6. Terrence Masson: CG 101: A Computer Graphics Industry Reference. S. 162. Digital Fauxtography 2007, ISBN 0-9778710-0-2
7. Oliver Abert u. a.: Direct and Fast Ray Tracing of NURBS Surfaces. In Proceedings of IEEE Symposium on Interactive Ray Tracing 2006. S. 161–168. IEEE, Salt Lake City 2006, ISBN 1-4244-0693-5 (PDF, 700 KB)
8. Vlastimil Havran u. a.: Statistical Comparison of Ray-Shooting Efficiency Schemes. Technical Report TR-186-2-00-14, Institute of Computer Graphics and Algorithms, Vienna University of Technology 2000 (Online)
9. Ingo Wald, Vlastimil Havran: On building fast kd-trees for ray tracing, and on doing that in O(N log N). In Proceedings of IEEE Symposium on Interactive Ray Tracing 2006. S. 61–69. IEEE, Salt Lake City 2006, ISBN 1-4244-0693-5 (PDF, 230 KB)
10. Douglas Scott Kay: Transparency, Refraction and Ray Tracing for Computer Synthesized Images. Thesis, Cornell University, Ithaca 1979
11. Turner Whitted: An Improved Illumination Model for Shaded Display. Communications of the ACM 23, 6 (June 1980): 343–349, ISSN 0001-0782 (PDF, 4,6 MB)
12. Robert Cook u. a.: Distributed ray tracing. ACM SIGGRAPH Computer Graphics 18, 3 (July 1984): 137–145, ISSN 0097-8930
13. James Kajiya: The Rendering Equation. ACM SIGGRAPH Computer Graphics 20, 4 (Aug. 1986): 143–150, ISSN 0097-8930
14. Eric Veach, Leonidas J. Guibas: Optimally combining sampling techniques for Monte Carlo rendering. In SIGGRAPH ’95 Proceedings, S. 419–428. ACM, New York 1995, ISBN 0-89791-701-4 (Online)