Ray tracing (grafika) - Ray tracing (graphics)

Toto rekurzivní paprskové sledování reflexních barevných koulí na bílém povrchu demonstruje účinky malé hloubky ostrosti , „plošných“ světelných zdrojů a difúzní interreflexe .

V 3D počítačové grafice , sledování paprsku je technika pro modelování lehké dopravu pro použití v široké škále vykreslování algoritmy pro vytváření digitálních snímků .

Na spektru výpočetních nákladů a vizuální věrnosti jsou vykreslovací techniky založené na sledování paprsků od odlévání paprsků , rekurzivního sledování paprsků , distribučního sledování paprsků , mapování fotonů až po trasování tras obecně pomalejší a vyšší věrnost než metody vykreslování skeneru . Sledování paprsků bylo tedy poprvé nasazeno v aplikacích, kde bylo možné tolerovat relativně dlouhou dobu vykreslování, například u stále počítačem generovaných obrazů a filmových a televizních vizuálních efektů (VFX), ale bylo méně vhodné pro aplikace v reálném čase, jako je jako videohry , kde je rychlost při vykreslování každého snímku rozhodující .

Od roku 2018 se však hardwarová akcelerace pro sledování paprsků v reálném čase stala standardem u nových komerčních grafických karet a grafická rozhraní API ji následovala, což vývojářům umožňuje používat ve hrách a dalších aplikacích v reálném čase hybridní trasování paprsků a vykreslování založené na rasterizaci s menší zásah do doby vykreslování snímků.

Ray tracing je schopen simulovat různé optické efekty, jako je odraz , lom , jemné stíny , rozptyl , hloubka ostrosti , pohybové rozostření , kaustika , okolní okluze a disperzní jevy (jako je chromatická aberace ). Lze jej také použít ke sledování dráhy zvukových vln podobným způsobem jako světelné vlny, což z něj činí životaschopnou volbu pro pohlcující zvukový design ve videohrách vykreslením realistického dozvuku a ozvěny . Ve skutečnosti lze pomocí sledování paprsku simulovat jakýkoli fyzický vlnový nebo částicový jev s přibližně lineárním pohybem .

Techniky vykreslování založené na sledování paprsků, které zahrnují vzorkování světla přes doménu, generují artefakty šumu obrazu, které lze řešit sledováním velmi velkého počtu paprsků nebo použitím technik odšumování .

Dějiny

Tento dřevoryt od Albrechta Dürera z roku 1525 ukazuje použití Dürerových dveří.

Tento obrázek Albrechta Dürera z roku 1532 ukazuje muže, který k vytvoření obrázku použil rozložení mřížky. Německý renesanční umělec je připočítán s prvním popisem techniky.

Myšlenka sledování paprsků pochází již z 16. století, kdy ji popsal Albrecht Dürer , který je zásluhou jejího vynálezu. Ve čtyřech knihách o měření popsal aparát zvaný Dürerovy dveře pomocí závitu připevněného na konci doteku, který asistent pohybuje po obrysech objektu, aby nakreslil. Vlákno prochází rámem dveří a poté hákem na zdi. Vlákno tvoří paprsek a hák funguje jako střed projekce a odpovídá poloze kamery při sledování paprsku.

Použití počítače ke sledování paprsků ke generování stínovaných obrázků bylo poprvé provedeno Arthurem Appelem v roce 1968. Appel používal trasování paprsků pro primární viditelnost (určování nejbližšího povrchu ke kameře v každém bodu obrazu) a od každého vysledoval sekundární paprsky ke zdroji světla bod je zastíněn, aby se určilo, zda byl bod ve stínu nebo ne.

Později, v roce 1971, Goldstein a Nagel z MAGI (Mathematical Applications Group, Inc.) publikovali „3-D Visual Simulation“, kde se pro vytváření stínovaných obrazů pevných látek používá simulace fotografického postupu v opačném směru. Vrhají paprsek skrz každý obrazový prvek (pixel) na obrazovce do scény, aby identifikovali viditelný povrch. První povrch protnutý paprskem byl ten viditelný. Tento rekurzivní algoritmus vykreslování na základě sledování paprsků se dnes nazývá „ ray casting “. V nalezeném průsečíku paprskového povrchu vypočítali normální povrch a při znalosti polohy světelného zdroje vypočítali jas pixelu na obrazovce. Jejich publikace popisuje krátký (30 sekundový) film „vyrobený pomocí zobrazovacího hardwaru University of Maryland vybaveného 16mm kamerou. Film ukázal helikoptéru a prosté postavení přízemního děla. Vrtulník byl naprogramován tak, aby prošel řadou manévrů včetně zatáček, vzletů a přistání atd., Dokud nakonec nebude sestřelen a havarován. “ Byl použit počítač CDC 6600 . V roce 1974 vytvořila společnost MAGI animační video s názvem MAGI/SynthaVision Sampler .

Flip kniha vytvořená v roce 1976 v Caltech

Další raná instance ray castingu přišla v roce 1976, kdy Scott Roth vytvořil animaci flip knihy v kurzu počítačové grafiky Boba Sproulla na Caltech . Naskenované stránky jsou vpravo zobrazeny jako video. Rothův počítačový program zaznamenal okrajový bod v pixelovém umístění, pokud paprsek protíná ohraničenou rovinu odlišnou od sousedních. Paprsek mohl samozřejmě protínat více rovin ve vesmíru, ale viditelný byl pouze povrchový bod nejblíže kameře. Okraje jsou zubaté, protože s výpočetním výkonem použitého časového sdílení DEC PDP-10 bylo praktické pouze hrubé rozlišení . „Terminál“ byl paměťový tubus Tektronix pro text a grafiku. K displeji byla připojena tiskárna, která by vytvořila obraz displeje na rolovacím termopapíru. Roth rozšířil rámec, zavedl termín ray casting v kontextu počítačové grafiky a modelování těles a později publikoval svou práci v GM Research Labs.

Turner Whitted byl první, kdo ukázal rekurzivní trasování paprsků pro zrcadlový odraz a pro lom přes průsvitné předměty s úhlem určeným indexem lomu tělesa a pro vyhlazování použil sledování paprsků . Whitted také ukázal paprsky vysledované stíny. V roce 1979 vytvořil jako inženýr v Bell Labs rekurzivní paprskem sledovaný film s názvem The Compleat Angler . Whittedův hluboce rekurzivní algoritmus pro sledování paprsku přeformuloval vykreslování z toho, že je primárně záležitostí určení viditelnosti povrchu na záležitost transportu světla. Jeho článek inspiroval sérii dalších prací dalších, které zahrnovaly trasování distribučních paprsků a nakonec nestranné trasování cest , což poskytuje rámec rovnice vykreslování , který umožnil počítačově generovaným snímkům věrnost realitě.

Po celá desetiletí bylo globální osvětlení hlavních filmů pomocí počítačem generovaných snímků zfalšováno dalšími světly. Vykreslování založené na sledování paprskem to nakonec změnilo povolením fyzicky založeného přenosu světla. Mezi rané celovečerní filmy vykreslené výhradně pomocí trasování cest patří Monster House (2006), Cloudy with a Chance of Meatballs (2009) a Monsters University (2013).

Přehled algoritmů

Algoritmus sledování paprsků vytváří obraz rozšířením paprsků do scény a jejich odrazem od povrchů a směrem ke zdrojům světla, aby se přiblížil barevné hodnotě pixelů.

Ilustrace algoritmu sledování paprsku pro jeden pixel (až do prvního odrazu)

Optické sledování paprsků popisuje způsob vytváření vizuálních obrazů vytvořených v prostředích 3D počítačové grafiky , s více fotorealismem, než jsou metody lití paprsků nebo vykreslování skeneru . Funguje to tak, že trasuje cestu z imaginárního oka přes každý pixel na virtuální obrazovce a vypočítá barvu objektu viditelného skrz něj.

Scény v ray tracingu jsou popsány matematicky programátorem nebo vizuálním umělcem (obvykle pomocí zprostředkovatelských nástrojů). Scény mohou také zahrnovat data z obrázků a modelů zachycených prostředky, jako je digitální fotografie.

Každý paprsek musí být obvykle testován na průnik s nějakou podmnožinou všech objektů ve scéně. Jakmile byl identifikován nejbližší objekt, algoritmus odhadne přicházející světlo v místě průniku, prozkoumá materiálové vlastnosti objektu a zkombinuje tyto informace pro výpočet konečné barvy pixelu. Některé algoritmy osvětlení a reflexní nebo průsvitné materiály mohou vyžadovat, aby bylo do scény znovu vrháno více paprsků.

Zpočátku se může zdát neintuitivní nebo „zpětné“ odesílání paprsků pryč z kamery, nikoli do ní (jak to ve skutečnosti dělá skutečné světlo), ale je to mnohem efektivnější. Protože drtivá většina světelných paprsků z daného světelného zdroje nepronikne přímo do oka diváka, simulace „vpřed“ by potenciálně mohla plýtvat ohromným množstvím výpočtů na světelných drahách, které nejsou nikdy zaznamenány.

Zkratka použitá v trasování paprsků má tedy předpokládat, že daný paprsek protíná rámeček pohledu. Poté, co buď maximální počet odrazů, nebo paprsek urazí určitou vzdálenost bez průsečíku, paprsek přestane cestovat a hodnota pixelu se aktualizuje.

Vypočítejte paprsky pro obdélníkový výřez

Na vstupu máme (při výpočtu používáme vektorovou normalizaci a křížový součin ):

${\ Displaystyle E \ in \ mathbb {R^{3}}}$ pozice očí
${\ Displaystyle T \ in \ mathbb {R^{3}}}$ cílová pozice
${\ Displaystyle \ theta \ v [0, \ pi]}$ zorné pole - u lidí můžeme předpokládat ${\ Displaystyle \ cca \ pi /2 {\ text {rad}} = 90^{\ circle}}$
${\ Displaystyle m, k \ in \ mathbb {N}}$ počet čtvercových pixelů ve vertikálním a horizontálním směru výřezu
${\ Displaystyle i, j \ in \ mathbb {N}, 1 \ leq i \ leq k \ land 1 \ leq j \ leq m}$ počet skutečných pixelů
${\ displaystyle {\ vec {v}} \ in \ mathbb {R^{3}}}$ svislý vektor, který udává, kde je nahoru a dolů, obvykle (na obrázku není vidět) - složka rolí, která určuje rotaci výřezu kolem bodu C (kde osa otáčení je ET úsek) ${\ displaystyle {\ vec {v}} = [0,1,0]}$

Cílem je najít polohu každého středu pixelu výřezu, což nám umožní najít čáru procházející z oka přes tento pixel a nakonec získat paprsek popsaný bodem a vektorem (nebo jeho normalizací ). Nejprve musíme najít souřadnice pixelu výřezu vlevo dole a najít další pixel provedením posunu ve směrech rovnoběžných s výřezem (vektory i ) vynásobeným velikostí pixelu. Níže uvádíme vzorce, které zahrnují vzdálenost mezi okem a výřezem. Tato hodnota se však během normalizace paprsku sníží (takže to můžete také přijmout a odebrat z výpočtů). ${\ displaystyle P_ {ij}}$ ${\ displaystyle E}$ ${\ displaystyle E}$ ${\ displaystyle {\ vec {R}} _ {ij} = P_ {ij} -E}$ ${\ displaystyle {\ vec {r}} _ {ij}}$ ${\ displaystyle P_ {1m}}$ ${\ displaystyle {\ vec {b}} _ {n}}$ ${\ displaystyle {\ vec {v}} _ {n}}$ ${\ displaystyle d}$ ${\ displaystyle {\ vec {r}} _ {ij}}$ ${\ displaystyle d = 1}$

Předvýpočty: pojďme najít a normalizovat vektor a vektory, které jsou rovnoběžné s výřezem (vše je znázorněno na výše uvedeném obrázku) ${\ displaystyle {\ vec {t}}}$ ${\ displaystyle {\ vec {b}}, {\ vec {v}}}$

{\ Displaystyle {\ vec {t}} = TE, \ qquad {\ vec {b}} = {\ vec {v}} \ times {\ vec {t}}}

{\ Displaystyle {\ vec {t}} _ {n} = {\ frac {\ vec {t}} {|| {\ vec {t}} ||}}, \ qquad {\ vec {b}} _ {n} = {\ frac {\ vec {b}} {|| {\ vec {b}} ||}}, \ qquad {\ vec {v}} _ {n} = {\ vec {t}} _ {n} \ times {\ vec {b}} _ {n}}

Všimněte si, že střed výřezu , dále vypočítáme velikosti výřezu dělené 2 včetně poměru stran ${\ Displaystyle C = E+{\ vec {t}} _ {n} d}$ ${\ displaystyle h_ {x}, h_ {y}}$ ${\ displaystyle {\ frac {m-1} {k-1}}}$

{\ Displaystyle g_ {x} = {\ frac {h_ {x}} {2}} = d \ tan {\ frac {\ theta} {2}}, \ qquad g_ {y} = {\ frac {h_ { y}} {2}} = g_ {x} {\ frac {m-1} {k-1}}}

a poté vypočítáme vektory posunující další pixely ve směrech rovnoběžných s výřezem ( ) a středem dolního pixelu ${\ displaystyle q_ {x}, q_ {y}}$ ${\ displaystyle {\ vec {b}}, {\ vec {v}}}$ ${\ displaystyle p_ {1m}}$

{\ Displaystyle {\ vec {q}} _ {x} = {\ frac {2g_ {x}} {k-1}} {\ vec {b}} _ {n}, \ qquad {\ vec {q} } _ {y} = {\ frac {2g_ {y}} {m-1}} {\ vec {v}} _ {n}, \ qquad {\ vec {p}} _ {1m} = {\ vec {t}} _ {n} d-g_ {x} {\ vec {b}} _ {n} -g_ {y} {\ vec {v}} _ {n}}

Výpočty: note a ray tak ${\ displaystyle P_ {ij} = E+{\ vec {p}} _ {ij}}$ ${\ displaystyle {\ vec {R}} _ {ij} = P_ {ij} -E = {\ vec {p}} _ {ij}}$

{\ displaystyle {\ vec {p}} _ {ij} = {\ vec {p}} _ {1m}+{\ vec {q}} _ {x} (i-1)+{\ vec {q} } _ {y} (j-1)}

{\ Displaystyle {\ vec {r}} _ {ij} = {\ frac {{\ vec {R}} _ {ij}} {|| {\ vec {R}} _ {ij} ||}} = {\ frac {{\ vec {p}} _ {ij}} {|| {\ vec {p}} _ {ij} ||}}}}

Výše uvedený vzorec byl testován v tomto projektu javascript (funguje v prohlížeči).

Podrobný popis počítačového algoritmu sledování paprsků a jeho vzniku

Co se děje v (zjednodušené) povaze

V přírodě zdroj světla vyzařuje paprsek světla, který nakonec cestuje na povrch, který přerušuje jeho postup. Tento „paprsek“ lze považovat za proud fotonů cestujících po stejné cestě. V dokonalém vakuu bude tento paprsek přímkou (ignorující relativistické efekty ). S tímto světelným paprskem se může stát jakákoli kombinace čtyř věcí: absorpce , odraz , lom a fluorescence . Povrch může absorbovat část světelného paprsku, což má za následek ztrátu intenzity odraženého a/nebo lámaného světla. Může také odrážet celý světelný paprsek nebo jeho část v jednom nebo více směrech. Pokud má povrch nějaké průhledné nebo průsvitné vlastnosti, láme část světelného paprsku do sebe v jiném směru, zatímco pohlcuje některé (nebo celé) spektrum (a případně mění barvu). Méně často může povrch absorbovat určitou část světla a fluorescenčně znovu vyzařovat světlo v barvě delší vlnové délky v náhodném směru, i když je to natolik vzácné, že to lze z většiny aplikací pro vykreslování zlevnit. Mezi absorpcí, odrazem, lomem a fluorescencí musí být započítáno všechno přicházející světlo a nic víc. Povrch nemůže například odrážet 66%přicházejícího světelného paprsku a lámat 50%, protože tyto dva by dohromady činily 116%. Odtud mohou odražené a/nebo lomené paprsky dopadat na jiné povrchy, kde jejich absorpční, refrakční, reflexní a fluorescenční vlastnosti opět ovlivňují postup přicházejících paprsků. Některé z těchto paprsků se pohybují takovým způsobem, že zasáhly naše oko, což způsobilo, že jsme viděli scénu a přispěli tak ke konečnému vykreslenému obrazu.

Algoritmus vrhání paprsků

Myšlenkou odlévání paprsků, předchůdce rekurzivního sledování paprsků, je vysledovat paprsky z oka, jeden na pixel, a najít nejbližší objekt blokující dráhu tohoto paprsku. Představte si obrázek jako dveře obrazovky, přičemž každý čtverec na obrazovce je pixel. To je pak předmět, který oko vidí přes tento pixel. Pomocí vlastností materiálu a vlivu světel ve scéně může tento algoritmus určit stínování tohoto objektu. Zjednodušujícím předpokladem je, že pokud je povrch obrácen ke světlu, světlo dosáhne tohoto povrchu a nebude blokováno nebo ve stínu. Stínování povrchu je počítáno pomocí tradičních 3D stínovacích modelů počítačové grafiky. Jednou z důležitých výhod odlévání paprsků nabízených oproti starším algoritmům scanline byla jeho schopnost snadno si poradit s nerovinnými povrchy a tělesy, jako jsou kužele a koule . Pokud lze matematický povrch protnout paprskem, lze jej vykreslit pomocí paprskového lití. Vypracované objekty lze vytvářet pomocí technik modelování těles a snadno je vykreslovat.

Algoritmus rekurzivního sledování paprsku

Ray tracing může vytvářet fotorealistické obrázky.

Kromě vysokého stupně realismu může sledování paprsků simulovat efekty kamery díky hloubce ostrosti a tvaru clony (v tomto případě šestiúhelníku ).

Počet odrazů nebo odrazů, které může „paprsek“ způsobit, a jak je ovlivněn při každém setkání s povrchem, je řízen nastavením v softwaru. Na tomto obrázku bylo každému paprsku dovoleno odrážet až 16krát . V těchto sférách je tedy možné vidět více „odrazů odrazů“. (Obrázek vytvořený pomocí Cobaltu .)

Počet lomů, které může „paprsek“ provést, a jak je ovlivněn pokaždé, když narazí na povrch, který umožňuje přenos světla , je řízen nastavením v softwaru. Zde byl každý paprsek nastaven tak, aby se lámal nebo odrážel („hloubka“) až 9krát . Byly použity Fresnelovy odrazy a jsou vidět kaustiky . (Obrázek vytvořený pomocí V-Ray .)

Dřívější algoritmy sledovaly paprsky z oka do scény, dokud nenarazily na předmět, ale určily barvu paprsku, aniž by rekurzivně sledovaly další paprsky. Rekurzivní sledování paprsků pokračuje v procesu. Když paprsek dopadne na povrch, mohou být vrhány další paprsky kvůli odrazu, lomu a stínu:

Ve směru zrcadlového odrazu je sledován odrazný paprsek. Nejbližší objekt, který protíná, je to, co bude vidět v odrazu.
Refrakční paprsek procházející transparentním materiálem funguje podobně s tím, že refrakční paprsek může vstupovat nebo vystupovat z materiálu. Turner Whitted rozšířil matematickou logiku paprsků procházejících transparentní pevnou látkou tak, aby zahrnovala efekty lomu.
Ke každému světlu je vysledován stínový paprsek. Pokud je mezi povrchem a světlem nalezen jakýkoli neprůhledný předmět, je povrch ve stínu a světlo jej neosvětluje.

Tyto rekurzivní paprsky dodávají obrazům sledovaným paprsky větší realismus.

Výhody oproti jiným metodám vykreslování

Popularita vykreslování založeného na ray tracingu vychází z jeho základu v realistické simulaci přenosu světla ve srovnání s jinými vykreslovacími metodami, jako je rastrování , které se více zaměřuje na realistickou simulaci geometrie. Efekty, jako jsou odrazy a stíny , které je obtížné simulovat pomocí jiných algoritmů, jsou přirozeným výsledkem algoritmu sledování paprsku. Díky výpočetní nezávislosti každého paprsku je trasování paprsků přístupné základní úrovni paralelizace , ale divergence paprskových drah znesnadňuje dosažení vysokého využití v paralelismu v praxi.

Nevýhody

Vážnou nevýhodou sledování paprsků je výkon (i když teoreticky může být rychlejší než tradiční vykreslování skeneru v závislosti na složitosti scény vs. počtu pixelů na obrazovce). Až do konce roku 2010 bylo sledování paprsku v reálném čase obvykle považováno za nemožné na spotřebitelském hardwaru pro netriviální úkoly. Algoritmy Scanline a další algoritmy využívají koherenci dat ke sdílení výpočtů mezi pixely, zatímco sledování paprsků obvykle spouští proces znovu, přičemž každý paprsek oka zpracovává samostatně. Toto oddělení však nabízí další výhody, například schopnost střílet více paprsků podle potřeby k provádění prostorového vyhlazování a zlepšování kvality obrazu v případě potřeby.

Ačkoli to zvládá interreflexe a optické efekty, jako je refrakce přesně, tradiční sledování paprsku také není nutně fotorealistické . Skutečný fotorealismus nastává, když je vykreslovací rovnice těsně aproximována nebo plně implementována. Implementace vykreslovací rovnice dává skutečný fotorealismus, protože rovnice popisuje každý fyzický účinek toku světla. To je však obvykle nemožné vzhledem k požadovaným výpočetním prostředkům.

Realismus všech vykreslovacích metod lze vyhodnotit jako přiblížení k rovnici. Ray tracing, pokud je omezen na Whittedův algoritmus, není nutně nejrealističtější. Metody, které sledují paprsky, ale zahrnují další techniky ( mapování fotonů , trasování cest ), poskytují mnohem přesnější simulaci osvětlení v reálném světě.

Obrácený směr procházení scény paprsky

Proces střelby paprsků z oka do zdroje světla k vykreslení obrazu se někdy nazývá zpětné sledování paprsku , protože ve skutečnosti se fotony pohybují v opačném směru. S touto terminologií však dochází k záměně. Časné sledování paprsků bylo vždy prováděno z oka a raní výzkumníci, jako byl James Arvo, používali termín zpětné sledování paprsků k mínění paprsků ze světel a shromažďování výsledků. Proto je jasnější rozlišovat eye-založené proti světla na bázi ray tracing.

Zatímco přímé osvětlení se obecně nejlépe odebírá pomocí sledování paprsků na bázi očí, určité nepřímé efekty mohou těžit ze paprsků generovaných ze světel. Kaustika jsou jasné obrazce způsobené zaostřením světla z široké reflexní oblasti na úzkou oblast (blízkého) difúzního povrchu. Algoritmus, který vrhá paprsky přímo ze světel na reflexní objekty a sleduje jejich cesty k oku, bude tento jev lépe vzorkovat. Tato integrace paprsků založených na oku a na světle je často vyjádřena jako obousměrné trasování cest, ve kterém jsou cesty sledovány jak z oka, tak ze světel, a cesty se následně po určité délce spojí spojovacím paprskem.

Mapování fotonů je další metodou, která využívá trasování paprsků na bázi světla i očí; v počátečním průchodu jsou energetické paprsky sledovány podél paprsků ze světelného zdroje, aby se vypočítal odhad zářivého toku jako funkce 3-dimenzionálního prostoru (samotná stejnojmenná fotonová mapa). V následujícím průchodu jsou paprsky sledovány z oka do scény pro určení viditelných povrchů a fotonová mapa se používá k odhadu osvětlení ve viditelných bodech povrchu. Výhodou mapování fotonů oproti obousměrnému trasování dráhy je schopnost dosáhnout významného opětovného použití fotonů, což snižuje výpočet, za cenu statistického zkreslení.

Další problém nastává, když světlo musí projít velmi úzkou clonou pro osvětlení scény (zvažte potemnělou místnost s mírně pootevřenými dveřmi vedoucí do jasně osvětlené místnosti) nebo scénu, ve které většina bodů nemá přímou linii -pohled na jakýkoli světelný zdroj (například u stropních svítidel nebo svítilen ). V takových případech bude energii přenášet pouze velmi malá podmnožina cest; Světelný transport metropole je metoda, která začíná náhodným hledáním prostoru dráhy, a když jsou nalezeny energetické dráhy, znovu použije tyto informace prozkoumáním blízkého prostoru paprsků.

Obrázek ukazující rekurzivně generované paprsky z „oka“ (a prostřednictvím obrazové roviny) do světelného zdroje po setkání se dvěma difuzními povrchy .

Vpravo je obrázek ukazující jednoduchý příklad cesty paprsků rekurzivně generovaných z kamery (nebo oka) ke zdroji světla pomocí výše uvedeného algoritmu. Difúzní povrch odráží světlo ve všech směrech.

Nejprve se paprsek vytvoří v oční špičce a vystopuje se pomocí pixelu do scény, kde dopadne na difúzní povrch. Z tohoto povrchu algoritmus rekurzivně generuje odrazový paprsek, který je sledován scénou, kde dopadá na jiný difúzní povrch. Nakonec se ve scéně vygeneruje další odrazný paprsek, který vystopuje scénu, kde dopadne na světelný zdroj a je absorbován. Barva pixelu nyní závisí na barvách prvního a druhého difuzního povrchu a barvě světla vyzařovaného ze světelného zdroje. Pokud například zdroj světla vyzařoval bílé světlo a dva difúzní povrchy byly modré, pak je výsledná barva pixelu modrá.

Příklad

Jako ukázku principů zapojených do sledování paprsku zvažte, jak by člověk našel průnik mezi paprskem a koulí. Toto je pouze matematika za průsečíkem čára - koule a následné určení barvy vypočítávaného pixelu. Obecného postupu sledování paprsku je samozřejmě mnohem více, ale toto ukazuje příklad použitých algoritmů.

V vektorový zápis , rovnice koule s centrem a poloměrem je ${\ displaystyle \ mathbf {c}}$ ${\ displaystyle r}$

{\ Displaystyle \ left \ Vert \ mathbf {x} -\ mathbf {c} \ right \ Vert ^{2} = r ^{2}.}

Jakýkoli bod paprsku začínající od bodu se směrem (zde je jednotkový vektor ) lze zapsat jako ${\ displaystyle \ mathbf {s}}$ ${\ displaystyle \ mathbf {d}}$ ${\ displaystyle \ mathbf {d}}$

{\ Displaystyle \ mathbf {x} = \ mathbf {s} +t \ mathbf {d},}

kde je jeho vzdálenost mezi a . V našem problému víme , , (např pozice světelného zdroje) a , a musíme najít . Nahrazujeme proto : ${\ displaystyle t}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle \ mathbf {s}}$ ${\ displaystyle \ mathbf {c}}$ ${\ displaystyle r}$ ${\ displaystyle \ mathbf {s}}$ ${\ displaystyle \ mathbf {d}}$ ${\ displaystyle t}$ ${\ displaystyle \ mathbf {x}}$

{\ Displaystyle \ left \ Vert \ mathbf {s} +t \ mathbf {d} -\ mathbf {c} \ right \ Vert ^{2} = r ^{2}.}

Nechte pro jednoduchost; pak ${\ Displaystyle \ mathbf {v} \ {\ stackrel {\ mathrm {def}} {=}} \ \ mathbf {s} -\ mathbf {c}}$

{\ Displaystyle \ left \ Vert \ mathbf {v} +t \ mathbf {d} \ right \ Vert ^{2} = r ^{2}}

{\ Displaystyle \ mathbf {v} ^{2}+t ^{2} \ mathbf {d} ^{2} +2 \ mathbf {v} \ cdot t \ mathbf {d} = r ^{2}}

{\ Displaystyle (\ mathbf {d} ^{2}) t ^{2}+(2 \ mathbf {v} \ cdot \ mathbf {d}) t+(\ mathbf {v} ^{2} -r ^{ 2}) = 0.}

Vědět, že d je jednotkový vektor, nám umožňuje toto menší zjednodušení:

{\ Displaystyle t^{2}+(2 \ mathbf {v} \ cdot \ mathbf {d}) t+(\ mathbf {v}^{2} -r^{2}) = 0.}

Tato kvadratická rovnice má řešení

{\ Displaystyle t = {\ frac {-(2 \ mathbf {v} \ cdot \ mathbf {d}) \ pm {\ sqrt {(2 \ mathbf {v} \ cdot \ mathbf {d})^{2} -4 (\ mathbf {v} ^{2} -r ^{2})}}} {2}} =-(\ mathbf {v} \ cdot \ mathbf {d}) \ pm {\ sqrt {(\ mathbf {v} \ cdot \ mathbf {d})^{2}-(\ mathbf {v}^{2} -r^{2})}}.}

Dvě hodnoty nalezené řešením této rovnice jsou dvě takové, které jsou body, kde paprsek protíná sféru. ${\ displaystyle t}$ ${\ Displaystyle \ mathbf {s} +t \ mathbf {d}}$

Jakákoli záporná hodnota neleží na paprsku, ale spíše na opačné polopřímce (tj. Na hodnotě začínající z opačného směru). ${\ displaystyle \ mathbf {s}}$

Pokud je množství pod odmocninou ( diskriminační ) záporné, paprsek neprotne sféru.

Předpokládejme nyní, že existuje alespoň pozitivní řešení, a buďme minimální. Kromě toho předpokládejme, že koule je nejbližší objekt na naší scéně protínající náš paprsek a že je vyrobena z reflexního materiálu. Musíme zjistit, ve kterém směru se světelný paprsek odráží. Zákony odrazu uvádějí, že úhel odrazu je stejný a je opačný k úhlu dopadu mezi dopadajícím paprskem a normálkou ke kouli. ${\ displaystyle t}$

Normální pro sféru je prostě

{\ Displaystyle \ mathbf {n} = {\ frac {\ mathbf {y} -\ mathbf {c}} {\ left \ Vert \ mathbf {y} -\ mathbf {c} \ right \ Vert}},}

kde je dříve nalezen průsečík. Směr odrazu lze nalézt pomocí odrazu o vzhledem k , který je ${\ Displaystyle \ mathbf {y} = \ mathbf {s} +t \ mathbf {d}}$ ${\ displaystyle \ mathbf {d}}$ ${\ displaystyle \ mathbf {n}}$

{\ Displaystyle \ mathbf {r} = \ mathbf {d} -2 (\ mathbf {n} \ cdot \ mathbf {d}) \ mathbf {n}.}

Odražený paprsek má tedy rovnici

{\ Displaystyle \ mathbf {x} = \ mathbf {y} +u \ mathbf {r}. \,}

Nyní stačí vypočítat průsečík posledně uvedeného paprsku s naším zorným polem , abychom získali pixel, na který dopadne náš paprsek odraženého světla. Nakonec je tento pixel nastaven na vhodnou barvu, přičemž se vezme v úvahu, jak jsou barvy původního světelného zdroje a jedné sféry spojeny odrazem.

Adaptivní ovládání hloubky

Adaptivní řízení hloubky znamená, že renderer zastaví generování odražených/vysílaných paprsků, když je vypočtená intenzita nižší než určitá prahová hodnota. Vždy musí existovat nastavená maximální hloubka, jinak by program generoval nekonečné množství paprsků. Pokud však povrchy nejsou vysoce reflexní, není vždy nutné jít do maximální hloubky. Chcete -li to otestovat, sledovač paprsků musí při sledování paprsků vypočítat a udržovat součin globálních a odrazových koeficientů.

Příklad: nechme Kr = 0,5 pro sadu ploch. Pak z prvního povrchu je maximální příspěvek 0,5, pro odraz od druhého: 0,5 × 0,5 = 0,25, třetí: 0,25 × 0,5 = 0,125, čtvrtý: 0,125 × 0,5 = 0,0625, pátý: 0,0625 × 0,5 = 0,03125 atd. Kromě toho bychom mohli implementovat faktor zeslabení vzdálenosti, jako je 1/D2, což by také snížilo příspěvek intenzity.

U přenášeného paprsku bychom mohli udělat něco podobného, ale v takovém případě by vzdálenost uražená objektem způsobila ještě rychlejší pokles intenzity. Jako příklad toho společnost Hall & Greenberg zjistila, že i pro velmi reflexní scénu použití s maximální hloubkou 15 vedlo k průměrné hloubce paprskového stromu 1,7.

Ohraničující objemy

Uzavření skupin objektů v sadách hierarchických ohraničujících svazků snižuje množství výpočtů potřebných pro ray tracing. Litý paprsek je nejprve testován na průsečík s ohraničujícím objemem a poté, pokud existuje, je objem rekurzivně rozdělen, dokud paprsek nenarazí na objekt. Nejlepší typ ohraničujícího objemu bude určen tvarem podkladového objektu nebo objektů. Pokud jsou například objekty dlouhé a tenké, pak koule uzavře ve srovnání s krabicí hlavně prázdné místo. Krabice lze také snáze generovat hierarchicky ohraničující svazky.

Všimněte si toho, že použití takového hierarchického systému (za předpokladu, že je to provedeno pečlivě) změní výpočetní čas průniku z lineární závislosti na počtu objektů na něco mezi lineární a logaritmickou závislostí. Důvodem je, že v perfektním případě by každý test průniku rozdělil možnosti dvěma a vyústil by ve strukturu binárního typu stromu. Pokuste se toho dosáhnout pomocí níže popsaných prostorových metod dělení.

Kay & Kajiya poskytují seznam požadovaných vlastností pro hierarchické ohraničující svazky:

Podstromy by měly obsahovat objekty, které jsou blízko sebe, a čím dále ve stromu, tím blíže by měly být objekty.
Objem každého uzlu by měl být minimální.
Součet objemů všech ohraničujících svazků by měl být minimální.
Větší pozornost by měla být věnována uzlům v blízkosti kořene, protože prořezáním větve poblíž kořene se odstraní více potenciálních objektů než jeden dále ve stromu.
Čas strávený budováním hierarchie by měl být mnohem kratší než čas uložený jeho používáním.

Interaktivní sledování paprsku

První implementací interaktivního paprskového sledovače byl počítačový grafický systém LINKS-1 postavený v roce 1982 na Technické univerzitě v Osace , profesory Ohmurou Kouichi, Shirakawa Isao a Kawata Toru s 50 studenty. Jednalo se o masivně paralelní zpracovávající počítačový systém s 514 mikroprocesory (257 Zilog Z8001s a 257 iAPX 86s ), sloužící k vykreslování realistické 3D počítačové grafiky s vysokorychlostním sledováním paprsků. Podle Information Processing Society of Japan : „Jádrem vykreslování 3D obrazu je výpočet svítivosti každého pixelu tvořícího vykreslenou plochu z daného úhlu pohledu, zdroje světla a polohy objektu. Systém LINKS-1 byl vyvinut za účelem realizace metodika vykreslování obrazu, ve které by každý pixel mohl být paralelně zpracováván nezávisle pomocí sledování paprsků. Díky vývoji nové softwarové metodiky speciálně pro vysokorychlostní vykreslování obrázků dokázal LINKS-1 rychle vykreslit vysoce realistické obrázky. “ To bylo používáno k vytvoření předčasného 3D planetárium like videa z nebes kompletně vyrobeny z počítačové grafiky. Video bylo představeno v pavilonu Fujitsu na mezinárodní výstavě 1985 v Tsukubě . „Byl to druhý systém, který tak učinil po Evans & Sutherland Digistar v roce 1982. LINKS-1 byl v roce 1984 údajně nejvýkonnějším počítačem na světě.

Nejstarší veřejný záznam sledování paprsků „v reálném čase“ s interaktivním vykreslováním (tj. Aktualizace větší než rámec za sekundu) byl připsán na konferenci počítačové grafiky SIGGRAPH 2005 jako nástroje REMRT/RT vyvinuté v roce 1986 Mike Muussem pro Systém modelování těles BRL-CAD . BRL-CAD ray tracer, který byl původně publikován v roce 1987 v USENIX , byl ranou implementací systému sledování paprsků distribuovaného v paralelní síti, který při vykreslování dosahoval několik snímků za sekundu. Tohoto výkonu bylo dosaženo pomocí vysoce optimalizovaného, ale na platformě nezávislého LIBRT ray tracing engine v BRL-CAD a použitím solidní implicitní geometrie CSG na několika paralelních strojích se sdílenou pamětí přes komoditní síť. Sledovač paprsků BRL-CAD, včetně nástrojů REMRT/RT, je i nadále k dispozici a je dnes vyvíjen jako software s otevřeným zdrojovým kódem.

Od té doby bylo vyvinuto značné úsilí a výzkum směřující k implementaci sledování paprsků rychlostí v reálném čase pro různé účely na samostatných konfiguracích stolních počítačů. Mezi tyto účely patří interaktivní 3D grafické aplikace, jako jsou demoscenní produkce , počítačové a videohry a vykreslování obrázků. Některé softwarové 3D motory v reálném čase založené na sledování paprsků byly vyvinuty fandy demo programátory od konce 90. let.

V roce 1999 tým z University of Utah , vedený Stevenem Parkerem, demonstroval interaktivní sledování paprsků živě na sympoziu 1999 o interaktivní 3D grafice. Vykreslili model 35 milionů koulí s rozlišením 512 x 512 pixelů, běžící přibližně 15 snímků za sekundu na 60 CPU.

Projekt OpenRT obsahoval vysoce optimalizované softwarové jádro pro trasování paprsků spolu s rozhraním API podobným OpenGL s cílem nabídnout alternativu k současnému přístupu založenému na rasterizaci pro interaktivní 3D grafiku. Hardware pro sledování paprsku , jako je experimentální jednotka pro zpracování paprsků vyvinutá Svenem Woopem na Sárské univerzitě , byl navržen tak, aby urychlil některé výpočetně náročné operace sledování paprsků. 16. března 2007 odhalila University of Sarland implementaci vysoce výkonného ray tracing enginu, který umožňoval vykreslování počítačových her pomocí ray tracingu bez intenzivního využívání zdrojů.

Přehrávejte média

Quake Wars Ray Traced

Dne 12. června 2008 společnost Intel předvedla speciální verzi hry Enemy Territory: Quake Wars s názvem Quake Wars: Ray Traced , která pro vykreslování využívá trasování paprsků a běží v základním rozlišení HD (720p). ETQW fungoval rychlostí 14–29 snímků za sekundu. Demonstrace probíhala na 16jádrovém (4 zásuvkovém, 4jádrovém) systému Xeon Tigerton běžícím na frekvenci 2,93 GHz.

Na SIGGRAPH 2009 Nvidia oznámila OptiX , bezplatné API pro sledování paprsků v reálném čase na GPU Nvidia. Rozhraní API odhaluje sedm programovatelných vstupních bodů v kanálu sledování paprsků, což umožňuje vlastní kamery, paprskově primitivní křižovatky, shadery, stínování atd. Tato flexibilita umožňuje obousměrné trasování cesty, přenos světla Metropolis a mnoho dalších algoritmů vykreslování, které nelze implementovat pomocí rekurze ocasu. Renderery založené na OptiX se používají v aplikacích Autodesk Arnold, Adobe AfterEffects , Bunkspeed Shot, Autodesk Maya , 3ds max a mnoha dalších.

Společnost Imagination Technologies nabízí bezplatné API s názvem OpenRL, které zrychluje vykreslovací algoritmy založené na rekurzivním sledování paprsků ocasu a společně s jejich patentovaným hardwarem pro sledování paprsků spolupracuje s Autodesk Maya na poskytování toho, co 3D World nazývá „raytracing v reálném čase pro běžného umělce“.

V roce 2014 demo videohry PlayStation 4 The Tomorrow Children , vyvinuté společnostmi Q-Games a Japan Studio , předvedlo nové světelné techniky vyvinuté společností Q-Games, zejména kaskádové sledování paprsků kužele voxel , které simuluje osvětlení v reálném čase a využívá realističtější odrazy než odrazy prostoru na obrazovce .

Nvidia nabízí hardwarově akcelerované sledování paprsků ve svých grafických kartách GeForce RTX a Quadro RTX, aktuálně založených na architektuře Ampere . Hardware Nvidia používá samostatný funkční blok, veřejně nazývaný „jádro RT“. Tato jednotka je do určité míry srovnatelná s texturovou jednotkou co do velikosti, latence a rozhraní k jádru procesoru. Jednotka nabízí průchod BVH, dekompresi komprimovaných uzlů BVH, testování průniku paprsků AABB a testování průsečíků paprsek-trojúhelník.

AMD nabízí interaktivní grafiku paprsků nad OpenCL na grafických kartách Vega prostřednictvím Radeon ProRender . V říjnu 2020 společnost na online akci představila řadu Radeon RX 6000 , druhou generaci GPU Navi s podporou hardwarově akcelerovaného sledování paprsků.

PlayStation 5 , Xbox řady X a řady S podporovat dedikované ray tracing hardwarových komponent ve svých GPU pro real-time efektů ray tracing.

Výpočetní náročnost

U určitých formulací problému sledování paprsku byly prokázány různé výsledky složitosti. Zejména pokud je rozhodovací verze problému sledování paprsku definována následovně - vzhledem k počáteční poloze a směru světelného paprsku a nějakému pevnému bodu paprsek nakonec dosáhne tohoto bodu, pak referenční papír prokáže následující výsledky:

Ray tracing v 3D optických systémech s konečnou sadou reflexních nebo refrakčních objektů reprezentovaných systémem racionálních kvadratických nerovností je nerozhodnutelný .
Ray tracing v 3D optických systémech s konečnou sadou refrakčních objektů reprezentovaných systémem racionálních lineárních nerovností je nerozhodnutelný.
Sledování paprsku v 3D optických systémech s konečnou sadou obdélníkových reflexních nebo refrakčních objektů je nerozhodnutelné.
Sledování paprsku v 3D optických systémech s konečnou sadou reflexních nebo částečně reflexních objektů reprezentovaných systémem lineárních nerovností, z nichž některé mohou být iracionální, je nerozhodnutelné.
Ray tracing v 3D optických systémech s konečnou sadou reflexních nebo částečně reflexních objektů reprezentovaných systémem racionálních lineárních nerovností je PSPACE -tvrdý.
Pro jakýkoli rozměr rovný nebo větší než 2 je sledování paprsků s konečnou sadou rovnoběžných a kolmých odrazných ploch reprezentovaných racionálními lineárními nerovnostmi v PSPACE.

Languages

In other projects