Universita Karlova v Praze. Matematicko-fyzikální fakulta. Diplomová práce. Lukáš Maršálek. Osvtlení na GPU

Universita Karlova v Praze Matematicko-fyzikální fakulta

Diplomová práce

Lukáš Maršálek

Osv tlení na GPU Kabinet software a výuky informatiky Vedoucí diplomové práce: RNDr. Josef Pelikán Studijní program: Informatika, Softwarové systémy, Po íta ová grafika

Prohlašuji, že jsem svou diplomovou práci napsal samostatn a výhradn s použitím citovaných pramen . Souhlasím se zap j ováním práce. V Praze dne 9.8.2005

Lukáš Maršálek

2

Obsah ÚVOD................................................................................................................................................10 1.1 ZOBRAZOVÁNÍ OBJEMU .............................................................................................................. 10 1.1.1 Principy a použití............................................................................................................... 10 1.1.2 Klasifikace podle zp sobu promítání................................................................................. 11 1.1.3 Klasifikace podle dominantního pr chodu ........................................................................ 12 1.2 STRUKTURA ZOBRAZOVACÍHO SYSTÉMU .................................................................................... 12 1.3 ZOBRAZOVÁNÍ V REÁLNÉM ASE ............................................................................................... 14 1.4 GRAFICKÝ HARDWARE ............................................................................................................... 15 1.5 CÍLE PRÁCE ................................................................................................................................ 20 1.6 ROZVRŽENÍ TEXTU ..................................................................................................................... 21 METODY HLEDAJÍCÍ POVRCH ................................................................................................23 2.1 ÚVOD ......................................................................................................................................... 23 2.2 KONSTRUKCE POVRCHU ............................................................................................................. 24 2.2.1 Napojování iso ar.............................................................................................................. 24 2.2.2 Marching Cubes ................................................................................................................ 26 2.3 KOMENTÁ ................................................................................................................................ 28 P ÍMÉ ZOBRAZOVACÍ METODY ............................................................................................30 3.1 ÚVOD ......................................................................................................................................... 30 3.2 OPTICKÉ MODELY ....................................................................................................................... 31 3.2.1 Simulace vlastností reálných látek..................................................................................... 32 3.2.2 Empirické mapování .......................................................................................................... 43 3.3 ZOBRAZOVACÍ POSTUPY ............................................................................................................. 44 3.3.1 Metody pr ez .................................................................................................................. 45 3.3.2 Metody otisk ..................................................................................................................... 47 3.3.3 Faktorizace ........................................................................................................................ 48 3.3.4 Vrhání paprsku .................................................................................................................. 50 3.3.5 Jiné p ístupy ...................................................................................................................... 52 3.4 KOMENTÁ ................................................................................................................................ 52 NÁVRH METODY PRO IMPLEMENTACI NA GPU ...............................................................53 4.1 PRINCIP EŠENÍ .......................................................................................................................... 53 4.2 ZOBRAZOVACÍ ALGORITMUS ...................................................................................................... 54 4.2.1 Generování paprsku........................................................................................................... 55 4.2.2 Vzorkování paprsku a kompozice....................................................................................... 59 4.3 POUŽITÉ OPTICKÉ MODELY ......................................................................................................... 60 4.4 P ÍPRAVA EXPERIMENTÁLNÍCH DAT ........................................................................................... 62 IMPLEMENTACE NA GPU..........................................................................................................63 5.1 MODEL PRÁCE A STRUKTURA KÓDU ........................................................................................... 63 5.1.1 Efekty ................................................................................................................................. 64 5.1.2 DXSAS ............................................................................................................................... 66 5.1.3 Efekty a HLSL.................................................................................................................... 66 5.1.4 Efekty a shadery mimo DirectX API .................................................................................. 67 5.2 VÝVOJOVÉ PROST EDÍ ............................................................................................................... 67 5.2.1 FXComposer 1.6 ................................................................................................................ 69 5.3 STRUKTURA KÓDU...................................................................................................................... 70 5.4 IMPLEMENTA NÍ ZAJÍMAVOSTI ................................................................................................... 73 5.4.1 Vertex shader..................................................................................................................... 73 5.4.2 Fragment shader................................................................................................................ 74

3

5.4.3 Geometrické výpo ty.......................................................................................................... 75 5.5 EXPERIMENTÁLNÍ DATA A PRÁCE S NIMI..................................................................................... 75 5.5.1 Implementace šumu a turbulence....................................................................................... 76 5.5.2 Práce s objemovými daty ................................................................................................... 76 5.6 TESTOVÁNÍ A VÝSLEDKY ............................................................................................................ 77 5.7 DISKUSE ..................................................................................................................................... 80 ZÁV R .............................................................................................................................................82 6.1 SM

RY DALŠÍ PRÁCE

.................................................................................................................. 83

4

Seznam obrázk Obrázek 1.1: Schéma zobrazovacího etezce............................................................. 17 Obrázek 1.2: Schéma architektury G70 ..................................................................... 19 Obrázek 2.1: Nejednozna né napojení iso ar ............................................................ 26 Obrázek 2.2: Konfigurace v algoritmu Marching Cubes.. ......................................... 27 Obrázek 3.1: Situace p i pr chodu sv tla objemem................................................... 32 Obrázek 3.2: Použití pohlcujícího modelu ší ení sv tla............................................. 33 Obrázek 3.3: Použití vyza ujícího modelu ší ení sv tla............................................. 34 Obrázek 3.4: Použití pohlcujícího a vyza ujícího modelu ší ení zá ení .................... 36 Obrázek 3.5: Ukázka sm rovosti HG aproximace pro c = 0,5 .................................. 39 Obrázek 3.6: Situace pro modelování vržených stín ................................................ 39 Obrázek 3.7: Srovnání efektu útlumu sv tla .............................................................. 41 Obrázek 3.8: Princip modelu podle Kniss et al.......................................................... 42 Obrázek 3.9: Výsledky empirického modelu............................................................. 43 Obrázek 3.10: Výsledky mapování podle Sabelly. .................................................... 44 Obrázek 3.11: Orientace vzorkovacích polygon ...................................................... 46 Obrázek 3.12: Zkosení p i rovnob žném promítání. ................................................. 48 Obrázek 3.13: Zkosení p i perspektivním promítání. ................................................ 49 Obrázek 4.1: Generování paprsku ve dvou pr chodech. ........................................... 56 Obrázek 4.2: Artefakty metody dvou pr chod ......................................................... 58 Obrázek 5.1: FXComposer......................................................................................... 69 Obrázek 5.2: Scéna ze [Stegmaier et al 05], odtud p evzato. Scéna HGAttenuated.. 78 Obrázek 5.3: Testovací scéna HG (vlevo), Testovací scéna Emission (vpravo) ....... 79

5

Seznam tabulek Tabulka 5.1: Výsledky p i konfiguraci 1 ................................................................... 78 Tabulka 5.2: Výsledky p i konfiguraci 2 ................................................................... 78 Tabulka 5.3: Výsledky p i konfiguraci 3 ................................................................... 78

6

Seznam výpis Výpis 5.1: Syntaxe parametru efektu ......................................................................... 64 Výpis 5.2: Použití anotací a sémantiky ...................................................................... 64 Výpis 5.3: Skript DXSAS v0.8 .................................................................................. 66 Výpis 5.4: Použití HLSL a shader assembleru........................................................... 66 Výpis 5.5: Struktura efekt ........................................................................................ 71 Výpis 5.6: Zápis dvou pr chodu a jejich spolupráce ................................................. 72 Výpis 5.7: Hlavní vertex shader................................................................................. 73 Výpis 5.8: Hlavní fragment shader ............................................................................ 74 Výpis 5.9: Výpo et vztahu (4.2) ................................................................................ 75 Výpis 5.10: Výpo et pr niku interval ...................................................................... 75 Výpis 5.11: Použití 3D textur .................................................................................... 76 Výpis 5.12: Metoda SampleVolume ...................................................................... 77

7

Název práce: Osv tlení na GPU Autor: Lukáš Maršálek Katedra (ústav): Kabinet software a výuky informatiky Vedoucí diplomové práce: RNDr. Josef Pelikán e-mail vedoucího: Josef.Peliká[email protected] Abstrakt: Cílem práce je prozkoumat možnost implementace zobrazování objemu na GPU. Zobrazováním objemu se rozumí metody, jejichž vstupními daty nejsou p ímo povrchové reprezentace t les, ale data zadaná trojrozm rnou m ížkou skalárních nebo vektorových veli in. Jejich tradi ními vlastnostmi jsou na jedné stran schopnost vykreslovat komplexní proceduráln definovaná t lesa a na stran druhé obtížné a pomalé zobrazování. Proto nem ly tyto metody v oblasti zobrazování v reálném ase velké uplatn ní. Výkon a flexibilita grafických systém v b žn dostupných stolních po íta ích narostly v sou asné dob natolik, že umož ují alespo experimentální implementaci t chto metod. V úvodu je nejprve vytvo en kontext a vyty en cíl práce. Poté jsou zevrubn prezentovány dosavadní p ístupy k problematice zobrazování objemu a je diskutována jejich vhodnost pro implementaci na GPU. Zahrnut je také teoretický základ optických model . Další ásti jsou v novány podrobn navržené zobrazovací metod a zp sobu a úskalím její implementace na GPU. Práci uzavírá otestování implementované metody, zhodnocení dosažených výsledk a nakonec je uveden nástin dalších sm r vývoje. Klí ová slova: GPU, zobrazování objemu, shader, vrhání paprsku, optické modely

8

Title: Lighting using GPU Author: Lukáš Maršálek Department: Department of Software and Computer Science Education Supervisor: RNDr. Josef Pelikán Supervisor’s e-mail address: [email protected] Abstract: The goal of this work is to examine the possibility of implementing a volume rendering method entirely on GPU. By the term volume rendering I mean methods which take as an input treedimensional scalar or vector grid data, rather than a classical surface representation. Traditional characteristics of these methods is the capability to render highly complex, possibly procedurally defined objects on one side and high computational cost on the other side. It was that computational cost which in the past prevented their widespread use in real-time rendering. However sheer computational power and flexibility of current widely available graphical systems has reached levels which allow for at least experimental implementation of these methods. First in the introduction the background and goals of this work are presented. Next current and past approaches to volume rendering are presented in detail and also their suitability for GPU implementation is discussed. A theoretical foundation for the optical models is also given. Further chapters are devoted in detail to the suggested method and to the means of its implementation on GPU. The work is closed by the testing of the method, analysis of the achieved results and finally further research directions are suggested. Keywords: GPU, volume rendering, shaders, ray-casting, optical models

9

Kapitola 1

Úvod Cílem této kapitoly je podat úvod do problematiky, kterou se práce zabývá, nebo která má vliv na prezentované výsledky a postupy. Nejprve se v §1.1 seznámíme s oblastí zobrazování objemových dat, k emu se metody z této oblasti používají a jak je lze obecn klasifikovat. §1.2 navazuje p ehledem základní posloupnosti krok , kterou musí výpo etní systém p i zobrazování objemu provést. Princip m zobrazování v reálném ase a zp sob m m ení výkonu a kvality zobrazovacích algoritm je v nován §1.3. V §1.4 je shrnuta platforma sou asných b žn dostupných grafických ešení pro stolní po íta e, která tvo í implementa ní prost edí pro tuto práci. Kapitolu uzavírá vyty ení cíl práce v §1.5 a rozvrh len ní textu v §1.6

1.1 Zobrazování objemu 1.1.1 Principy a použití Zobrazováním objemu nazýváme souhrnn metody p evád jící data z vícerozm rných skalárních i vektorových m ížek na dvourozm rnou pr m tnu [Owen 99]. Od tradi ního zobrazování objekt uložených v povrchové reprezentaci se liší v mnoha aspektech. Zp sob, jakým jsou data reprezentována, jejich charakter a velikost a také cíle jejich vizualizace, jsou všechno p í iny návrhu a implementace odlišných zobrazovacích technik. Nejb žn ji se setkáváme s t írozm rnými m ížkami, které reprezentují hodnoty m ené nebo vypo ítané veli iny v prostoru. asté jsou také ty rozm rné m ížky reprezentující danou veli inu v prostoru a ase. Podle zdroje dat se také velmi liší druh m ížek, ve kterých jsou data definována [Elvins 92]. Lze se setkat s kartézkými m ížkami, kde bu ky jsou identické, osov orientované krychle. Obecn jší jsou pravidelné a rovnob žné m ížky, kde bu ky tvo í identické osov orientované kvádry, respektive osov orientované kvádry ne nutn stejných rozm r . Nejobecn jší jsou pak strukturované, blokov strukturované a nestrukturované m ížky. Zdroje dat pocházejí ze dvou základních oblastí. Jedná se o v deckou i pr myslovou vizualizaci a fotorealistické zobrazování.

10

Kapitola 1: Úvod P íkladem z první oblasti mohou být medicínská data získaná z MRI (Magnetic Resonance Imaging), CT (Computed Tomography) i PET (Positron Emission Tomography). Tato data jsou skalární a jsou zaznamenávána zpravidla do t írozm rné rovnob žné m ížky. Vícerozm rná data jsou produkována nap íklad v meteorologii, kde rozm r bývá i v ádu desítek. asto je však k t mto dat m p istupováno jako ke skalárním a je zobrazována najednou vždy jen jedna veli ina. Odv tvím, kde jsou produkována skute n vektorová data, typicky na ty rozm rné m ížce, jsou pr myslové po íta ové simulace jako CFD (Computational Fluid Dynamics). Ve v decké a pr myslové vizualizaci se zobrazování objemu používá zejména pro získání lepšího náhledu na sledovaná data. Jde nap íklad o jejich prostorové rozložení, pozice extrém a zp soby p echodu mezi nimi i množství a velikost oblastí se stejnými hodnotami. P i zobrazování dat v ase bývá navíc snahou zachytit trend zm ny dat, jako nap íklad sm r i druh proud ní. Ve fotorealistickém zobrazování jsou pomocí t í nebo ty rozm rných skalárních dat modelovány p írodní fenomény jako mlha, mraky, ohe a kou nebo také objekty s extrémn složitým povrchem. Cílem zde bývá dosažení maximální v rohodnosti napodobovaného fenoménu. Velkým p ínosem n kterých metod zobrazování objemu je možnost v rn modelovat fyzikální vlastnosti pr hledných a pr svitných objekt jako je útlum, rozptyl a lom sv tla. V obou uvedených oblastech je velkou výhodou, pokud lze dosáhnout interaktivních rychlostí zobrazování. P i zobrazování prostorových dat ve v decké a pr myslové vizualizaci interaktivní rychlost umož uje nap íklad efektivn nastavovat a m nit parametry mapování barev i prohlížet data z r zných pozic a vzdáleností. V oblasti fotorealistického zobrazování se pak otevírají možnosti využít zobrazovaných objekt ve virtuálních prost edích i ve hrách a nejen ke generování statických snímk a neinteraktivních videí. Tato práce se zam uje na oblast zobrazování skalárních dat definovaných na t írozm rné rovnob žné m ížce. Jak uvidíme v následujících dvou kapitolách, bylo vyvinuto mnoho r zných p ístup k zobrazování objemu. Lze však i p esto nalézt n kolik kritérií, podle kterých se tyto metody klasifikují.

1.1.2 Klasifikace podle zp sobu promítání Tento zp sob klasifikace metod pro zobrazování objemu je velmi astý. D lí algoritmy podle toho, jak promítají objemová data na pr m tnu, na metody hledající povrch a na p ímé zobrazovací metody. Metody hledající povrch Tyto metody jsou shodn založeny na principu hledání míst v objemu, kde hodnoty nabývají zadaného prahu (isoploch) a vizualizaci t chto míst pomocí standardních polygonálních ploch i povrchových bod a již známých algoritm pro jejich zobrazování. Obecn jsou tyto metody velmi rychlé, jakmile je jednou hledaný povrch zkonstruován. Nevýhodou jsou n které artefakty, jako nap íklad falešné rysy povrchu nebo nep esnosti p i zachycování drobných detail a v tvení povrchu. Tyto algoritmy mají také omezené použití na objekty, u nichž je p irozené isoplochy hledat a zobrazovat. Pro „amorfní“ objekty jako mraky a ohe jsou tyto metody obecn nevhodné. 11

Kapitola 1: Úvod

P ímé zobrazovací metody Jiný p ístup používají takzvané p ímé zobrazovací metody. Jak název napovídá, snaží se tyto metody p ímo promítnout objemová data na pr m tnu bez použití polygonálních objekt . Jejich obecnými vlastnostmi jsou schopnost generovat vysoce kvalitní výstup, ovšem za cenu zna né výpo etní náro nosti. T mto metodám byla a je v nována velká pozornost, nebo na rozdíl od metod hledajících povrch, umož ují zobrazit objem jako celek a s pomocí simulace pr chodu sv tla objemem zobrazovat jeho d ležité i požadované vlastnosti.

1.1.3 Klasifikace podle dominantního pr chodu Jiným kritériem pro klasifikaci metod zobrazování objemu je dominantní pr chod. Metody lze podle tohoto kritéria op t rozd lit na dv t ídy. Objemov orientované metody Primární smy kou pro tyto algoritmy je pr chod p es objemová data. Algoritmus projde každou bu ku objemu a provede s ní n jakou operaci. V této t íd lze nalézt jak algoritmy hledající povrch, tak p ímé zobrazovací metody. Obrazov orientované metody U t chto metod naopak p evládá pr chod p es pixely výsledného obrazu. Tyto jsou procházeny jeden za druhým a pro každý je ur ena jeho barva. Pro ur ení barvy je tedy nutné nalézt bu ky objemu, které mají na daný pixel vliv. Obrazov orientované metody najdeme pouze mezi p ímými zobrazovacími metodami.

1.2 Struktura zobrazovacího systému Jak bylo e eno v minulém odstavci, metody pro zobrazování objemu jsou velmi rozmanité a lze se setkat se zcela odlišnými p ístupy. Ovšem stejn jako lze, i p es tuto rozmanitost, metody klasifikovat, lze také obecn ur it posloupnost krok , kterou je nutné p i zobrazování objemu provést. V tšina dále popsaných metod, v etn metody prezentované v této práci, implementuje podmnožinu níže uvedených krok . Ostatní bu to zjednodušuje pomocí dodate ných p edpoklad nebo p edpokládá, že jsou provedeny mimo vlastní metodu. Obdobnou klasifikaci, jako je uvedena níže, lze nalézt nap . v [Elvins 92]. Práci s objemovými daty, od jejich získání až po vytvo ení kone ného obrazu, lze shrnout do následujících krok : • Po ízení dat • Úprava dat do podoby požadované pro zobrazování • Klasifikace dat • Promítnutí dat na pr m tnu • Zobrazení pixel pr m tny Po ízení dat (s1) V tomto kroku jsou nam ena nebo spo ítána vlastní objemová data. P itom již dochází k prvnímu vzorkování. Veli ina i funkce je m ícím za ízením nebo

12

Kapitola 1: Úvod výpo tem vzorkována. Všechny metody pro zobrazování objemu p edpokládají, že tento krok byl proveden korektn . Tedy zejména, že data byla navzorkována s frekvencí nad Nyquistovým limitem a lze je proto korektn rekonstruovat. Je samoz ejmé, že tento požadavek nelze vždy dodržet, nebo nelze obecn zaru it frekven ní omezenost m ených dat. Úprava dat do podoby vhodné pro zobrazování (s2) Spo ítaná i nam ená data nemusejí být p ímo vhodná pro zobrazování nebo je žádoucí na nich provést p ed zobrazením n jaké korekce. Typické provád né kroky bývají ekvalizace histogramu, úprava kontrastu a sv tlosti i odstran ní šumu. Pokud jsou nam ená data v nestrukturovaných m ížkách i mají nesymetrické rozm ry, bývají asto p epo ítána do symetrických kartézkých nebo rovnob žných m ížek. To zahrnuje interpolaci dat v nových uzlových bodech i tvorbu dodate ných ez . Nej ast ji se používají pomalé, ale kvalitní interpolace, jako nap íklad trikubická nebo radiální. Zejména v medicínských aplikacích se v tomto kroku mohou také kombinovat r zné datové množiny. Tento proces zahrnuje jejich registraci (tedy proces zarovnání odpovídajících si bod v obou množinách) a kombinaci hodnot do výsledné množiny. Klasifikace dat (s3) P edchozí dva kroky bývají stejné pro všechny metody zobrazování objemu. Klasifikace dat je první krok, kde se metody za ínají odlišovat. Klasifikací dat se rozumí mapování vstupních hodnot na veli iny používané p i zobrazování. V metodách hledajících povrch se tento krok skládá z volby prahu, pro který je hledán povrch a n kdy také z volby barvy, kterou je tento povrch zobrazován. V n kterých aplikacích lze zobrazovat v jednom obrázku více povrch pro více prahových hodnot a barevn je odlišovat. V metodách p ímého zobrazování objemu, klasifikace dat typicky sestává z p i azení pr hlednosti a barvy pro každou z možných vstupních hodnot. V n kterých aplikací je také do klasifikace zahrnuta pozice vzorku. Hustota a barva jsou tak modifikovány nejen podle hodnoty vzorku, ale i podle jeho prostorových sou adnic. V aplikacích ve fotorealistickém zobrazování bývá také provád n speciální krok, který simuluje ší ení sv tla ze sv telných zdroj objemem. Nap íklad pokud objem napodobuje mraky, je nutné pro každý sv telný zdroj vy ešit rovnice pro ší ení zá ení v prostoru (viz §3.2) a pro každou bu ku objemových dat zaznamenat množství, pop ípad barvu dopadajícího sv tla. N kdy bývá tento krok provád n sou asn s promítáním dat na pr m tnu. Je to zejména v p ípad , kdy ne ešíme sekundární rozptyl sv tla objemu a po ítáme pouze p ímé p ísp vky ze sv telných zdroj . I v takovém p ípad ale bývá efektivn jší provést tyto výpo ty v klasifika ním kroku a opakovat je pouze tehdy, pokud se sv telné podmínky zm ní. Promítnutí dat na pr m tnu (s4) Tento krok je zásadním momentem celé metody. Co p esn je provedeno za operace, se zna n liší od metody k metod a bude to podrobn probráno u každé prezentované metody zvláš . Obecn lze íci, že krom vlastního promítnutí objemových dat na pr m tnu, tedy ur ení jaké bu ky mají vliv na jaké pixely, se v tomto kroku provádí také kompozice a ur ení viditelnosti a bývají aplikovány prost edky antialiasingu.

13

Kapitola 1: Úvod

Zobrazení pixel pr m tny (s5) Záv re ný krok je op t typicky stejný u v tšiny metod. Liší se spíše podle implementa ního prost edí. Pokud je metoda implementována p ímo v software, je pot eba uložená barevná i šedotónová data p enést z hlavní pam ti do zobrazovacího za ízení a vydat pot ebné instrukce k jejich zobrazení. Pokud pracujeme na hardwarové architektu e, bývá o tento krok asto již postaráno, nebo obrazová data jsou zapisována p ímo do obrazové pam ti, odkud jsou automaticky zobrazována na výstupním za ízení.

1.3 Zobrazování v reálném ase Zobrazování v reálném ase se uplat uje samoz ejm nejenom v oblasti zobrazování objemu. Je to velmi široké a aktuální téma. Hlavní snahou je prezentovat grafické informace uživateli takovou rychlostí, aby m l pocit okamžité odezvy na své akce, i byl schopen vnímat plynulý pohyb virtuálních objekt . V oblasti teorie algoritm bylo formalizováno n kolik postup pro m ení rychlosti algoritm a jejich srovnávání na teoretické bázi. Pojem „v reálném ase“ je z toho pohledu velmi vágní a jeho p esný význam se typicky odvozuje až od p íslušné aplika ní oblasti. Je to zejména proto, že se snažíme m it spokojenost uživatele s n jakým rysem a je závislé na druhu aplikace, co p esn tyto pocity ur uje. Nicmén b hem asu se vyvinulo n kolik m ítek, která jsou obecn p ijímána jako ukazatel rychlosti zobrazování. Nejb žn ji používanými m ítky, kterých se budeme držet i v této práci, je hodnota snímkovací frekvence a její konzistence. Snímkovací frekvencí (dále fps z anglického frames per second) rozumíme po et snímk , který je systém schopen prezentovat uživateli za jednu vte inu. Tato hodnota m že být zna n ovlivn na zp sobem, jakým se pracuje se zobrazovacím za ízením. Lze ji chápat jako po et snímk , které je systém nebo algoritmus skute n schopen dodat za vte inu nebo jako po et, kolikrát se obrázek na monitoru skute n objeví. K rozdílu mezi první a druhou interpretací dojde, pokud systém používá metodu double-bufferingu (nebo i více buffer ) a eká na synchronizaci se zobrazovacím za ízením. V takovém p ípad nem že hodnota fps p esáhnout vertikální obnovovací frekvenci zobrazovacího za ízení (v anglické terminologii n kdy uvád né jako refresh rate). V této práci je používán první zp sob. Konzistencí snímkovací frekvence rozumíme schopnost algoritmu i systému udržet hodnotu fps konstantní v ase. V mnoha studiích (nap . [Yuan et al. 97]) se ukazuje, že krom vlastní maximální hodnoty fps je d ležitá práv její konzistence. Typické problémy, kterými uživatelé trpí, pokud není hodnota fps konzistentní, jsou neschopnost provád t zadané úkoly ve virtuálním prost edí a v n kterých p ípadech i nap . nevolnost i ztráta zrakov -pohybové koordinace. Je z ejmé, že dv výše uvedená m ítka ur itým zp sobem vypovídají o rychlosti zobrazovacích algoritm , ale jejich vztah ke skute né odezv systému, tedy dob mezi akcí uživatele a jejím projevením se na grafické informaci, je ovlivn n n kolika dalšími faktory. Jde zejména o zpožd ní, které nastává mezi akcí uživatele a p edáním zm n ných parametr zobrazovacímu systému. Toto zpožd ní je asto zp sobeno za ízeními sledujícími akce uživatele (složit jší polohovací systémy,

14

Kapitola 1: Úvod head-mounted nebo head-coupled displays apod.) a také interpretací této akce a jejím p evedením na parametry zobrazovacího systému. Nyní máme tedy rozumné obecné m ítko rychlosti zobrazovacího algoritmu. Zbývá ur it, jaká hodnota fps je p ijatelná pro konkrétní ú ely. Typicky je tato hodnota zjiš ována experimentáln . Uživatel m je p edložen n jaký úkol a poté je informace zobrazována s r znými hodnotami fps a je sledována reakce uživatel . Nejb žn ji je cílová hodnota fps ur ena podle vnímání plynulosti pohybu. P esto, že je op t závislá na uživateli, typická minimální hodnota je 72-75 fps pro za ízení a algoritmy, které neaplikují n kterou z metod pro zvýšení plynulosti pohybu, jako nap . rozmazání pohybem (motion blur). V oblasti po íta ových her i simulací se tyto metody aplikují mén asto, nebo zhoršují vnímání detail a p esné pozice rychle se pohybujících objekt . asto je hodnota fps také studována v souvislosti s prost edími pro virtuální realitu. Konkrétn se schopností uživatel provád t n jaké úkony, jako nap íklad p enos i zam ení t les ve virtuálním sv t . Typické m ené hodnoty se pohybují v rozmezí 10 až 30 fps. Studie, jako [Meehan et al. 02] ukazují, že zvyšující se hodnota fps dává uživateli lepší pocit p i pobytu ve virtuálním prost edí. Nízké hodnoty okolo 10 fps dávají asto nejasné výsledky, které mají tendenci se lišit podle uživatel . Hodnoty jsou zna n nižší, než u vnímaní plynulosti pohybu, nebo typické úkoly dávané v uvedených studiích jsou jednodušší, než nap . v po íta ových hrách a nezahrnují rychle se pohybující objekty. V oblasti zpracování videa se studie zam ují na to, jak uživatelé hodnotí kvalitu p enosu. Typickou požadovanou hodnotu je 24 až 30 fps. N které studie [McCarthy et al. 04] ovšem nazna ují, že posta ují i hodnoty 6 fps, tedy daleko nižší, než se b žn p edpokládá. Zde je ovšem kladen d raz na celkový dojem z pasivního pozorování a není vyžadována žádná aktivita uživatel . Jiní auto i [Lastra et al. 95], zabývající se programovatelným stínováním, považují za interaktivní hodnotu 30 až 60 fps.

1.4 Grafický hardware V této kapitole se zam íme na principy, jak se programuje sou asný konzumní grafický hardware. Cílem této kapitoly není podat vy erpávající popis stávajících architektur, ale poukázat na základní principy a rozdíly od programování pro obecné procesory. Historie Po velmi dlouhou dobu byl hardware specializovaný na grafické operace doménou velmi drahých pracovních stanic, simulátor i super-po íta , p evážn pod kontrolou firmy SGI. Postupem asu se ovšem za íná objevovat grafický hardware v b žn dostupných stolních po íta ích. Tento trend za al v roce 1996 p íchodem karet Voodoo 1 od firmy 3Dfx a v letech 1997 a 1998 uvedením prvních karet od firmy Nvidia Riva 128 a Riva TNT. Tyto ranné grafické akcelerátory byly zam eny zejména na urychlení práce s texturami v multimédiích a v po íta ových hrách. V dalších letech se rozsah innosti, kterou vykonává hardware, za íná rozši ovat. Objevují se první hardwarov urychlované transformace a osv tlovací výpo ty (souhrnn nazývané T&L: Transform&Lighting) v ad karet Nvidia 15

Kapitola 1: Úvod GeForce 256, které byly uvedeny na trh v roce 1999. Vývoj pokra oval v roce 2000 adami karet Nvidia GeForce 2 a ATI Radeon. Tyto karty p inášejí další zvýšení výkonu a flexibility v oblasti texturování a objevují se první programovatelné vertex shadery. Skute ný zlom nastává ovšem v roce 2001 p edstavením standardu Microsoft DirectX 8.0 a adou karet Nvidia Geforce3 a ATI Radeon 8500. Ve specifikaci DirectX 8.0 jsou standardizovány první verze vertex a fragment shader a za íná tak éra programovatelného stínování na konzumních po íta ích. Tyto karty lze také ozna it jako první GPU (Graphics Processing Unit). Obsahují totiž skute né procesory, které jsou schopné vykonávat i když zatím jen velmi omezený kód psaný programátorem ve speciálním jazyku, který je podobný assembleru. Je to práv tento jazyk, který DirectX 8.0 standardizoval. Poté nastává velký rozvoj programovatelného stínování. V roce 2002 p ichází nová specifikace Microsoft DirectX 9.0 s ní další rozší ení možností, zejména v oblasti flexibility programovacího jazyka. Za ínají se také objevovat první vysokoúrov ové programovací jazyky pro práci s GPU, jako jsou Cg a HLSL. V roce 2003 se stávají karty podporující DirectX 9.0 skute n dostupnými pro každého. Ke konci roku 2004 spat ila sv tlo sv ta specifikace Microsoft DirectX 9.0c a v ní definovaný Shader Model 3.0. Zárove se objevuje první ada karet, která tuto specifikaci pln podporuje a to Nvidia GeForce 6. Shader Model 3.0 p inesl nové možnosti, zejména z programátorského hlediska. Umož uje totiž používat ve fragment shaderech skute né podmín n ukon ené smy ky a tak rozši uje výrazové možnosti, stejn jako škálu implementovatelných algoritm . Shader Model 3.0 p inesl samoz ejm ješt daleko více novinek, ovšem výše uvedené dynamické smy ky jsou zásadním p ínosem pro tuto práci. Je to totiž práv platforma karet Nvidia GeForce 6 a specifikace Microsoft DirectX 9.0c, pro niž je cílena metoda navrhovaná v této práci. V polovin roku 2005 se objevuje ješt nová ada karet Nvidia GeForce 7, která p ináší extrémní rychlost pro t ídu program implementovaných podle standardu DirectX 9.0c. Fixní a programovatelný zobrazovací et zec S trochou nadsázky lze íci, že než se objevil specializovaný grafický hardware, byl celý zobrazovací et zec programovatelný. Veškerý kód byl tvo en v obecných programovacích jazycích a spoušt n na b žných procesorech. Výsledkem t chto výpo t byla matice hodnot jednotlivých pixel výsledného obrazu. S postupem asu, jak bylo shrnuto v p edcházející sekci, za al být vyráb n specializovaný hardware, který vykonával n které funkce zobrazovacího procesu. Tento hardware byl stav n z d vod urychlení grafických výpo t . Z konstruk ních d vod byl ovšem velmi omezený v rozsahu funkcí, které zastával. Až do p íchodu GPU nebylo možné tento hardware programovat v klasickém slova smyslu pomocí n jakého programovacího jazyka. Bylo pouze možné p epína i nastavovat chování n kterých jeho ástí. Nap íklad ve fázi osv tlovaní byl v hardware implementován pouze jeden algoritmus pro aproximaci osv tlení ve vrcholech. Bylo možné nastavit parametry tohoto algoritmu, ale nikoliv jej zm nit. Takto pracující zobrazovací et zec za al být ozna ován jako fixní et zec.(Fixed-Function pipeline). Jak se hardware vyvíjel dále, za al být systém práce s p epína i p íliš nep ehledný a nemotorný. Nebo již padla i technická omezení, byly n které ásti

16

Kapitola 1: Úvod fixního et zce nahrazeny programovatelnými jednotkami. Pro takto zkonstruovaný zobrazovací et z se vžil název programovatelný et zec (Programmable pipeline). Obrázek 1.1 ukazuje schéma zobrazovacího et zce. Modré ásti jsou spole né pro fixní i programovatelný et zec. Šedé ásti pat í do fixního et zce a v programovatelném et zci jsou nahrazeny zelenými ástmi.

Obrázek 1.1: Schéma zobrazovacího etezce

Nejprve jsou do zobrazovacího et zce dodána geometrická data.Ta mohou být ve form polygonální sít nebo jako r zné druhy plát i povrchy vyšších ád . V následujícím kroku jsou tato primitiva zpracována, p esn ji jsou vždy p evedena na trojúhelníkovou sí . Výsledem tohoto kroku je seznam unikátních vrchol s atributy (nap . pozice, normála, texturovací sou adnice atd.) a informace o tom, které vrcholy tvo í které trojúhelníky. V následující fázi jsou na každý vrchol aplikovány r zné transformace a m že být proveden výpo et osv tlení. Ve fixním et zci byl sled transformací a osv tlovacích výpo t p esn ur en a bylo pouze možné nastavit p íslušné transforma ní matice a parametry osv tlovacího modelu. V programovatelném et zci je tento krok nahrazen zpracováním, programátorem definovaného, programu. Tento program se nazývá vertex shader. Jeho vstupem je práv jeden vrchol s atributy a výstupem minimáln pozice v sou adném systému promítací roviny (clipspace position). Vertex shader m že produkovat ješt adu dalších dat. Zásadním p edpokladem je, že vertex shader zpracovává vždy práv jeden vrchol a nemá k dispozici informace o ostatních vrcholech, ani o topologii trojúhelníkové sít . Nelze tedy nap íklad p ímo získat informaci o sousedních vrcholech nebo vytvo it nový vrchol. Dále jsou transformovaná data o ezána podle pohledového objemu a potencionáln i podle dalších, uživatelsky definovaných rovin. Je také provedena

17

Kapitola 1: Úvod transformace do okna (viewport transformation) a výsledné trojúhelníky jsou v sou adném systému okna rasterizovány. Výsledkem p edchozí fáze jsou tzv. fragmenty. V n kterých kontextech bývá zam ován pojem fragment a pixel. Fragment je výsledem rasterizace a jedná se o pozici v sou adném systému okna spolu s množstvím dalších atribut . D ležitým rozdílem je, že tato pozice nemusí být celo íselná a asto je se sub-pixelovou p esností. Do výsledné barvy jednoho pixelu tak m že p isp t i n kolik fragment (nap . p i aplikaci technik anti-aliasingu). Atributy fragmentu jsou interpolovány bilineární interpolací z hodnot ve vrcholech trojúhelníku, odkud byl fragment vygenerován. Ve fixním et zci je nyní ve fázi Kombinace textur ur ena barva fragmentu (ješt ne ale finální barva) jako kombinace primární barvy a barev z textur, které jsou nalezeny podle interpolovaných texturovacích sou adnic. Po et textur, které je možné v jednom pr chodu aplikovat na jeden fragment rostl s vývojem grafického hardware. Stejn tak se zdokonalovaly zp soby, jak lze tyto textury kombinovat do výsledné barvy. Mechanismy práce byly stejné jako všude jinde ve fixním et zci, tedy existovala sada p eddefinovaných operací pro kombinaci textur a p epína i bylo možné je m nit a nastavovat jejich parametry. V programovatelném et zci je celá tato fáze nahrazena zpracováním programátorem definovaného kódu, tzv. fragment shaderu.(lze se setkat také s ozna ením pixel shader, nap . v [DirectX9.0c 05]). Tento kód má na vstupu op t práv jeden fragment, spolu s jeho atributy a výstupem je barva fragmentu a v n kterých architekturách také hloubka fragmentu. Op t nelze fragmenty vytvá et, ani p ímo odstra ovat. Nelze také m nit pozici fragmentu. Záv re ným stádiem je ur ení barvy jednotlivých pixel . V tomto stádiu dochází ješt k ad dalších operací jako ur ení barvy mlhy, aplikaci alfa a stencil test a v neposlední ad také test hloubky a aplikace technik anti-aliasingu. Principy programovatelného stínování Programovatelným stínováním nazýváme práci s programovatelným et zcem. Práce v tomto výpo etním prost edí se velmi liší od programování pro obecné procesory. Zásadním rozdílem je, že nepíšeme program, který na vstupu dostává objekty ve scén a na výstupu má matici pixel výsledného obrazu, ale tvo íme dva odd lené programy, vertex shader a pixel shader. Pro správné a efektivní používání vertex a pixel shader je nutné porozum t blíže zp sobu, jak je programovatelný et zec uvedený v p edchozí sekci implementován. Obrázek 1.2 ukazuje schéma nejnov jší ady karet firmy Nvidia, p esn ji architekturu G70 používanou v kartách ady GeForce 7800 GTX. Na schématu je vid t, že programovatelných jednotek, starající se o zpracování vertex a pixel shader , je velké množství. Konkrétn v této architektu e se jedná o 8 vertex jednotek a 24 fragment jednotek. Ve spodní ásti schématu vidíme také 16 tzv. ROP (Render Output Pipeline), což jsou jednotky, které se starají o operace v Obrázek 1.1 ozna ené jako Vykreslení pixel . P i programování vertex a pixel shader tedy pracujeme s masivn paralelní SIMD architekturou. Takováto masivní paralelizace je umožn na omezeními na vstupy a výstupy vertex a fragment shader , jak byly uvedeny v p edchozí sekci. Jedná se hlavn o p edpoklad, že vertex shader zpracovává pouze jeden vrchol bez závislosti na ostatních. To samé platí o fragment shaderu a fragmentu, který zpracovává.

18

Kapitola 1: Úvod

Obrázek 1.2: Schéma architektury G70

Aniž by bylo nutné zabíhat do úplných detail , lze formulovat n kolik základních pravidel a odlišností pro programovatelné stínování: • Výstupy vertex shaderu jsou interpolovány do vstup fragment shaderu, aniž by grafický hardware vždy znal jejich sémantiku. Vertex a fragment shadery tedy na sebe „navazují“ a programátor si m že p edávat mezi nimi vícemén libovolná data. • Vertex shader je spušt n na každý vrchol zcela samostatn s vlastním kontextem. • Fragment shader je spušt n na každý fragment zcela samostatn s vlastním kontextem. Po et zpracovávaných fragment m že být obrovský v ádu stovek milión na jeden snímek. • Stále existují ásti zobrazovacího et zce, které nelze p ímo programovat a tak je t eba zajistit jejich správné nastavení pro spolupráci s vertex a fragment shadery. • Vertex a fragment jednotky jsou specializované vektorové procesory, které mají speciální instruk ní sadu p izp sobenou pro grafické operace. To znamená, že operace až na 4 složkových vektorech trvají stejn dlouho jako operace na skalárech a existují speciální instrukce, jako nap íklad instrukce dp4 provád jící skalární sou in dvou 4 složkových vektor nebo instrukce lit, která p ímo provádí výpo et jednoduchého osv tlovacího modelu.

19

Kapitola 1: Úvod • Vertex a fragment shadery nejsou samostatné jednotky. Jinými slovy napsáním vertex a fragment shader práce nekon í. Pro jejich zavedení a spušt ní v n jakém grafickém engine je pot eba ješt nastavit neprogramovatelné ásti grafického et zce, implementovat p enos pot ebných parametr , zajistit kontrolu pot ebné verze hardwarového profilu a v neposlední ad ur it pro jakou geometrii se mají tyto vertex a fragment shadery používat. • Nelze p ímo iniciovat spušt ní vertex nebo fragment shaderu. Vertex a fragment shadery jsou spoušt ny automaticky grafickým hardware jako reakce na existenci vrcholu nebo fragmentu. Pokud neexistuje žádný relevantní vrchol nebo fragment, vertex a fragment shadery se v bec neprovedou. Celý zobrazovací et zec tedy spustíme zasláním geometrie z aplikace. Je ješt n kolik subsystému grafického hardware, o kterých jsem se v této kapitole nezmínil. Jedná se p edevším o pam ový subsystém, který má také svá specifika a je op t optimalizován pro grafické operace, zejména výb r hodnot z textur. Další podrobné informace o hardwarové architektu e lze nalézt nap íklad v [AnandTech]. Detailní popis zobrazovacího et zce je uveden v [DirectX9.0c 05] a popisy interface lze nalézt v [DirectX9.0c 05, OpenGL 2.0 04].

1.5 Cíle práce Cílem této práce bylo navrhnout a implementovat metodu pro zobrazování objemu, která by spl ovala následující kritéria: Rychlost zobrazovaní (c1) Metoda by m la být použitelná pro zobrazování v reálném ase. Snahou bylo dosáhnout maximální snímkovací frekvence m ené ve snímcích za vte inu. P i tvorb práce byl brán ohled i na konzistenci snímkovací frekvence. Její p ímé m ení jsem ovšem neprovád l, nebo použité experimentální prost edí to p ímo neumož uje a neexistovala p im en sch dná cesta, jak toto prost edí rozší it. Kombinace s jinými zobrazovacími metodami (c2) Ve v tšin reálných aplikací vyvstává problém, jak zobrazovat najednou objemová data a ostatní, typicky polygonáln reprezentované objekty [Levoy 90]. Je proto výhodné, pokud metoda umí bu zobrazovat jak objemová, tak polygonální data nebo je schopná v jednom snímku zobrazit r zné skupiny objekt r znými metodami. Implementace výhradn uvnit shader (c3) Výhodou používání shader krom jejich rychlosti je fakt, že zat žují hlavní procesor po íta e jen minimáln , a tak jej uvol ují pro jiné výpo ty. To je velmi d ležité pro zobrazovací metody, nebo typicky v reálných aplikací tvo í zobrazování jen ást výpo t , které je t eba provád t. Zárove je to velmi výhodné vzhledem k požadavku (c2), nebo sou asná b hová prost edí pro práci se shadery umožnují relativn snadno nastavovat aktivní shadery a m nit tak zp sob zobrazování od objektu k objektu. 20

Kapitola 1: Úvod

Samostatnost a p enositelnost(c4) Jak bylo nastín no v ásti o grafickém hardware, spušt ní kódu pro programovatelný et zec je relativn komplikovanou záležitostí zahrnující daleko více inností než jen napsání vlastního kódu. Z toho d vodu je p enositelnost vertex a fragment shader omezená, zejména u komplikovaných program . V nedávné dob se za aly objevovat první pokusy o standardizaci formátu, který by byl schopen zachytit všechny pot ebné informace na jednom míst a jedním zp sobem tak, aby množina soubor v tomto formátu byla samostatnou jednotkou, kterou lze zavést v každém enginu, který tento formát podporuje. Cílem pro kód napsaný v této práci je implementovat ho v tomto formátu a dosáhnout tak samostatnosti a p enositelnosti. Hlavní p ínosy práce by m ly být zejména: Vysoké snímkovací frekvence a kvalita zobrazení Ambicí implementace bylo dosáhnout v tších snímkovacích frekvencí než u p edchozích prací [Krüger a Westermann 03] a srovnatelných výsledk , co se tý e rychlosti i kvality zobrazení, se sou asnými prácemi [Green 05, Stegmaier et al. 05]. Implementace pomocí Shader Modelu 3.0 P i implementaci jsem se zam il pouze na nejnov jší t ídu grafického hardware pro stolní po íta e a Shader Model 3.0, který podporují. To umožnilo oproti p edchozím pracím výrazn snížit po et pr chod uvnit shaderu a také poukázalo na možnosti implementace urychlovacích metod. Zárove jsem ov il výpo etní rychlost této generace karet a našel limity, kdy je t eba pro další zvýšení rychlosti a kvality použít urychlovací techniky a nelze se spoléhat pouze na výpo etní výkon. Zhodnocení vhodnosti použité architektury Sou asné architektury GPU jsou navrženy zejména pro zpracování polygonálních model a nejsou na první pohled p íliš vhodné pro implementaci metod pro zobrazování objemu. Nicmén úsp šná implementace zobrazování objemu na GPU by byla velmi vítaná, jak v oblasti fotorealistického zobrazování, tak v decké a pr myslové vizualizaci. Pokud by se ukázalo, že implementace není z n jakého d vod možná, bylo cílem tyto potíže objektivn zhodnotit a navrhnout jejich možné ešení.

1.6 Rozvržení textu V této úvodní kapitole jsem uvedl základní principy a pojmy z oblasti zobrazování objemu. Probral jsem také problematiku zobrazování v reálném ase a jeden možný zp sob m ení rychlosti zobrazování. Shrnut byl také vývoj a principy grafického hardware pro stolní po íta e. Kapitolu uzavírá vyty ení cíl práce v podob ty požadavk , formulace p edpokládaných p ínos a rozvržení obsahu práce. V kapitole 2 se podrobn ji v nuji kategorii metod hledajících povrch. Je prezentována historie t chto metod, jejich obecné výhody a nevýhody. Na metodách Napojování iso ar a Marching Cubes je prezentován princip p ístup z této oblasti. Nakonec je zhodnocena vhodnost použití pro implementaci na GPU. 21

Kapitola 1: Úvod

V kapitole 3 jsou prezentovány základní metody z oblasti p ímého zobrazování objemu. Kapitola je rozd lena na dv ásti. První ást se v nuje optickým model m a druhá zobrazovacím metodám. Obdobn jako v kapitole 2 je shrnuta historie zobrazovacích postup a jejich obecné výhody a nevýhody. Kapitoly 2 a 3 jsou souhrnn koncipovány tak, aby poskytly kompletní p ehled o oblasti zobrazování objemu. P ehled historie v obou kapitolách mapuje vývoj zobrazování objemu od po átku až po sou asnost a v nuje se i metodám, které nejsou p ímo vysv tlovány. Kapitola 4 prezentuje návrh metody pro implementaci na GPU. Na úvod je metoda uvedena do kontextu zobrazovacího systému tak, jak je uveden v §1.2. Poté je rozebrán návrh jednotlivých ástí a prezentováno použití pokro ilých optických model . Kapitolu uzavírá ást o p íprav testovacích a vývojových dat. Kapitola 5 je v nována podrobn implementaci postupu navrženého v Kapitole 4. Nejprve je detailn rozebrán princip práce s programovatelným et zcem a je vysv tlena obecná struktura kódu. Následuje p edstavení použitého vývojového a experimentálního prost edí, jeho výhod a omezení. V dalších podkapitolách upozor uji na n které zajímavé ásti, které se týkají optických model , geometrických a jiných výpo t . Nakonec je vysv tlen zp sob, jak jsou v implementaci ukládána objemová data a celá kapitola je uzav ena výsledky testování metody a jejich diskuzí. Záv re ná Kapitola 6 podává shrnutí celé práce. Jedná se o zhodnocení dosažených výsledk a zd razn ní vlastního p ínosu. Poté jsou nastín ny možnosti dalšího rozvoje a práce je ukon ena p ehledem citované literatury. V textu nejsou p ekládány názvy obecn známých metod (Marching Cubes, Dividing Cubes) a pojm , pro které zatím neexistuje uspokojivý eský ekvivalent (vertex, fragment, shadery, GPU). V p ípad , že neexistuje ustanovený p eklad cizojazy ného pojmu, ale lze jej uspokojiv se zachováním významu p eložit, je u jeho prvního výskytu uveden ekvivalent v p vodním jazyce v závorkách.

22

Kapitola 2

Metody hledající povrch Cílem v této kapitole není dopodrobna vysv tlit každou z metod založených na principu hledání povrchu. Cílem je ukázat, jak tato skupina metod pracuje a v em se liší od metod p ímého zobrazování. V úvodu kapitoly (§2.1) rozeberu základní kroky t chto metod a uvedu výhody a nevýhody toho p ístupu jako celku. Dále jsou probrány dva algoritmy zajiš ující st žejní ást, tedy konstrukci povrchu z objemových dat. R zných algoritm pro konstrukci povrchu lze samoz ejm v literatu e nalézt více. Uvedené dva postupy p edstavují základní metody a ostatní další algoritmy na nich stav jí i je rozši ují nebo jsou myšlenkov podobné. V ástech o historii jsou uvedeny i základní principy a reference na tyto rozši ující práce a to takovým zp sobem, aby ob kapitoly dohromady tvo ily úplný p ehled vývoje v oblasti metod hledajících povrch. Na konci kapitoly v §2.3 se v nuji možnostem implementace na GPU.

2.1 Úvod Spole nou myšlenkou metod hledajících povrch je zobrazovat pouze ásti objemu odpovídající zadané hodnot . Tento požadavek vychází z reálných, zejména medicínských aplikací. Lidské t lo si lze totiž velmi dob e p edstavit jako skupinu orgán a tkání, z nichž každá má dob e definovanou a homogenní hustotu. Zárove d ležitou informací je práv tvar rozhraní t chto tkání. Tento myšlený povrch se pak metody snaží aproximovat polygonální sítí, která je následn zobrazena b žnými zobrazovacími technikami, v etn ešení viditelnosti. Výhody a nevýhody Již p i úvodní formulaci problému naráží tyto metody na n kolik obtíží. Jde zejména o zp sob, jak formulovat, pro které bu ky objemu se má generovat polygonální povrch. Nejjednodušším p ístupem by bylo definovat prahovou hodnotu f p a

23

Kapitola 2: Metody hledající povrch zobrazit povrch pro každou bu ku, která má hodnotu f ≥ f p . To ovšem znamená, že lze najednou zobrazit pouze jeden povrch pro jednu prahovou hodnotu. Navíc spousta geometrie, která je vygenerována, nebude díky zakrytí vid t. Jinou možností by bylo specifikovat okno pomocí dvou hodnot f bot a f top a pracovat s bu kami, pro jejichž hodnotu f platí f bot ≤ f ≤ f top . Pokud ovšem okno nastavíme p íliš úzké, budou se v povrchu objevovat mezery, naopak bude-li p íliš silné, dostáváme se do stejného problému, jako v p ípad jednoho prahu. Oba výše zmín né p ístupy navíc trpí defekty, které plynou z nucené binární klasifikace, tedy nutnosti vždy rozhodnout, zda má pro danou bu ku být geometrie vygenerována i nikoliv. D sledkem jsou falešné „vypouklé“ ásti, kde byla nesprávn zahrnuta dodate ná bu ka nebo falešné mezery, kde byla nesprávn bu ka opominuta. Tyto defekty mají obzvlášt velký dopad práv v medicínských aplikací, kde by mohly být nesprávn považovány za rys dat. Spole nou výhodou t chto metod je rychlost. Jakmile je jednou povrch zkonstruován, lze jej rychle zobrazovat, bez ohledu na pozici pozorovatele a sv telné podmínky. Stínování a optické modely objemu Metody hledající povrch se nesnaží modelovat objem jako celek a nesnaží se napodobovat jeho reálné optické vlastnosti. Nicmén pro zlepšení vnímání vlastností zobrazovaného povrchu se asto aplikují empirické stínovací modely, nap íklad Phong v model, který je schopný simulovat difusní i lesklý odraz sv tla na povrchu. Pro aplikaci t chto model je nutné znát normálu povrchu v p íslušném bod . Bylo by možné ji spo ítat p ímo jako normálu polygonální sít . Tento p ístup se ovšem nepoužívá, nebo dává p íliš hrub vypadající výsledky. ast ji se normála aproximuje pomocí centrálních diferencí p ímo z objemových dat. Tento postup je vysv tlen v §4.4.

2.2 Konstrukce povrchu V této podkapitole uvedu dva algoritmy generování polygonální sít z objemových dat. Již se nebudu zabývat zp soby, jak takto vygenerovaný povrch zobrazit.

2.2.1 Napojování iso ar Metoda napojování iso ar je založena na myšlence nalézt pro každý dvoudimensionální pr ez objemu množinu uzav ených iso ar, které odpovídají zadané prahové hodnot a poté, ez po ezu, tyto iso áry napojovat a vytvá et tak isoplochu. Ukazuje se, že tento p ístup obsahuje n kolik obtížných míst. V dob publikování prvních prací byl problém již s první krokem, tedy hledáním iso áry ve dvourozm rném pr ezu. Zejména v hodn zašum ných datech nebo v datech s nízkým kontrastem bylo obtížné nalézt iso áry tak, aby tvo ily množinu uzav ených k ivek. asto bylo zapot ebí zásahu operátora, aby sporná místa opravil [Elvins 92]. Druhý problém vzniká p i napojování iso ar v sousedních ezech. V n kterých p ípadech nelze jednozna n rozhodnout, které ásti mají být k sob

24

Kapitola 2: Metody hledající povrch napojeny a vzniká tak chybný povrch, což je zejména v medicínských aplikacích nep ijatelné. Tomuto problému lze zabránit dostate n hustým vzorkováním tak, aby nevznikala situace napojení M:N (tedy p ípad, kdy v jednom ezu je M > 1 a v sousedním N > 1 uzav ených iso ar). Nevýhodou je také pom rn komplikovaná implementace, která obsahuje adu speciálních p ípad . Historie První pokusy se zobrazováním objemových dat vedly na použití tehdy známých algoritm pro generování kontur na dvourozm rných pr ezech a jejich napojovaní tak, aby vznikl polygonální povrch ve t írozm rném prostoru. Poprvé byl tento p ístup publikován v [Keppel 75], pozd ji zdokonalen ve [Fuchs et al. 77] a dále rozvíjen nap . v [Ekoule et al. 91]. V dalších letech nenajdeme mnoho prací publikovaných na st žejních konferencích. Je to zejména proto, že problém hledání povrchu byl pozd ji vhodn ji formulován a byly vyvinuty nové p ístupy, které umož ovaly hledat a zobrazovat isoplochy v objemu efektivn ji a v lepší kvalit p i použitích jednodušších algoritm . Princip Následující popis vychází z práce [Ekoule et al. 91]. Tato práce pat í mezi pokro ilejší metody v oblasti napojování iso ar a umí ešit i velmi komplikované situace. Algoritmus lze rozd lit na t i základní kroky: • Výpo et iso ar v jednotlivých ezech. Iso áru reprezentujeme jako lomenou áru, tedy posloupností bod . Jeden ez m že obsahovat více uzav ených iso ar. • Výpo et isoplochy ze sousedních ez s iso árami. Isoplocha se vytvá í triangulací mezi sousedními iso árami. Základním požadavkem je, aby vytvá ené trojúhelníky m ly rozumný tvar, tedy nebyly p íliš tenké a protáhlé. • Zobrazení vytvo ené trojúhelníkové sít Nejv tší komplexita algoritmu se skrývá v druhém kroku. K problému vytvá ení isoplochy lze p istoupit dv ma zp soby. Bu hledáním optimální triangulace nebo použitím heuristické metody. Jak je v takovýchto p ípadech obvyklé, optimální triangulace dává dobré výsledky, ale její výpo et je extrémn pomalý. Naopak heuristický proces je rychlejší, ale v n kterých p ípadech generuje nesprávné výsledky. Následující algoritmus používá heuristickou metodu, která je speciáln upravena tak, aby generovala korektní výsledky i v obtížných situacích. Dalším problémem, který je nutné vy ešit, jsou topologicky obtížné konfigurace iso ar ve dvou sousedních ezech. V druhém kroku tedy postupujeme následujícím zp sobem: 1. Pracujeme vždy na dvou sousedních ezech, které si p ipravíme. 2. Rozhodneme, o který druh napojení se jedná: a. 1:1, ob kontury konvexní. V tomto p ípad je postup nejjednodušší. Ur íme konturu, která má mén bod . Pro každý bod této kontury pak v sousedním ezu najdeme bod, který je mu nejblíže. Poté již jen doplníme hrany od nespárovaných vrchol tak, aby vznikla triangulace. b. 1:1, jedna nebo ob kontury jsou nekonvexní. Výše uvedený heuristický zp sob napojovaní dává dobré výsledky pouze pro podobné konvexní iso áry. Proto v tomto p ípad promítneme nekonvexní iso áru na její konvexní obal. Poté provedeme triangulaci

25

Kapitola 2: Metody hledající povrch podle bodu a. Transformace iso áry na její konvexní obal dává jednozna nou korespondenci mezi body na iso á e a odpovídajícími body na konvexním obalu. V moment , kdy máme hotovou triangulaci mezi konvexními obaly, lze tuto korespondenci p ímo použit k triangulaci p vodních iso ar. c. 1:N. V tomto p ípad je postup o n co složit jší. V jednom ezu máme tedy iso áru Q a v druhém sadu iso ar Pj , j ∈ [1, N ] . Nejprve

z iso ar Pj vytvo íme spole nou uzav enou iso áru P , která je jejich obalem. Poté z iso ar Q a P vytvo íme pomocnou iso áru S , která leží v polovin jejich vzdálenosti. Nyní již pouze provedeme napojení iso ar Q a S podle bodu a. nebo b. Na druhé stran provedeme n napojení podle bodu a. nebo b. Vždy spojujeme iso áru Pj s iso árou S. d. M:N. Tento p ípad je jednozna n nejsložit jší. Problémem zde je, které z iso ar v jednom ezu napojit na které iso áry v druhém ezu. Budeme p edpokládat, že pokud mají být dv iso áry v sousedních ezech napojeny, jsou p ibližn na stejném míst . To lze zajistit dostate n hustým vzorkováním. Na Obrázek 2.1 vlevo je p ípad, kdy tento p edpoklad neplatí a kdy nelze jednozna n rozhodnout o správném napojení. Tento p ípad lze ovšem vy ešit p idáním dodate ného ezu, jako je ukázáno na Obrázek 2.1 vpravo. Jestliže se tedy spolehneme na uvedený p edpoklad, lze iso áry mezi sebou p i adit na základ jejich vzájemného zakrytí. Ur íme tedy zakrytí všech dvojic iso ar v r zných ezech a vybereme množiny, které mají být sob p i azeny. Tyto množiny nemusí korespondovat 1:1, ale m že také nastat p ípad 1:N. Oba dva ale již umíme ešit z p edchozích krok .

Obrázek 2.1: Nejednozna né napojení iso ar. P evzato z [Ekoule et al. 91]

2.2.2 Marching Cubes Algoritmus Marching Cubes op t slouží k vytvo ení polygonální aproximace isoplochy v objemu. Tentokrát je povrch ovšem p ímo generován jako trojúhelníková sí ve t ech dimenzích. Výhodou algoritmu je snadnost implementace a to i p ímo v hardware. P íjemnou vlastností také je, že generuje trojúhelníky vhodných tvar , tedy trojúhelníky maximáln podobné rovnostranným, bez dlouhých a protáhlých hran. Jednou z mála nep íjemností je, že po et generovaných trojúhelník je velmi vysoký a trojúhelníky jsou asto velmi malé, n kdy i sub-pixelových velikostí.

26

Kapitola 2: Metody hledající povrch Co se tý e rychlosti zobrazovaní, chová se tento algoritmus stejn jako ostatní metody hledající povrch. Tedy, jakmile je jednou povrch zkonstruován, lze jej rychle zobrazovat bez ohledu na pozici pozorovatele a sv telné podmínky.

Historie První p ístup, podobný algoritmu Marching Cubes, je z doby jen o málo pozd jší než metoda napojování iso ar. Jedná se o algoritmus nepr hledných kostek, neboli Cuberille [Herman a Liu 79]. V této práci jsou hledány bu ky objemu, jejichž vrcholové hodnoty leží na obou stranách explicitn zadaného prahu. Pro každou takovou bu ku je vygenerován polygonální kvádr, který je následn zobrazen. Tento sm r byl dále rozvíjen a zdokonalován a v roce 1987 byla publikována práv metoda Marching Cubes [Lorensen a Cline 87]. Její princip je stejný jako v práci Hermanna a Liu. Povrch je ovšem souvislý a je tvo en trojúhelníky, které jsou generovány podle zp sobu, jak isoplocha bu kou prochází. Tento postup byl dále zkoumán a vznikly další, na n m založené, algoritmy jako Marching Tetrahedra [Shirley a Tuchman 90], který každou bu ku rozd lí dále na p t, šest i dvacet ty i ty st n a generuje trojúhelníky podle polohy isoplochy v t chto ty st nech. Známý algoritmus této kategorie Dividing Cubes byl prezentován v práci [Cline et al 88]. Tato metoda si všímá skute nosti, že mnoho generovaných polygon je menších než pixel a spolu s hierarchickým d lením bun k používá tento fakt k vykreslování element objemu jako povrchových bod . Princip Následující popis vychází z práce [Lorensen a Cline 87]. Úkolem algoritmu je vygenerovat trojúhelníkovou sí , která aproximuje isoplochu zadanou uživatelsky definovaným prahem. Uvažme krychli takovou, že ve všech osmi rozích známe vstupní hodnoty a chceme zjistit, jak povrch touto bu kou prochází. Pro každý z osmi vrchol jsou možné dva stavy: hodnota v n m je v tší nebo rovna zadanému prahu (1) a vrchol tedy leží „uvnit “ nebo na isoploše. Nebo je hodnota ost e menší (0) než zadaný práh a pak vrchol leží „vn “ isoplochy. To nám p i osmi vrcholech dává celkem 28 = 256 možných konfigurací. Auto i algoritmu ukázali, že symetriemi lze tento po et zredukovat na 15 konfigurací. Tyto konfigurace jsou zobrazeny na Obrázek 2.2.

Obrázek 2.2: Konfigurace v algoritmu Marching Cubes. P evzato z [Lorensen a Cline 87].

27

Kapitola 2: Metody hledající povrch P ed vlastním zapo etím práce algoritmu je pot eba p ipravit tabulku t chto konfigurací. Vytvo íme strukturu, do které se budeme odkazovat osmi bitovým indexem, kde každý bit reprezentuje stav jednoho vrcholu. Tabulka obsahuje pro každou ze 14 konfigurací (konfigurace 0 negeneruje žádné trojúhelníky) seznam hran, které jsou povrchem protnuty. Vlastní algoritmus Marching Cubes lze pak popsat následujícími kroky: 1. ty i sousední ezy jsou na teny do pam ti. 2. Procházíme prost ední dva ezy a vždy vytvo íme krychli tak, že ty i její vrcholy leží v jednom ezu a ty i v druhém ezu. 3. Spo teme index této krychle tak, že porovnáme hodnoty objemových dat ve vrcholech krychle se zadaným prahem. 4. Tento index použijeme do tabulky konfigurací a na teme seznam hran, které jsou povrchem protnuty. 5. Z hodnot ve vrcholech hran ur ených p edchozím krokem lineárn interpolujeme p esnou pozici pr se íku s povrchem na každé z t chto hran. 6. Spo teme normálu ve vrcholech krychle pomocí centrálních diferencí (z tohoto d vodu pot ebujeme pracovat se ty mi ezy, ne jen se dv ma). Tyto normály pak interpolujeme do vrchol vygenerovaných trojúhelník . 7. Na výstup pošleme trojúhelníky a normály ve vrcholech.

2.3 Komentá Na záv r kapitoly o metodách hledajících povrch zhodnotím jejich vhodnost pro implementaci na GPU. Cílem této práce bylo implementovat metodu zobrazování objemu zcela pomocí GPU, tedy tak, aby co nejmenší objem prací byl provád n na hlavním procesoru po íta e. Zobrazování povrch , které vygenerují metody hledající povrch lze velmi dob e hardwarov urychlovat, a také toho je asto využíváno. Takto je ovšem urychlováno pouze zobrazování vygenerovaného povrchu a vlastní pr chod objemovými daty a extrakce povrchu je typicky provád na na hlavním procesoru. Pokud bych cht l n kterou z metod hledající povrch kompletn implementovat uvnit shader , znamenalo by to procházet p ímo na GPU objemová data a konstruovat z nich polygonální povrch. Tento typ pr chodu daty je ovšem pro výpo etní model GPU nevhodný. Jak bylo nazna eno v úvodní kapitole, sou asné GPU dosahují vysokého výkonu zejména kv li proudové architektu e a vysokému stupni paralelizace. Tato paralelizace ovšem probíhá na úrovni zpracování vrchol a fragment . Princip spo ívá v tom, že zpracování jednotlivých vrchol a fragment lze efektivn odd lit a tak výpo ty nad nimi masivn paralelizovat. Proto p ímo implementovat pr chod objemem na sou asných GPU architekturách nelze. Programátor má možnost pouze ovliv ovat zpracování existujících jednotlivých vrchol a fragment . Sou asný výpo etní model také neumož uje uvnit vertex shader vytvá et nové vrcholy nebo existující rušit. Aby bylo ale možné implementovat pr chod objemem, je nutné um t vytvá et nové polygony a tedy i nové vrcholy. Toto omezení lze áste n obejít tím, že se na GPU ke zpracování odešle sada degenerovaných polygon a uvnit vertex shader se m ní pozice jejich vrchol tak, aby vzniklo požadované t leso. Stále ovšem z stává problém, že p edem nevíme, kolik polygon bude pot eba a také uvnit vertex

28

Kapitola 2: Metody hledající povrch shader nemáme k dispozici informaci o topologii polygon , tedy informaci, které polygony jsou tvo eny kterými vrcholy. P i implementaci b hem této práce jsem m l také na mysli zobrazování „amorfních“ objekt , jako jsou mraky a ohe , pro které je použití metod hledajících povrch nevhodné. Proto, když jsem zkombinoval uvedené technické a estetické potíže, ukázaly se metody hledající povrch jako nevhodný základ pro tuto práci. Všimn me si ješt jednoho faktu, který plyne z diskuse v p edchozích odstavcích. Díky konstrukci sou asných GPU lze obecn íci, že jakákoliv metoda, která používá jako primární pr chod objemovými daty a p i tomto pr chodu vytvá í obraz na pr m tn , je nevhodná pro implementaci uvnit shader . Tento fakt bude hrát d ležitou roli u n kterých p ímých zobrazovacích metod, jako nap íklad u metody otisk .

29

Kapitola 3

P ímé zobrazovací metody V této kapitole se budeme zabývat druhou velkou skupinou p ístup k zobrazování objemu, a to jsou p ímé zobrazovací metody. P itom se budu voln držet rešerše uvedené v pracích [Kajiya 84 a Von Herzen, Krüger a Westermann 03]. Škála vyvinutých p ístup se zde liší ješt více než u metod hledajících povrch. Protože jako základ pro tuto práci byl vybrána práv metoda z oblasti p ímých zobrazovacích metod, je této kapitole v nován v tší prostor než kapitole 2. Po úvodní ásti (§3.1), kde op t proberu základní principy a výhody a nevýhody této t ídy metod, následuje kapitola o optických modelech (§3.2). Zde se budeme zabývat zp soby, jak simulovat pr chod sv tla prost edím. Tento krok je u p ímých zobrazovacích metod daleko d ležit jší, než u metod hledajících povrch. V §3.3 o zobrazovacích postupech jsou p edstaveny ty i základní p ístupy. U každého je shrnuta jeho historie a obdobn jako v kapitole 2 takovým zp sobem, aby souhrn ástí o historii dával celkový p ehled vývoje oblasti p ímých zobrazovacích metod. V §3.3.1 se zabývám metodami pr ez . Jde o myšlenkov velmi jednoduchý p ístup navržený p ímo pro implementaci v hardware. Druhými v po adí v §3.3.2 jsou metody otisk . Tento princip a práce z n j vycházející jsou velmi zajímavé a ukazují širokou škálu možností, jak k problému zobrazování objemových dat p istoupit. V p edposledním §3.3.3 je p edstavena skupina metod založených na faktorizaci. Tyto metody reprezentují sm r vývoje, který byl udáván snahou o využití prostorové koherence dat u existujících metod. V §3.3.4 jsou p edstaveny p ístupy založené na vrhání paprsku, které tvo í také základ metody navrhované v této práci. ást o zobrazovacích postupech uzavírá §3.3.5, kde stru n zmíním ješt další p ístupy, které se b hem vývoje objevily. Na záv r kapitoly v §3.4 je op t uveden komentá ke vhodnosti implementace na GPU.

3.1 Úvod P ímé metody zobrazování objemu jsou historicky o málo starší, než p ístupy založené na hledání povrchu. Snahou p i návrhu p ímých zobrazovacích metod bylo odstranit n které defekty hledání povrchu a také umožnit práci s objemovými daty i v jiných oblastech.

30

Kapitola 3: P ímé zobrazovací metody Metody p ímého zobrazování objemu odstra ují použití polygonálních primitiv a snaží se objem zobrazit p ímou projekcí na pr m tnu. Tímto p ístupem je možné se zbavit velkého množství problém , zejména nutnosti klasifikace bun k na p ítomnost i nep ítomnost povrchu a s tím spojených artefakt . Zárove je možné zobrazovat „amorfní“ objemy, kde pojem povrchu je nejasný i nevhodný pro vizualizaci, nap . p írodní fenomény jako mraky a ohe . Je zde ovšem také mnoho problém nových, z nichž n které se ukazují jako velmi složité. Nyní již nemáme k dispozici povrch, který bychom mohli p ímo stínovat a je nutné vyvinout n jaké postupy pro zp sob p enosu objemových dat na zobrazitelné hodnoty, jako je pr hlednost a barva. Tento bod se ukazuje jako klí ový, a proto je mu v nován celý §3.2. Dalším problémem je z ejmá velká výpo etní náro nost t chto metod. P i konstrukci povrchu sta ilo jednou projít celý objem, vytvo it povrch a pak ho opakovan zobrazovat. Zde ovšem podobnou „mezilehlou“ reprezentaci nemáme a je tedy nutné objem opakovan procházet p i zm n pozice pozorovatele a/nebo sv telných podmínek. Je to proto, že díky p ímému promítání je každý vygenerovaný obraz závislý práv na pozici pozorovatele. Zajímavý zp sob, jak tento problém ešit a p itom stále ješt pracovat s p ímým zobrazování nabízí t ída metod založených na faktorizaci (§3.3.3). Lze tedy shrnout, že p ímé zobrazovací metody jsou schopny dosahovat velmi kvalitních výsledk , jsou flexibilní díky možnosti využití široké škály optických model , ale jsou velmi výpo etn náro né.

3.2 Optické modely P i použití p ímých zobrazovacích metod je d ležitým krokem zp sob, jakým mapujeme vstupní hodnoty na zobrazitelné veli iny, jako barva a pr hlednost. K tomuto problému lze p istoupit dv ma zp soby. Bu se budeme snažit simulovat skute né fyzikální vlastnosti n jaké látky nebo budeme mapování tvo it empiricky tak, abychom zobrazili i zd raznili požadované rysy objemu. V oblasti fotorealistického zobrazování se budeme držet fyzikálních vlastností simulovaného fenoménu. I když i zde lze nalézt empirické p ístupy. Bývá to z d vodu výpo etní složitosti fyzikáln založených metod. V oblasti v decké vizualizace lze nalézt argumenty pro ospravedln ní obou p ístup . Výhoda simulace fyzikálních vlastností ur ité látky spo ívá v tom, že lidé pracující s výslednými obrázky i animacemi, mají s touto látkou reálné zkušenosti a bývají schopni odvodit dodate né vlastnosti, které nejsou p ímo z ejmé. Tato vlastnost se m že ovšem ukázat jako fatální, pokud by naše simulace vlastností látky nebyla ve shod s fyzikální realitou. Empirické mapování má naopak výhodu, že lze p ímo zobrazit n které vlastnosti, které se ve fyzikální realit vizuáln neprojevují. Nevýhodou naopak je, že uživatelé nejsou na použité mapování zvyklí a je pot eba p ípravy a tréninku, aby byli schopni jeho vlastností využít. Velmi dobrým p íkladem je práce [Sabella 88].

31

Kapitola 3: P ímé zobrazovací metody

3.2.1 Simulace vlastností reálných látek Pro napodobení vizuálních vlastností libovolné reálné látky musíme um t simulovat zp sob interakce této látky se sv tlem. Budeme se tedy zajímat o to, jak se sv tlo chová v médiu, jak toto chování matematicky formalizovat a jak získané vzorce využít. Nejprve proberu, od nejjednodušších k nejsložit jším, fyzikáln reálné modely ší ení zá ení v prostoru a nakonec zmíním jeden empirický model, který se snaží napodobovat násobný rozptyl, ovšem nikoliv pomocí fyzikáln reálných výpo t , ale pomocí empirického vzorce. Velmi dobrý p ehled optických model a jejich odvození je uveden v [Max 95] a této práce se v následujícím výkladu držím. Podrobná odvození obdobných rovnic lze nalézt také nap íklad v pracích [Kajiya a Von Herzen 84, Blinn 82, Sabella 88]. Obecn tyto práce vycházejí z fyzikálních teorií o ší ení zá ení, nap .[Chandrasekhar 50]. Chování zá ení v prostoru lze popsat jeho pohlcováním, vyza ováním a rozptylem od malých ástic média, jako jsou nap íklad kapi ky vody, prachové ástice nebo i jednotlivé molekuly látky. V následujících odstavcích popíši geometricky optické chování takovýchto ástic a z nich odvozené rovnice pro popis pr chodu sv tla látkou. Pokud nebude e eno dále jinak, budeme studovat pr chod zá ení látkou v situaci zobrazenou na Obrázek 3.1. Zá ení sledujeme podél n jakého paprsku P, který je parametrizovaný parametrem t. V bod odpovídajícím t = 0 zá ení do objemu vstupuje a v bod odpovídajícím t = D objem opouští.

Obrázek 3.1: Situace p i pr chodu sv tla objemem

Dále v následujících odvozeních p edpokládám, že médium je spojité, a že ástice jsou nekone n malé, tedy p esn ji, že události pohlcování, vyza ování a rozptylování se odehrávají v každém nekone n malém segmentu paprsku P.

Pohlcující model Nejjednodušším médiem je látka složená z ástic s vlastnostmi perfektního erného t lesa, které veškeré incidentní sv tlo pohltí, nic nevyza uje ani nerozptyluje. Nyní odvodíme model ší ení sv tla v takovéto látce. P edpokládejme, že ástice v látce jsou dokonalé identické koule o polom ru r a promítnuté na dvourozm rnou pr m tnu mají tedy plochu A = π ⋅ r 2 . Uvažme nyní válcový pás se základnou B a výškou ∆s . Plochu základny B ozna me E. Zá ení skrze tento pás prochází ve sm ru válce. Ozna me ρ po et ástic na jednotkový objem látky. Potom, nebo objem toho pásu je V = E ⋅ ∆s , lze v n m 32

Kapitola 3: P ímé zobrazovací metody nalézt N = ρE∆s ástic. Pokud bude ∆s malé, je také malá pravd podobnost, že se pr m ty ástic na základnu B budou protínat. Pak plocha, kterou pr m ty ástic na základnu B zabírají, je p ibližn N ⋅ A = ρE∆sA . Tedy ást zá ení, která projde základnou je úm rná ρEA∆s / E = ρA∆s . Nyní uvažme tento výraz v limit pro ∆s → 0 . Dostáváme tak diferenciální rovnici dI = − ρ ( s ) AI ( s ) = −τ ( s ) I ( s ) (3.1) ds kde: • I ( s ) je intensita zá ení v bod , který odpovídá parametru s

• ρ ( s ) je po et ástic na jednotkový objem v bod , který odpovídá parametru s

Tato rovnice íká, jaký je p ír stek (zm na) intensity zá ení v diferenciáln malém válcovém pásu. len τ ( s ) je ozna ován jako koeficient útlumu. ešením této diferenciální rovnice je výraz s

I ( s ) = I 0 ⋅ exp − τ ( t ) dt

(3.2)

0

kde • I0 je intesita zá ení v bod s = 0 , tedy v bod , kdy zá ení do objemu vstoupilo. P i ešení bylo využito faktu, že pravd podobnost P ( 0, V ) , že v objemu V nebude

žádná ástice, lze vyjád it Poissonových rozd lením P ( 0, V ) = e − N , kde stejn jako výše N je p edpokládaný po et ástic v objemu V. asto bývá v podobných výrazech oto en smysl sledovaného paprsku. V rovnici (3.2) je bod pro t = 0 nejdále od pozorovatele a bod pro t = s nejblíže k pozorovateli.

Obrázek 3.2: Použití pohlcujícího modelu ší ení sv tla

Obrázek 3.2 byl vytvo en zobrazovací metodou implementovanou v této práci, za použití výše uvedeného modelu ší ení sv tla. Obrázek nalevo ukazuje, jak proceduráln definovaný mrak pohlcuje sv tlo p icházející zpoza objemu z obrázku

33

Kapitola 3: P ímé zobrazovací metody Zem . Obrázek napravo ukazuje, jak lze pomocí pohlcujícího modelu vytvá et obrázky napodobující rentgenové snímky.

Vyza ující model Dalším druhem velmi jednoduchého média je látka, která pouze vyza uje sv tlo a ani jej neodráží a ani nepohlcuje. Fyzikáln je takováto látka nereálná, ale nejvíce se jí blíží nap íklad plamen ohn . Op t p edpokládejme, že látka je složena z ástic, které jsou identické koule. Dále p edpokládejme, že jsou zcela pr hledné a tedy ani neodrážejí ani nepohlcují sv tlo. Každá taková ástice nech vyza uje s intesitou C na jednotku promítnuté plochy. Potom podle vzorce z minulé sekce dostáváme, že základna válcového pásu vyza uje s intensitou C ρ AE ∆s neboli C ρ A∆s na jednotkovou plochu. Op t pro ∆s → 0 dostáváme diferenciální rovnici:

dI = C ( s ) ρ ( s ) A = C ( s )τ ( s ) = g ( s ) ds

(3.3)

kde: • C ( s ) je intensita vyza ování v bod , který odpovídá parametru s na paprsku.od pozorovatele. len g ( s ) je nazýván zdrojový len a obecn se používá k vyjád ení množství vyza ovaného sv tla. V dalších složit jších modelech do tohoto lenu zahrneme i vyza ování zp sobené odrazem od vn jších zdroj sv tla. ešení této diferenciální rovnice je jednoduché, ve tvaru: s

I ( s ) = I 0 + g ( t ) dt

(3.4)

0

kde • g ( t ) je zdrojový len. Obrázek 3.3 ukazuje použití vyza ujícího modelu sv tla. Obrázek napravo pracuje pouze s vyza ovanou intenzitou. Obrázek nalevo ukazuje použití pro modelování plamene. Látka vyza uje r znou barvu podle polohy. Uvnit je barva žlutá a sm rem k okraj m plamene p echází do oranžové až ervené.

Obrázek 3.3: Použití vyza ujícího modelu ší ení sv tla

34

Kapitola 3: P ímé zobrazovací metody Všimn me si jednoho zásadního rozdílu od pohlcujícího modelu sv tla. V pohlcujícím modelu mohla intesita dosáhnout maximáln hodnoty, která p ichází zpoza objemu. Naopak u vyza ujícího modelu toto omezení není a v místech, kde je materiál dostate n hustý, snadno dojde k p ekro ení zobrazitelného rozsahu hodnot. Tento efekt lze na Obrázek 3.3 pozorovat uvnit látky. Tento efekt je ovšem u siln vyza ujících materiál obvyklý, nebo i lidské oko je schopné se adaptovat jen na omezený rozsah hodnot jasu (i když tento rozsah je ádov vyšší než použitých 256 hodnot).

Vyza ující a pohlcující model Logickým krokem p i vytvá ení dalších, složit jších model ší ení sv tla, je slou it oba p edchozí modely do jednoho. V této sekci se tedy budeme zabývat látkou, která pohlcuje i vyza uje sv tlo. Do diferenciální rovnice, která nám popisuje p ír stek intensity sv tla v diferenciáln malém válcovém pásu, tedy zahrneme jak len pro útlum, tak len pro vyza ování. Rovnice má tedy tvar:

kde • g ( s ) je zdrojový

dI = g ( s ) −τ ( s ) I ( s ) ds

(3.5)

len. Nyní budeme, na rozdíl od p edchozí sekce,

p edpokládat, že tento len má obecný tvar a nemusí nutn být ve form g ( s ) = C ( s )τ ( s ) Tuto rovnici lze n kolika aritmetickými úpravami p evést do tvaru:

d I ( s ) exp ds

s

τ ( t ) dt

s

= g ( s ) exp

0

τ ( t ) dt

0

Pokud budeme nyní integrovat od s = 0 na vzdáleném konci objemu až po s = D u pozorovatele, dostáváme rovnici,

I ( D ) exp

D

D

s

0

0

τ ( t ) dt − I 0 = g ( s ) exp

0

τ ( t ) dt ds

kterou lze op t n kolika aritmetickými úpravami dovést do kone ného tvaru: D

D

D

0

0

s

I ( D ) = I 0 exp − τ ( t ) dt + g ( s ) exp − τ ( t ) dt ds

(3.6)

Podrobné odvození, v etn vynechaných aritmetických úprav, lze nalézt nap íklad v [Max 95]. Na Obrázek 3.4 je op t ukázka použití práv odvozeného modelu ší ení sv tla. Obrázek napravo ukazuje model aplikovaný, podobn jako výše, na jednoduchý objekt p ipomínající mrak. V tomto obrázku se pracuje pouze s vyza ovanou intensitou zá ení. Obrázek vlevo je o poznání složitejší. Je na n m zobrazena ohnivá koule, která by mohla nap íklad vznikout po výbuchu. Vnit ek

35

Kapitola 3: P ímé zobrazovací metody látky zá í žlutým a oranžovým sv tlem, které je dále pohlcováno vn jšími vrstvami kou e, který sám vyza uje málo, ale má vysoký koeficient útlumu. Koeficient útlumu navíc roste sm rem od st edu exploze. Centrální „žhavé“ ásti, p edstavující ohe , mají koeficient útlumu minimální, naopak vn jší kou ové ásti velmi vysoký. Na první pohled je patrné, že obrázek je p íliš tmavý. To je zp sobeno tím, že použití pohlcujícího a vyza ujícího modelu nebere v úvahu rozptyl zá ení uvnit látky. Tento rozptyl by zp sobil, že vn jší kou ové vrstvy by byly daleko více osv tleny, než jsou nyní.

Obrázek 3.4: Použití pohlcujícího a vyza ujícího modelu ší ení zá ení

Stínování a rozptyl Dalším krokem k v tšímu realismu a v rohodnosti optického modelu je zahrnutí osv tlení látky z vn jších zdroj . Doposud jsem uvažoval pouze isotropní vnit ní vyza ování látky. Je-li látka osv tlována z externího zdroje, zá ení dopadá na ástice látky, kde je áste n odraženo a áste n pohlceno. Modelování chování zá ení p i odrazu, nazýváme stínování. V závislosti na druhu látky, dochází ješt k násobným odraz m uvnit média, než je zá ení zcela pohlceno nebo než objem opustí. Odrážení zá ení uvnit látky se nazývá rozptyl a zp sob, jak jej napodobujeme model rozptylu. V této ásti se zam ím na nejjednoduší model osv tlení z vn jších zdroj a hlavn na princip stínování. Budu uvažovat osv tlení jedním vn jším zdrojem. Dalším p edpokladem bude, že zá ení není na své dráze nijak utlumeno, a to ani mezilehlými ásticemi objemu a je odraženo práv jednou. Zajímat nás bude pouze zm na intensity rozptýleného zá ení. V obecném p ípad není pouze popis intensity dosta ující a je t eba sledovat n kolik dalších faktor , jako nap íklad zm nu polarizace i vlnové délky. Nejd íve se v nujme stínování z fyzikálního hlediska. Pro výše uvedený zjednodušený p ípad lze událost odrazu zá ení od ástice v objemu popsat následující rovnicí: S ( X , ω, ω′) = r ( X , ω, ω′) i ( X , ω′)

(3.7)

kde • S ( X , ω , ω ′ ) je intensita zá ení p icházejícího ze sm ru ω ′ odraženého v bod X do sm ru ω

36

Kapitola 3: P ímé zobrazovací metody

• r ( X , ω , ω ′)

je takzvaná BRDF (Bidirectional Reflectance Distribution

Function) neboli Obousm rná funkce odrazivosti • i ( X , ω ′ ) je intensita zá ení, které dopadá do bodu X ze sm ru ω ′ Rovnice (3.7) je platná práv pro jeden zdroj osv tlení, který leží ve sm ru ω ′ . Tento sm r m že být, v p ípad rovnob žného zdroje osv tlení, stejný pro všechny body X nebo je nutné jej pro každý bod ur it zvláš . Nejd ležit jším lenem rovnice (3.7) je BRDF. Tato funkce je závislá na konkrétním bodu X, sm ru ω ′ , odkud zá ení p ichází a sm ru ω , ve kterém intensitu zá ení sledujeme. Hodnota funkce BRDF je z intervalu [ 0,1] a udává vztah, jaká ást zá ení dopadajícího ve sm ru ω ′

je odražena do sm ru ω . D ležitý je také p edpoklad jednoduchého rozptylu. V rovnici (3.7) je totiž intensita zá ení odraženého do sm ru ω závislá pouze na intensit zá ení p icházejícího ze sm ru ω ′ , kde leží sv telný zdroj. V p ípad násobného rozptylu bychom museli integrovat p es všechny sm ry na jednotkové kouli okolo bodu X. V p ípad více sv telných zdroj sta í vyhodnotit rovnici (3.7) pro každý z nich a výsledky se íst. Pro p ípad látky, kde pracujeme nikoliv s jednotlivými ásticemi látky, ale s jejich hustotou na jednotkový objem, lze blíže specifikovat tvar BRDF:

r ( X , ω , ω ′ ) = a ( X )τ ( X ) p ( ω , ω ′ )

(3.8)

kde • a ( X ) se nazývá albedo látky a udává, jaká ást z útlumu p ipadá na rozptyl spíše, než na pohlcování zá ení. Vysoké albedo má nap íklad látka složená z kapi ek vody, nízké nap íklad kou složený p evážn se sazí. • τ ( X ) je op t koeficient útlumu, tak jak jej známe z p edchozích model . Pouze není parametrizovaný parametrem na paprsku, ale bodem X v prostoru. • p (ω , ω ′ ) se nazývá fázová funkce a udává sm rovost rozptylu látky, tedy kolik ze zá ení p icházejícího ze sm ru ω ′ bude rozptýleno do sm ru ω Jak lze p edpokládat, zásadním prvkem je v rovnici (3.8) fázová funkce. Její podoba se liší od látky k látce a pro p esnou simulaci reálných látek by bylo nutné její hodnoty nam it. Jak ve fyzice, tak v po íta ové grafice byla vyvinuta ada p ístup , jak aproximovat hodnotu fázové funkce pro ur itou t ídu látek. Jejich podrobný popis lze nalézt v literatu e a detailn zmínit by jen n kolik z nich je mimo rozsah této práce. Uvedu proto pouze informativn pár nejb žn ji používaných aproximací. Látka složená z kulových ástic nebo z náhodn orientovaných ástic libovolného tvaru, bude vykazovat isotropický rozptyl. V takovém p ípad hodnota fázové funkce bude záviset pouze na úhlu x mezi sm ry ω a ω ′ , tedy:

p (ω , ω ′ ) = cos ( x ) = ω ⋅ ω ′

(3.9)

Na zp sob rozptylu sv tla má zásadní vliv pom r velikosti ástic látky k vlnové délce zá ení. Pro r zné hodnoty tohoto pom ru byly sestaveny modely, které popisují rozptyl za p íslušných podmínek.

37

Kapitola 3: P ímé zobrazovací metody Rozptyl zá ení ásticemi, jejichž velikost je ádov menší, než vlnová délka zá ení se popisuje takzvaným Rayleigh rozptylem (Rayleigh scattering). Zevrubný popis lze nalézt nap íklad v [Chandrasekhar 50]. Rozptyl v látce, jejíž ástice jsou srovnatelné s vlnovou délkou sv tla a mají kulový tvar nebo je jejich orientace náhodná, je popsán takzvaným Mie rozptylem (Mie scattering). Teorie zabývající se tímto druhem rozptylu je relativn složitá a odvozené vztahy p íliš komplikované pro p ímé použití (narozdíl nap . od Rayleigh rozptylu). Proto je v praxi tento druh rozptylu aproximován empirickými funkcemi, klasicky nap íklad pomocí Henyey-Greensteinovy funkce, jejíž detailní popis lze nalézt v [Henyey a Greenstein 40]. Abychom m li vý et úplný, je t eba dodat, že zvláštní anomálie nastává u rozptylu ásticemi, které jsou ádov v tší než vlnová délka zá ení. Zde, oproti o ekávání, je útlum sv tla dvojnásobný, než je geometrický pr ez ástice kolmý na sm r ší ení vlny. Ovšem, aby bylo možno tento poznatek aplikovat, je t eba jev pozorovat ze vzdálenosti op t ádov v tší, než je velikost ástice. Proto se tento jev uplat uje spíše v astronomických rozm rech a v po íta ové grafice není asto v bec uvažován. V n kterých aplikacích není pot eba, nebo to ani není vhodné, provád t stínování podle fyzikální princip . Jde zejména o p ípady, kdy chceme z objemových dat zobrazit pouze ty ásti, které odpovídají n jaké p edem stanovené hodnot p echodové funkce. Tyto ásti objemu bychom nyní cht li zobrazovat jako pseudopovrch s odpovídajícím stínovaním. Pro tyto ú ely se asto používají, místo fyzikáln založené BRDF, empiricky odvozené modely, nej ast ji Phong v model (viz [Phong 75]). Proto, abychom mohli tyto empirické modely používat, pot ebujeme typicky znát normálový vektor k myšlenému povrchu. Nejb žn ji používaným zp sobem, jak tento normálový vektor z objemových dat získat, je aproximovat ho pomocí metody centrální diferencí. Normálový vektor v bod X = ( xi , y j , zk ) získáme jako

N(X ) =

∇f ( X )

(3.10)

∇f ( X )

kde • N ( X ) je normálový vektor v bod X

•

f ( X ) je hodnota funkce vracející objemová data v bod X

• ∇f ( X ) je gradient funkce f v bod X

a vektor derivací ∇f aproximujeme diferencemi jako: 1 f ( xi +1 , y j , zk ) − f ( xi −1 , y j , zk ) , 2 1 ∇f ( X ) = ∇f ( xi , y j , zk ) = f ( xi , y j +1 , zk ) − f ( xi , y j −1 , zk ) , 2 1 f ( xi , y j , zk +1 ) − f ( xi , y j , zk −1 ) 2

(

)

(

)

(

)

38

(3.11)

Kapitola 3: P ímé zobrazovací metody V sekci o vyza ujícím modelu jsem napsal, že do zdrojového

lenu g ( s ) lze

zahrnout, krom vlastního vyza ování, také p ír stek intensity zp sobený rozptylem. Zdrojový len lze tedy nyní vyjád it jako: g ( X , ω, ω ′) = E ( X ) + S ( X , ω, ω ′)

(3.12)

kde • E ( X ) je vlastní vyza ování látky v bod X Všimn me si, že nyní již zdrojový len není závislý pouze na pozici uvnit objemu, ale také na sm ru odkud p ichází sv tlo a na sm ru, kterým je sv tlo vyza ováno. Z toho d vodu již není zdrojový len parametrizován parametrem na paprsku. Pro vlastní práci s odraženým sv tlem tak, jak je popsáno v této sekci, sta í do rovnice (3.6) substituovat upravený zdrojový len g ( X , ω , ω ′ ) .

Obrázek 3.5: Ukázka sm rovosti HG aproximace pro c = 0,5

Vržené stíny D íve než se pustíme do odvozování vztah pro útlum zá ení na jeho cest od vn jšího sv telného zdroje, provedeme úpravu základní situace, ve které budeme zá ení sledovat. Doposud jsme zá ení sledovali podél paprsku tak, jak je to zachyceno na Obrázek 3.1. Nyní je pot eba ud lat dv úpravy. Novou situaci zachycuje Obrázek 3.6.

Obrázek 3.6: Situace pro modelování vržených stín

39

Kapitola 3: P ímé zobrazovací metody První zm nou je, že již nebudeme parametrizovat pouze jednorozm rným parametrem na paprsku, ale p ímo bodem v t írozm rném prostoru. Tento zp sob parametrizace byl použit již v minulé ásti o stínování. D vodem je, že v následujících rovnicích pot ebujeme pracovat s body v prostoru, které neleží pouze na jednom paprsku jako doposud. Druhou zm nou je oto ení smyslu parametru na paprsku. Tu provedeme zejména z d vodu názornosti a p ehlednosti zápisu vztah , které budou následovat. Máme tedy sledovaný bod X, který leží na paprsku, jehož jednotkový sm rový vektor je −ω . Body na tomto hlavním paprsku jsou parametrizovány parametrem s tak, že bod ve vzdálenosti s od X ve sm ru −ω vyjád íme jako X − sω . Pro každý tento bod máme sm r −ω ′ , odkud p ichází osv tlení. Libovolný bod na paprsku ur eném sm rem −ω ′ a bodem X − sω lze pak vyjád it jako X − sω − tω ′ . Nyní se m žeme pustit do odvození pot ebných vztah . V minulé sekci jsem se zabýval chováním zá ení p i dopadu na ástici látky a zp sobem, jak lze modelovat zp sob jeho odrazu. P itom jsem p edpokládal, že sv tlo není na své cest nijak utlumeno. P irozeným rozší ením tohoto modelu, p i zachování jednoduchého rozptylu, je uvažovat útlum zá ení na cest od zdroje. Vezmeme tedy rovnici (3.7) a upravíme len vyjad ující intensitu zá ení dopadajícího ze sm ru ω ′ : ∞

i ( X , ω ′ ) = L exp − τ ( X − tω ′ )dt

(3.13)

0

kde • L je intensita zdroje zá ení Vidíme tedy, že intensita zá ení L je utlumena o výraz, který je nám znám již z rovnice (3.2) uvedené u úvodního pohlcujícího modelu. Jediným rozdílem je, že v rovnici (3.13) je obrácen smysl parametrizace paprsku. Tedy bod pro t = 0 je bod X, ve kterém nastala událost rozptylu. V praxi samoz ejm integrace neprobíhá až po t = ∞ , ale pouze k hranici objemu. Obrácený smysl parametrizace paprsku, tedy pro t = 0 v míst pozorovatele X je nyní i p es složitost zápisu výhodn jší. Proto p epíšeme rovnici (3.6) s touto obrácenou parametrizací. Dostáváme tedy: D

D

s

0

0

0

I ( X ) = I 0 exp − τ ( X − tω ) dt + g ( X − sω ) exp − τ ( X − tω ) dt ds (3.14) kde • ω je sm r paprsku od pozorovatele v bod X. Pro p ehlednost ozna me: D

Τ ( t ) = exp − τ ( X − tω ) dt ,

(3.15)

0

s

Τ′ ( t ) = exp − τ ( X − tω ) dt , 0

40

(3.16)

Kapitola 3: P ímé zobrazovací metody

∞

Τ′′ ( t , s ) = exp − τ ( X − sω − tω ′ ) dt

(3.17)

0

Nyní nám zbývá pouze do rovnice (3.14) substituovat výrazy (3.7), (3.12) a (3.13) a dostáváme: I ( X ) = I0Τ ( t ) +

D

0

( E ( X − sω ) + r ( X − sω , ω , ω ′) LΤ′′ ( t , s ) ) Τ′ ( t )ds

(3.18)

kde • ω je op t sm r paprsku od pozorovatele v bod X • ω ′ je sm r paprsku od bodu X − sω ke zdroji sv tla. Tento sm r je v p ípad rovnob žného osv tlení stejný pro všechny takové body, v p ípad bodového osv tlení je nutné jej ur it pro každý takový bod zvláš . V modelu, který vyjad uje rovnice (3.18) tedy máme zahrnuty všechny doposud zmín né faktory. len E ( X − sω ) vyjad uje vlastní vyza ování látky. Osv tlení o intensit L z externího zdroje je utlumeno jednak pr chodem objemem o faktor ∞

exp − τ ( X − sω − tω ′ ) dt

a

také

dvousm rovou

funkcí

odrazivosti

0

reprezentovanou lenem r ( X − sω , ω , ω ′ ) . Celý tento p ír stek intensity je dále s

utlumen na dráze k pozorovateli o faktor exp − τ ( X − tω ) dt . 0

Obrázek 3.7: Srovnání efektu útlumu sv tla

Model pro násobný rozptyl Logicky dalším krokem v rozvoji optických model je zahrnutí násobného rozptylu. Tento krok je ovšem daleko složit jší, než byly p echody v minulých sekcích. ešení tohoto problému je ekvivalentní nap íklad problému globálního osv tlení a výpo tu

41

Kapitola 3: P ímé zobrazovací metody zobrazovací rovnice (viz [Kajiya 86]). P i jednoduchém rozptylu jsme pracovali s jedním sm rem sv tla a zdrojový len zahrnoval vlastní vyza ování plus p ísp vek z toho jednoho sm ru utlumený pomocí BRDF. Nyní bychom pot ebovali p ísp vek ze všech možných sm r . Nyní již nelze ovšem použít p ímo utlumenou hodnotu intensity sv telného zdroje, ale je pot eba ta samá hodnota, jako se snažíme spo ítat. len vyjad ující rozptyl by tedy bylo nutné z tvaru (3.7) upravit na:

S ( X , ω , ω ′) =

r ( X , ω , ω ′) I ( X , ω ′) dω ′

(3.19)

4π

kde • r ( X , ω , ω ′ ) je op t BRDF pro sm ry ω a ω ′

• I ( X , ω ′ ) je intensita zá ení dopadajícího do bodu X ze sm ru ω ′

Uv domme si, že výsledek celého výpo tu je hodnota I ( X , ω ) . Implementace tohoto modelu osv tlení je mimo možnosti této práce. Jak je vid t v §5.6, již p edchozí model s jednoduchým rozptylem je velkým zatížením. Problém násobného rozptylu je ovšem ješt o ád složit jší.

Empirický model podle Kniss et al. V mnoha pracích a na mnoha ukázkách bylo prokázáno, že vliv násobného rozptylu a tedy nep ímé propagace sv tla v objemu je velmi d ležitý pro simulaci mnoha fenomén a i b žný uživatel je schopen zachytit jeho nep ítomnost v polopr hledných mediích jako nap íklad mraky, kou i vosk. Proto bylo vyvinuto spousta zjednodušení problému obecného rozptylu tak, aby tento jev mohl být alespo áste n simulován. V této ásti si p edstavíme alespo jeden takový model, jako zástupce za adu ostatních. Tato zjednodušení lze rozd lit do dvou kategorií. V prvním p ípad se jedná o zjednodušení vlastností média i okolních vliv tak, aby bylo možné zobrazovací rovnici analyticky spo ítat. Tato omezení bývají ovšem asto p íliš velká. Jedná se nap íklad o požadavek homogenní hustoty média i omezení konfigurace sv telných zdroj .

Obrázek 3.8: Princip modelu podle Kniss et al. P evzato z [Kniss et al. 02a]

Druhou skupinou jsou empirické aproximace. Tyto aproximace zám rn vypoušt jí n kterou z ástí zobrazovací rovnice tak, aby bylo visuáln dosaženo požadovaného efektu i za cenu, že výpo et je evidentn nekorektní. Model, který je prezentovaný v práci [Kniss et al 02a] spadá do druhé kategorie. Auto i si všímají faktu, že nejd ležit jším efektem, který násobný rozptyl

42

Kapitola 3: P ímé zobrazovací metody p ináší, je propagace sv tla objemem dále, než by bylo možné jen za p ímého osv tlení. Jejich snahou je tedy napodobit tento efekt. Obrázek 3.8 ukazuje princip tohoto empirického modelu. Na obrázku vlevo vidíme situaci p i reálném násobném rozptylu, kdy se zá ení do bodu S dostává ze všech sm r . Na obrázku vpravo je situace zjednodušena tak, že uvažujeme p ísp vek nikoliv ze všech sm r , ale pouze ze sm r pod ur itým úhlem θ . D ležité je, že vzhledem ke sm ru zdroje osv tlení, leží všechny pot ebné body p ed bodem S. Tento fakt umož uje po ítat p ísp vek nep ímého osv tlení po úrovních ve sm ru od zdroje sv tla (jak je na obrázku nazna eno horizontálními bílými arami). Na výsledcích prezentovaných autory se ukazuje, že tato p ibližná aproximace dává rozumn vypadající výsledky a že hlavní cíl, tedy simulovat propagaci sv tla objemem, je dosažen. Na Obrázek 3.9 jsou ukázány dosažené výsledky.

Obrázek 3.9: Výsledky empirického modelu. P evzato z [Kniss et al. 02a]

Obrázek vlevo ukazuje fotografii voskové sví ky a napravo je ta samá scéna zobrazená pomocí prezentovaného empirického modelu. Vidíme, že sv tlo je opravdu propagováno ve sm ru od sv telného zdroje. Díky zanedbání n kterých p ísp vk ovšem znateln mén . Pokud bychom ovšem nem li k dispozici fotografii, jen velmi zkušený pozorovatel by poznal rozdíl.

3.2.2 Empirické mapování V p edchozí sekci jsem podrobn prezentoval fyzikáln založené optické modely a na konci jeden empirický model, jehož ú elem je ovšem simulovat reálné vlastnosti látky a empirický postup je použit pouze k zjednodušení fyzikální reality. V oblasti v decké vizualizace ovšem nemusí být reáln vypadající obrázek vždy cílem. N kdy to ani není možné, nebo nap íklad p i zobrazování map elektronové hustoty neexistuje pozorovatelná fyzikální p edloha. Cílem ve v decké vizualizaci je náhled na data, a proto je n kdy žádoucí barvou i stínováním zd raznit n které rysy v datech. Jiným p ípadem, kdy je lepší sáhnout po empirickém mapování je moment, kdy pot ebujeme zobrazit n jakou vlastnost dat, která by p i fotorealistickém zobrazení z stala skryta. Tyto modely bývají asto konstruovány p ímo pro konkrétní množinu dat, na rozdíl od fyzikáln založených optických model . Nej ast ji tyto modely po ítají n jakou z verzí optického modelu prezentovaného v §3.2.1. Nepoužívají ovšem tento výpo et pro všechny barevné kanály, ale s výsledkem pracují jako se skalárem, který modifikuje empiricky ur ené mapování do barevného prostoru. Jedním takovým modelem je model prezentovaný v práci [Sabella 88].

43

Kapitola 3: P ímé zobrazovací metody

Model podle Sabelly V této práci je prezentována metoda pro zobrazování objemu založená na vrhání paprsku. Podél každého z paprsk je po ítána utlumovaná intensita vyza ující látky analogicky, jako v §3.2.1 v pohlcujícím a vyza ujícím modelu. Výsledek toho výpo tu je skalár ur ují intensitu zá ení podél daného paprsku. Zajímavý je zp sob, jak jsou další vlastnosti objemu mapovány do barevného prostoru. V následujících výrazech používám identické zna ení jako v §3.2.1.

Obrázek 3.10: Výsledky mapování podle Sabelly. P evzato ze [Sabella 88]

Podél paprsku jsou sledovány následující vlastnosti:

• Maximální hodnota M podél paprsku: M = max 0D (τ ( t ) ) • Vzdálenost M od bodu pro t = D • Utlumená intensita I, která je výsledkem výpo tu pomocí optického modelu D

• T žišt C: C =

tτ ( t ) dt

0 D

τ ( t ) dt

0

Pro práci s barvou pak není použit b žn jší RGB model, ale HSV model. Mapování je dvou druh : 1. M je mapováno na odstín H, D je mapováno na saturaci S, I je mapováno na sv tlost V 2. M je mapováno na odstín H, C je mapováno na saturaci S, I je mapováno na sv tlost V Výsledkem toho mapování jsou tedy obrázky, kde barva ur uje velikost maximální hodnoty ( ervená je nejv tší). ím blíže je tato maximální hodnota k pozorovateli, tím je barva jasn jší a ím hustší je látka v daném míst , tím sv tlejší toto místo je. Výsledky jsou ukázány na Obrázek 3.10. Vlevo jsou seismická data zobrazená pouze pomocí intensity I. Vpravo ta samá data s mapováním barev podle klí e 1.

3.3 Zobrazovací postupy V následujících podkapitolách jsou prezentovány ty i t ídy p ístup k zobrazování objemu. Z hlediska principu zobrazovacího systému tak, jak je uveden v §1.2 budu

44

Kapitola 3: P ímé zobrazovací metody hovo it o krocích (s3, s4), tedy klasifikaci dat a jejich promítnutí na pr m tnu. P itom se budu hojn odkazovat na §3.2 o optických modelech. Kroky (s1, s2) se nezabývám z d vod uvedených v §1.2. Tento p ístup je ve shod s praxí autor p vodních prací, kte í se typicky odkazují na stejné p edpoklady. Krok (s5) je implicitn daný použitou architekturou. Dále budu p edpokládat, že existuje skalární spojitá funkce f ′ ( X ) : 3 → , která vrací hodnoty v libovolném bod objemu X. Typicky je tato funkce implementována pomocí interpolace z diskrétních vstupních hodnot. V praxi se používají dva zp soby interpolace. První z nich je hodnotou nejbližšího souseda, což znamená, že pro daný bod X nalezneme nejbližší bod m ížky a jeho hodnotu vrátíme jako hodnotu v bod X. V tomto p ípad se na objem konceptuáln nahlíží jako na sadu voxel , kde každý voxel má definovanou hodnotu, která je konstantní p es celý jeho objem. Druhým konceptuálním náhledem je, dívat se na objem jako na sadu hodnot v uzlových bodech a p i dotazu na hodnotu v bod X ji interpolovat z hodnot uzl v okolí tohoto bodu. Nej ast ji je používána trilineární interpolace, kdy je hodnota ur ena z osmi nejbližších uzl . Lze se setkat i s interpolacemi vyšších ád , ale pouze pom rn z ídka. Je to zejména z d vodu, že uvád ná interpolace je jednou z nej ast jších operací p i zobrazování objemu a tedy cena, nap íklad trikubické interpolace, kdy používáme 64 sousedních uzlových hodnot, je p íliš vysoká. N kdy budu také tuto funkci z d vodu p ehlednosti psát jako f ( t ) : → , kde t bude zna it parametr na paprsku.

3.3.1 Metody pr ez Metoda pr ez vznikla jako snaha využít specializovaných schopností hardware k urychlení zobrazování objemu. Nejvíce perspektivní z nich bylo hardwarov urychlované mapování textur, p esn ji trilineární interpolace implementovaná p i tení hodnot z 3D textur. Typicky je vytvo ena sada polygon , vzniklá o ezáním rovin rovnob žných s pr m tnou pomocí obálky objemu. Na tyto polygony je pak namapována 3D textura (tedy vlastní objemová data) a je ponecháno na hardware, aby provedl interpolaci z hodnot uložených v textu e. Výhodou toho p ístupu je snadnost implementace a vysoká rychlost zobrazování. Množství kódu, které musí programátor fyzicky napsat je p ekvapiv nízké. asto sta í pomocí standardizovaných API pouze vhodn nastavit zobrazovací et zec a množinu rovin pro o ezávání a hardware a runtime p íslušného API provede v tšinu zbývajících operací. Nevýhodou je, že množství pam ti pro uložení 3D textury je jen omezené a tak i na nejmodern jších konzumních grafických kartách lze zobrazovat pouze st edn velké množiny dat.

Historie Poprvé byl tento p ístup použit v práci [Cullip a Neumann 93]. Využit byl p itom hardware v tehdejších stanicích firmy SGI s názvem RealityEngine. Rychlost této metody byla na tehdejší dobu skute n revolu ní. Auto i dosahují na datech velikosti 128x128x64 p i výstupu do okna 512x512 rychlostí okolo 10 fps. Postup byl dále zkoumán a rozší en na aplikace v medicín v práci [Cabral et al. 94]. V následujících letech byly tyto techniky zdokonalovány a postupn byl p ístup založený na 45

Kapitola 3: P ímé zobrazovací metody mapování textur p ijat jako metoda p ímého zobrazování objemu schopná dosáhnout interaktivních rychlostí. Byl k tomu využíván speciáln zkonstruovaný hardware v pracovních stanicích [Van Geldern a Kwansik 96, Westermann a Ertl 98, Meissner et al. 99] a pozd ji i hardware konzumních po íta , jako nap íklad v pracích [RezskSalama et al. 00, Engel et al. 01, Guthe et al. 02, Kniss et al. 02a]. V nedávné dob byl tento p ístup, spolu s ist vyza ujícím modelem plyn , použit pro vizualizaci planetárních mlhovin [Magnor et al. 04]

Princip Následující výklad sleduje práci [Cullip a Neumann 93]. Abychom mohli zobrazovat objemová data, pot ebujeme um t vzorkovat tato data podél paprsk , které sm ují od pozorovatele skrze pr m tnu do objemu. Uvážíme p ípad, kdy tyto vzorky leží vždy v jedné rovin . Potom m žeme tuto rovinu nahradit jedním polygonem a na n m vzorkování provést. Pokud navíc uložíme vstupní objemová data jako 3D texturu, je postup velmi p ímo arý. Sta í vygenerovat sadu polygon v p íslušných pozicích uvnit objemu a namapovat na n tuto 3D texturu. Hardware pak již zajistí správné navzorkování. Jsou dva možné p ístupy, jak umístit vzorkovací polygony do objemu. Bu je možné je orientovat v sou adnicovém prostoru objemu nebo v sou adnicovém prostoru pr m tny. Obrázek 3.11 nalevo ukazuje situaci p i práci v sou adnicovém prostoru objemu, obrázek napravo p i práci v sou adnicovém systému pr m tny. P i práci v sou adnicovém systému objemu je nutné nejprve ur it osu, která je nejvíce rovnob žná se sm rem pohledu. To lze ud lat nap íklad analýzou pohledové a modelové matice. Polygony poté vygenerujeme p ímo tak, aby byly kolmé na tuto osu a ležely p esn uvnit objemu. P i práci v sou adnicovém systému pr m tny m žeme polygony vygenerovat p ímo. Je ovšem nutné, je pak p evést do sou adného systému objemu a tam je, podle ohrani ující obálky objemu, o íznout. Nicmén i tuto operaci m že velmi rychle provád t grafický hardware.

Obrázek 3.11: Orientace vzorkovacích polygon . P evzato z [Cullip a Neumann 93].

Poslední v cí, kterou zbývá rozhodnout, je jakým zp sobem budeme hodnoty navzorkované na polygonech skládat. Lze to provést pomocí n jaké obecné operace skládání, pokud nám nejde o fyzikální v rnost. Pokud bychom cht li simulovat nap íklad pohlcující model tak, jak je prezentován v §3.2 a generovat tak obrázky podobné negativu rentgenovým snímk m, je pot eba do kompozice zahrnout vzdálenost mezi jednotlivými vzorkovacími polygony. Tato vzdálenost je jiná pro každý paprsek, ale stejná pro všechny vzorky na paprsku. V takovém p ípad sta í za objem umístit dodate ný polygon, který bude mít namapovanou texturu

46

Kapitola 3: P ímé zobrazovací metody s akumulovanými vzdálenostmi mezi rovinami. Tuto texturu je pak pot eba p epo ítávat p i každé zm n pozice pozorovatele.

3.3.2 Metody otisk Historie Ke konci devadesátých let byly vyvinuty nové p ístupy, které lze souhrnn ozna it jako metody otisk (splatting). První takovou metodou je V-buffer prezentovaný v [Upson a Keeler 88], následovaný prací Westovera [Westover 90]. Spole nou myšlenkou t chto metod je promítnout každou bu ku objemu na pr m tnu a pomocí rekonstruk ního, typicky Gaussovského jádra (nazývaného otisk bu ky), ur it její p ísp vek do pixel výsledného obrazu. Princip Následující postup sleduje práci [Westover 90]. Základní kroky „splatting“ algoritmu lze shrnout následujícím zp sobem: 1. Zpracováváme jednu bu ku objemu za druhou. Podle druhu m ížky a velikosti otisku lze ur it, které bu ky se nemohou ovliv ovat a zpracovávat více bun k objemu najednou. 2. Ur íme st ed otisku bu ky na pr m tn . 3. Ur íme tvar (rozsah) otisku bu ky na pr m tn . 4. Pro každý pixel, který je otiskem pokryt ur íme integrací rekonstruk ního jádra p ísp vek otisku do pixelu 5. P ísp vek z p edchozího kroku p i teme k již akumulované hodnot v pixelu. Pokud tato hodnota p esáhla nap íklad maximální mez pr hlednosti, lze pixel ozna it a v dalších bu kách jej již nezpracovávat. Tento na první pohled jednoduchý algoritmus má adu úskalí. Prvním z nich je ur ení tvaru otisku na pr m tn . Jako tvar, který promítáním deformujeme, je použita koule. Koule se nám m že promítnout do kruhu nebo do elipsoidu. Tvar otisku závisí na zvolené projekci a druhu m ížky, ve které jsou objemová data uložena. Pokud máme stejnou vzdálenost mezi bu kami m ížky ve všech sm rech (pracujeme tedy s kartézkou m ížkou), tak p i rovnob žném promítání je otisk vždy kruh a navíc pro daný sm r pohledu vždy stejný pro všechny bu ky objemu. Pokud je m ížka jiná, je pot eba otisk po ítat, v nejhorším p ípad pro každou bu ku zvláš . Obdobný nep íjemný p ípad nastává u perspektivního promítání, kde se koule také promítne na elipsoid a je nutné jej po ítat pro každou bu ku zvláš . Tím ovšem t žkosti nekon í. V bodu 4. je uvedeno, že p ísp vek získáme integrací rekonstruk ního jádra. Typicky složitost jádra odpovídá nep ímo úm rn kvalit zobrazení. Proto jádra asto nelze integrovat analyticky nebo to ani z d vodu výpo etní složitosti není možné (uvažme, že tato integrace jádra je jednou z nej ast jších operací algoritmu). Mezi použitá jádra pat í nap íklad kužel, Gaussovské jádro nebo n kolik prvních vln funkce sync. Proto bývají hodnoty jádra p edintegrovány pro obecný tvar otisku a uloženy v tabulce. V tomto p ípad je nutné transformovat pohledov závislý otisk na obecný otisk tak, aby bylo možné vyzvednout správnou hodnotu z p edp ipravené tabulky. Jedná se tedy o transformaci z elipsoidu na kruh. Je také jasné, že velikost tabulky velmi ovliv uje kvalitu zobrazení. Velikosti tabulek jsou ádku desítek na každý rozm r.

47

Kapitola 3: P ímé zobrazovací metody

3.3.3 Faktorizace Historie metody V pracích [Cameron a Undrill 92, Lacroute a Levoy 94] byla prezentována ješt další metoda. Již d íve byly snahy využít koherence bun k objemu i pixel pr m tny pro urychlení existujících metod. Problémy zp sobovala p edevším perspektivní projekce, dlouhá doba p edzpracování objemu nutná pro vytvo ení prostorov koherentních datových struktur a jejich pohledová závislost. Metoda faktorizace (shear-warp factorization) spo ívá v rozd lení (faktorizaci) pohledové matice na dv (u n kterých autor i více) ásti. Nejprve jsou objemová data promítnuta na do asnou pr m tnu a poté je obraz na této pr m tn zdeformován jednoduchou 2D transformací na skute nou pr m tnu. Princip metod spo ívá v tom, že do asná pr m tna je rovnob žná s jednou z primárních os a pixely v ní jsou zarovnány s bu kami objemu, což umož uje jeho efektivní promítnutí. Výhodou t chto metod je využití prostorové koherence objemových dat p i uchování krátké doby p edzpracování a pohledové nezávislosti. Princip Následující výklad sleduje práci [Lacroute a Levoy 94]. Princip celé metody spo ívá v transformaci objemových dat do pomocného sou adného systému, který je zvolen tak, aby se v n m objemová data snadno a rychle promítala na pr m tnu. Zavedeme pomocný „zkosený“ sou adnicový systém následujícím zp sobem: Zkosený sou adnicový systém je takový, v n mž jsou všechny promítací paprsky (viewing rays) rovnob žné se t etí sou adnou osou. Dále budeme p edpokládat, že objemová data jsou vzorkována na rovnob žné m ížce. Transformaci dat do zkoseného sou adného systému provedeme tak, že ur íme, který z hlavních sm r je nejvíce rovnob žný se sm rem pohledu a p euspo ádáme sou adnice tak, aby tento sm r byl v po adí t etí. Následn zkosíme objemová data v osách kolmých na tento sm r a provedeme promítnutí na do asnou pr m tnu. Pokud používáme perspektivní promítání, musíme krom zkosení objemovým dat m také p íslušn zm nit m ítko.

Obrázek 3.12: Zkosení p i rovnob žném promítání. P evzato z [Lacroute a Levoy 94].

Výše uvedený postup pro rovnob žné promítaní ukazuje Obrázek 3.12 a perspektivní p ípad ilustruje Obrázek 3.13.

48

Kapitola 3: P ímé zobrazovací metody

Obrázek 3.13: Zkosení p i perspektivním promítání. P evzato z [Lacroute a Levoy 94].

Definici zkoseného sou adného systému m žeme formalizovat jako faktorizaci pohledové matice na t i ásti:

M view = P ⋅ S ⋅ M warp

(3.20)

kde: • M view je pohledová matice • P je permuta ní matice, která prohazuje sou adnice tak, jak je popsáno výše • S je matice zkosení, p ípadn matice zkosení a zm ny m ítka Matice zkosení je velmi jednoduchá:

S paral =

1

0

0 0

0

1

0 0

sx

sy

1 0

0

0

0 1

(3.21)

kde: • sx je míra zkosení v první sou adné ose

• s y je míra zkosení v druhé sou adné ose Pro perspektivní p ípad není o mnoho složit jší:

S persp =

1

0

0

0

0

1

0

0

sx

sy

1 sw

0

0

0

kde: • sx je míra zkosení v první sou adné ose

• s y je míra zkosení v druhé sou adné ose • sw je míra zm ny m ítka

49

1

(3.22)

Kapitola 3: P ímé zobrazovací metody Poslední len, tedy matici M warp získáme jako dopln k výše uvedeného sou inu, tedy: M warp = S −1 ⋅ P −1 ⋅ M view . Nyní m žeme celý algoritmus shrnout do t í krok : 1. Objemová data jsou transformována do zkoseného sou adného systému pomocí matice S. Matice P ur uje kolmo k jakému sm ru budeme posouvat. 2. Transformovaná a p evzorkovaná data promítneme na do asnou pr m tnu, která je také ve zkoseném sou adném systému a je kolmá na hlavní sm r. 3. Obraz na do asné pr m tn zdeformujeme pomocí matice M warp do kone né podoby. Výše uvedený postup prezentuje základní verzi algoritmu. D ležitým krokem, kv li kterému je celý algoritmus navržen, je projekce na do asnou pr m tnu. Díky tomu, že máme možnost data libovoln v i pixel m pr m tny naškálovat a zarovnat, otevírá se prostor pro mnoho urychlovacích technik, které jsou v obecném p ípad nepoužitelné i p íliš „drahé“. Jejich podrobný popis lze nalézt nap íklad v práci [Lacroute a Levoy 94].

3.3.4 Vrhání paprsku Metody založené na vrhání paprsku se objevují velmi brzo po prvních metodách hledajících povrch. Jsou velmi p irozeným zp sobem, jak ešit rovnice uvedené v §3.2. Ve skute nosti jsou p ímým rozší ením zp sobu, jak jsou tyto rovnice odvozovány. Není proto náhodou, že tyto metody se objevují spolu s prvními prácemi o použití teorie ší ení zá ení v po íta ové grafice. Jejich velkou výhodou je schopnost generovat vysoce kvalitní výstup a velmi snadná implementace základních variant t chto algoritm . Nevýhodou je vysoká výpo etní náro nost, která velmi dlouho vy azovala metody toho druhu z použití pro interaktivní aplikace.

Historie Od po átku osmdesátých let byly zkoumány nové p ístupy k zobrazování objemu. Ukazovalo se, že metody hledající povrch jsou vhodné pouze pro n které aplikace a v p ípad , že bychom se snažili zobrazit objem jako celek, jsou zcela nedostate né. Jednou z motivací za touto snahou byl ur it fakt, že mnoho p írodních fenomén lze pohodln definovat práv ve form objemových dat, ale k jejich fotorealistickému zobrazení nesta í vykreslovat povrch ur ený jedním nebo více prahy. Objevují se proto nové p ístupy založené na technice vrhání paprsku a výpo tu chování sv tla uvnit objemu podél této lineární dráhy. Pro fotorealistické zobrazení p írodních fenomén , jako mlha i mraky, bylo pot eba realisticky modelovat p enos zá ení uvnit objemu a zobrazovat jej jako polopr hledný materiál. Poprvé byly integrální rovnice pro simulaci p enosu zá ení uvnit objemu použity Blinnem [Blinn 82], který s jejich pomocí zobrazoval rovinnou atmosféru. V následujích letech byla jeho technika rozší ena na obecn jší objekty [Max 83], [Voss 83], byly formulovány rovnice i pro simulaci sekundárního rozptylu [Kajiya a Von Herzen 84] a byla prezentována nutnost jejich použití v objemech s vysokou

50

Kapitola 3: P ímé zobrazovací metody mírou rozptylu (high-albedo volumes). Jak je vid t z chronologických údaj , vývoj t chto metod probíhal ruku v ruce s rozvojem ostatních oblastí po íta ové grafiky a není náhodou, že st žejní práce globálních osv tlovacích metod [Kajiya 86], kde je formulována integrální globální zobrazovací rovnice, byla publikována nedlouho po práci [Kajiya a Von Herzen 84], kde byly prezentovány rovnice pro sekundární rozptyl sv tla, které jsou založeny na totožném fyzikálním principu, tedy p enosu zá ení v prost edí. V dalších letech byla zkoumána možnost zobrazovat s objemovými daty také standardní polygonáln reprezentované objekty, nap íklad [Levoy 90]. Tato snaha byla motivována jednak aplikacemi ve fotorealistickém zobrazování, kde objemová data tvo ila jen menší ást zobrazovaných objekt , ale také medicínskými a v deckými aplikacemi, kde bylo pot eba spolu s objemem zobrazovat pomocné objekty, které umož ují lepší náhled na data. Jedná se nap íklad o sm ry lé ebných radioaktivních paprsk v onkologii modelované jako komolé kužele, um lé kloubní a jiné náhrady v ortopedii i dvourozm rné m ížky umožnující lepší prostorovou orientaci a svázání objemového modelu s jeho prost edím V souvislosti se vzr stem výkonu b žn dostupných grafických karet byly zkoumány implementace i mimo pracovní stanice na konzumním grafickém hardware. Byla publikována implementace rekurzivního sledování paprsku [Purcell et al. 02] a o rok pozd ji i zobrazování objemu pomocí vrhání paprsku, které bylo rozší eno o standardní urychlovací techniky, jako je p ed asné ukon ení zpracování paprsku (early ray-termination) a p eskakování prázdného prostoru (empty-space skipping) [Krüger 03]. P i použití obou t chto urychlovacích technik auto i dosahují, v závislosti na druhu zobrazované scény, rychlostí mezi 13.6 a 23.4 snímk za vte inu p i vykreslování do tvercového okna o stran 512 pixel . Nicmén v ur itých p ípadech použití t chto urychlovacích technik výpo et naopak zpomaluje. Jedná se zejména o polopr hledné objemy vypl ující celou obálku, nebo zde se ani jedno z kritérií neuplatní.

Princip Princip této metody je dob e známý a je podrobn rozebírán dále, zmíním se proto o n m na tomto míst jen velmi stru n . Algoritmus vychází z faktu, že k ur ení barvy pixelu v pr m tn je pot eba zjistit množství dopadajícího zá ení na plochu tohoto pixelu. Zá ení budeme sledovat podél paprsku, který vrháme v opa ném sm ru než proudí zá ení, tedy od pozorovatele skrze pr m tnu ven do scény. V oblasti zobrazování objemových dat je ur en pr se ík tohoto paprsku s obálkou objemu. ást paprsku, která leží uvnit objemu je navzorkována a p ísp vky z jednotlivých vzork jsou složeny do výsledné hodnoty, kterou tento paprsek do pixelu p isp je. Zp sob , jak jsou navzorkované hodnoty na paprsku skládány, je velké množství a n které z nich byly p edstaveny v §3.2. D ležité je také poznamenat, že nemusí existovat korespondence 1:1 mezi pixely pr m tny a paprsky. Je možné vrhat více paprsk jedním pixelem a stejn tak symetricky n které pixely opomíjet a hodnoty v nich dopo ítávat z hodnot soused . Je samoz ejmé, že do výše zmín né analogie s dopadajícím zá ení má tento základní algoritmus daleko. Je ovšem výhodou této metody, že ji lze snadno rozši ovat tak, aby se maximáln blížila fyzikální realit . V tšinou ovšem za cenu zvýšení výpo etní náro nosti. 51

Kapitola 3: P ímé zobrazovací metody

3.3.5 Jiné p ístupy Zcela odlišný a ojedin lý p ístup byl prezentován v pracích [Dunne et al. 90, Levoy 92, Malzbender 93, Totsuka a Levoy 93]. Jeho význam je spíše v ukázce rozmanitosti p ístup k danému problému, než v praktické použitelnosti. Je zde použito zobrazování objemu pomocí p evodu do frekven ní oblasti. Objemová data jsou nejprve p evedena Rychlou Fourierovou Transformací do frekven ní oblasti. Poté je v této t ídimenzionální projekci vybrán pr ez, který je obsažený v rovin rovnob žné s pr m tnou a procházející po átkem. Tento pr ez je pak Inverzní Fourierovou Transformací p eveden zp t do prostorové oblasti a zobrazen. Velkou nevýhodou t chto metod je neschopnost zachytit zakrytí ástí objemu místy, která jsou blíže k pozorovateli.

3.4 Komentá Nyní máme p ehled o p ímých metodách zobrazování objemu a je tedy možné op t zhodnotit jejich vhodnost pro implementaci na GPU. V §2.3 jsem zd vodnil, pro objektov orientované metody nejsou vhodné pro implementaci na GPU a tak metody otisk a faktorizace z následující diskuse rovnou vypadávají. Z stávají dv metody a to metoda pr ez a metoda vrhání paprsku. Je na první pohled z ejmé, že tyto dv metody jsou velmi podobné. Metoda pr ez je analogická metod vrhání paprsk . Pouze vzorkování neprovádí po jednotlivých paprscích, ale po rovinách. Jako základ pro implementovanou metodu jsem zvolil vrhání paprsku z následujících t í d vod : • Implementace této metody pomocí grafického hardware je daleko mén prozkoumaná. V tšina prací o hardwarov urychlovaném zobrazování objemu se donedávna v novala práv metodám pr ez . Proto je tato oblast dob e prozkoumána a metoda sama nenabízí p íliš mnoho možností k softwarové optimalizaci. Je to práv proto, že její hlavní výhoda je v masovém provád ní jednoduchých operací p ímo pomocí hardware. • Metoda má v tší potenciál, co se tý e rozši itelnosti. Pokro ilé efekty jako nap íklad lom sv tla jsou pomocí vrhání paprsku, p esn ji jeho rozší ení rekurzivního sledování paprsku, lépe implementovatelné • Metoda pr ez je evidentn limitovaná rasteriza ní rychlostí grafického hardware. Naproti tomu metoda vrhání paprsku nabízí ur ité možnosti, jak ást zát že p enést do stadia zpracování vrchol . (viz §5.4.1).

52

Kapitola 4

Návrh metody pro implementaci na GPU Na základ poznatk shrnutých do p edchozích kapitol této práce, jsem navrhl a implementoval metodu pro zobrazování objemu na GPU. P i návrhu jsem se ídil cíli uvedenými v §1.5. Na úvod v §4.1 p edstavím princip implementované metody a uvedu ji do kontextu s klasifikacemi a strukturou zobrazovacího systému uvedenou v kapitole 1. Následuje detailní popis zobrazovacího algoritmu a jeho variant, které byly vyzkoušeny (§4.2). Poté jsou v §4.3 shrnuty použité optické modely a jejich vztah k model m odvozeným v §3.2. Kapitolu uzavírá §4.4 o p íprav vývojových a testovacích dat, v etn dat použitých k vytvo ení ilustrací v této práci.

4.1 Princip ešení Navržená metoda je obrazov orientovaná metoda pro p ímé zobrazování objemu ur ená pro implementaci na platform programovatelného grafického hardware, který podporuje Shader Model 3.0 [DirectX9.0c 05].

Po ízení dat (s1) a jejich úprava do podoby vhodné pro zobrazování (s2) Metoda p edpokládá, že tyto kroky byly provedeny v p edstihu a jejich návrhem se nezabývá. P edpokládám, že výsledkem t chto krok a tedy vstupem do navrhované metody je t ídimenzionální vektorová kartézká m ížka dat. V každém bod této m ížky jsou uloženy ty i hodnoty x, y, z, w. Poslední hodnota w je z rozsahu [ 0,1] a p edstavuje nam enou nebo spo ítanou hodnotu, kterou se metoda snaží vizualizovat. Jak je tato hodnota mapována na barvu a pr hlednos, je závislé na použitém optickém modelu a je to uvedeno u každého z použitých model v §4.3. V dalším textu budu f ( s ) zna it funkci, která pro libovolný parametr s na n jakém paprsku vrací hodnotu w. Tato hodnota je trilineárn interpolována z hodnot vstupní m ížky.

53

Kapitola 4: Návrh metody pro implementaci na GPU První t i hodnoty x, y, z jsou používány jen ve speciálních p ípadech a p edstavují gradient aproximovaný pomocí metody centrálních diferencí, viz §3.2. Každá z t chto t í hodnot leží v intervalu [ −2, 2] .

Klasifikace dat (s3) Klasifika ní funkce se liší podle implementovaného optického modelu a obsahuje vždy sadu parametr , které je možné v reálném ase nastavovat a m nit tak do ur ité míry zp sob interpretace vstupních dat. Podrobn jsou tyto úpravy rozebrány v §4.3 Promítnutí dat na pr m tnu (s4) Vlastní promítání na pr m tnu je provád no pomocí vrhání paprsku. Metoda modifikuje klasický obrazov orientovaný p ístup v tom smyslu, že paprsky nejsou vrhány pro každý pixel pr m tny, ale jenom pro pixely, do kterých zasahuje pr m t obálky objemu (viz následující podkapitola). U složit jších optických model je provád no stínování a výpo et vržených stín . Oba tyto kroky jsou implementovány p ímo p i procesu vzorkování paprsku a jsou opakovány p i každém vzorkování vstupních dat. To umož uje metod interaktivn reagovat, jak na zm nu pozice pozorovatele, tak na zm nu osv tlovacích podmínek. Metoda neklade omezení na po et a konfiguraci sv telných zdroj . Lze tedy používat sv telné zdroje v libovolné pozici, v etn pozice uvnit zobrazovaného objemu. Lze používat i libovolné bodové sv telné zdroje. Pozice pozorovatele je omezena na prostor vn obálky objemu. Jakmile se pozorovatel ocitne uvnit , p estane metoda objemová data zcela zobrazovat. Zobrazení pixel pr m tny (s5) Hodnoty spo ítané pro dané pixely pr m tny jsou následn automaticky zapisovány do obrazové pam ti, odkud jsou p ímo zobrazovány. Metoda je schopná pracovat ve dvou odlišných režimech. První režim je pro samostatné zobrazování objemových dat. V tomto režimu je na za átku zpracování každého snímku barevný buffer vy išt n a pam hloubky vypnuta. Hodnoty získané pomocí vrhání paprsk jsou pak p ímo zapisovány do barevného bufferu. V druhém režimu metoda nic nep edpokládá o obsahu barevného bufferu a pam hloubky je zapnuta. Získané hodnoty jsou pak do barevného bufferu míchány pomocí alfa kanálu. Tak je možné spolu s objemovými daty zobrazovat také polygonální geometrii nebo i jiná objemová data. Omezením je, že tato data se nesmí protínat s obálkou objemu. P i tomto režimu jsou hodnoty již uložené v barevném bufferu správn objemem utlumeny. P íklad takové kombinace je na Obrázek 3.2 vlevo.

4.2 Zobrazovací algoritmus V této podkapitole se budu detailn zabývat popisem zp sobu promítání dat na pr m tnu. Zam ím se na zp sob vrhání paprsku a kompozice navzorkovaných dat podél tohoto paprsku. Nejprve je t eba pro objemová data definovat takzvanou proxy geometrii. Proxy geometrie je polygonální objekt reprezentovaný trojúhelníkovou sítí a spl uje následující kritéria:

54

Kapitola 4: Návrh metody pro implementaci na GPU

Obálka Proxy geometrie musí být obálkou zobrazovaného objemu. Jakákoliv ást objemu, která se nachází mimo proxy geometrii nebude zobrazena. Konvexita Proxy geometrie musí být konvexní t leso. Pokud by tomu tak nebylo, nebude metoda poskytovat korektní výsledky. P i použití generování paprsk pomocí dvou pr chod (viz níže) je nutný p edpoklad, že na libovolném paprsku leží práv jeden fragment p ivrácených ploch a práv jeden fragment odvrácených ploch proxy geometrie. P i použití geometrického p ístupu by bylo z ejm možné metodu modifikovat tak, aby p ipoušt la, že pr nik paprsku s proxy geometrií je tvo en více úseky. Tato možnost ovšem nebyla zkoumána, zejména z d vodu, že omezení na konvexní proxy geometrii nep ináší žádné výrazné problémy. V implementaci byl použit jako proxy geometrie osov orientovaný kvádr. Transformace proxy geometrie v zobrazované scén také ur uje transformaci zobrazovaného objemu. Objemová data jsou vždy transformována tak, že vypl ují práv vnit ek proxy geometrie. Zobrazování objemu zahájíme posláním dat proxy geometrie do zobrazovacího et zce. Proxy geometrie je promítnuta na pr m tnu a rasterizována na jednotlivé fragmenty. Pro každý takový fragment vygenerujeme paprsek od pozorovatele a ur íme jeho pr se íky s proxy geometrií objemu. Vznikne tedy orientovaná úse ka, kterou v pravidelných krocích navzorkujeme a ur íme v t chto bodech hodnotu klasifika ní funkce f . Takto získané hodnoty p evedeme pomocí n jaké klasifika ní funkce na smysluplné hodnoty, které poté pr chodem zep edu-dozadu složíme. Jakým zp sobem se takto získaná hodnota vztahuje k výsledné barv fragmentu je odvislé od použitého optického modelu. Tento fragment je pak odeslán k dalšímu zpracování v zobrazovacím et zci, jak bylo popsáno výše. Následující dv podkapitoly se v nují zp sob m generování paprsku, jeho vzorkování a kompozici získaných dat.

4.2.1 Generování paprsku Nyní jsme v algoritmu v situaci, kdy máme k dispozici prostorové sou adnice bodu F na povrchu p ivrácené plochy proxy geometrie, který p isp je do práv zpracovávaného fragmentu. Nejprve pot ebujeme paprsek, který je ur en tímto bodem a pozicí kamery. Za druhé pot ebujeme ur it dva parametry na tomto paprsku, které ur ují jeho pr nik s proxy geometrií. Paprsek hledáme v parametrickém tvaru ur ený jedním jeho libovolným bodem a sm rových vektorem. Paprsek je pak množina bod , pro které platí:

P = S + t ⋅v kde: • P je bod paprsku • S je jeho po áte ní bod • t je parametr paprsku

55

(4.1)

Kapitola 4: Návrh metody pro implementaci na GPU

• v je sm rový vektor. Pot ebujeme tedy nalézt ty i hodnoty: Sou adnice po áte ního bodu S, sm rový vektor v a dv hodnoty t0 a t1 parametru paprsku t, které ohrani ují množinu bod paprsku ležících uvnit proxy geometrie. Následující dv podkapitoly prezentují použité metody pro výpo et t chto hodnot.

Použití dvou pr chod Prvním p ístupem, který jsem implementoval byl výpo et pomocí dvou pr chod p es proxy geometrii. Nejd íve se v prvním pr chodu uloží pomocné informace. Tyto informace se v druhém pr chodu použijí k ur ení sm rového vektoru paprsku a k ur ení parametr t0 a t1. Pro první pr chod nastavíme orientaci vykreslovaných primitiv tak, aby se vykreslovaly odvrácené plochy. Pro každý fragment t chto odvrácených ploch se tedy provede kód p ipraveného fragment shaderu. V n m zaznamenáme sou adnice vektoru vb ur eného sou adnicemi bodu F a pozicí kamery C. Pro druhý pr chod oto íme nastavení orientace primitiv tak, aby se tentokrát vykreslovaly p ivrácené plochy. Obdobn jako vektor vb , spo ítáme vektor v f daný op t jako rozdíl sou adnic bodu F a pozice kamery C. (zde dochází k kolizi ve zna ení, ovšem z d vodu p ehlednosti tento nedostatek neopravuji. V obou pr chodech zna ím bod na povrchu proxy geometrie, který reprezentuje aktuáln zpracovávaný fragment, F. Ovšem pokaždé se jedná o bod s jinými sou adnicemi)

Obrázek 4.1: Generování paprsku ve dvou pr chodech.

Z uvedených dvou vektor jsme již schopni ur it všechny požadované informace. Jako po áte ní bod S paprsku použijeme sou adnice bodu F. Sm rový vektor v paprsku spo teme jako rozdíl vektor vb a v f (Obrázek 4.1) Zbývá nám ur it hodnoty parametr t0 a t1. Vzhledem ke zp sobu výpo tu vektoru v a ur ení po áte ního bodu S víme, že hledané hodnoty jsou t 0 = 0 a t1 = 1 , nebo : S + 0⋅v = S

a bod S je shodný s bodem F a je tedy zárove prvním bodem paprsku P = S + t ⋅ v , který protíná proxy geometrii. Zárove víme, že poslední bod E paprsku, který leží uvnit proxy geometrie, lze vyjád it jako

E = C + vb

56

Kapitola 4: Návrh metody pro implementaci na GPU a zárove platí:

S + 1 ⋅ v = S + (vb − v f ) = S − v f + vb = C + vb = E

a tedy t1 = 1 .

Geometrický p ístup Geometrický p ístup byl navržen a implementován podle [Green 05]. Základní myšlenkou toho p ístupu je fakt, že v naprosté v tšin p ípad posta ují jako proxy geometrie jednoduchá primitiva, nap íklad koule i kvádr. Výpo et pr se ík s t mito t lesy je dob e prozkoumán a jsou pro n j vyvinuty efektivní metody. Navíc lze výpo et ješt urychlit pomocí vektorových výpo t na GPU. Geometrický p ístup spot ebuje na vygenerování po áte ního bodu S, vektoru v a dvou parametr t0 a t1 pouze jeden pr chod. V tomto pr chodu je orientace primitiv nastavena tak, jak je b žné, tedy na zobrazování p ivrácených ploch. Pro každý fragment t chto ploch je op t spušt n fragment shader. V tomto shaderu nejprve ur íme paprsek procházející pozicí kamery a bodem F (který obdobn jako v minulém odstavci ozna uje bod na povrchu proxy geometrie, který p isp je do práv zpracovávaného fragmentu) a poté nalezneme analyticky hodnoty parametr t0 a t1, které ur ují vstupní a výstupní bod paprsku v i proxy geometrii. Za po áte ní bod S = (S 0 , S1 , S 2 ) paprsku P použijeme pozici kamery C. Op t p edpokládáme, že pozice kamery je uvedena v sou adném systému proxy geometrie. Sm rový vektor v = (v0 , v1 , v 2 ) získáme jako rozdíl pozice fragmentu a pozice kamery. Jako obalové t leso byl v metod použit osov orientovaný kvádr. Nebo pracujeme v lokálních sou adnicích proxy geometrie, nemusí brát ohled na její posunutí a oto ení. Takovýto kvádr lze ur it pomocí t í skalárních hodnot délek jednotlivých stran. Proto pokud je použit geometrický p ístup, metoda musí na vstupu obdržet vektor hodnot d = (d 0 , d 1 , d 2 ) ur ující po ad délky stran v osách x, y a z. Dolním levým rohem kvádru je tedy bod K bl = (− d 0 / 2,− d1 / 2,− d 2 / 2 ) a horním pravým rohem je bod K tr = (d 0 / 2, d1 / 2, d 2 / 2 ) . Osov orientovaný kvádr se skládá ze t í dvojic rovnob žných rovin. Nejprve vypo teme pr se ík paprsku P s každou z t chto dvojic podle následujícího postupu: , dx − Sx d t0 = 2 , t1 = t0 + x (4.2) vx vx kde: • t0 je jeden hrani ní parametr na paprsku • t1 je druhý hrani ní parametr na paprsku • dx zastupuje hodnotu rozm ru kvádru pro každou z os • Sx zastupuje sou adnici po áte ního bodu paprsku pro každou z os • v x zastupuje sou adnici sm rového vektoru paprsku pro každou z os Nyní máme šest hodnot parametr na paprsku, které ur ují pr se íky se šesti rovinami ur ujícími osov orientovaný kvádr. Z výše uvedeného výpo tu ovšem nemáme zaru eno, že t 0 ≤ t1 , jak bychom o ekávali. Proto dalším krokem je

57

Kapitola 4: Návrh metody pro implementaci na GPU porovnání parametr odpovídajících pr se ík m dvou rovnob žných rovin a jejich p ípadné prohození tak, aby vždy t 0 ≤ t1 Posledním krokem je ur ení správné dvojice parametr na paprsku, která ur uje skute né pr se íky s osov orientovaným kvádrem. Díky zp sobu, jakým generujeme paprsky se nem že stát, že by paprsek kvádr zcela minul. Je to proto, že paprsek je vygenerován z pozice bodu F a tedy již tato hodnota ur uje první pr se ík, který odpovídá parametru t0. Proto je hledání správných dvou parametr zjednodušené a sta í pouze najít nejvnit n jší dvojici, tedy nejv tší z parametr t0 a nejmenší z parametr t1.

Srovnání obou p ístup Nyní se nabízí otázka, který z p ístup je lepší a bylo by výhodn jší jej použít ve výsledném programu. Jako obvykle, není odpov d na tuto otázku jednozna ná a zaleží na kritériích, podle kterých oba p ístupy posuzujeme. Efektivita M ení hodnot fps ukazuje, že za identických nastavení je shader používající geometrický p ístup p ibližn o dv t etiny rychlejší než s pomocí dvou pr chod . To je zp sobeno nižším po tem pr chod u geometrického p ístupu a také efektivitou výpo tu parametr na paprsku, u kterých se ukázalo, že je lze velmi p kn na GPU implementovat s pomocí vektorových operací. Kvalita zobrazení Metoda dvou pr chod trpí nežádoucími artefakty na obrysových hranách proxy geometrie. Je to zp sobeno tím, že v t chto místech jsou paprsky v metod dvou pr chod nekorektn generovány.

Obrázek 4.2: Artefakty metody dvou pr chod

P esn ji se p i implementaci ukázalo, že v textu e, kde jsou uloženy vektory vb , není hodnota v bec zaznamenána, což zna í, že p íslušný fragment nebyl pro odvrácenou plochu v bec vygenerován. Je tedy na teno pozadí textury a vektor tak získá nekorektní sm r. P esný d vod, pro se tak d je, zatím není znám. Obecnost Velkou výhodou metody dvou pr chod je skute nost, že jako proxy objekt je schopná zpracovat libovolnou geometrii. Naproti tomu geometrický p ístup je

58

Kapitola 4: Návrh metody pro implementaci na GPU omezen na explicitn zadaná jednoduchá t lesa. Na první pohled by se tato skute nost mohla jevit jako velké omezení. Ovšem v praktickém použití je její vliv zanedbatelný. To proto, že v tšinu b žných dat lze bez velkých neefektivit (jako nap . p íliš mnoho volného prostoru mezi proxy geometrií a zpracovávanými daty) obalit kvádrem. Stejn tak v tšina proceduráln definovaných objem pracuje 3 s defini ním oborem [ 0,1] , který je pro tyto ú ely vhodný. Záv rem lze tedy íci, že krom speciálních p ípad , kdy pot ebujeme jedine nou proxy geometrii, vychází daleko lépe generovaní paprsk pomocí ist geometrického p ístupu.

4.2.2 Vzorkování paprsku a kompozice Na paprsek vržený od pozorovatele lze koncep n nahlížet jako na sm r ší ení sv tla, podél kterého se snažím aproximovat matematické vztahy uvedené v §3.2. Základním bodem je správná aproximace integrálu tvaru: b

h ( t ) dt

(4.3)

a

kde • h ( t ) je n jaká funkce a t je parametr na paprsku od pozorovatele. Interval [ a, b ] rozd lme na n stejných úsek

délky ∆s . I-tý úsek je ohrani en

hodnotami parametr xi a xi +1 , p i emž xi = a a xn +1 = b . Potom lze vztah (4.3) aproximovat Riemannovskou sumou jako: n i =1

h ( xi ) ∆s

(4.4)

nebo hodnota ∆s je stejná pro všechny intervaly, lze ji vytknout p ed sumu jako

∆s

n i =1

h ( xi )

(4.5)

To nám dává základ, jak vzorkovat objemová data podél dráhy paprsku. Z fáze generování paprsku, popsané v §4.2.1, máme dv hodnoty parametru t0 a t1 , které ohrani ují množinu bod

ležících uvnit proxy geometrie. Položíme x1 = t0 a

xn +1 = t1 , n-krát ur íme požadované hodnoty v bodech S + xi v a složíme je podle vzorce (4.5). Hodnoty, které budeme skládat, se liší podle použitého optického modelu. N kdy se jedná pouze o klasifika ní funkci pro útlum, jindy o sadu hodnot ur ujících útlum, vyza ování a p ír stek z externích zdroj sv tla. Otázkou zcela na míst je, jak ur it vzdálenost vzork v objemu. P edpokládejme, že chceme, aby na každém paprsku, který objemem projde bylo umíst no maximáln n vzork . Jak bylo e eno výše, jako proxy geometrie byl

59

Kapitola 4: Návrh metody pro implementaci na GPU v implementaci použit osov

orientovaný kvádr o stranách

( a , b, c )

se st edem

v po átku. Nejdelší paprsek, který m že skrze tento kvádr projít je ve sm ru jeho t lesové úhlop í ky, jejíž velikost je d = a 2 + b 2 + c 2 . Pak pro vzdálenost vzork dostáváme vztah d ∆s = (4.6) n

4.3 Použité optické modely V experimentální implementaci jsem použil ty i z optických model popsaných v §3.2. Jedná se o: • Pohlcující model • Vyza ující model • Vyza ující a pohlcující model • Rozptylující model a vržené stíny Všechny tyto modely jsou fyzikáln založené pro zcela korektní simulaci látek, pomocí nich by bylo pot eba znát materiálové konstanty, jako nap íklad koeficient útlumu i hodnotu fázové funkce. Nicmén cílem implementované metody je vytvo it v rn vypadající obrázky. Proto jsem do vzorc p idal, podobn jako nap íklad v práci [Sabella 88], sadu interaktivn nastavitelných konstant, které ovliv ují hodnoty neznámých fyzikálních veli in.

Pohlcující model V pohlcujícím modelu je zobrazován pouze útlum zp sobený ásticemi látky. Do modelu byly p idány dv konstanty podle [Sabella 88]. Konstanta γ ídí zp sob mapování hodnot funkce f na hustotu ástic. Konstanta κ ídí velikost koeficientu útlumu. P vodní rovnice (3.2), jejíž tvar je s

I ( s ) = I 0 ⋅ exp − τ ( t ) dt 0

má po p idání t chto konstant tvar: s

I ( s ) = I 0 ⋅ exp −κ f γ ( t ) dt

(4.7)

0

Vyza ující model Ve vyza ujícím modelu je naopak modelováno pouze vnit ní vyza ování látky. Toto vnit ní vyza ování je kombinováno se zá ením p icházejícím zpoza objemu, tedy konkrétn s barvou již uloženou v barevném bufferu. Kombinace je provedena pouhým se tením, nebo žádný útlum není modelován. Do modelu tak, jak je popsán rovnicí (3.4), je p idán len γ , který op t ídí mapování hodnot funkce f na hustotu ástic. Po p idání této konstanty má tedy vztah (3.4) tvar:

60

Kapitola 4: Návrh metody pro implementaci na GPU s

I ( s ) = I 0 + C ( s ) f γ ( t ) dt

(4.8)

0

kde • I ( s ) je výsledná intensita

• C ( s ) je míra vyza ování ástice podle vztahu (3.3) • I 0 je intensita pozadí

Hodnota C ( s ) nemusí být konstantní pro celou látku, a je proto také v ur itém smyslu parametrem.

Vyza ující a pohlcující model Tento model je pouze kombinací p edchozích dvou model , a proto jsou použity identické konstanty. P vodní vztah (3.6) má po p idání konstant tvar: D

I ( D ) = I 0 exp −κ f 0

γ

( t ) dt

D

+ C (s) f

γ

( s ) exp −κ

0

s

f γ ( t ) dt ds

(4.9)

0

Rozptylující model a vržené stíny Tento model je nejkomplikovan jší z implementovaných model . Modeluje nejen vyza ování a pohlcování látky, ale také její osv tlení z vn jších zdroj sv tla. Do vztahu (3.18) byla p idána ada konstant, z nichž n které jsou shodné z konstantami p edchozích model . leny (3.15), (3.16), (3.17) reprezentující útlum jsou upraveny stejn jako v p ípad p edchozích model , tedy konstantami κ a γ : D

Τ ( t ) = exp −κ f γ ( X − tω ) dt ,

(4.10)

0

s

Τ′ ( t ) = exp −κ f γ ( X − tω ) dt ,

(4.11)

0

∞

Τ′′ ( t , s ) = exp −κ f γ ( X − sω − tω ′ ) dt

(4.12)

0

Úprava zdrojového lenu (3.12) je o trochu složit jší.

len E ( X ) reprezentující

vlastní vyza ování látky je upraven stejn jako u vyza ujícího modelu, tedy:

E(X ) =C(X ) f γ (X )

(4.13)

Zcela novým prvkem je BRDF. V experimentální implementaci je BRDF rozvinuta podle vztahu (3.8) a jako fázová funkce je použita Henyey-Greensteinova aproximace. Hodnota albeda a ( X ) je nastavitelný parametr, který je ovšem stejný

61

Kapitola 4: Návrh metody pro implementaci na GPU pro celou látku. Stejn tak lze nastavit konstantu c ur ující sm rovost rozptylu. Výsledný tvar BRDF je tedy:

r ( X − sω , ω , ω ′ ) = af γ ( X − sω )

1 1 − c2 4π 1 + c 2 − 2c ω ⋅ ω ′ ( )

(

)

3

2

(4.14)

4.4 P íprava experimentálních dat V § 4.1 je p esn specifikováno, jak mají vypadat vstupní data pro implementovanou metodu. Abych mohl metodu otestovat, bylo nutné taková data p ipravit. Pro testování jsem p ipravil dv syntetické množiny dat. Každou z nich jak v m ížce 64x64x64 bod , tak v m ížce 128x128x128 bod . Data byla vytvo ena jako turbulence upraveného Perlinova šumu. Síla turbulence a její p ír stek (gain) je libovoln nastavitelný, základní hodnoty jsou ty i oktávy a p ír stek 2. První množina, uložená v souborech s názvy BoxTurb.dds a BoxTurb128.dds je p esn turbulence, jak je popsána výše. Druhá, uložená v souborech s názvy SphereTurb.dds a SphereTurb128.dds je stejná turbulence, pouze omezená na kouli vepsanou p vodní m ížce. Sm rem od centra této koule je také snižována „hustota“ množiny tak, aby se „kulový mrak“, který p edstavuje, pozvolna rozplýval. Perlin v šum byl použit v moderní variant publikované v práci [Perlin 02]. Oproti p vodnímu šumu, který byl publikován v práci [Perlin 84], tato varianta odstra uje n které nedostatky p vodní implementace, zejména ob asné nespojitosti ve výsledných hodnotách. Je také o n co málo výpo etn efektivn jší. Perlin v šum obecn generuje hodnoty v rozsahu [ −1,1] . Ve vygenerovaných datech je tento rozsah o íznut na [ 0,1] , což zp sobuje v tší nespojitosti v generovaných hodnotách a

spolu s aplikovanou turbulencí dodává výsledné množin více „rozvln ný“ dojem. Hodnoty gradientu tak, jak jsou požadovány v §4.1, jsou vygenerovány pomocí metody centrálních diferencí.

62

Kapitola 5

Implementace na GPU V minulé kapitole jsem uvedl navrženou metodu z teoretického hlediska. V této kapitole se jí budu v novat po implementa ní stránce. Nejprve detailn proberu model práce s programovatelným et zcem (§5.1). Uvedu princip použitých technologií, zp sob jak se s nimi pracuje a jak je s jejich pomocí kód navržen. Dále p edstavím použité vývojové prost edí a budu se zabývat jeho p ednostmi a nevýhodami (§5.2). §5.4 obsahuje popis programátorsky zajímavých míst kódu nebo jeho ástí, kde jsem p i implementaci narazil na vážn jší problémy. Následuje §5.5, který p edstavuje zp sob p ípravy experimentálních dat, jejich uložení na grafickou kartu a poukazuje na n které zvláštnosti v práci s nimi. Kapitolu uzavírají §5.6 a §5.7. První z nich obsahuje popis testování implementace, nam ené výsledky a jejich diskusi. Druhý se zabývá zhodnocením implementace jako celku, zejména vzhledem k cíl vyty eným v §1.5.

5.1 Model práce a struktura kódu Jak bylo nastín no v úvodní kapitole, v ásti o grafickém hardware, práce s programy pro programovatelný et zec zahrnuje daleko více operací, než jen napsání kódu vertex a fragment shader . P i zvažování zp sobu implementace jsem vycházel ze zadaných cíl , hlavn z (c2), (c3) a (c4). P i návrhu metody se ukázalo, že krom vlastního kódu uvnit shader bude pot eba provád t zejména následující operace: • Nastavovat zp sob kone ného míchání barev (color blending) tak, aby výsledná barva byla správnou kombinací barvy pozadí a barvy fragmentu. • Provád t více pr chod p es geometrii s tím, že tyto pr chody si musejí p edávat data skrze pomocné textury (off-screen buffers). • istit barevné a pomocné buffery mezi pr chody. • P edávat hodnoty z aplikace do relativn velkého po tu parametr pro shadery. Tyto operace není možné provád t uvnit vertex a fragment shader . Spadají totiž do oblasti nastavování neprogramovatelné ásti zobrazovacího et zce, a to se typicky

63

Kapitola 4: Návrh metody pro implementaci na GPU provádí voláním funkcí b hového prost edí. Stejn tak p edávání hodnot parametr m shader je aplika n závislou inností. ešením se ukázalo být použití takzvaných Efekt spolu s DXSAS (DirectX Standard Annotations and Semantics), které jsou oba sou ástí specifikace Microsoft DirectX (viz [DirectX9.0c 05]). Efekty jsou systém, který umož uje jednotným zp sobem a na jednom míst definovat nejenom vertex a fragment shadery, ale také pot ebný stav zobrazovacího et zce a pomocí metadat p i azovat význam parametr m shader , což lze následn použít pro automatické p edávání hodnot t chto parametr z aplikace. DXSAS je standard, který definuje zp sob zadávání metadat a jejich význam tak, že aplikace a efekt, které se oba tohoto standardu drží, mohou vzájemn zcela automaticky komunikovat. DXSAS také definuje jednoduchý skriptovací jazyk, který lze zapsat v metadatech a který umož uje automatizovat práci s více pr chody, efekt m komunikovat mezi sebou a ídit stav zobrazovacího et zce. Jak je tedy vid t, kombinace t chto dvou standard je schopná vy ešit všechny problémy uvedené v úvodu tohoto paragrafu.

5.1.1 Efekty Systém efekt se skládá ze dvou ástí. První je definice formátu textových soubor , do kterých se efekty zapisují. Druhou je b hové prost edí a sada funkcí, které slouží k práci s tímto formátem. B hové prost edí obsahuje funkce, které umož ují na tení efektu ze souboru, jeho kompilaci a aktivaci. Jejich vý et lze nalézt v [DirectX9.0c 05]. Daleko zajímav jší je pro nás v tuto chvíli formát soubor s efekty. Každý efekt je uložen v samostatném souboru, typicky s p íponou .fx. Každý takový soubor se skládá ze t í blok : • Parametry • Funkce • Techniky a pr chody

Parametry Parametry jsou prom nné efektu. Deklarují se podobn jako prom nné v jiných programovacích jazycích a jejich ú el je stejný. Výpis 5.1 ukazuje syntaxi parametru efektu. V tšina prvk v deklaraci je stejná jako v jiných programovacích jazycích, až na dva zvláštní, kterými jsou anotace a sémantika. usage

type

id

[: semantic]

[< annotation(s) >]

[= expression];

Výpis 5.1: Syntaxe parametru efektu

Sémantika, jak název napovídá, jsou metadata, která napovídají jednak kompilátoru, ale hlavn externí aplikaci, o smyslu p íslušného parametru. float4x4 worldViewProj : WORLDVIEWPROJECTION <string UIWidget="none";>; texture flameOutline < string ResourceType = "2D"; string ResourceName = "..\\Images\\FlameOutline2.dds"; >;

Výpis 5.2: Použití anotací a sémantiky

64

Kapitola 4: Návrh metody pro implementaci na GPU Anotace je další druh metadat, do kterých lze napsat libovolný text. Tento text není zpracováván kompilátorem, ale programem, který s efekty pracuje. Do anotací lze zapisovat dodate né informace, jako nap íklad jména soubor s texturami, zp sob nastavení grafického et zce p i práci s parametrem, ale také nap íklad vyžádat grafický manipula ní prvek pro hodnotu toho parametru apod. Výpis 5.2 ukazuje použití sémantiky a anotací. Nejd íve je deklarován parametr worldViewProj jako ty rozm rná matice a poté je sémantikou e eno, že do tohoto parametru má být dosazována transforma ní matice složená z modelové, pohledové a projek ní matice. Zárove je u toho parametru anotací e eno, že nemá být v bec zobrazován v uživatelském rozhranní. Druhým deklarovaným parametrem je textura. Tento parametr nepoužívá sémantiku, pouze je anotací e eno, že se jedná o dvou-dimensionální texturu a že se její obsah má na íst z uvedeného souboru. Ješt jednou je t eba zd raznit, že s anotacemi a sémantikou nepracuje kompilátor ani ovlada grafické karty, ale musí je podporovat aplikace, která s efekty pracuje (i když n které kompilátory používají sémantiku k optimalizaci uložení parametr v registrech). Je dobré také poznamenat, že sémantika je pouze vodítko a není pro programátora závazná. Nic tedy programátorovi nebrání v tom, výše zmín ný parametr použít jakýmkoliv jiným zp sobem, než jako transforma ní matici.

Funkce Funkce jsou výkonnou ástí efektu. Vertex a fragment shadery se zapisují práv jako funkce. Jejich syntaxe je podobná jazyku C. Funkce nemohou být vno ené a všechny tedy musejí být definované na globální úrovni. K parametr m efektu se chovají jako ke globálním prom nných. Uvnit funkce lze tedy p istupovat k d íve deklarovaným parametr m. Krom toho má samoz ejm funkce také svoje p edávané parametry. Existuje pouze jeden zp sob p edávání a to hodnotou. Techniky a pr chody Techniky jsou hybnou silou vykreslování (slovy specifikace [DirectX9.0c 05]). Technika sdružuje definici stavu zobrazovacího et zce s voláním vertex a fragment shader . Každá technika obsahuje jeden nebo více pr chod . Každý pr chod, p esn podle svého názvu, reprezentuje jeden pr chod geometrie skrze zobrazovací et zec. Má tedy vlastní sadu nastavení a také vlastní vertex a fragment shadery. Dobrou otázkou je pro by efekt m l obsahovat více technik ? V odpov di se skrývá jedna z velmi silných stránek celého systému efekt . U každé techniky lze nadefinovat typ hardwarové architektury, pro kterou jsou vertex a fragment shadery v této technice ur eny. B hové prost edí pro efekty pak obsahuje funkce, které jsou schopné tuto definici porovnat se schopnostmi hardware, kde efekt skute n b ží a vydat verdikt o tom, zda je technika spustitelná na tom kterém systému. Je tedy možné v jednom efektu definovat více technik, každou pro jinou skupinu hardware a bude automaticky zajišt no, že se nakonec spustí technika, která nejvíce odpovídá schopnostem hardware. To umož uje s minimem práce psát programy tak, že jsou spustitelné na velmi široké škále hardware a p itom nemusí ob tovat kvalitu zobrazení ší i podporovaného hardware. Jinými slovy, každý dostane p esn to, jaký má v systému hardware.

65

Kapitola 4: Návrh metody pro implementaci na GPU

5.1.2 DXSAS Výše popsaný systém anotací a sémantik sám o sob ovšem nesta í. Aby byl skute n k užitku, je pot eba obsah sémantik a anotací standardizovat. To p esn d lá DXSAS. Je to tedy standard, který definuje druhy sémantik a jejich význam a obsah anotací a jejich význam. DXSAS obsahuje jednak pravidla pro tv rce efekt , tedy syntaktická pravidla, jak se mají sémantiky a anotace psát a jednak pravidla pro tv rce aplikací, které s efekty pracují, kde se íká, co která sémantika znamená a jaká hodnota má být kam dopln na. P íkladem sémantiky podle DXSAS je ve Výpis 5.2 sémantika WORDVIEWPROJECTION. Anotace v tomtéž výpisu se také drží DXSAS. DXSAS definuje také jednoduchý skriptovací jazyk, který se zapisuje do anotací a umož uje detailn kontrolovat pr chod geometrie zobrazovacím et zcem a také umož uje interakci mezi dv ma i více efekty. Detailní popis tohoto skriptovacího jazyka je mimo rozsah této práce. Podrobný popis lze nalézt ve specifikaci [DirectX9.0c 05]. technique RayCast < string Script = "ClearSetColor=clearColor;" "Pass = MainPass;"; > { pass MainPass < string Script = "RenderColorTarget=;" "Clear=color;" "Draw=Geometry"; > { … } }

Výpis 5.3: Skript DXSAS v0.8

Na Výpis 5.3 m žeme vid t ukázku skriptu DXSAS. Vidíme také, že anotace lze p idávat k technikám a pr chod m, stejn jako k parametr m.

5.1.3 Efekty a HLSL Až dosud jsem se nezmínil, krom pár slov v úvodní kapitole, o vysokoúrov ových programovacích jazycích a jejich vztahu k systému efekt . { … VertexShader = compile vs_2_0 Transform(); PixelShader = compile ps_2_0 PassThrough(dTSampler); } { … VertexShader = asm{…}; PixelShader = asm{…}; }

Výpis 5.4: Použití HLSL a shader assembleru

66

Kapitola 4: Návrh metody pro implementaci na GPU HLSL (High-Level Shader Language) je jazyk, který byl vyvinutý pro psaní vertex a fragment shader . P ed p íchodem HLSL se vertex a fragment shadery psaly v jazyce podobném assembleru, který byl specifický pro každou verzi shader . Formát efekt je z návrhu na HLSL nezávislý. Potud teorie. Syntaxe parametr efekt odpovídá syntaxi HLSL a jako typ parametru lze zadat libovolný typ jazyka HLSL. Funkce mají také syntaxi HLSL a o návratových typech platí to samé, co o typech parametr . T la funkcí musí být napsána v jazyce HLSL. Syntaxe technik a pr chod není na HLSL p ímo závislá. Je sice HLSL podobná, ale jazykové konstrukce jsou specifické pro formát efekt . Pokud bychom cht li používat systém efekt , ale vyhnout se použití HLSL, je to možné. V takovém p ípad nebudeme v bec používat parametry a funkce, pouze deklarujeme p íslušné techniky a pr chody. V pr chodu poté p i deklaraci stavu vertex a fragment shader nepoužijeme klí ové slovo compile následované jménem funkce, ale klí ové slovo asm uvozující blok kódu v shader assembleru. Tento rozdíl ukazuje Výpis 5.4. Horní ást kódu ukazuje použití HLSL funkcí jako vertex a fragment shader , dolní ást pak použití shader assembleru.

5.1.4 Efekty a shadery mimo DirectX API Z výkladu v p edchozích kapitolách by se mohlo zdát, že pokud chceme používat systém efekt a vysokoúrov ový programovací jazyk, nemáme jinou šanci, než se p iklonit k DirectX API. Našt stí tomu tak není. Firma Microsoft spolu s firmou Nvidia p vodn vyvíjely vysokoúrov ový jazyk pro programovatelné stínování. Microsoft ho do svého DirectX API za adil pod názvem HLSL a Nvidia jej p edstavila jako Cg. Tyto jazyky se pak dále za aly trochu lišit, hlavn v podporovaných hardwarových profilech. Stále však platí, že kód v HLSL lze jen s minimálními úpravami p eložit kompilátorem pro Cg a naopak. To samé platí i o formátu efekt . Firma Nvidia p ipravila vlastní formát efekt nazývaný CgFX. Tento formát je ovšem zcela totožný s efekt formátem uvedeným ve specifikaci DirectX. Liší se pouze b hové prost edí. B hové prost edí CgFX umí pracovat jak nad OpenGL, tak nad DirectX. Záv rem lze tedy íci, že všechno e ené v p edchozích odstavcích lze aplikovat i na vývoj nad OpenGL API, s jazykem Cg a formátem CgFX.

5.2 Vývojové prost edí V dob psaní této práce je odv tví programovatelného stínování mladá oblast, a proto zatím neexistuje integrované programátorské prost edí, jako nap íklad Microsoft Visual Studio .NET. Je tomu tak z n kolika d vod : • Vertex a fragment shadery jsou relativn malé kusy kódu a jejich správa a udržování není zdaleka tak komplexním úkolem jako u jiných programátorských projekt . Proto po integrovaném prost edí není mezi programátory zatím taková poptávka.

67

Kapitola 4: Návrh metody pro implementaci na GPU • Tvorba nástroj pro lad ní je velmi obtížná. Vychází to z faktu, že grafické karty jsou masivn paralelní architektury a po et jednotlivých spušt ní vertex nebo fragment shaderu je obrovský. • Vertex a fragment shadery jsou malým kouskem skládanky v oblasti, kde se používají. Plnohodnotný grafický engine obsahuje spoustu dalších komponent, které by v integrovaném vývojovém prost edí musely být p ítomny. Nicmén i p es tyto obtíže existovalo v dob zahájení této práce rozumné vývojové prost edí od firmy Nvidia s názvem FXComposer a to ve verzi 1.6. Zvažovanou alternativou použití toho prost edí bylo použití vlastního grafického enginu, který jsem vytvo il spolu s týmem dalších lidí p i práci na projektu Almorea (viz. [Almorea]). Prost edí Almorea je plnohodnotný grafický engine, který je schopen pracovat práv s vertex a fragment shadery. FXComposer naproti tomu je prost edí vyvinuté jedním z pr kopník programovatelného stínování, firmou Nvidia. Nakonec byl pro tuto práci zvolen FXComposer, zejména z následujících d vod : • FXComposer podporuje efektový formát podle specifikace DirectX. • FXComposer poskytuje integrovaný textový editor p izp sobený pro práci s vertex a fragment shadery v jazyce HLSL. • Prost edí má pom rn rozumn vy ešenou práci s geometrií a navazování geometrických vlastností t les na parametry shader a je tak možné se zam it hlavn na vývoj vertex a fragment shader . • FXComposer lze použít také jako experimentální prost edí. Je v n m integrovaný interaktivní náhled a cyklus vývoje je tak velmi urychlen. Zárove poskytuje možnost m it rychlost zobrazování ve snímcích za vte inu. • Podporuje práci 3D texturami. Práce s FXComposer p inesla ovšem také n které nevýhody. Mezi n pat í zejména: • FXComposer podporuje pouze DirectX a HLSL. Není možné v n m pracovat se Cg a OpenGL. • M ení rychlosti zobrazování není úpln srovnatelné s herním enginem. Lze o ekávat, že hodnoty nam ené uvnit FXComposeru budou nižší. Požadavkem, který v dob vytvá ení této práce nemohlo uspokojit žádné vývojové prost edí, je možnost lad ní vertex a fragment program . Možnosti lad ní jsou i v FXComposeru velmi omezené. K dispozici je pouze b žný grafický výstup. Lad ní je tedy nutné provád t tak, že hodnoty, které chceme znát, n jakým zp sobem p evedeme na barevnou reprezentaci a následn p ímo zobrazíme. V sou asné dob jsou k dispozici pouze nástroje na analýzu výkonu. Tyto nástroje jsou schopny zobrazovat zatížení jednotlivých ástí grafického systému a dovolují tak analyzovat a nalézat úzká místa. Krom FXComposeru bylo pro vývoj programu, který p ipravuje experimentální data, použito prost edí Microsoft Visual Studio .NET. Pro vytvo ení scén s proxy geometrií jsem použil modelovací nástroj Blender. Ob prost edí, jak FXComposer, tak Blender jsou voln ší itelné programy, Blender dokonce pod licencí LGPL. Pro práci s Microsoft Visual Studiem .NET byla použita instalace v universitních laborato ích.

68

Kapitola 4: Návrh metody pro implementaci na GPU

5.2.1 FXComposer 1.6 Nyní stru n p edstavím prost edí FXComposeru. Obrázek 5.1 ukazuje pracovní plochu FXComposeru. Centrální okno je textový editor se záložkami, který má vestav ný syntax-highlighting pro jazyk HLSL i pro efekt formát. Uvnit FXComposeru se pracuje s pojmem materiál. Každé t leso ve scén má p i azeno n jaký materiál, který ur uje vzhled tohoto t lesa. Takovýto materiál se skládá z práv jednoho efektového souboru. Dole pod oknem pro práci s materiály je okno nazvané Textures. Jak název napovídá, jsou v tomto okn zobrazeny všechny textury, kterou jsou použité v práv aktivním materiálu.

Obrázek 5.1:FXComposer

Na pravé stran pracovní plochy naho e je okno, kde jsou zobrazeny nastavitelné parametry aktivního materiálu. Zde se zobrazují práv prvky uživatelského rozhraní, které jsou specifikovány pomocí DXSAS anotací. Takto jsou nap íklad zp ístupn ny parametry osv tlovacích model , jak jsou uvedeny v §4.3. Napravo dole je vid t okno náhledu na scénu. Veškeré zm ny provedené v textovém editoru se po uložení souboru nebo jeho kompilaci ihned promítnou v okn náhledu. To umož uje velmi rychlou reflexi na práv vykonané zm ny a zna n tak zrychluje práci, zejména v kone ných fázích tvorby efektu, kdy se jedná p evážn o správné nastavení r zných parametr . V okn náhledu lze také interaktivn scénou procházet i otá et a pohybovat t lesy v ní. Dole uprost ed nalezneme i nezbytné okno s hlášeními. Zde se zobrazují zprávy o kompilaci a jejích p ípadných chybách. Nakonec se volba FXComposeru za vývojové prost edí ukázala jako zda ilá. Vývoj v n m probíhal, i p es jeho drobné nedostatky, pohodln a relativn rychle. Ve verzi

69

Kapitola 4: Návrh metody pro implementaci na GPU 1.6 je jeho asi nejv tší nevýhodou stabilita, se kterou má ob as problémy a také zp sob práce s geometrií a se scénou není ve všech p ípadech úpln ideální. Ovšem odv tví vývojových prost edí pro programovatelné stínování je teprve v za átcích a velmi rychle se rozvíjí. Již b hem tvorby této práce vyšla nová verze 1.7.

5.3 Struktura kódu Nyní jsme již vybaveni pot ebnými znalostmi princip práce s programovatelným et zcem a znalostí vývojového prost edí, takže je možné prezentovat strukturu kódu pro implementovanou metodu. V rámci této práce bylo vytvo ena sada efekt , tak jak jsou popsány výše. Pro vývoj bylo použit systém Efekt podle specifikace [DirectX9.0c 05], k programování shader byl použit jazyk HLSL a DXSAS ve verzi 0.8. Podrobn ji jsou d vody pro tuto volbu popsány v následujícím paragrafu o vývojovém prost edí. Pro každý implementovaný optický model, tak jak jsou popsány v §4.3 byl vytvo en samostatný efekt, který je uložen v jednom souboru s p íponou .fx. Dále byla vytvo ena sada „hlavi kových soubor “, které neobsahují p ímo efekty, ale pouze pomocné HLSL funkce a deklarace efektových parametr , které jsou spole né pro v tšinu efekt . Jedná se o následující soubory: • Geometry.fxh. Tento soubor obsahuje funkce, které po ítají pr se ík paprsku s proxy geometrií • Volume.fxh. Zde jsou funkce, které se starají o práci se sou adnicemi a vyzvedávání vstupních objemových dat z 3D textur. • Lighting.fxh. Tento soubor obsahuje definice sv tel a funkce pro práci s nimi, v etn všech použitých BRDF. Nakonec, krom efekt pro optické modely, byl vytvo en ješt soubor SimpleTexture.fx, který obsahuje kód pro jednoduché mapování textury na objekt. Tento efekt je použitý v n kterých ukázkových scénách, nap íklad p i tvorb Obrázek 3.2. Popis všech soubor spolu s jejich adresá ovou strukturou je v Dodatku A. Pro testování efekt byly použity t i experimentální scény. První z nich, s názvem Box300.x obsahuje krychli o stran 300 jednotek s st edem v po átku. Druhá s názvem Box500a300.x obsahuje, jak název napovídá, centrovanou krychli o stran 300 jednotek a pod ní umíst ný kvádr o rozm rech 500x500x2. Poslední scéna Box2-2-4.x byla p ipravena pro scénu s ohn m (viz Obrázek 3.3) a obsahuje centrovaný kvádr o stranách 200x200x400. Tyto krychle a kvádry slouží jako proxy geometrie pro zobrazovaný objem. Celková struktura efektového souboru je stejná pro všechny druhy efekt . Její schématické znázorn ní je na Výpis 5.5. Každý efekt za íná hlavi kou, kde jsou uvedeny informace o daném souboru a optickém modelu, který implementuje. Další ást Adjustable parameters obsahuje všechny parametry efektu, které jsou p ístupné uživateli. Všechny tyto parametry mají nadefinován uživatelský prvek uvnit FXComposeru. Typicky tu najdeme parametry optického modelu, po et vzork na paprsku a barvu pozadí scény.

70

Kapitola 4: Návrh metody pro implementaci na GPU //----------------------------------------------------------------// GPU Volume Rendering // Lukas Marsalek, 2005 // ... //----------------------------------------------------------------//-----------------------------------// Adjustable parameters //-----------------------------------... //-----------------------------------// Transformation matrices //-----------------------------------... //-----------------------------------// Static variables //-----------------------------------... //-----------------------------------// Volume and Lights processing //-----------------------------------#include "Volume.fxh" #include "Lighting.fxh" ... //-----------------------------------// Geometry processing //-----------------------------------#include "Geometry.fxh" //-----------------------------------// I/O structures //-----------------------------------... //-----------------------------------// Vertex Shaders //-----------------------------------... //----------------------------------// Fragment Shaders //----------------------------------... //-----------------------------------// Script entry point //-----------------------------------... //-----------------------------------// Drawing //-----------------------------------...

Výpis 5.5: Struktura efekt

Následují všechny transforma ní matice v ásti nazvané, jak jinak, Transformation matrices. Tyto matice jsou dodávány FXComposerem pomocí DXSAS sémantik, které tyto standardní matice ozna ují. Další na ad jsou statické prom nné Static variables. Tyto prom nné jsou specifické v tom, že jsou inicializovány pouze jednou p i zavedení efektu a jejich inicializátor m že obsahovat i komplikované HLSL konstrukce. Tato inicializace je provád na na CPU, nikoliv na GPU. T chto vlastností lze s výhodou využít k p edpo ítání n kterých „drahých“ hodnot, které se b hem práce efektu nem ní, ale jejichž výpo et zahrnuje nap íklad d lení i odmoc ování, apod. Následující ást Volume and Lights Processing již obsahuje krom parametr také HLSL funkce. Nejd íve je vložen soubor s funkcemi, které se starají o výb r vstupních hodnot z 3D textury. Dále je vložen soubor, kde jsou deklarována vn jší

71

Kapitola 4: Návrh metody pro implementaci na GPU sv tla a funkce pro práci s nimi. Následují funkce, které mapují vstupní hodnoty na fyzikální vlastnosti vyjád ené v optických modelech, jako nap íklad útlum i vyza ování. Oddíl je zakon en funkcemi, které se starají o zpracování vn jšího osv tlení, p esn ji jedna o útlum p i pr chodu objemem a druhá o odraz sv tla p i dopadu na ástice látky. U efekt , které neobsahují interakci s vn jším osv tlením je tento oddíl redukován pouze na práci se vstupními daty. Další ást Geometry processing pouze vkládá soubor, kde jsou funkce pro výpo et pr se ík paprsku s proxy geometrií. I následující ást I/O structures je krátká. Jsou v ní definovány dv struktury. První z nich vertexInput udává tvar vstupu do vertex shaderu a druhá vertexOutput naopak výstup vertex shaderu a zárove vstup do fragment shaderu. Struktura pro výstup fragment shaderu není nutná, protože fragment shader vrací vždy pouze ty dimensionální vektor barvy fragmentu. Následují dv d ležité ásti, Vertex Shaders a Fragment Shaders. Jejich obsah je z ejmý z názv . Dodejme pouze, že každá obsahuje práv jeden vertex nebo fragment shader. P edposlední krátká ást Script entry point obsahuje povinný parametr vyžadovaný standardem DXSAS. Tento parametr musí mít sémantiku STANDARDSGLOBAL a v anotaci obsahuje vstupní deklarace pro DXSAS skript a jako hodnotu má použitou verzi DXSAS. Poslední ást nazvaná Drawing obsahuje popis technik a pr chod . Tato ást se liší podle zp sobu, jak jsou generovány paprsky (viz §4.2.1). technique RayCast < string Script = "ClearSetColor=clearColor;" "Pass = BackPass;" "Pass = MainPass;"; > { pass BackPass < string Script= "RenderColorTarget = rayTexture;" "ClearSetColor=texClearColor;" "Clear=color;" "Draw=Geometry;"; > { … VertexShader = compile vs_2_0 XYZColor_VS(); PixelShader = compile ps_2_0 BackRay_PS(cameraPosition); } pass MainPass < string Script = "RenderColorTarget=;" "ClearSetColor=clearColor;" "Clear=color;" "Draw=Geometry"; > { … VertexShader = compile vs_3_0 Volume_VS(); PixelShader=compile ps_3_0 Volume_PS(rayTextureSampler,cameraPosition); } }

Výpis 5.6: Zápis dvou pr chodu a jejich spolupráce

72

Kapitola 4: Návrh metody pro implementaci na GPU P i generování paprsku geometrickým p ístupem je provád n pouze jeden pr chod a je definován jeden vertex shader a jeden fragment shader, které jsou oba kompilovány pro Shader Model 3.0. P i generování paprsku pomocí dvou pr chodu jsou evidentn pr chody dva. Tyto jsou uloženy v jedné technice a kontrolovány pomocí DXSAS skriptu. Výpis 5.6 ukazuje, jak jsou pomocí DXSAS skriptu spušt ny oba dva pr chody postupn za sebou. Všimn me si, že v prvním pr chodu BackPass je nastavena do asná textura rayTexture jako cíl pro vykreslování a následn je v druhém pr chodu vykreslovací cíl op t vrácen na hlavní barevný buffer. Každý z pr chod má také vlastní sadu vertex a fragment shader .

5.4 Implementa ní zajímavosti V této podkapitole se zam ím na nejzajímav jší ásti celé implementace. První z nich se zabývá zp sobem rozd lení práce mezi vertex a fragment shader a obsahem vertex shaderu. §5.4.2 obsahuje popis konstrukce hlavního fragment shaderu, který obstarává v tšinu „práce“. Nakonec jsou v §5.4.3 p edstaveny geometrické výpo ty pr se íku paprsku s proxy geometrií, které slouží jako p kná ukázka výhod vektorových procesor .

5.4.1 Vertex shader Rozd lení práce mezi vertex a fragment shader je velmi nerovnom rné. Vertex shader, jak ukazuje Výpis 5.7, pouze p edává dál do fragment shaderu sv tové a modelové sou adnice proxy geometrie. Zbytek práce se provádí uvnit fragment shaderu. vertexOutput Volume_VS(vertexInput input) { vertexOutput o; o.pos = mul(float4(input.pos,1),worldViewProj); o.fragObjPos = input.pos; o.fragTexPos = o.pos; return o; }

Výpis 5.7: Hlavní vertex shader

Toto nerovnom rné rozd lení vzniká z povahy použité metody vrhání paprsku. Pot ebujeme totiž vrhat paprsek skrze každý fragment a ur ovat v n m výslednou barvu nezávisle na ostatních. Pokud bychom ten samý postup provedli pouze v n kolika málo vrcholech proxy geometrie, byly by výsledky nepoužitelné. Faktem ovšem je, že toto nerovnom rné zatížení není ideální z výkonnostního hlediska. V tšinu asu, kdy fragmentové jednotky pracují na plný výkon, tak vertex procesory stojí. Zajímavým sm rem pro další výzkum je, pokusit se zát ž rovnom rn ji rozd lit mezi vertex a fragment shader. To by šlo nap íklad ud lat tak, že proxy geometrie bude obsahovat daleko více rovnom rn rozprost ených vrchol . Potom by se ekvivalentní proces mohl provést také ve vertex shaderu a ve fragment shaderu pak pouze dopo ítávat potenciáln zajímavá místa. Stojí za to podotknout, že tento postup je možný pouze v Shader Modelu 3.0. Abychom mohli výše zmín nou

73

Kapitola 4: Návrh metody pro implementaci na GPU myšlenku provést, je totiž nutné um t uvnit vertex shaderu íst z textur. A to nebylo až do p íchodu Shader Modelu 3.0 možné.

5.4.2 Fragment shader P es velké množství práce, kterou fragment shader provádí, je jeho struktura jednoduchá. 1 float4 Volume_PS(vertexOutput input, 2 uniform float4 objSpaceCamera): COLOR 3 { 4 float3 v = normalize(input.fragObjPos - objSpaceCamera.xyz); 5 float3 s = objSpaceCamera.xyz; 6 float2 rayBounds = RayAnalytical(s,v,bbDim); 7 8 float3 sampleCoords; 9 float3 samplePoint; 10 float4 volumeSample; 11 float extinction = 0.0f; 12 float currentExt; 13 float3 emission = 0.0f; 14 float t = rayBounds.x; 15 16 while(t < rayBounds.y) 17 { 18 samplePoint = s+t*v; 19 sampleCoords=PrepareSampleCoords(samplePoint,bbDimHalf,bbDim); 20 volumeSample = SampleVolume(sampleCoords); 21 currentExt = TransferExtinction(volumeSample); 22 extinction += currentExt; 23 emission += 24 (TransferEmission(volumeSample,currentExt)+ 25 Scattering(currentExt,v,samplePoint)) 26 *exp(tau*sampleDist*(-extinction)); 27 t+=sampleDist; 28 } 29 return float4(emission,exp(tau*sampleDist*(-extinction))); 30 }

Výpis 5.8: Hlavní fragment shader

V úvodu je nejprve ur en sm rový vektor ( ádek 4) a po áte ní bod ( ádek 5) paprsku, který ur í hodnotu práv zpracovávaného fragmentu. Následn na ádku 6 je analyticky ur en pr se ík tohoto paprsku s proxy geometrií, která je zadána t írozm rným vektorem délek stran bbDim. Další akce se za íná dít až na ádku 16. Zde je st žejní moment celé implementace. Tím je použití while cyklu s podmín ným ukon ením. Po et iterací toho while cyklu nelze ur it p i kompilaci, a proto musí být skute n realizován instrukcí pro podmín ný skok break_ge x y, která je umíst na uvnit bloku rep/endrep.Tato funkcionalita je dostupná uvnit fragment shader až od Shader Modelu 3.0. Bez t chto podmín ných skok by bylo nutné realizovat celou tuto smy ku násobnými pr chody. Vnit ek smy ky již p esn kopíruje strukturu model z §4.3. Výpis 5.8 ukazuje nejsložit jší model, tedy rozptyl s vrženými stíny. U jednodušších model se liší ádky 21 až 26. Na ádku 21 a 22 je akumulován útlum osv tlení p icházejícího zpoza objemu, který je nakonec aplikován na ádku 29. Vyza ování, jak vlastní tak externí, je s ítáno v prom nné emission. Jak vidíme, vlastní vyza ování je se teno z rozptýleným sv tlem a výsledná hodnota je upravena doposud nas ítaným

74

Kapitola 4: Návrh metody pro implementaci na GPU útlumem. Je tedy vid t, že vzorkování paprsku b ží od pozorovatele sm rem dovnit objemu.

5.4.3 Geometrické výpo ty Zajímavou ukázkou práce s vektory jsou výpo ty pr se íku paprsku z proxy geometrií. Výpis 5.9 ukazuje zp sob výpo tu vztahu (4.2). void ComputeSegments(float3 S, float3 v, float3 dims, out float3 tn, out float3 tf) { float3 invV = 1/v; tn = (-dims/2.0f - S)*invV; tf = tn + dims*invV; }

Výpis 5.9: Výpo et vztahu (4.2)

Vidíme, že pr se íky pro všechny t i osy jsou po ítány najednou pomocí vektorových operací. Instrukce GPU jsou navíc opravdu vektorové, takže uvedené operace se nep eloží do trojnásobného po tu skalárních operací, ale opravdu jsou provedeny tak, jak jsou zapsány. Na Výpis 5.10 vidíme, že se vyplatí vektorizovat i skalární výpo ty. Je tedy lepší uložit skalární hodnoty do vektoru a provést jednu vektorovou operaci, než dv odd lené skalární. 1 float2 Intersect(float3 tn, float3 tf) 2 { 3 float2 final; 4 float2 t = max(tn.xx,tn.yz); 5 final.x = max(t.x,t.y); 6 t = min(tf.xx,tf.yz); 7 final.y = min(t.x,t.y); 8 return final; 9 }

Výpis 5.10: Výpo et pr niku interval

Výpis 5.10 ukazuje výpo et správné dvojice pr se ík paprsku s proxy geometrií. Detaily viz §4.2.1. Uvedená vektorizace je vid t nap . na ádku 4, kde dv skalární porovnání jsou provedena na dvourozm rných vektorech, navíc s pomocí tzv. swizzlingu, který umož uje p euspo ádávat a vybírat komponenty vektor podle pot eby.

5.5 Experimentální data a práce s nimi Na záv r se zmíním o zp sobu implementace algoritmu pro p ípravu experimentálních dat tak, jak je popsán v §4.4. Budu se také v novat zp sobu p enosu a práci s t mito daty uvnit fragment shader .

75

Kapitola 4: Návrh metody pro implementaci na GPU

5.5.1 Implementace šumu a turbulence P i tvorb experimentálních data bylo hlavním cílem rychle a jednoduše vytvo it rozumnou množinu experimentálních objemových dat. Proto jsem zvolil jednoduchý objem vypln ný turbulencí Perlinova šumu. Implementaci algoritmu pro generování šumu jsem p evzal podle [Perlin]. Zde je uvedena kompletní implementace algoritmu z [Perlin 02] v jazyce C. Tato implementace byla dopln na o kód, který zajiš uje p evedení vypo ítaných dat do formátu DDS a jejich uložení na disk. Formát DDS se ukázal jako nejvhodn jší pro uložení pot ebných dat z n kolika d vod : • Je schopen ukládat objemové textury jako sadu dvou-dimensionálních pr ez . • Existuje rozumné API pro práci s tímto formátem, které je p ímo dostupné v [DirectX9.0c 05] a umož uje snadno formát íst a ukládat. • Formát podporuje n kolik r zných zp sob a velikostí uložení dat. Je schopen pracovat jak s formáty používajícími 32bit na pixel, tak s formáty používajícími 64bit na pixel. Tyto 64bitové formáty ukládají hodnoty ve form 16bitových ísel s plovoucí ádovou árkou. • Experimentální prost edí FXComposer poskytuje dobrou podporu toho formátu, v etn jeho objemových 64bitových variant. • V [DirectX9.0c 05] je také prohlíže formátu DDS, který op t zvládá i práci s objemovými texturami.

5.5.2 Práce s objemovými daty Jazyk HLSL p ímo podporuje 3D textury. Je zde definovaný speciální druh textury a k ní p íslušející sampler, který umí s 3D texturami pracovat. Pomocí DXSAS lze pak do této textury p ímo na íst objemová data uložená ve formátu DDS. texture noise3D < string ResourceType = "3D"; string ResourceName = "..\\Volumes\\SphereTurb.dds"; >; sampler noise3DSampler = sampler_state { texture = <noise3D>; AddressU = WRAP; AddressV = WRAP; AddressW = WRAP; MIPFILTER = LINEAR; MINFILTER = LINEAR; MAGFILTER = LINEAR; };

Výpis 5.11: Použití 3D textur

Takto na tená data nejsou ješt v dalším kódu p ímo používána. Pro manipulaci s nimi slouží dv metody: PrepareSampleCoords a SampleVolume. První z nich má na starosti p evod mezi sou adnicovými systémy. Sou adnice do textur v HLSL jsou vždy v rozmezí [ 0,1] . Z výpo tu p i generování paprsku ovšem p icházejí data v sou adném systému proxy geometrie. Funkce PrepareSampleCoords p evádí práv mezi t mito sou adnými systémy pomocí znalosti velikosti proxy geometrie.

76

Kapitola 4: Návrh metody pro implementaci na GPU Funkce SampleVolume pouze pomocí funkcí standardní knihovny HLSL vyzvedává hodnoty z 3D textury a vrací je jako ty -dimensionální vektor. Je zde ovšem jeden drobný trik, který není na první pohled zcela z ejmý. float4 SampleVolume(float3 samplePoint) { return tex3Dlod(noise3DSampler,float4(samplePoint,0)); }

Výpis 5.12: Metoda SampleVolume

B žn by v této metod byla standardní funkce tex3D, která vyzvedává hodnoty z 3D textur. Tato funkce ovšem implicitn pracuje s mip-úrovn mi, a to i když je textura explicitn neobsahuje. Výb r správné mip-úrovn zahrnuje odhad gradientu texturovacích sou adnic, který je provád n aproximací pomocí diferencí v sousedních fragmentech výsledného obrazu. Funkce SampleVolume je ovšem volána uvnit smy ky, která obsahuje dynamické v tvení. Uvnit dynamického v tvení není ale použití aproximace pomocí diferencí povoleno. Je to z toho d vodu, že je možné, že kód pro sousední fragment, jehož texturovací sou adnice pot ebuje znát, se vydal jinou v tví dynamického v tvení a tedy požadovaná hodnota nemusí být v bec k dispozici. Pokud bychom se pokusili použít funkci tex3D, skon í kompilace s chybovou hláškou, která nanešt stí navíc ohlásí p í inu chyby kompilace jako p ekro ení maximálního po tu iterací smy ky. Naproti tomu funkce tex3Dlod nechává výb r mip-úrovn na uživateli. Jak si lze všimnout na Výpis 5.12, funkce má jako druhý parametr ty -dimensionální vektor, i když k vyhledání hodnoty v textu e sta í sou adnice t i. tvrtá hodnota je práv mip-úrove , která se má použít. 0 zna í základní úrove .

5.6 Testování a výsledky Testování rychlosti metody jsem provád l p ímo v prost edí FXComposeru, který umož uje sledovat po et snímk za vte inu. Konfigurace testovacího po íta e byla následující: AMD Athlon 64 3000+ 512 MB RAM MSI TD128E NX6600GT, 128MB RAM Microsoft WindowsXP Professional, ServicePack 2 FXComposer v1.6 Testovaní jsem provád l na t ech scénách a ve t ech konfiguracích. Všechny testovací scény m ly stejný obsah, lišily se pouze použitým shaderem, tedy simulovaným optickým modelem. V každé scén bylo obsaženo jedno bodové sv tlo a jedna krychle obsahující objemová data. Použité optické modely byly následující: • Emission. Vyza ující optický model. Co se tý e výpo etní náro nosti, je z použitých model nejjednodušší. • HG. Pohlcující a vyza ující model používající Henyey-Greensteinovu fázovou funkci. Leží uprost ed spektra výpo etní náro nosti. • HGAttenuated. Pohlcující a vyza ující model používající HenyeyGreensteinovu fázovou funkci. Osv tlení z vn jší zdroj je na své dráze

77

Kapitola 4: Návrh metody pro implementaci na GPU objemem utlumeno. Tento model koresponduje s Rozptylujícím modelem a vrženými stíny, podle §4.3. Z použitých model je nejvíce výpo etn náro ný. Všechny tyto t i modely byly testovány v r zných konfiguracích: 1. Jako objemová data je použita turbulence v m ížce 64x64x64. Výstup je vykreslován do okna 512x512 pixel . Model Emission HG HGAttenuated

100 vzork 50 21 <1

64 vzork 74 32 2

50 vzork 92 57 5

Tabulka 5.1: Výsledky p i konfiguraci 1

2. Jako objemová data je použita turbulence v m ížce 64x64x64. Výstup je vykreslován do okna 256x256 pixel . Model Emission HG HGAttenuated

100 vzork 203 91 4

64 vzork 303 139,7 9

Tabulka 5.2: Výsledky p i konfiguraci 2

3. Jako objemová data je použita turbulence v m ížce 128x128x128. Výstup je vykreslován do okna 512x512 pixel . Model Emission HG HGAttenuated

50 vzork 87 44 4

Tabulka 5.3: Výsledky p i konfiguraci 3

V rámci každé konfigurace ješt byly m eny hodnoty s r zným po tem vzork na paprsku, jmenovit 100, 64 a 50 vzork .

Obrázek 5.2: Testovací scéna ze [Stegmaier et al 05], odtud p evzato. Testovací scéna HGAttenuated

78

Kapitola 4: Návrh metody pro implementaci na GPU Tabulky 5.1 – 5.3 ukazují nam ené hodnoty fps. M ení bylo provád no tak, že na testovacím po íta i b žela pouze aplikace FXComposer. Po na tení scény jsem po kal 30 vte in a poté jsem ode etl nam ené fps. Výsledky z konfigurace 1 nejsou p íliš p ekvapivé. Ukazují, že metoda je skute n použitelná pro zobrazování v reálném ase. Ve shod s o ekáváním je po et vzork na paprsku jedním ze zásadních initel . Nanešt stí je také zásadním faktorem p i kvalit výstupu. 64 vzork je ješt p ípustných, aby kvalita výsledného obrazu nebyla p íliš nízká. 100 vzork je ideálních. P i zvyšování nad 100 vzork je vzr st kvality znatelný jen minimáln . Zajímavé jsou extrémn nízké hodnoty u nejsložit jšího optického modelu. Vzhledem ke zp sobu implementace nejsou ale p íliš p ekvapením a ani není možné z nich odvozovat n jaké zásadní záv ry. Zp sob práce se „stínovacími“ paprsky má velké rezervy a lze o ekávat ádový nár st p i použitích n kterých optimalizací (viz §6.1). Konfigurace 2 byla zahrnuta do testování, aby bylo možné odhadnout, do jaké míry je implementace limitována výkonem fragmentových procesor karty. Konfigurace 2 je totožná s konfigurací 1, pouze vykresluje ty ikrát mén pixel . Pokud se podíváme na nam ené hodnoty, zjistíme, že jsou s drobnými odchylkami ty ikrát v tší. To znamená, že implementace je skute n limitovaná výkonem fragmentových procesor . Je zde tedy prostor pro optimalizaci navrhovanou v §5.4.1 a její realizace z ejm p inese významné zvýšení výkonu. Je d ležité také vzít v úvahu, že použitá grafická karta ady 6600GT je karta vyšší st ední t ídy a oproti nejvyšší t íd karet ady GeForce 6, 6800 Ultra má dvojnásobn menší výkon. V sou asné dob se objevila navíc nová ada karet GeForce 7, která má podle test ješt o 70% vyšší výkon, že GeForce 6800 Ultra. Pokud k tomu p idáme ješt technologii SLI od firmy Nvidia, která umož uje použití dvou grafických karet v jednom systému s nár stem výkonu také ádov o 60-70%, dostáváme se k teoretickým hodnotám okolo 110fps pro st edn obtížnou scénu HG vykreslovanou se 100 vzorky do okna 512x512.

Obrázek 5.3: Testovací scéna HG (vlevo), Testovací scéna Emission (vpravo)

Konfigurace 3 byla do test za azena pro porovnání s ostatními prácemi podobného zam ení. Úpln korektní p ímé srovnání není možné, pokusme se alespo o odhad. V ervnu 2005 byla na konferenci Volume Graphics prezentována práce [Stegmaier at al. 05], která se zabývá totožnou problematikou a implementuje postupy velmi podobné t m prezentovaným v této práci. Auto i prezentují výsledky na následující konfiguraci:

79

Kapitola 4: Návrh metody pro implementaci na GPU

• Standartní PC s GeForce6800 Ultra • Velikost dat 256x256x110 • Ve scén je vykreslen jeden model shaderem, který napodobuje pr hledný materiál. • Paprsek je vzorkován p ibližn 50 vzorky. V této konfiguraci dosahují pr m rné rychlosti 5.7 fps a maximální 6.7fps.V konfiguraci 3 byl zv tšen objem vstupních dat na 128x128x128 tak, aby výsledky byly rozumn srovnatelné. M ížka 64x64x64 obsahuje 256 144 bod a m ížka 128x128x128 obsahuje 2 097 152 bod . P estože tedy konfigurace 3 má osmkrát více vstupních dat, nam ené hodnoty jsou v pr m ru pouze 15% nižší než v konfiguraci 2. Výsledky z konfigurace 3 lze, alespo p ibližn srovnat s výsledky Stegmaiera et al. Jejich testovací sada má 3,5krát více vzork , ovšem jejich systém má ádov dvakrát rychlejší grafickou kartu. Je tedy vid t, že i nejpomalejší z model HGAttenuated dosahuje srovnatelných nebo vyšších rychlostí. St edn komplexní model dosahuje dokonce o ád v tších rychlostí. Je ovšem nutné poznamenat, že výše uvedené srovnání je p ibližné a nelze z n j vyvozovat p esné záv ry, zejména z následujících d vod : • Je možné, že zvýšením objemu vstupních dat na 256x256x110 bychom dosáhli kritické úrovn a zpomalení by mohlo být ádové. • Dvojnásobná rychlost karty GeForce 6800 Ultra je teoretická. • Na rychlosti zobrazování se výrazn projevuje velikost oblasti okna, kterou objem pokrývá. Toto pokrytí není možné zvolit tak, aby si scény p esn odpovídaly.

5.7 Diskuse Na záv r kapitoly o implementaci bych rád uvedl diskusi této implementace ve sv tle p vodn stanovených cíl . Projdeme každý z cíl samostatn :

Rychlost zobrazování (c1) Ve sv tle p edchozí sekce lze konstatovat, že rychlost metody je pro experimentální implementaci velmi uspokojivá. Dosahuje srovnatelných výsledk s ostatními prácemi a dokonce se zdá, že je schopna je p edstihnout. Pro použití ve v decké vizualizaci jsou již sou asné rychlosti, krom nejsložit jšího modelu, zcela dostate né. Pro použití v po íta ových hrách by bylo pot eba dosahovat rychlostí jednou až dvakrát takových, ekn me tedy okolo 120fps pro HG v konfiguraci 3. Nicmén i tak je možné být optimistický, nebo jak bylo zmín no v minulých sekcích, tato experimentální metoda má ješt velké rezervy v efektivit a rychlosti, zejména v t chto oblastech: • M ení je provád no na kart st ední vyšší t ídy. Špi ky sou asného konzumního hardware jsou schopny dosahovat p ibližn p tkrát v tšího výkonu • Nejpomalejší shader HGAttenuated má zna né rezervy v efektivit implementace a lze po úprav o ekávat ádový nár st.

80

Kapitola 4: Návrh metody pro implementaci na GPU Je ovšem t eba zmínit fakt, že rychlost zobrazování je zna n závislá na velikosti oblasti, kterou objem na obrazovce pokrývá. To by se mohlo u interaktivních aplikací i her ukázat jako nep íjemný problém.

Kombinace s jinými zobrazovacími metodami(c2) Implementovaná metoda je schopna bez problém pracovat dohromady se standardními metodami pro polygonální objekty. Jediné omezení sou asné implementace je objemová data se nesm jí protínat s jinou geometrií, a je to jiný objem nebo polygonální data. Implementace výhradn uvnit shader (c3) Tento cíl spln n beze zbytku. Celá metoda je implementovaná pomocí jednoho efektu, který obsahuje práv jeden vertex shader a jeden fragment shader a sadu globálních parametr , které zajiš ují navázání na externí aplikaci. Samostatnost a p enositelnost(c4) Tím, že je celá metoda implementována pomocí efektu, stává se tak p enositelnou, jak to jen je v sou asné dob možné. Drobnou nevýhodou je, že musí být kompilována pro Shader Model 3.0, který v sou asné dob podporují pouze dv ady karet firmy Nvidia. Lze ale v nejbližší dob o ekávat podporu tohoto modelu i ze stranu druhého velkého výrobce grafický karet, firmy ATI. Celkov lze tedy íci, že práce dosáhla stanovených cíl , v n kterých ohledech dokonce p ekvapiv dob e. Zajímavé jsou zkušenosti, které byly b hem tvorby této práce získány. Jedním z p ínos této práce je získání zkušeností s platformou programovatelného stínování na konzumních po íta ích a získaní velmi dobré p edstavy o jejích možnostech. Ukázalo se, že tato platforma b hem své krátké šestileté existence dosáhla zna ného stupn vysp losti. Ší e implementovatelných algoritm je daleko v tší, než se v za átcích této práce zdálo. Stejn tak programovací prost edí je relativn pohodlné a produktivní. Lze jenom uzav ít, že další výzkum v oblasti zobrazování objemových dat na platform konzumních grafických systém má mnoho zajímavých možností k rozvoji a skute nému uplatn ní.

81

Kapitola 6

Záv r Tato diplomová práce prezentuje zobrazování objemových dat jako ucelenou oblast po íta ové grafiky, která stojí na dobrém teoretickém základ . Ukazuje také ší i p ístup , které byly pro ešení tohoto problému vyvinuty. Na základ t chto znalostí a studia prost edí sou asných konzumních grafických systém prezentuje implementaci metody zobrazování objemu pro tuto platformu. Podrobn ji lze výsledky této práce shrnout do následujících bod : • Nejprve je podán ucelený úvod do problém , kterých se tato práce dotýká, tedy zobrazování objemových dat, zobrazování v reálném ase a architektury sou asných konzumních grafických systém . • V následujících dvou kapitolách je systematicky prezentován vývoj oblasti zobrazování objemových dat. Je p edstavena celá ší e používaných p ístup , od po átk studia tohoto problému až po sou asnost. D raz je kladen na obecné principy t chto metod, vysv tlení jejich vzájemných odlišností, výhod a nevýhod. • V kapitole 3 je podán teoretický základ pro fotorealistické zobrazování objemových dat. Na základ p edchozích teoretických prací je ukázáno, že principy, kterými se zobrazování objemových dat ídí, lze budovat jednak systematicky na základ fyzikálních zákon , ale i empiricky podle pot eb aplika ní oblasti. To ukazuje sílu metod pro zobrazování objemu a jejich širokou použitelnost. • Za použití všech získaných informací je navržena metoda pro zobrazování objemových dat na konzumním hardware. Jejími hlavními rysy jsou universálnost, co se tý e použitelných optických model a p enositelnost mezi r znými grafickými aplikacemi. P i návrhu byl kladen d raz na její správnost a teoretický základ pro použité optické modely. • Dále je navržená metoda ov ena experimentální implementací na cílové platform . Implementace sloužila zejména k p ímému ov ení použitelnosti platformy konzumních grafických systému pro metody zobrazování objemu. Významných p ínosem je také zhodnocení problém a nedostatk této architektury.

82

Kapitola 6: Záv r • P i hledání vhodného implementa ního prost edí a nástroj byla prov ena v tšina z dostupných softwarových balík pro oblast programovatelného stínování. Mezi vlastní p ísp vky této práce pat í zejména: • Na základ studia dostupné literatury byl p esn ji formulován, mnohdy jen vágn používaný, pojem zobrazování v reálném ase. • Shrnutí celé oblasti zobrazování objemových dat na základ p vodních v deckých prací. Základ v tšiny doposud používaných metod je vysv tlen a jednotlivé p ístupy jsou porovnány a zhodnoceny jejich výhody a nevýhody. • Optické modely jsou implementovány p esn podle teoretických model a je do nich p idána sada konstant tak, aby bylo možno rychle získat, co nejlépe vypadající výstup. • Implementace navržené metody s použitím nejnov jších postup a metod v oblasti programovatelného stínování. Mnoho použitých technologií a softwarových balík je ješt ve vývoji. To dává implementaci velký potenciál do budoucna. • Implementace pomocí Shader Model 3.0 pat í mezi první svého druhu, p itom její p ínos je zna ný. Umož uje totiž celou metodu implementovat pomocí jednoho pr chodu, což bylo d íve nemyslitelné. Obdobný p ístup byl prezentován až t sn p ed dokon ením této práce na konferenci Volume Graphics v ervnu 2005. • Implementovaná metoda je v rámci dostupných možností otestována a jsou prezentovány její výsledky.

6.1 Sm ry další práce Velmi podstatným rysem této práce je, že po dokon ení vyvolala stejn otázek, jako poskytla odpov dí. Ukázalo se, že možnosti platformy konzumních grafických systém zna n pokro ily a skute n se otevírají možnosti pro reáln použitelnou implementaci zobrazování objemu. Implementace prezentovaná v této práci je experimentální a p i jejím zahájením nebylo zcela jasné, zda se jí poda í dovést do funk ního stavu. B hem prací bylo zjišt no mnoho optimalizací a nových postup , které by bylo možné použít k dalšímu zlepšení metody. N které z nich nebyly do implementace zahrnuty, nebo preference byla na stran p ehlednosti a správnosti metody, spíše než na její rychlosti a efektivit . Jiné nebylo možné implementovat ist z asových d vod . N které z dalších možností vývoje této metody lze shrnout do následujících bod : • Zp sob generování „stínovacích“ paprsk (tedy zp sob výpo tu útlumu sv tla na dráze od vn jšího zdroje) je velmi neefektivní. V literatu e jsou navrženy zp soby, jak tento výpo et provád t efektivn ji ([Kajiya a Von Herzen 84]), ovšem zp sob jejich implementace uvnit shader není úpln z ejmý a je pot eba dalšího výzkumu možností GPU.

83

Kapitola 6: Záv r • Rozd lení zatížení vertex a fragment shader je velmi nerovnom rné. P evedení v tšího dílu práce na vertex procesory by ur it p ineslo významné zvýšení výkonu. Zp sob, jak by se tato distribuce dala provést byl nastín n v §5.4.1. • V implementaci není použitá žádná z urychlovacích technik, které se v jiných implementacích vrhání i rekurzivního sledování paprsku používají. V n kterých p ípadech lze navíc již nyní íci, že jejich implementace nebude nijak obtížná a zvýšení rychlosti by mohlo být znatelné. • Pro reálnou aplikovatelnost metody je pot eba zlepšit interakci s ostatními objekty ve scén . Metoda sice bez problému koexistuje s ostatními t lesy ve scén , ale pouze pokud mají tyto neprázdný pr nik se zobrazovaným objemem. Tento nedostatek je závažný p edevším pro použití v herním odv tví. U fenomén jako je nap íklad ohe a kou je zcela nezbytné, aby se proxy geometrie objemu mohla protínat s ostatními t lesy. • V prezentované implementaci je použito pouze jedno sv tlo. Je ist technickou záležitostí dodat sv tel více, ovšem p ínos, zejména z hlediska kvality výstupu, by byl znatelný.

84

Literatura [Almorea] Domácí stránka projektu Almorea, http://almorea.jikos.cz [AnandTech] Internetový portál o hardware AnandTech, www.anandtech.com [Blinn 82] J. F. Blinn: Light reflection functions for simulation of clouds and dusty surfaces, Proceedings of SIGGRAPH Conference (1982) [Cabral et al. 94] B. Cabral, N. Cam, J. Foran: Accelerated volume rendering and tomographic reconstruction using texture mapping hardware, ACM Symposium on Volume Visualization (1994), 91-98 [Cameron a Undrill 92] G.G. Cameron, P.E. Undrill: Rendering volumetric medical image data on SIMD-architecture computer, Proceedings of the Third Eurographics Workshop on Rendering, (b ezen 1992), 135-145 [Chandrasekhar 50] S. Chandrasekhar: Radiative Transfer, Oxford University Press (1950) [Cline et al. 88] H.E.Cline, W.E. Lorensen, S.Ludke, C.R. Craword, B.C. Teeter: Two Algorithms for Three-dimensional Reconstruction of Tomograms, Medical Physics Volume 15 Number 3, (b ezen/duben 1988)320-327 [Cullip 93] T. Cullip, U. Neumann: Accelerating Volume Reconstruction with 3D texture hardware, Technical Report TR93-027 University of North Carolina, Chapel Hill, N.C. [DirectX9.0c 05] Microsoft DirectX9.0c msdn.microsoft.com/directx/

SDK,

April

2005

Release,

[Dunne et al. 90] S. Dunne, S. Napel, B. Rutt: Fast Reprojection of Volume Data, Proceedings of the First Conference on Visualization in Biochemical Computing (1990),11-18 [Ekoule et al. 91] A.B. Ekoule, F.C. Peyrin, C.L. Odet: A triangulation algorithm from Arbitrary Shaped Multiple Planar Contours, ACM Transactions of Graphics Volume 10 Number 2 (duben 1991), 182-199

85

[Elvins 92] T. Todd Elvins: A survey of algorithms for volume visualization, ACM SIGGRAPH Computer Graphics, Volume 26 Issue 3 [Engel et al. 01] K. Engel, M. Kraus, T. Ertl: High-quality pre-integrated volume rendering using hardware-accelerated pixel shading, SIGGRAPH/Eurographics Workshop on Graphics Hardware [Friedlander 00] S.K.Friedlander: Smoke, Dust and Haze: Fundamentals of Aerosol Dynamics, Second Edition, Kapitola 5: Light Scattering, Oxford University Press 2000 [Fuchs et al. 77] H. Fuchs, Z. M. Kedem, S.P.Uselton: Optimal Surface Reconstruction from Planar Contours, Communications of the ACM Volume 20 Number 10, ( íjen 1977), 693-702 [Green 05] S. Green: Volume Rendering for Games, Game Developer Conference (2005), http://developer.nvidia.com [Guthe et al. 02] S. Guthe, S. Roettger, A. Schieber, W. Strasser, T. Ertl: Highquality unstructured volume rendering on the PC platform, SIGGRAPH/Eurographics Hardware Workshop [Henyey a Greenstein 40] G.L.Henyey, J.L. Greenstein: Diffuse radiation in the galaxy, Astrophysical Journal volume 88, 1940, 70-73 [Herman a Liu 79] G.T. Herman, H.K.Liu: Three-dimensional Display of Human Organs from Computed Tomograms, Computer Graphics and Image Processing, Volume 9 Number 1 (leden 1979), 1-21 [Kajiya 86] J. T. Kajiya: The rendering equation, Computer Graphics Volume 20 Number 4 (srpen 1986),143-150 [Kajiya a Von Herzen 84] J. T. Kajiya, B. P. Von Herzen: Ray Tracing Volume Densities, Proceedings of the SIGGRAPH Conference (1984) [Kniss et al. 02a] J. Kniss, S. Premoze, C. Hansen, D. Ebert: Interactive translucent volume rendering and procedural modeling, Proceedings of IEEE Visualization (2002), stránky168-176 [Krüger a Westermann 03] J. Krüger, R.Westermann: Acceleration techniques for GPU-based Volume Rendering, Proceedings of IEEE Visualization (2003) [Lacroute a Levoy 94] P. Lacroute, M. Levoy: Fast volume rendering using shearwarp factorization of the viewing matrix, Proceedings of the 21st annual conference on Computer graphics and interactive techniques (1994),451458 [Lastra et al. 95] A. Lastra, S. Molnar, Y. Wang: Real-time programmable shading, Proceedings of the symposium on Interactive 3D graphics (duben 1995)

86

[Levoy 90] Marc Levoy: Volume Rendering: A hybrid Ray Tracer for Rendering Polygon and Volume Data, IEEE Computer Graphics and Applications (b ezen 1990), 33-40 [Levoy 92] M. Levoy: Volume Rendering using the Fourier Projection-Slice Theorem, Proceedings of the Graphics Interface (1992), 61-69 [Lorensen a Cline 87] W.E. Lorensen, H.E. Cline: Marching Cubes: A High Resolution 3D Surface Construction Algorithm, Computer Graphics Volume 21 Number 4, ( ervenec 1987),163-169 [Magnor et al. 04] M. Magnor, G. Kindlmann, Ch. Hansen: Constrained Inverse Volume Rendering for Planetary Nebulae, Proceedings of the Conference on Visualization (2004) [Malzbender 93] T. Malzbender: Fourier Volume Rendering, ACM Transactions on Graphics Volume 12 Number 3, ( ervenec 1993) [Max 83] N. Max: Panel on the simulation of natural phenomena, Proceedings of SIGGRAPH Conference (1983) [Max 95] N. Max: Optical Models for Direct Volume Rendering, IEEE Transaction on Visualization and Computer Graphics 1,2 ( erven 1995), 99-108 [McCarthy et al. 04] J. D. McCarthy, M. A. Sasse, D. Miras: Sharp or Smooth ?: comparing the effects of quantization vs. frame rate for streamed video, Proceedings of the SIGCHI on Human factors in computing systems (duben 2004) [Meehan et al. 02] M. Meehan, B. Insko, M. Whiton, F. P. Brooks: Psychological measures of presence in stressful virtual environments, ACM Transaction of Graphics, Proceedings of th 29th annual conference on Computer graphics and interactive techniques ( ervenec 2002) [Meissner et al. 99] M. Meissner, U. Hoffman, W. Strasser: Enabling classification and shading for 3d texture mapping based volume rendering using OpenGL and extensions, Proceedings of IEEE Visualization (1999), stránky 110-119 [OpenGL 2.0 04] The OpenGL Graphics System: A specification, October 22, 2004, www.opengl.org [Owen 99] G. S.Owen: Volume Visualization and Rendering, Výukové materiály ACM Education Committee, (modifikováno 1999), www.siggraph.org/education/materials/HyperVis/vistech/volume/volume .htm [Perlin 02] K. Perlin, Improving Noise, Computer Graphics, volume 35, No. 3

87

[Perlin 84] K. Perlin, course in Advanced Image Synthesis, ACM SIGGRAPH (1984) [Perlin] Domácí stránka Kena Perlina, http://mrl.nyu.edu/~perlin [PG III] J. Pelikán, Skripta k p ednášce Po íta ová grafika III, cgg.ms.mff.cuni.cz/~pepca [Phong 75] Bui-Tuong Phong, Illumination for Computer-Generated Pictures, CACM ( erven 1975), 311-317 [Purcell et al. 02] T. J. Purcell, I. Buck, W.R. Mark, P. Hanrahan: Ray tracing on programmable graphics hardware, Proceedings of the 29th annual conference on Computer graphics and interactive techniques ( ervenec 2002), 703-712 [Rezk-Salama et al. 00] C. Rezk-Salama, K. Engel, M. Bauer, G. Geiner, T. Ertl: Interactive Volume rendering on standard PC graphics hardware using multi-textures and multi-stage rasterization, SIGGRAPH/Eurographics Workshop on Graphics Hardware, stránky 109-119 [Sabella 88] P. Sabella: A Rendering Algorithm for Visualizing 3D Scalar Fields, Computer Graphics Volume 22 Number 4 ( ervenec 1988), 51-58 [Shirley a Tuchman 90] P. Shirley, A. Tuchman: A polygonal Approximation to Direct Scalar Volume Rendering, Computer Graphics Volume 24 Number 5 (listopad 1990), 63-70 [Stegmaier et al. 05] S. Stegmaier, M.Strengert, T.Klein, T.Ertl, A Simple and Flexible Volume Rendering Framework for Graphics-Hardware-based Raycasting, Volume Graphics (2005) [Totsuka a Levoy 93] T.Totsuka, M. Levoy: Frequency domain volume rendering, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, 271-278 [Upson a Keeler 88] C. Upson, M. Keeler: The V-Buffer: Visible Volume Rendering, Computer Graphics Volume 22 Number 4 ( erven 1988), 59-64 [Van Geldern a Kwansik 96] A. Van Geldern, K. Kwansik: Direct Volume Rendering with Shading via Three-Dimensional Textures, Proceedings of ACM Symposium on Volume Visualization (1994), stránky 23-30 [Voss 83] R.Voss: Fourier synthesis of Gaussian fractals: 1/f noises, landscapes and flakes, Tutorial on the State of the Art Images Synthesis, volume 10, SIGGRAPH (1983) [Westermann a Ertl 98] R. Westermann, T. Ertl: Efficiently using graphics hardware in volume rendering applications, Proceedings of SIGGRAPH (1998), stránky 291-294.

88

[Westover 90] L. Westover: Footprint Evaluation For Volume Rendering, Computer Graphics Volume 24 Number 4, (srpen 1990), 267-376 [Yuan et al. 97] P.Yuan, M.Green, R.W.H.Lau: A framework for performance evaluation of real-time rendering algorithms in virtual reality, Proceedings of the ACM Symposium on Virtual Reality software and technology (zá í 1997)

89

P íloha A: Obsah CD Doprovodné CD je vybaveno systémem automatického spoušt ní. Po vložení CD do mechaniky se spustí webová stránka index.htm. Pokud je automatické spoušt ní v opera ním systému vypnuto, lze stránku index.htm nalézt p ímo v ko enovém adresá i CD. Na této stránce je uveden obsah CD spolu s odkazy na jednotlivé adresá e. CD má následující obsah: • Adresá DataPreparation. V tomto adresá i je uložen pomocný program pro tvorbu experimentálních dat. Program je ve form úplného projektu (solution) pro prost edí Microsoft Visual Studio. NET 2003. • Adresá Effects. Tento adresá obsahuje všechny vytvo ené efektové soubory. Jsou zde také uloženy testovací scény (/Effects/Scenes), experimentální objemová data (/Effects/Volumes) a pomocné bitmapy (/Effects/Images). • Adresá Text. Zde je uložen text této diplomové práce ve formátu PDF. P iložen je také zdrojový soubor ve formátu Microsoft Word.