Progressive photon mapping na GPU

2015 http://excel.fit.vutbr.cz

Progressive photon mapping na GPU ´ s Lysek* Tomaˇ Abstrakt ´ cne´ výpoˇcetn´ı techniky - global Pro tvorbu fotorealistických obrazu˚ je nutne´ pouˇz´ıt cˇ asoveˇ naroˇ ˇ s´ı techniky patˇr´ı photon mapping a jeho progresivn´ı varianta. illumination techniky. Mezi nejnovejˇ ´ Tento cˇ lanek se bude zabývat implementac´ı progressive photon mappingu (ppm) na dneˇsn´ıch ´ a porovna´ rychlost implementace mezi CPU variantou a GPU variantou. Dale ´ grafických kartach ´ ı hitpointu˚ vybere nejpomalejˇs´ı blok ppm a navrhne urychlen´ı. Navrhnute´ urychlen´ı je zclustrovan´ do bl´ızkých clusteru˚ a pouˇz´ıt´ı pravidelne´ mˇr´ızˇ ky pro photony. ˇ a´ slova: progressive photon mapping — global illumination — gpgpu Kl´ıcov ´ Pˇriloˇzene´ materialy: N/A *[email protected], Faculty of Information Technology, Brno University of Technology

brazovac´ı rovnice (rendering equation), kterou v roce 1986 sepsal James T. Kajiya[1]. Od zaˇca´ tku poˇc´ıtaˇcové grafiky byla snaha o co nejreZobrazovac´ı rovnice popisuje výpoˇcet odraˇzeného alistiˇctˇejˇs´ı výsledné sn´ımky. Pro co nejrealistiˇctˇejˇs´ı jasu (radiance) v urˇcitém bodˇe. Popisuje to jako souˇcet obrazy je potˇreba provést sloˇzitou fyzikáln´ı simulaci svˇetla, která je velmi cˇ asovˇe nároˇcná. Pomˇernˇe novou (integrál) vˇsech pˇr´ıspˇevk˚u osvˇetlen´ı ze vˇsech smˇer˚u fotorealistickou metodou je metoda fotonových map pˇres hemisféru kolem vyˇsetˇrovaného bodu. Pomoc´ı to(photon mapping) a jeho nejnovˇejˇs´ı varianta progres- hoto pˇr´ıstupu je moˇzné analyticky vypoˇc´ıtat osvˇetlen´ı sive photon mapping. Posledn´ı dobou nastal velký scény, problém ovˇsem nastává s t´ım, zˇ e pro rozumnˇe boom GPGPU poˇc´ıtán´ı, grafickou kartu má v dneˇsn´ı sloˇzité scény je toto ˇreˇsen´ı nerealizovatelné - z cˇ asových dobˇe skoro kaˇzdý PC a proto se zdá jako zajmavá vari- d˚uvodu. V cˇ lánku o zobrazovac´ı rovnici James T. Kajia[1] anta vyzkouˇset akcelerovat progressive photon mapping na grafické kartˇe. Tato práce nejprve navrhne narvhnul zp˚usob jak vypoˇc´ıtat tuto rovnici a to t´ım jednoduchou gpu implementaci progressive photon zp˚usobem, zˇ e pro výpoˇcet integrálu pouˇzil monte carlo mappingu a poté pro nejpomalejˇs´ı blok navrhne urychle- metody. Tato metoda se oznaˇcuje jako path tracing n´ı. Nejpomalejˇs´ı blok byl vybrán a tento blok se po- a vˇsechny metody, které vycház´ı z path tracingu se moc´ı jednoduché akceleraˇcn´ı struktury podaˇrilo urych- nazývaj´ı monte carlo raytracing metody. Path tracing funguje podobnˇe jako raytracing, vyˇsle lit oproti CPU implementace v´ıce neˇz 30 krát. se paprsek z oka (kamery), který putuje do scény. Pˇri pr˚useˇc´ıku paprsku se scénou v bodˇe x se vyˇsle 2. Related work sekundárn´ı paprsek náhodným smˇerem a ten se vyˇsetˇr´ı. Nejlepˇs´ı fotorealistické výsledky se v dneˇsn´ı dobˇe Protoˇze náhodný paprsek nedokázˇ e vypoˇc´ıtat pˇresnˇe dosahuj´ı pomoc´ı tˇr´ıdy technik, které se nazývaj´ı global osvˇetlen´ı bodu x vyˇsle se v´ıce paprsku z daného pixillumination (globáln´ı osvˇetlen´ı). Ne vˇsechny global il- elu a proˇsetˇr´ı v´ıce náhodných cest - odtud název path lumination techniky jsou rozumnˇe implementovatelné tracing. na GPU a proto je potˇreba vybrat vhodnou techniku. Rozˇs´ıˇren´ım path tracnigu byla v roce 1993 [2] Tyto metody se snaˇz´ı o korektn´ı simulaci svˇetla ve a v roce 1994 [3] technika zvaná bidirectional path scénˇe a základn´ım kamenem pro tyto metody byla zo- tracing. Tato technika prohledává cesty jak od kamery

1. Introduction

tak od svˇetla najednou a poté vypoˇcte jaký pˇr´ıspˇevek máj´ı obˇe dvˇe cesty mezi sebou a podle toho spoˇcte osvˇetlen´ı. Dalˇs´ım rozˇs´ıˇren´ım path tracingu je technika zvaná Metropolis Problém monte carlo metod je ten, zˇ e pro dobré fotorealistické výsledky je potˇreba proj´ıt mnoho cest kaˇzdým pixelem. V literatuˇre se p´ısˇ e, zˇ e bˇezˇ né cˇ ´ıslo jsou tis´ıce cest na pixel, z cˇ ehoˇz vyplývá obrovská cˇ asová nároˇcnost. Dalˇs´ı moˇznost´ı je pouˇz´ıt novou techniku zvanou Photon mapping. Photon mapping byl vymyˇslen v Henrikem Wann Jensenem v roce 1996 [4]. Photon mapping je dvou-pr˚uchodová technika, která v prvn´ım kroce spoˇc´ıtá pˇr´ıspˇevek svˇetla ve scénˇe vzorkován´ım svˇetla. Jeden vzorek svˇetla - foton - je proˇsetˇren scénou podobnˇe jako paprsek u raytracingu a pˇri dopadu na dif˚uzn´ı povrch je foton uloˇzen do fotonové mapy. Poté v druhém pr˚uchodu, se pˇri výpoˇctu lokáln´ıho osvˇetlovac´ıho modelu vypoˇcte nepˇr´ımé osvˇetlen´ı z nejbliˇzsˇ´ıch foton˚u uloˇzených ve fotonové mapˇe. Pro dobré výsledky pomoc´ı klasického photon mappingu je potˇreba vyslat mnoho (des´ıtky milon˚u) foton˚u ze svˇetelných zdroj˚u, coˇz má za následek velkou mapu foton˚u - z toho plyne velká pamˇet’ová sloˇzitost a nav´ıc cˇ´ım v´ıc foton˚u je uloˇzených ve fotonové mapˇe, t´ım pomalejˇs´ı vyhledáván´ı ve fotonové mapˇe je. Problém s velikosti fotonové mapy se snaˇz´ı ˇreˇsit progresivn´ı varianta photon mappingu - progressive photon mapping, která vyˇsle ze svˇetelného zdroje pouze cˇ a´ st foton˚u, pomoc´ı této cˇ a´ sti spoˇc´ıtá osvˇetlen´ı, vyslané fotony zahod´ı a v dalˇs´ı iteraci vyˇsle znova menˇs´ı cˇ a´ st foton˚u, pˇriˇcte osvˇetlen´ı a takhle poˇra´ d dokola.

Progressive photon mapping Progressive photon mapping se jev´ı jako jako zajmavá metoda pro implementaci na grafické kartˇe - malá pamˇet’ová sloˇzitost, iteraˇcn´ı výpoˇcet, velká koherence. Proto tato sekce rozep´ısˇe teorii za progressive photon mappingem trochu do hloubky. V klasickém photon mappingu se jas v bodˇe x a ~ spoˇc´ıtá jako: smˇeru ω

1 ~)≈ 2 Lr (x, ω πr

N

∑ f (x, ω~ , ω~ p )∆Φ p (x, ω~ p )

(1)

p=1

~ p ) je záˇre z fotonu p uloˇzena ve fotonové kde ∆Φ p (x, ω ~ ,ω ~ p ) je BRDF funkce. Suma zahrnuje mapˇe a f (x, ω N nejbliˇzsˇ´ıch foton˚u z bodu x ve fotonové mapˇe. Jak jiˇz bylo zm´ınˇeno, problém photon mappingu je v jeji cˇ asové a pamˇet’ové sloˇzitosti. Pˇri výpoˇctu je photon mapping limitován operaˇcn´ı pamˇet´ı PC a pˇri

velké fotonové mapˇe je prohledáván´ı taky pomalejˇs´ı. Právˇe proto byla snaha rozdˇelit jednu velkou fotonovou mapu na mnoho menˇs´ıch fotonových map a z nich spoˇc´ıtat osvˇetlen´ı. Jednou jednoduchou variantou bylo vypoˇc´ıst n-krát klasický foton mapping s menˇs´ım poˇctem foton˚u a poté výsledky jednotlivých iterac´ı zpr˚umˇerovat, toto ˇreˇsen´ı bylo rychlejˇs´ı ale nevedlo k konzistentn´ımu (správnému) výsledku. Dalˇs´ı moˇznost byla vymyˇslena právˇe pomoc´ı progressive photon mappingu, která vhodnˇe pˇripoˇc´ıtá osvˇetlen´ı dané iterace k pˇredcházej´ıc´ı iteraci.

´ Obrazek 1. Schéma progressive photon mappingu[5]

Obrázek 1 zobrazuje schéma progresive photon mappingu. Nejprve je nad scénou vypoˇc´ıtán raytracing, v pr˚useˇc´ıc´ıch paprsk˚u s dif˚uzn´ım povrchem je uloˇzený bod - tzv. hitpoint. V hitpointu je uloˇzena pozice, barva, souˇradnice ve výsledném obrazku, polomˇer a poˇcet foton˚u, které pˇrispˇely k osvˇetlen´ı daného hitpointu. Druhá cˇ a´ st je rozdˇelena do iterac´ı, kde se vˇzdy vyˇsle urˇcitá cˇ a´ st foton˚u, v kaˇzdém hitpointu se naleznou vˇsechny fotony v jeho polomˇeru, vypoˇcte se podle nich pˇr´ıspˇevek osvetlen´ı, progresivnˇe se pˇripoˇcte k jiˇz vypoˇctenému osvˇetlen´ı. Pote se vypoˇc´ıtané fotony zahod´ı a celý proces vys´ılán´ı foton˚u se opakuje (teoreticky) donekoneˇcna. Polomˇer v hitpointu by se mˇel v kaˇzdé iteraci zmenˇsovat, coˇz vede k zpˇresˇnován´ı jiˇz vypoˇcteného ˇreˇsen´ı, nový polomˇer se vypoˇc´ıtá jako:

s ˆ = R(x) R(x)

N(x) + αM(x) N(x) + M(x)

(2)

ˆ kde R(x) respektive R(x) je polomˇer v hitpointu x respektive nový polomˇer v hitpointu x. N(x) je poˇcet jiˇz uloˇzených foton˚u (z pˇredcházej´ıc´ıch iterac´ı) v hitpointu x, M(x) je poˇcet nových foton˚u ze zrovna poˇc´ıtané iteraci v polomˇeru R(x). α je hodnota v rozsahu 0 - 1 a udává jak moc nových foton˚u bude pˇridáno do výsledného osvˇetlen´ı a jak rychle se bude polomˇer zmenˇsovat. ~ ) v bodˇe x je spoˇcteNová hodnota osvˇetlen´ı τNˆ (x, ω na jako:

~ ) = τN+M (x, ω ~) τNˆ (x, ω

N(x) + αM(x) N(x) + M(x)

(3)

~ ) je suma jasu z pˇredchoz´ıch iterac´ı a z kde τN+M (x, ω nynˇejˇs´ı iterace spoˇctena rovnic´ı 1 a hodnoty N(x), M(x) a α jsou stejné hodnoty jako v rovnici 2. ~ Výsledné osvˇetlen´ı v bodˇe x smˇeˇruj´ıc´ı smˇerem ω je spoˇcteno jako:

~) ≈ L(x, ω

~) 1 τNˆ (x, ω ˆ 2 Nemmited π R(x)

(4)

Pouˇzit´ım progressive photon mappingu je nav´ıc moˇzné doc´ılit nˇekterých fotorealistických elementu, které jsou velmi sloˇzité u ostatn´ıch metod globáln´ıho osvˇetlen´ı, jako napˇr´ıklad kaustiky, SDS cesty a jiné. (SDS cesty jsou z názvu specular-diffuse-specular a klasická ukázka tˇechto cest jsou napˇr´ıklad kaustiky na dnˇe bazénu).

´ obrazu Synteza Posledn´ı blok naˇcte paralelnˇe hitpoint, vypoˇcte barvu podle rovnice 4 a uloˇz´ı spoˇctenou barvu na pozici ve framebufferu.

3. Evaluace jednoduche´ implementace Byla provedena jednoduchá implementace jednotlivých blok˚u. I kdyˇz vˇetˇsina blok˚u je velmi naivn´ıch, tak tato implementace slouˇz´ı pouze k nalezen´ı nejslabˇs´ıch m´ıst photon mappingu. Tato implementace byla otestovaná na jednoduché scénˇe a obrázek 2 ukazuje postupné progresivn´ı - zlepˇsován´ı výsledné kvality obrazu. Byla také provedena CPU implementace, která byla rozˇs´ıˇrena o rychlejˇs´ı hledán´ı foton˚u pomoc´ı kdstromu. CPU a GPU implementace byla evaluována na notebooku s Intel i7-4702MQ processoru, napsána v c++ a kompilována Intel C++ 15.0 kompilátorem. GPU na které bˇezˇ ela OpenCL implementace byla spusˇ t’eˇ na na grafice GeForce GT 750M. Rychlost CPU implementace byla mˇeˇrena pomoc´ı std::chrono knihovny a GPU implementace pomoc´ı nvidia nsight.

Jednoducha´ GPGPU dekompozice Progressive photon mapping m˚uzˇ e být rozdˇelen do nˇekolika nezávislých blok˚u: raytracing, photon tracing, hitpoint illumination a syntéza obrazu. Raytracing Raytracing m˚uzˇ e být chápán jako sekvenˇcn´ı procházen´ı pixel˚u výsledného obrazu a prohledáván´ı scény pomoc´ı patˇriˇcných paprsk˚u. Procházec´ı rutina je pro vˇsechny paprsky stejná, takˇze paralelizace je velmi jednoduchá - jedno vlákno - jeden pixel. Oproti klasickému raytracingu, tento raytracing je rozˇs´ıˇren o uloˇzen´ı hitpointu do pamˇeti. Jedna vˇec mus´ı být poznamenána, a to ta, zˇ e raytracing je v základn´ı podobˇe rekurzivn´ı algoritmus. V dneˇsn´ı dobˇe grafické karty neum´ı zpracovat rekurzivn´ı volán´ı funkce a proto je potˇreba upravit raytracing aby fungoval iteraˇcnˇe. Photon tracing Blok photon tracingu je velmi podobný raytracingu, neukládá ovˇsem hitpointy, ale ukládá fotony. Pro procházen´ı fotonového paprsku je pouˇzit velmi podobná rutina jako u raytracingu. Hitpoint illumination V tomto bloku se paralelnˇe pro kaˇzdý hitpoint vypoˇcte nové osvˇetlen´ı hitpointu x. Nejjednoduˇssˇ´ı (a taky nejnaivnˇejˇs´ı) varianta je proj´ıt vˇsechny fotony na daném objektu a ty které maj´ı vzdálenost od bodu x menˇs´ı neˇz R(x) se zahrnou do výpoˇctu.

Raytracing Photon tracing Hitpoint Illumination Synthesize

GPU CPU 0.706 ms 1172 ms 7.897 ms 317 ms 2041 ms 1593 ms 0.247 ms 3 ms

Tabulka 1. Výkonost mezi GPU a CPU variantou

algoritmu pˇri rozliˇsen´ı 320*280 a pˇri velikosti fotonové mapy 100 tis´ıc foton˚u. Raytracing Photon tracing Hitpoint Illumination Synthesize

GPU CPU 12.107 ms 6 197 ms 7.897 ms 317 ms 38 603 ms 23 957 ms 4.924 ms 91 ms

Tabulka 2. Výkonost mezi GPU a CPU variantou

algoritmu pˇri rozliˇsen´ı 1280*1080 a pˇri velikosti fotonové mapy 100 tis´ıc foton˚u. Tabulky 1 a 2 ukazuj´ı výkonost mezi GPU a CPU implementac´ı. Jak je moˇzné z tˇechto tabulek vidˇet, vˇsechny bloky kromˇe Hitpoint illumination se na GPU znaˇcnˇe urychlily. Jednu vˇec je potˇreba podotknout, na CPU funguje v bloku Hitpoint illumination vyledáván´ı pomoc´ı kd-stromu, pokud se na cpu pouˇzije stejná metoda - tedy bruteforce - tak pˇri malém rozliˇsen´ı 320*280 trvá tento blok 68 sekund. Rychlost raytracingu a photon tracingu je ovlivnˇena poˇctem pixel˚u / foton˚u a sloˇzitost´ı scény. I kdyˇz byla testovac´ı scéna velmi jednoduchá, photon tracing a raytracing nejsou nejslabˇs´ı m´ısta. Nav´ıc pro komplexnˇejˇs´ı scény existuj´ı sofistikované algoritmy a datové struktury, pomoc´ı kterých se dá dosáhnout vysoká výkonost

nevad´ı, protoˇze i v mnohem komplexnˇejˇs´ı scénˇe se ˇreˇs´ı naprosto stejné problémy a cˇ asovˇe (pokud se zachová poˇcet foton˚u a rozliˇsen´ı) budou stejné.

´ 4. Navrh akcelerace Zmiˇnovaný hitpoint illumination blok je naprogramovaný velmi naivnˇe. Tato sekce pop´ısˇ e postupnˇe jaké akceleraˇcn´ı techniky se navrhly, pouˇzily a byly stavebn´ı bloky pro nejrychlejˇs´ı ˇreˇsen´ı. ´ ı pamet ˇ Lokaln´ V naivn´ım ˇreˇsen´ı kaˇzdý thread naˇc´ıtal postupnˇe z globáln´ı pamˇeti jeden foton za druhým. Pˇr´ıstup do globáln´ı pamˇeti je na GPU velmi drahý, proto prvn´ı akceleraˇcn´ı technika je vyuˇz´ıt´ı lokáln´ı pamˇet’i, do které je mnohem rychlejˇs´ı pˇr´ıstup. V kaˇzdé workgroupˇe se pˇriprav´ı lokáln´ı pamˇet’ a pˇretáhne se blok globáln´ı pamˇeti do lokáln´ı pamˇeti. Vˇsechny thready v workgroupˇe zpracuj´ı vˇsechny fotony v lokáln´ı pamˇeti a poté se naˇcte dalˇs´ı blok pamˇeti a tak poˇra´ d dokola.

´ Obrazek 2. Výsledky postupného poˇc´ıtán´ı

progressive photon mappingu. Na vrchn´ım obrázku je výsledek s jednou iterac´ı, uprostˇred s deseti iteracemi a dole se sto iteracemi. i pˇri komplexn´ıch scénách a pokud by se netvoˇril jednoduchý renderer, tak je moˇzné pouˇz´ıt nvidia OptiX framework, který má zabudovaný a vysoce optimalizovaný raytracing, který by se na tyto dva bloky dal pouˇz´ıt. Hitpoint illumination blok je nejpomalejˇs´ı blok. Je to dáno t´ım, zˇ e pouˇz´ıvaná technika je velmi naivn´ı a tento blok testuje velké mnoˇzstv´ı foton˚u, které nejsou v˚ubec (dáno topologi´ı scény) potˇreba. Blok vybraný k akceleraci je teda hitpoint illumination blok. To zˇ e je scéna velmi jednoduchá v tomto pˇr´ıpadˇe v˚ubec

ˇ Razen´ ı fotonu˚ Kdyˇz se poˇc´ıtá osvˇetlen´ı hitpointu x, tak se do výpoˇctu osvˇetlen´ı mus´ı zaˇradit pouze ty fotony, které leˇz´ı na stejném objektu jako hitpoint x. Proto kdyˇz máme jediné pole foton˚u, tak velká cˇ a´ st foton˚u se zavrhne, protoˇze leˇz´ı na jiném objektu a drahé naˇc´ıtán´ı bylo zbyteˇcné. Navrhnuté ˇreˇsen´ı je rozdˇelit jedno pole foton˚u na N pol´ı foton˚u, kde v kaˇzdém poli jsou fotony pouze z jednoho objektu. Proto se mezi photon tracing blok a hitpoint illumination blok vloˇz´ı blok na rozˇrazen´ı foton˚u a tento blok roztˇr´ıd´ı fotony do pˇr´ısluˇsných pol´ı. Rychlost tohoto bloku je zanedbatelná (1.5ms) v porovnán´ı s rychlost´ı bloku hitpoint illumination. Protoˇze nen´ı zajiˇstˇeno, zˇ e vˇsechny hitpointy v jedné workgroupˇe budou ze stejného objektu, nen´ı moˇzné pouˇz´ıt v tomto pˇr´ıpadˇe lokáln´ı pamˇet’. ˇ Razen´ ı hitpointu˚ Aby se dosáhla vˇetˇs´ı koherence, je nutné zajistit, zˇ e vˇsechny hitpointy v jedné workgroupˇe budou z jednoho objektu, je nutné pouˇz´ıt nˇejaký systém rozˇrazen´ı. Toto rozˇrazen´ı je moˇzné provést na CPU, protoˇze bude v celém procesu pouˇzité pouze jednou. Jediný problém, který nastává je pˇri pˇrechodu (v poli) mezi jednotlivými objekty. Je nutné vloˇzit do pole s hitpointy takzvané filler hitpointy, které jsou neaktivn´ı a zajiˇst’uj´ı pouze to, zˇ e v workgoupˇe budou hitpointy pouze z jednoho objektu, nebo právˇe filler hitpointy.

ˇ ´ ı pamet ˇ’ Razen´ ı hitpointu˚ a lokaln´ Protoˇze nyn´ı jsou v jedné workgroupˇe pouze hitpointy z jednoho objektu, je moˇzné slouˇcit vˇsechny pˇredchoz´ı pˇr´ıstupy a pouˇz´ıt lokáln´ı pamˇet’ a rozˇrazené fotony najednou. ´ ı hitpointu˚ a spatial grid Klastrovan´ Pˇredchoz´ı ˇreˇsen´ı i kdyˇz je rychlé, poˇra´ d prohledává velké mnoˇzstv´ı zbyteˇcných foton˚u. Kdyˇz se pod´ıváme na CPU implementaci pomoc´ı kd-stromu, jde vidˇet, zˇ e CPU akceleraˇcn´ı technika na vyhledáván´ı foton˚u pˇrinesla obrovské zrychlen´ı, proto by bylo vhodné pouˇz´ıt podobnou akceleraˇcn´ı techiku i na GPU. Kd-strom je ovˇsem tˇezˇ ko sestrojitelný za bˇehu na GPU. Proto vybrané ˇreˇsen´ı je pravidelná mˇr´ızˇ ka. Pˇri tvorbˇe pravidelné mˇr´ızˇ ky pro jeden objekt, se nejprve vypoˇcte bounding box daného objektu. Pro jednoduchost a adaptabilitu se vyuˇzije dˇel´ıc´ı faktor n, který urˇcuje kolikrát se bude dˇelit nejdelˇs´ı strana bounding boxu a z jednoho d´ılku se poté vypoˇcte sˇ´ıˇrka pravidelné mˇr´ızˇ ky. Pˇri urˇcován´ı v jaké cˇ a´ sti mˇr´ızky se bod x nacház´ı, staˇc´ı pouze vypoˇc´ıst vektor smˇeˇruj´ıc´ı z minimáln´ıho bodu bounding boxu do bodu x a poté podˇelit kaˇzdou sloˇzku sˇ´ıˇrkou jednoho boxu pravidelné mˇr´ızˇ ky. T´ımto po zaokrouhlen´ı smˇerem dol˚u vypadnou celoˇc´ıselné hodnoty x, y, z, které udávaj´ı pozici v mˇr´ızˇ ce.

workgroupy a nejefektivnˇejˇs´ı velikost worgkroupy se m˚uzˇ e liˇsit dle rozliˇsen´ı.

5. Vyhodnocen´ı vysledk ´ u˚ Vˇsechny akceleraˇcn´ı techniky, které byly pˇredstavené v minulé sekci byly naimplementovány a byla zmˇeˇrena jejich rychlost na rozliˇsen´ı 1920*1080 a 320*280. Naive solution Local memory Photon sorting Hitpoint sorting Hitpoint sorting, local memory

320*280 2041 ms 1109 ms 611 ms 484 ms 327 ms

1920*1080 38 603 ms 17 750 ms 10 539 ms 8 384 ms 5 422 ms

Tabulka 3. Vyhodnocen´ı výsledku navrhnutých

akceleraˇcn´ıch ˇreˇsen´ı. Tabulka 3 ukazuje, zˇ e postupnˇe vˇsechny postupy bez pravidelné pˇrinásˇely zˇ a´ dané urychlen´ı a postupnˇe se podaˇrilo pˇrekonat a z´ıskat zrychlen´ı oproti CPU variantˇe. Vˇsechny tyto testy byly vykonány pomoc´ı OpenCL. Pro výpoˇcet vzdálenosti byla pouˇzita zabudovaná funkce distance(). Jakmile se funkce distance() nahradila za ruˇcn´ı vypoˇc´ıtán´ı vzdálenosti, vedlo to k skoro 3x rychlejˇs´ımu výsledku. A tedy rychlost hitpoint illumination bloku je pˇri rozliˇsen´ı 320*280 125 ms a pˇri rozliˇsen´ı 1920*1080 1 941ms. Testován´ı pravidelné mˇr´ızˇ ky je nutné provést oddˇelenˇe a to z d˚uvodu velkého mnoˇzstv´ı filler hitpoint˚u. Pˇri rozliˇsen´ı 1920*1080 ve výsledném výpoˇctu bylo pˇr´ıtomno 33% filler hitpoint˚u a tedy algoritmus fungoval pouze na 66%. Je nutné tedy uvést cˇ asy i bez pravidelné mˇr´ızˇ ky. Tabulka 4 ukazuje fináln´ı a maximáln´ı zrychlen´ı navrhovaných metod. 320*280 1920*1080 Hitpoint sorting, local memory 172 ms 2 852 ms Grid structure 87 ms 730 ms Tabulka 4. Rychlost pravidelné mˇr´ızˇ ky.

´ Obrazek 3. Klastry hitpoint˚u vytvoˇrené algoritmem

k-means Posledn´ım problémem, který je potˇreba vyˇreˇsit, je maximáln´ı koherence hitpoint˚u, coˇz znamená, zˇ e je nutné zajistit, aby hitpointy v jedné workgroupˇe byly co nejbl´ızˇ e (prostorovˇe) u sebe a t´ımpádem budou procházet stejné podprostory mˇr´ızˇ ky. Pro toto zajiˇstˇen´ı je vyuˇzito na CPU stranˇe algoritmu k-means, který vytvoˇr´ı na poli hitpoint˚u klastry. Velký problém algoritmu k-means je ten, zˇ e nen´ı moˇzné zajistit aby vracel klustry fixn´ı velikosti a tedy mnoho filler hitpoint˚u je pouˇzito. Obrázek 3 znázorˇnuje jak vypadaj´ı klastry ve scénˇe. Velikost klastr˚u je omezena podle velikosti

´ er ˇ 6. Zav Tato práce popisuje experimentáln´ı implementaci progresivn´ıho photon mappingu na grafické kartˇe. Pro kaˇzdý dekomponovaný blok je navrhnuta gpu implementace a nejpomalejˇs´ı blok byl postupnˇe zrychlený 52 krát oproti naivn´ı implementaci a 32krát oproti CPU implementaci. V dalˇs´ım pokraˇcován´ı práce by bylo vhodné vymyslet jiný algoritmus klastrován´ı, napˇr´ıklad pomoc´ı evoluˇcn´ıch algoritm˚u navrhnout takové rozˇrazen´ı hitpoint˚u, které sn´ızˇ ´ı chybu z 33% na menˇs´ı hodnotu a vyuˇzije se vˇetˇs´ı potenciál grafické karty.

ˇ ´ ı Podekov an´ Chtˇel bych podˇekovat vedouc´ımu mé diplomové práce profesorovi Pavlovi Zemˇc´ıkovi za uˇziteˇcné rady a trpˇelivost, kterou se mnou mˇel.

Literatura [1] James T. Kajiya. The rendering equation. SIGGRAPH Comput. Graph., 20(4):143–150, August 1986. [2] Eric P. Lafortune and Yves D. Willems. directional path tracing. 1993.

Bi-

[3] Eric Veach and Leonidas Guibas. Bidirectional Estimators for Light Transport. 1994. [4] Henrik Wann Jensen. Global illumination using photon maps. In Proceedings of the eurographics workshop on Rendering techniques ’96, pages 21– 30, London, UK, UK, 1996. Springer-Verlag. [5] Toshiya Hachisuka, Shinji Ogaki, and Henrik Wann Jensen. Progressive photon mapping. ACM Trans. Graph., 27(5):130:1–130:8, December 2008.

Progressive photon mapping na GPU

Recommend Documents