M A S A R Y K O V A U N I V E R Z I T A F A K U L T A I N F O R M A T I K Y Aplikace metod raytracingu na molekulárni systémy D I P L O M O V Á P R Á C E Bc. František Dvořáček Brno, podzim 2013 Prohlášení Prohlašuji, že tato diplomová práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. Bc. František Dvořáček Vedoucí práce: R N D r . Barbora Kozlíková, P h . D . ii Poděkování Rád bych na tomto místě poděkoval vedoucí své diplomové práce R N D r . Barboře Kozlíkové, P h . D . a Mgr. Vilému Sustrovi za jejich trpělivost, cenné rady a pomoc při tvorbě této práce. iii Shrnutí Cílem této práce je popsat implementaci raytraceru, který umožní vytvořit rendery molekul proteinů a jejich tunelů ve vysokém rozlišení. Implementace podporuje vykreslení molekul a jejich tunelů pomocí nejrozšířenějších a nejčastěji používaných metod zobrazení. Z důvodů snížení časové náročnosti algoritmu je pro organizaci scény použita třídimenzionální mřížka. Vytvořený raytracer b y l integrován do aplikace C A V E R Analyst. iv Klíčová slova raytracing, vrhání paprsku, molekula, protein, tunel, objemová data, trojúhelník, koule, válec, kvádr v Obsah 1 Úvod 3 2 Metody zobrazení proteinů 5 2.1 Typy zobrazení molekul 5 2.1.1 Van der Waals (VdW) 5 2.1.2 Tyčinky a koule 6 2.1.3 Tyčinky 6 2.1.4 Povrch molekuly 7 2.2 Typy zobrazení tunelů 7 2.2.1 Středová osa (Centerline) 8 2.2.2 Koule 9 2.2.3 Povrch 9 3 Raytracing 10 3.1 Algoritmus 10 3.2 Implementace raytraceru 12 3.2.1 Struktura raytraceru 13 4 Vrhání paprsků 15 4.1 Paprsek 15 4.2 Kamera 15 4.3 Primární paprsky 17 4.4 Supersampling 19 4.5 Adaptivní vzorkování 21 4.6 Adaptivní supersampling 22 5 Nalezení průsečíku 24 5.1 Scéna 24 5.2 Trojúhelník 24 5.2.1 Definice trojúhelníku 24 5.2.2 Barycentrické souřadnice 25 5.2.3 Nalezení průsečíku 25 5.2.4 Implementace 28 5.2.5 Výpočet normály 29 5.3 Koule 30 5.3.1 Definice koule 30 5.3.2 Geometrické řešení 30 5.3.3 Výpočet normály 34 5.3.4 Implementace 34 1 5.4 Válec 35 5.4.1 Nalezení průsečíku 35 5.4.2 Výpočet normály 38 5.5 Osově orientovaný kvádr 38 5.5.1 Nalezení průsečíku 38 5.5.2 Implementace 41 6 Výpočet barvy 43 6.1 Phongův osvětlovací model 43 6.1.1 Materiál 43 6.1.2 Ambientní složka 44 6.1.3 Difúzni složka 44 6.1.4 Spekulární složka 46 6.2 Výpočet stínů 47 7 Zobrazení objemových dat 48 7.1 Konstrukce mřížky 48 7.2 Procházení mřížkou 49 7.2.1 Algoritmus 3 D - D D A 49 8 Urychlující struktury 55 8.1 Vytvoření mřížky 55 8.2 Vložení objektů 56 8.3 Nalezení nejbližšího průsečíku 57 8.4 Porovnání rychlosti 58 9 Závěr 59 10 Příloha 64 2 1 Úvod Struktury proteinů jsou základním stavebním kamenem všech žijících organizmů. Najdeme je v každé z buněk, z nichž se tyto organizmy skládají. Výzkumu zaměřenému na proteiny se tedy věnuje značná pozornost. Proteiny jsou struktury, představované molekulami, které se mohou skládat z tisíců jednotlivých atomů propojených kovalentními vazbami. Pro správnou představu o struktuře proteinů je tedy potřeba nalézt vhodné nástroje pro jejich zobrazení. V současné době se pro zobrazení molekul proteinů používá k o m binace d v o u technik. Pro vykreslování v reálném čase se používají techniky využívající rasterizaci (například OpenGL). Pro vytvoření statických renderů ve vyšší kvalitě a rozlišení se pak využívá raytracing. Vyšší kvalita zobrazení je požadována například při prezentaci a vkládání renderů proteinů do vědeckých prací. Cílem mé diplomové práce bylo vytvořit implementaci raytracingu, která by umožňovala vytvoření renderů ve vysokém rozlišení pro jednotlivé metody zobrazení používané v aplikaci C A V E R A n a ­ lyst. Textová část práce se zaměřuje na jednotlivé techniky použité při této implementaci. Kapitola 2 popisuje metody zobrazení podporované vytvořeným raytracerem. Text této kapitoly je doplněn o rendery proteinů vytvořené pomocí implementovaného algoritmu. V první části kapitoly 3 představuji základní algoritmus pro zobrazení pomocí raytracingu. V části druhé popíši strukturu implementovaného raytraceru postaveného na tomto algoritmu. Kapitola 4 se věnuje různým metodám vzorkování scény. N a použité vzorkovací metodě závisí kvalita zobrazení a doba potřebná pro vykreslení scény. Základní kámen raytracingu, nalezení průsečíků paprsků s objekty ve scéně, je popsán v kapitole 5. V této kapitole se věnuji detailnímu popisu technik pro nalezení průsečíku paprsku s jednotlivými základními objekty, používanými pro vytvoření komplexních scén. Kapitola 6 uvádí využití Phongova osvětlovacího modelu a stínových paprsků pro výpočet obarvení objektů ve scéně. 3 1. Ú V O D Raytracing lze využít i pro zobrazení objemových dat. Této tématice se věnuje kapitola 7. Kapitola 8 se zaměřuje na vytvoření urychlující struktury pro organizaci scény S její pomocí je dosaženo snížení časové náročnosti algoritmu. V závěru práce hodnotím dosažené výsledky a navrhuji možná rozšíření raytraceru. 4 2 Metody zobrazení proteinů Základní stavební kameny každé molekuly jsou atomy propojené kovalentními vazbami. Existuje několik způsobů jak zobrazovat proteiny Níže uvedené metody byly implementovány v rámci mé diplomové práce. Všechny obrázky použité v této kapitole byly vyrenderovány pomocí vytvořeného raytraceru. 2.1 Typy zobrazení molekul 2.1.1 Van der Waals (VdW) Při V d W zobrazení jsou atomy vykresleny jako koule, obrázek 2.1. Jejich velikost je dána v a n der Waalsovým poloměrem [6]. Vzdálenost mezi atomy, propojenými kovalentními vazbami, je menší než součet jejich poloměrů. Proto se koule použité při V d W zobrazení navzájem pronikají a vazby mezi n i m i nejsou viditelné. Barvy atomů reprezentují chemický prvek, který dané atomy představují. Například pro zobrazení atomů kyslíku se používá červená barva. V d W zobrazení se hodí pro představu o celkovém objemu molekuly. Obrázek 2.1: Molekula ledw, zobrazena pomocí V d W 5 2. M E T O D Y Z O B R A Z E N Í P R O T E I N Ů 2.1.2 Tyčinky a koule N a obrázku 2.2 jsou vykresleny jednotlivé atomy a vazby mezi nimi. Tomuto zobrazení se říká tyčinky a koule. A t o m y jsou reprezentovány pomocí koulí. Jejich velikost odpovídá jedné třetině van der Waalsova poloměru. Kovalentní vazby jsou vykresleny pomocí válců s malým průměrem. Jejich jednotlivé poloviny jsou obarveny podle koncových atomů, které propojují. Obrázek 2.2: Molekula ledw, zobrazena pomocí tyčinek a koulí. 2.1.3 Tyčinky Snadnější pochopení celkové struktury proteinu umožňuje zobrazení molekuly jen jako množiny vazeb mezi jednotlivými atomy, obrázek 2.3. Tyto vazby jsou vykresleny pomocí válců s malým poloměrem. Barva jednotlivých konců vazeb odpovídá barvě atomů, které propojují, stejně jako je t o m u u předešlého zobrazení. 6 2. M E T O D Y Z O B R A Z E N Í P R O T E I N Ů Obrázek 2.3: Molekula ledw, zobrazena pomocí tyčinek. 2.1.4 Povrch molekuly Proteiny samy o sobě nemají fyzický povrch. Umělé vytvoření jejich povrchu usnadní vizuální představu vlastností proteinů. Jednou z důležitých vlastností je členitost povrchu, která může být známkou, do jaké míry je protein schopen reagovat se svým okolím. Více členitý povrch může obsahovat trhliny, tzv. tunely, vedoucí do nitra molekuly. Ukázka povrchu molekuly je zobrazena na obrázku 2.4. 2.2 Typy zobrazení tunelů Tunel představuje cestu vedoucí z povrchu proteinu do jeho středu, tzv. aktivního místa proteinu. Cílem výpočtu tunelů je nalézt takové tunely, které by umožnily transport malých molekul (například molekul vody) do aktivního místa proteinu, a tím umožnili jejich vzájemnou reakci. Detailní popis jednotlivých technik pro nalezení tunelů a výpočet dat pro jejich zobrazení může být nalezen v [6] [1]. 7 2. M E T O D Y Z O B R A Z E N Í P R O T E I N Ů Obrázek 2.4: Povrch molekuly ledw 2.2.1 Středová osa (Centerline) Středová osa spojuje body, které leží ve středech jednotlivých segmentů tunelu, obrázek 2.5. Může být zobrazena pomocí válců s malým průměrem, spojujících sousední body. Toto zobrazení je vhodné pro základní představu o tvaru a délce tunelu. Obrázek 2.5: Tunel zobrazený pomocí středové linie. 8 2. M E T O D Y Z O B R A Z E N Í P R O T E I N Ů 2.2.2 Koule Zobrazení pomocí koulí použité na obrázku 2.6 vznikne sestrojením koulí v jednotlivých bodech středové linie. Poloměr koulí určuje maximální poloměr tunelu v daném místě proteinu. Dostáváme tak představu o tvaru a šířce tunelu. Obrázek 2.6: Tunel zobrazený pomocí koulí, představující jeho šířku v daném bodě středové linie 2.2.3 Povrch N a obrázku 2.7 je povrch tunelu vykreslen pomocí sítě trojúhelníků. Takové zobrazení umožňuje přesnou představu o tvaru tunelu. Obrázek 2.7: Detailní povrch tunelu 3 Raytracing V první části této kapitoly popíši princip algoritmu publikovaném v roce 1980 Turnerem Whittedem [10]. Druhá část kapitoly se bude zabývat popisem implementace raytraceru vzniklého na základě tohoto algoritmu. 3.1 Algoritmus Algoritmus 3.1 popisuje základní kroky při výpočtu zobrazení scény pomocí raytracingu. Algoritmus můžeme rozdělit do několika částí. Algoritmus 3.1 Raytracing 1. Sestroj paprsek skrz každý pixel obrazovky. 2. Nalezni nejbližší průsečík ve scéně. P o k u d neexistuje, vrať barvu pozadí. 3. Sestroj stínové paprsky. Viditelné světelné zdroje zahrň do výpočtu osvětlení. 4. Vypočti osvětlení. 5. Sestroj odražený paprsek a lomený paprsek a rekurzivně opakuj kroky 2 až 5 d o k u d paprsek neopustí scénu nebo není dosaženo hloubky rekurze. 6. D o pixelu obrazovky ulož výslednou barvu. První částí je vrhání paprsků, k d y z pozice pozorovatele vystřelíme do scény primární paprsky skrz všechny pixely obrazovky (krok 1). V druhé části, nalezení průsečíků, zjišťujeme, z d a ve scéně existuje objekt, který námi vržený paprsek protíná. P o k u d ano, je v y počtena přesná poloha průsečíku s paprskem. V případě, že paprsek protíná více objektů, zajímá nás jen průsečík ležící nejblíže k rovině promítání. P o k u d paprsek neprotne žádný objekt, výpočet skončí a do barvy paprsku je přiřazena barva pozadí (krok 2). 10 3. R A Y T R A C I N G Poslední částí je výpočet barvy v bodě nalezeného průsečíku. Barva v daném bodě je dána součtem barevných příspěvků osvětlení a barevných příspěvků sekundárních paprsků. N a osvětlení se podílí pouze zdroje světla viditelné z daného bodu. Viditelnost světelných zdrojů zjistíme pomocí takzvaných stínových paprsků (krok 3). Pro vlastní výpočet osvětlení poté můžeme použít například Phongův osvětlovací model (krok 4). Existují dva druhy sekundárních paprsků, odražené a lomené. Odražený paprsek slouží pro výpočet zrcadlových odrazů. Jeho počátek leží v bodě průniku a směr je dán odrazem přicházejícího paprsku od povrchu objektu. Lomený paprsek slouží pro výpočet lomů světla v poloprůhledných objektech. Počátek je opět v bodě průniku. Paprsek poté směřuje skrz objekt (krok 5). Pro dosažení vícenásobných světelných odrazů a lomů opakujeme kroky 2 až 5. V případě, že paprsek opustí scénu nebo je dosažena předem daná hloubka rekurze, vytváření nových paprsků se ukončí a do obrazové paměti je na pozici pixelu uložena barevná hodnota primárního paprsku (krok 6). N a obrázku 3.1 jsou znázorněny paprsky vytvořené ve scéně pro výpočet barvy pixelu na pozici (x, y). Scéna obsahuje polopropustné zrcadlo Z, matnou kouli K a dva světelné zdroje S1 a S2. Paprsek p je primární paprsek vystřelený z pozice kamery směrem daným pozicí pixelu. Při průchodu scénou zasáhne zrcadlo Z v bodě B1. Jedná se o jediný průsečík paprsku s objekty, proto je v y počítána jeho barva, která je později uložena do pixelu (x, y). Pro výpočet osvětlení b o d u B1 sestrojíme stínové paprsky spi a sp2 ke zdrojům světla Si a S2. Paprsek sp2 protíná kouli K, proto světelný zdroj S2 nebude zahrnut do výpočtu osvětlení v bodě B1. Pro výpočet celkové barvy b o d u B\ musíme vytvořit odražený paprsek op a lomený paprsek lpi. Paprsek op dále putuje scénou, kde zasáhne kouli K v bodě B2. Pro barvu v tomto bodě stačí spočítat osvětlení, protože koule K je matná a nepropustná, takže sekundární paprsky nebudou vystřeleny. Lomený paprsek lpi projde tělesem a opustí jej v bodě B3 jako paprsek lp2. Tento paprsek nezasáhne žádné těleso ve scéně. Výpočet 11 3. R A Y T R A C I N G je ukončen a barva paprsku odpovídá barvě pozadí. Výsledná barva v bodě B1 se tedy skládá z osvětlení pomocí světelného zdroje BS\, barevného přírůstku odraženého paprsku op v y počteného v bodě B2 a barevného přírůstku lomeného paprsku lps. pozorovatel Obrázek 3.1: Výpočet barvy pixelu (x,y) 3.2 Implementace raytraceru Tato kapitola se věnuje popisu implementace raytraceru, který b y l vytvořen podle algoritmu představeném v předchozí kapitole. V následujícím textu se zaměřím na jednotlivé části algoritmu a jejich možná rozšíření. 12 3. R A Y T R A C I N G 3.2.1 Struktura raytraceru N a obrázku 3.2 je znázorněna struktura raytraceru vytvořeného v rámci mé diplomové práce. Jednotlivé stavy odpovídají hlavním částem algoritmu 3.1 Přechody mezi stavy jsou nadepsány názvy objektů, které jsou vytvořeny v jednotlivých částech. Vrháni paprsků Jednoduché vzorkování Adaptivní vzorkování Supersampling Adaptivní Supersampling Paprsek(počátek, směr) Nalezení průsečíků Trojúhelník Koule Válec Kvádr Stínový paprsek (průsečík, směr ke světlu) Průsečikfpaprsek, objekt) Výpočet barvy Phongův osvětlovací model Stínové parpsky Barva Scéna Vstup Výstup Render scény Obrázek 3.2: Obecná struktura raytraceru Vstupem algoritmu je scéna, kterou si přejeme zobrazit. Scéna se skládá z těles, světel a kamery. Algoritmus umožňuje vytvářet různý počet primárních paprsků procházejících jedním pixelem. O d jednoduchého vzorkování, k d y jedním pixelem prochází jen jeden paprsek, po vzorkování s vyšší frekvencí (tzv. supersampling), k d y pixelem prochází paprsků několik. Počet primárních paprsků je možné redukovat pomocí adaptivního vzorkování, které mění hustotu primárních paprsků v závislosti na barevných změnách v obraze. Raytracer umožňuje nalezení průsečíku paprsku se čtyřmi základními objekty Těmi jsou trojúhelníky, koule, válce a kvádry. V části nalezení průsečíku algoritmus projde všechny objekty ve scéně a vrátí průsečík s objektem ležícím nejblíže počátku paprsku. Po nalezení průsečíku je potřeba vypočítat jeho barvu. Toho je 13 3. R A Y T R A C I N G dosaženo pomocí stínových paprsků a Phongova osvětlovacího modelu. Vícenásobné světelné odrazy a lomy nejsou při zobrazování molekul potřeba a proto nebyl jejich výpočet implementován. Po vypočtení barev všech pixelů je výsledný render uložen do souboru a zobrazen na obrazovce. N a obrázku 3.3 je znázorněna struktura algoritmu obsahující náz v y hlavních metod jednotlivých částí, popřípadě názvy tříd reprezentujících jednotlivá tělesa. Vrhání paprsků castPrimaryRaysQ castAARaysQ castAdaptiveAARaysf) Scene Vstup Ray(origin, direction) Nalezení průsečíků Triangle Sphere Cylinder Box ShadowRay (intersection, direction) Intersectionfray, primitive) Výpočet barvy calculatePhongO casIShadowRayQ Color Výstup Screen Obrázek 3.3: Struktura raytraceru - třídy a metody 14 4 Vrhání paprsků Následující kapitola se věnuje první části algoritmu 3.1. Nejdříve b u dou definovány pojmy paprsek a kamera, které později použiji při popisu jednotlivých metod vrhání primárních paprsků. 4.1 Paprsek Paprsek je polopřímka v prostoru definovaná svým počátkem a směrem. Kterýkoliv b o d P ležící na této přímce je popsán rovnicí 4.1. p = 0 + t*d (4.1) Trojrozměrný vektor O představuje počátek paprsku, vektor d jeho směr. P o k u d je směr paprsku normalizovaný, parametr t udává vzdálenost b o d u P o d počátku paprsku. t>0 Obrázek 4.1: Poloha bodu na přímce v závislosti na parametru t Jak lze vidět na obrázku 4.1, b o d P leží na paprsku, p o k u d je hodnota parametru t > 0. Pro t = 0 platí, že b o d leží přímo v počátku paprsku. P o k u d je t < 0, b o d leží za počátkem a neleží tedy na pa­ prsku. 4.2 Kamera Pro přesné zobrazení scény je potřeba definovat kameru, její pozici a bod, na který je kamera zaměřena. N a obrázku 4.2 vidíme nákres 15 4. V R H Á N Í P A P R S K Ů takové kamery. První dva parametry určují již zmíněnou pozici kamery v prostoru, představovanou vektorem position, a souřadnice bodu look at, n a který je kamera zaměřena. Tento b o d je středem promítacího plátna o šířce width a výšce height. Směr, kterým je kamera namířena, popisuje vektor direction. Tento vektor je definován jako rozdíl vektorů position a look at. Vektor direction také představuje optickou osu kamery. Natočení kamery je určeno dvěma jednotkovými vektory up a right. O b a tyto vektory jsou kolmé n a osu kamery. Vektor up určuje směr vzhůru a vektor right ukazuje vpravo o d osy kamery. Obrázek 4.2: Popis parametrů kamery. Velikost promítacího plátna se vypočítá z úhlu záběru kamery (field ofview) a vzdálenosti plátna o d kamery [7]. U h e l a n a obrázku představuje polovinu úhlu záběru kamery. Šířku promítacího plátna vypočteme pomocí rovnice 4.2. Parametr / představuje délku vektoru direction, tedy vzdálenost kamery o d promítacího plátna. width = 2*1 * tan a (4.2) Rovnice 4.3 slouží pro výpočet výšky promítacího plátna pomocí šířky plátna a parametru aspect, který udává poměr šířky a výšky 16 4. V R H Á N Í P A P R S K Ů promítacího plátna. Tento parametr může být definován uživatelem nebo odvozen z rozlišení, ve kterém si přejeme scénu renderovat. height = aspect / width (4.3) 4.3 Primární paprsky Při jednoduchém vzorkování prochází každým pixelem obrazovky právě jeden primární paprsek. Jeho počátek je shodný s pozicí kamery a směr je vypočten ze směru kamery a pozice pixelu na obrazovce, kterým daný paprsek prochází. Obrazovka a promítací plátno nejsou totožné. Liší se velikostí a umístěním počátků svých lokálních souřadných systémů. Pro přesný výpočet směru je tedy potřeba převést souřadnice obrazovky (x,y) na souřadnice promítacího plátna (x',y'). Rozdíly mezi obrazovkou a promítacím plátnem je znázorněn na obrázku 4.3. 0,0 heighť2 promítací x',y' plátno 0,0 width/2, -height/2 resX, resY Obrázek 4.3: Vztah mezi obrazovkou a plátnem Nejdříve převedeme velikost obrazovky na velikost plátna. Cílem je, aby plátno mělo stejný počet pixelů jako obrazovka a lišila se jejich velikost. Pixely na obrazovce jsou čtvercové. P o k u d předpokládáme, že poměry stran obrazovky a plátna jsou stejné, b u d o u čtvercové i pixely plátna. Pro výpočet velikosti pixelu plátna nám tedy stačí zjistit poměr šířky promítacího plátna a obrazovky podle rovnice 4.4. velikostPixelu = width/resX (4.4) obrazovka -width/2, x,y 17 4. V R H Á N Í P A P R S K Ů Dalším krokem při výpočtu souřadnice (x',y') je úprava souřadného systému. Zatímco souřadný systém obrazovky začíná v levém horním rohu a hodnoty rostou směrem k pravému dolnímu rohu, souřadný systém promítací roviny je umístěn do jejího středu s hodnotami rostoucími směrem k pravému hornímu rohu. Z toho dův o d u při výpočtu x' o d souřadnice obrazovky x odečteme hodnotu width/2. Protože souřadnice y ' roste v opačném směru než y, při jejím výpočtu hodnotu y odečteme o d height/2. Převod souřadnice obrazovky (x,y) na souřadnici plátna (x',y') je uveden v rovnicích 4.5 a 4.6. x = —width/2 + x * velikostPixelu (4.5) y' = height/2 — y * velikostPixelu (4.6) Jakmile známe souřadnici (x',y'), zbývá vypočítat směr primárního paprsku. Sestrojení primárního paprsku s počátkem camera position a směrem direction je zobrazeno na obrázku 4.4. -width/2, height/2 camera position Obrázek 4.4: Výpočet směru primárního paprsku 18 4. V R H Á N Í P A P R S K Ů Směr paprsku se podle rovnice 4.7 vypočte přičtením vektorů up a right ke směru kamery camera direction. Oba tyto vektory jsou jednotkové. Vynásobením každé z jejich složek hodnotami x' a y ' změníme jejich velikost, která poté odpovídá poloze pixelu v souřadném systému promítací roviny. direction = cameraDirection + right * (x1 ) + up* {%)') (4.7) Všechny kroky potřebné pro vytvoření primárních paprsků jsou shrnuty v algoritmu 4.1. Algoritmus 4.1 Sestroj primární paprsky 1. Velikost pixelu = šířka promítací plochy / šířka obrazovky 2. Pro každý pixel obrazovky (x,y) 3. x' = - 1 /2 šířky promítací plochy + x * velikost pixelu 4. y' = 1 /2 šířky promítací plochy - y * velikost pixelu 5. Směr = směr kamery + (right vektor * x') + (up vektor * y') 6. Sestroj paprsek(pozice kamery, směr) V prvním kroku je vypočtena velikost pixelu plátna. Tato velikost je stejná pro všechny pixely a její výpočet je proto proveden m i m o hlavní cyklus. V cyklu samotném projdeme všechny pixely obrazovky. V krocích 2 a 3 převedeme souřadnice pixelu plátna na souřadnice pixelu obrazovky. Jakmile známe tyto souřadnice, můžeme v kroku 5 vypočítat směr paprsku, který v posledním kroku algoritmu sestrojíme. 4.4 Supersampling N a obrázku 4.5 je zobrazena molekula l e d w vyrenderována pomocí jednoduchého vzorkování popsaného v kapitole 4.3. Použité rozli- 19 4. V R H Á N Í P A P R S K Ů šení obrazovky je 640 * 480 pixelů a jedním pixelem prochází právě jeden primární paprsek. Obrázek 4.5: Molekula ledw renderována jedním paprskem na pixel N a okrajích koulí reprezentujících jednotlivé atomy molekuly lze vidět, že hrany v takto vytvořeném obraze jsou zubaté. Tento jev, tzv. alias, v z n i k l díky nízké hustotě primární paprsků, kterými b y l obraz vytvořen. Alias může být potlačen pomocí vzorkování s vyšší frekvencí, tzv. supersampling, k d y je jedním pixelem sestrojeno větší množství primárních paprsků [12]. Výsledná barva pixelu se potom vypočte jako průměr barev získaných z jednotlivých primárních paprsků procházejících tímto pixelem. Díky průměrování barevných hodnot v jednotlivých pixelů jsou hrany objektů rozmazané. Takové zobrazení je pro lidské oko přijatelnější a výsledný obraz tak působí lepším dojmem. N a obrázku 4.6 je zvětšen detail molekuly ledw. Vlevo je obrázek renderován jedním paprskem skrz pixel, s jasně patrnými zubatými hranami. Uprostřed byly sestrojeny čtyři paprsky skrz každý 20 4. V R H Á N Í P A P R S K Ů pixel. H r a n y se začínají jevit hladší, místy však lze stále vidět zuby. Poslední obrázek b y l renderován šestnácti paprsky skrz pixel. Díky většímu množství paprsků se hrany jeví téměř hladké. (a) 1 paprsek (b) 4 paprsky (c) 16 paprsků Obrázek 4.6: Supersampling - ukázka Je patrné, že s vyšším počtem paprsků roste i kvalita zobrazení. Úměrně tomu však roste i čas potřebný k vykreslení scény. 4.5 Adaptivní vzorkování Jedním ze způsobů, jak snížit dobu potřebnou na vykreslení scény, je snížení počtu primárních paprsků. Důležité však je, aby byla zachována stejná kvalita zobrazení. Toho je možné dosáhnout pomocí adaptivního vzorkování [12]. Adaptivní vzorkování analyzuje obraz pomocí primárních paprsků vyslaných s nižší hustotou vzorkování. N a základě získaných vzorků je rozhodnuto, kde v obraze dochází k barevné změně a kde je tedy potřeba vyslat další primární paprsky pro určení přesné barevné hodnoty. P o k u d však ve zpracovávané oblasti obrazu k barevné změně nedochází, barevná hodnota je odvozena z okolních vzorků. Implementované adaptivní vzorkování se skládá ze d v o u kroků. V prvním kroku jsou vrženy paprsky skrz každý druhý pixel (šedé pixely na obrázku 4.7). Tyto paprsky slouží pro získání vzorků, které jsou v druhém kroku analyzovány. 21 4. V R H Á N Í P A P R S K Ů Ve druhém kroku jsou dopočítány hodnoty pixelů, kterými nebyly sestrojeny primární paprsky (např. pixel (x,y) na obrázku 4.7). Pro každý takový pixel se porovnají barevné hodnoty jeho sousedů. P o k u d jsou všechny stejné, lze předpokládat, že v dané oblasti nedochází k barevné změně a barva v pixelu bude stejná jako u jeho sousedů. Obrázek 4.7: Vzorky P o k u d se však barvy okolních pixelů liší, je potřeba vypočítat přesnou barvu pixelu pomocí vržení primárního paprsku skrz daný pixel. Zvýšením vzdálenosti mezi jednotlivými vzorky v prvním kroku, by mohlo být dosaženo většího snížení počtu primárních paprsků. S větší vzdáleností však roste i šance na ztrátu barevné informace. Implementované řešení z toho důvodu pracuje s roztečí paprsků jeden pixel. Minimální množství vystřelených paprsků je tedy poloviční oproti vrhání paprsků skrz každý pixel. 4.6 Adaptivní supersampling Adaptivní vzorkování může být také kombinováno se vzorkováním s vyšší frekvencí. V principu obraz vytváříme jednoduchým vzorkováním a v případě, že v obraze dojde k barevné změně, použijeme supersampling pro detailnější zobrazení. Implementace má opět dva kroky. V prvním kroku vytvoříme obraz pomocí jednoduchého nebo adaptivního vzorkování. V druhém kroku pro každý pixel porovnáme jeho barevnou hodnotu s barvou jeho sousedů. P o k u d je hodnota různá, dochází v okolí daného pixelu k barevné změně. Pixelem proto sestrojíme další paprsky a pomocí jejich barevného příspěvku upravíme barevnou hodnotu pixelu. N a obrázku 4.8 je zobrazena stejná molekula, jako v kapitole 4.4. Obrázek b y l vyrenderován ve stejném rozlišení, v tomto případě b y l však pro jeho vykreslení použit adaptivní supersampling se 16 paprsky skrz pixel. z 22 4. V R H Á N Í P A P R S K Ů 5 Nalezení průsečíku Srdcem každého raytraceru je část zabývající se nalezením průsečíků mezi paprsky a tělesy ve scéně. Jedná se také o výpočetně nejnáročnější krok algoritmu a je tedy potřeba nalézt co nej optimálnější metody pro výpočet těchto průsečíků. 5.1 Scéna Všechna tělesa, která je raytracer schopen zobrazit, jsou organizována ve scéně. Kromě nich scéna obsahuje i kolekci světel a definici kamery. Každé z těles ve scéně musí umožnit nalezení průsečíku s paprskem a p o k u d se jedná o zobrazitelné těleso, tak i výpočet normály povrchu. Ve vytvořeném raytraceru existují tři základní druhy zobrazitelných objektů. A to trojúhelníky, koule a válce. Čtvrtým typem objektu je, kvádr, sloužící pro tvorbu obálek urychlujících datových struktur. V následujících podkapitolách se b u d u věnovat nalezení průsečíku s každým z těchto těles. P o k u d se bude jednat o zobrazitelné těleso, popíši i výpočet normály povrchu. 5.2 Trojúhelník V počítačové grafice je trojúhelník jedním z nejpoužívanějších objektů. S jeho pomocí lze definovat povrchy složitějších těles, často se skládajících z několik set tisíc trojúhelníků. Z toho důvodu je potřeba, aby algoritmus pro nalezení průsečíku mezi paprskem a trojúhelníkem b y l co nejméně časově náročný. 5.2.1 Definice trojúhelníku Trojúhelník je definován třemi body, svými vrcholy (A, B, C). Podle konvence jsou vrcholy uloženy v pořadí proti směru hodinových r u čiček. P o k u d body neleží na přímce, definují rovinu. Pozici b o d u na 24 5. N A L E Z E N Í P R Ů S E Č Í K U této rovině můžeme vyjádřit pomocí barycentrických souřadnic. 5.2.2 Barycentrické souřadnice Barycentrické souřadnice (a, (3,7), zobrazené na obrázku 5.1, určují vzdálenost b o d u v rovině o d vrcholů trojúhelníka (A, B, C). Pozice b o d u P je popsána pomocí barycentrických souřadnic v rovnici 5.1. C Obrázek 5.1: Barycentrické souřadnice trojúhelníku ABC P(a, f3,7) = aA + f3B + (5.1) Souřadnice (a, (3,7) musí splňovat podmínku 5.2. a + f3 + 7 = 1 (5.2) 5.2.3 Nalezení průsečíku Následující postup pro nalezení průsečíku paprsku s trojúhelníkem je převzat z [8]. Rovnice 5.1 platí pro všechny body v rovině, definované body (A, B, C). Naším cílem je však zjistit, z d a daný b o d leží uvnitř trojúhelníku. B o d P leží uvnitř trojúhelníku, p o k u d jeho barycentrické souřadnice splňují podmínky 5.3. 0 < a < 1 0 < (3 < 1 (5.3) 0 < 7 < 1 25 5. N A L E Z E N Í P R Ů S E Č Í K U Ve skutečnosti k určení polohy b o d u nepotřebujeme všechny tři barycentrické souřadnice, stačí nám jen dvě z nich. Vyjádřením a z podmínky 5.2 dostaneme a = 1 — ß — 7. Poté substitucí za a do rovnice 5.1 získáme novou rovnici pro výpočet polohy b o d u p. P(ß, 1) = A + ß{B-A) + 7 ( č ľ - A) (5.4) Nesmíme zapomenout upravit i podmínky pro zjištění, z d a je bod uvnitř trojúhelníku. Nové podmínky pro ß a 7 jsou uvedeny v rovnici 5.5. 0 < ß < 1 0 < 7 < 1 (5.5) 0 < ß + 7 < 1 Pro nalezení průsečíku trojúhelníku s paprskem dosadíme rovnici paprsku P = O + td do rovnice 5.4. O + td = A + ß{B - A) + 7 ( C - A) (5.6) Dostáváme lineární rovnici o třech neznámých ß, 7 a t. Převedením všech neznámých na levou stranu dostáváme rovnici 5.7. ß{A - B)+1(A-C)+td = A-O (5.7) Všechny známé proměnné A, B, C, d a O jsou vektory. Rovnici 5.7 proto můžeme rozepsat do soustavy tří samostatných rovnic o třech neznámých. Každá z rovnic platí pro jednu z vektorových složek (x,y,z). ß(Ax - Bx) + 7 ( A Z - Cx) + tdx = Ax-Ox ß{Ay ~ By) + j(Ay - Cy) + tdy = Ay ~ Oy (5.8) ß(Az - Bz) + ~f(Az - Cz) + tdz = Az-Oz Přepsáním soustavy rovnic 5.8 do maticové formy dostaneme: a d g ~ ß~ ' j ' b e h 7 = k _ c f i _ _ t _ _ l _ Pro větší přehlednost jsou jednotlivé koeficienty nahrazeny písmeny a -1. Jejich význam je následující: 26 5. N A L E Z E N Í P R Ů S E Č Í K U a=(Ax-Bx), d b={Ay-By), e c=(Ag-Bg), f \AX — Cx). (Ay — Cy), (Az — Cz). 9 h tdx. ~t/ďy .k l \AX — Ox). {Ay — Oy). (Az - Oz (5.10) Pro vyřešení soustavy lineárních rovnic využijeme Cramerovo pravidlo uvedené v rovnici 5.11. Xi = detMi/detM (5.11) Podle Cramerova pravidla pro naši soustavu lineárních rovnic 5.9, platí /3 = detMp/M 7 = detMjM (5.12) t = detMt/M Pro výpočet jednotlivých neznámých je nejprve potřeba určit jednotlivé matice. Matice M je matice z levé strany rovnice 5.9. M a b d e f 9 h (5.13) Podle Cramerova pravidla je matice M , sestrojena z matice M s i-tým sloupcem nahrazeným vektorem odpovídajícím pravé straně soustavy lineárních rovnic. V našem případě je to vektor (j,k,l) a matice Ma, M g a Mt jsou: Ma = 3 d g k e h l f t M p — a j 9 b k h c l i Mt = a d j b e k c f l (5.14) Dolní index u matice, značí pro kterou z neznámých je matice vytvořena. Jakmile máme vyjádřeny všechny matice, je potřeba vypočítat jejich determinanty. Jejich výpočet je popsán v rovnicích 5.15. detM = a(ei — hf) + b(gf — di) + c(dh — eg) detMp = j(ei-hf) + k(gf - di) + l(dh - eg) (5.15) detM1 = i(ak — jb) + h(jc — al) + g{bl — kc) 27 5. N A L E Z E N Í P R Ů S E Č Í K U Když známe všechny determinanty, můžeme podle rovnice 5.12 vypočítat hodnoty pro /3 a 7. P o k u d hodnoty splňují podmínky 5.5, průsečík paprsku a trojúhelníku existuje a vzdálenost průsečíku o d počátku paprsku t může být spočítána podle rovnice 5.12. 5.2.4 Implementace Algoritmus 5.1 Nalezení průsečíku - trojúhelník 1. při inicializaci nového trojúhelníku 2. předpočítej proměnné a až g z matice M 3. v metodě nalezení průsečíku 4. vypočti zbylé proměnné matice M 5. vypočti pomocné proměnné pro výpočet determinantů 6. spočti determinant matice M 7. spočti beta a ukonči výpočet, p o k u d nesplní podmínku 8. spočti gama a ukonči výpočet, p o k u d nesplní podmínku 9. P o k u d je beta + gama < 1 10. spočti vzdálenost t Koeficienty a, b, c, d, e, f, g jsou závislé jen n a vrcholech trojúhelníku. Můžeme je tedy předpočítat při vytváření trojúhelníků a snížit tak výpočetní náročnost samotného nalezení průsečíku. Zbylé koeficienty se dopočítají v těle metody pro nalezení průsečíku podle rovnice 5.9. Při pohledu n a rovnici 5.15 si všimneme, že rovnice pro výpočet detM a detMp jsou si podobné. Stejně tak si jsou podobné i rovnice M 7 a detMt. Vytvořením pomocných proměnných 28 5. N A L E Z E N Í P R Ů S E Č Í K U betal = (ei — hf), gamal = (ak — jb), betďl = (gf — di), gamďl = [je — al), (5.16) beta3 = (dh — eg), gama3 = {bl — ke), opět snížíme počet potřebných výpočtů. Dosazením pomocných proměnných získáme vzorce 5.17 pro výpočet souřadnic beta a gama. detM = a* betal + b * beta2 + c * beta3 Jjg^Q j*betal-\-k*beta2-\-l*beta3 ^ 17) i*go-'mO'í+h*gama2+g*gama3 gama — d e t A Po spočtení první ze souřadnic, beta, testujeme podmínku 5.5. Pok u d není splněna můžeme předčasně ukončit výpočet, protože průsečík paprsku a trojúhelníku neexistuje. P o k u d splněna je, vypočítáme souřadnici gama a opět testujeme podmínku 5.5. P o k u d jsou všechny podmínky splněny, průsečík P leží v trojúhelníku a zbývá nám jen vypočítat jeho vzdálenost o d počátku paprsku podle rovnice 5.18. / * gamal + e * gamal + d * gama3 (5.18)detM 5.2.5 Výpočet normály Normála je důležitá pro výpočet barvy při použití Phongova osvětlujícího modelu, stejně jako při tvorbě odražených paprsků. N o r mála trojúhelníku s vrcholy (A, B, C) se vypočítá v době jeho vytváření, jako vektorový součin d v o u vektorů představujících jeho strany. Díky uspořádání vrcholů trojúhelníku můžeme tedy normálu vypočítat podle vztahu 5.19. n = (B - A) * (C - A) (5.19) 29 5. N A L E Z E N Í P R Ů S E Č Í K U 5.3 Koule Molekula zobrazená v kapitole 4.4 se skládá z 399 atomů. Při použitém V d W zobrazení jsou tyto atomy vykresleny jako koule. K jejich vytvoření bychom mohli použít síť sestavenou z trojúhelníků popsaných v předchozí kapitole. Tato síť b y však jen aproximovala tvar koule a na její vytvoření by bylo potřeba mnoho trojúhelníků. Lepším řešením je implementovat kouli jako jedno se základních těles, s vlastními metodami pro nalezení průsečíku a výpočet normály. Tím snížíme časovou i paměťovou náročnost algoritmu a zvýšíme kvalitu zobrazení. 5.3.1 Definice koule Koule je jedno ze základních matematických těles. Je definovaná jako množina bodů s konstantní vzdáleností o d jednoho bodu, středu. Rovnice 5.20 popisuje matematické vyjádření koule s poloměrem r. x2 + y2 + z2 = r2 (5.20) Prvním řešením pro nalezení průsečíku koule s paprskem, co nás většinou napadne, je t z v algebraické řešení. Je založeno na dosazení rovnice paprsku p = o + td do rovnice koule 5.20. Tím získáme kvadratickou rovnici, jenž má dvě řešení v případě, že paprsek kouli protíná, jedno, p o k u d je paprsek tečnou koule a žádné, p o k u d paprsek kouli míjí. Více o tomto řešení může být nalezeno v [8]. Nevýhodou algebraického řešení je náročnost výpočtu kvadratické rovnice. Existuje však tzv. geometrické řešení, které je o poznání rychlejší [5]. 5.3.2 Geometrické řešení Zatímco algebraické řešení určuje polohu průsečíku numerickým výpočtem rovnice 5.20, geometrické řešení využívá vyjádření paprsku, polohy koule a jejího poloměru pomocí vektorů v prostoru. Porovnáním jejích směrů, velikostí a poloh je možné zjistit, zda paprsek kouli mine nebo ne a určit polohu průsečíku v případě, že takový průsečík existuje. 30 5. N A L E Z E N Í P R Ů S E Č Í K U Vlastní výpočet se skládá ze tří podmínek a, p o k u d jsou všechny splněny, výpočtu polohy průsečíku. V každé z podmínek testujeme, zda má paprsek šanci trefit kouli. P o k u d nemá, průsečík neexistuje a výpočet může být ukončen bez dalších nadbytečných výpočtů. Pok u d testovaná podmínka splněna je, hodnoty získané při jejím výpočtu se použijí jako hodnoty pro výpočet podmínky další. Díky tomu nejsou žádné z výpočtů prováděny zbytečně a je tím ušetřen čas potřebný pro nalezení průsečíku. První podmínka oc2 > r 2 (5.21) Cílem první podmínky je zjistit, zda paprsek začíná uvnitř koule nebo m i m o ni. P o k u d začíná uvnitř koule, vše, co by bylo zobrazeno, by byla tato koule. Tomu se chceme vyhnout a proto tyto koule ne­ zobrazujeme. Obrázek 5.2: První podmínka. Výpočet vektoru oc. N a obrázku 5.2 je zobrazena koule a dva paprsky R\ a R2, s počátky v bodech 0\ a O2. Porovnáním velikostí vektorů oc\ a 0C2 (origin to center) s poloměrem koule r zjistíme, který z paprsků začíná vně koule (i?i), a který uvnitř (i?2 ). Vektor oc sestrojíme podle rovnice 5.22. D r u h o u mocninu jeho velikosti oc2 , vypočteme pomocí skalárního součinu v rovnici 5.23. 31 5. N A L E Z E N Í P R Ů S E Č Í K U 0 C = C - 0 (5.22) oc2 = oc.oc (5.23) Podmínka 5.21 říká, že p o k u d je druhá mocnina velikosti vektoru oc větší, než druhá mocnina poloměru koule, paprsek začíná m i m o kouli a výpočet může pokračovat d u h o u podmínkou. Druhá podmínka tom > 0 (5.24) Jakmile víme, že paprsek neleží uvnitř koule, je třeba zjistit, z d a směřuje směrem ke kouli, nebo o d ní. P o k u d směřuje o d ní, je jasné, že ji nikdy netrefí a výpočet průsečíku se tedy může ukončit. Obrázek 5.3: Druhá podmínka. Výpočet í, To, zda paprsek směřuje ke kouli nebo ne, zjistíme pomocí vzdálenosti počátku paprsku o d b o d u M , ve kterém je paprsek nejblíže středu koule. Výpočet této vzdálenosti ( č o m ) je ukázán na obrázku 5.3. Vzdálenost (čo m ) vypočítáme podle vztahu 5.25, jako skalární součin vektoru oc, vypočteném v rovnici 5.22, a směru paprsku d. tom = oc.d (5.25) 32 5. N A L E Z E N Í P R Ů S E Č Í K U N a obrázku 5.3 je opět znázorněna koule a d v a paprsky. Vzdálenost tomi je kladná a paprsek R1 tedy směřuje ke kouli, kterou má šanci protnout. Oproti t o m u paprsek R2 směřuje o d koule a vzdálenost tom2 vyjde záporná a m y tedy můžeme ukončit nalezení průsečíku s tímto paprskem, protože ten kouli jistě neprotne. Třetí podmínka fpm > 0 (5.26) D o p o s u d víme, že počátek paprsku neleží v kouli, a že paprsek směřuje ke kouli. Poslední co zbývá zjistit je, z d a paprsek kouli trefí nebo ne. To je dosaženo spočtením hodnoty t2 m, která udává vzdálenost průsečíku P o d b o d u M . P o k u d je t2 pm < 0, průsečík paprsku a koule neexistuje. Výpočet tpm má d v a kroky. V prvním, zobrazeném n a obrázku 5.4, vypočteme vzdálenost b o d u M o d středu koule (l). Hodnota / je vypočítána pomocí Pythagorovy věty, podle vztahu 5.27. I2 = oc2 - ťom (5.27) 5. N A L E Z E N Í P R Ů S E Č Í K U tm = r 2 - l 2 (5.28) Obrázek 5.5: Třetí podmínka. Výpočet rv P o k u d je splněna podmínka 5.26, paprsek kouli zasáhne. Poté zbývá už jen vypočítat hodnotu t, udávající vzdálenost nalezeného průsečíku o d počátku paprsku. To se provede odečtením hodnoty tpm o d tom/ podle rovnice 5.29. 5.3.3 Výpočet normály Normála povrchu koule n v bodě P odpovídá vektoru sestrojenému ze středu koule C, skrz b o d P. Správnou velikost vektoru zajistíme jeho normalizováním pomocí poloměru koule r. P — C n = (5.30) r 5.3.4 Implementace Implementace nalezení průsečíku s koulí je vcelku přímočará. Postupně kontrolujeme všechny podmínky. P o k u d některá z nich není 34 5. N A L E Z E N Í P R Ů S E Č Í K U splněna, přerušíme výpočet a oznámíme, že průsečík nebyl nalezen. Protože hodnoty oc a oc2 , použité při výpočtech ve všech podmínkách, nejsou závislé na parametrech paprsku, můžeme je předpočítat při inicializaci koulí. A dosáhnout tak snížení výpočetní náročnosti. 5.4 Válec Válec lze definovat dvěma body, A a B, ležícími ve středech jeho podstav. Výška válce je dána vzdáleností těchto bodů. Šířka je dána poloměrem jeho podstav r. O s u válce představuje vektor c. Jeho směr je z b o d u A do b o d u B. B-A (5.31) 5.4.1 Nalezení průsečíku Pro jakýkoliv b o d P, který leží na povrchu válce, platí rovnice 5.32. w 0 řC B řC B c C A Obrázek 5.6: Válec definovaný body A aB (5.32) Vektor v, zobrazený na obrázku 5.7, směřuje o d b o d u A do průsečíku P a vypočte se jako: P-A (5.33) Vektor w odpovídá komponentě vektoru v, rovnoběžné s osou válce c. Vektor w se vypočítá podle vztahu uvedeného v rovnici 5.34. w v.c — ( c. c (5.34) Operátor . představuje skalární součin vektoru. Výsledkem podílu v.c/c.c je tedy skalár, kterým poté násobíme každou ze složek vektoru c. Rozdíl vektorů v aw znázorněný na obrázku 5.7 je kolmý na osu c a prochází bodem P. Velikost tohoto vektoru představuje vzdálenost bodu P o d osy válce. Všechny body ležící na povrchu válce musí mít tuto vzdálenost rovnu r. 35 5. N A L E Z E N Í P R Ů S E Č Í K U Protože skalární součin vektoru se sebou samým se rovná druhé mocnině velikosti tohoto vektoru, v rovnici použijeme r2 a díky tomu nebudeme muset počítat s odmocninami. Tím dosáhneme snížení náročnosti výpočtu. C B •C B • r_ ^ n v-w • c v \ 1A Obrázek 5.7: Nalezení průsečíku s válcem. Pro nalezení průsečíku dosadíme d o rovnice 5.32 z a b o d P rovnici paprsku P = O + td. Nyní v = O + td — A. Substitucí m = O — A dostáváme nový vztah pro v. v = m + td (5.35) Posloupností matematických úprav rovnice 5.32 dostáváme nov o u rovnici 5.36 s neznámou t. ,, , (d.c)2 , 9 . , (d.c)(m.c). (m.c)2 , ., ^s (d.d--—-)t2 + 2(m.d--— -)t + m.m-- - - r 2 = 0 (5.36) c.c c.c c.c A b y c h o m nemuseli počítat s dělením, vynásobíme celou rovnici 5.32 členem c.c. Dostaneme upravenou rovnici ((c.c)(d.d) - (d.c)2 )t2 + 2((c.c)(m.d) - (d.c)(m.c))t+ (5.37) (c.c)((m.m) — r2 ) — (m.c)2 = 0 Získáme tak kvadratickou rovnici pro neznámou t, ve tvaru at2 + 2bt + c = 0, kde jednotlivé členy jsou, 36 5. N A L E Z E N Í P R Ů S E Č Í K U a = (c.c)(d.ď) — (d.c)2 b = (c.c)(m.d) — (d.c)(m.c) c = (c.c)((m.m) — r2 ) — (m.c)2 (5.38) Vzdálenost bližšího z průsečíků t se vypočítá podle vztahu 5.39. t - 2 6 - ^ / ( 2 6 ) 2 - 4 0 0 2o (5.39) Diskriminant rovnice 5.39 (D = (26)2 — 4ac) určí kolik existuje průsečíků paprsku a válce. P o k u d je D < 0, paprsek válec míjí. Pro D = 0 existuje jeden průsečík, paprsek je tečnou válce. A nakonec D > 0 dává d v a průsečíky. Menší z hodnot t udává vzdálenost k bližšímu z těchto průsečíků. 0 < t < c2 AM Výše uvedené výpočty vedly k nalezení průsečíku s nekonečným válcem. M y však chceme, aby b y l válec ohraničen rovinami procházejícími body A a B. N a obrázku 5.8 je zobrazen řez válcem ohraničeným body A a B. Paprsek protíná válec v bodě P. Pro zjištění, z d a b o d P leží v mezích válce, využijeme stejného postupu jako v druhé podmínce, při hledání průsečíku paprsku s koulí, pomocí geometrického řešení, v kapitole 5.3.2. Tentokrát vypočítáme proměnnou ÍAM, která udává druhou mocninu vzdálenosti b o d u M, ležícího na ose válce c nejblíže k průsečíku P, o d dolní hranice válce A. H o d nota ÍAM se vypočítá jako skalární součin vektorů ap, spojujícího spodní mez válce A s průsečíkem P, a osou válce c. B i L C M \ > ap\ l A Obrázek 5.8: Výpočet vzdálenosti t AM ap.c (5.40) 37 5. N A L E Z E N Í P R Ů S E Č Í K U P o k u d je t\M < 0, paprsek prochází p o d dolní hranicí válce A a válec tedy míjí. P o k u d je t\M > c2 , paprsek prochází nad horní mezí válce B a válec opět míjí. 5.4.2 Výpočet normály Normála povrchu válce se sestrojí jako vektor z b o d u M, skrz průsečík P. Polohu b o d u M vypočítáme pomocí vztahu 5.41. M = A + tAMc (5.41) 5.5 Osově orientovaný kvádr V implementovaném raytraceru neslouží osově orientovaný kvádr jako zobrazitelný objekt. Není totiž vhodný pro vykreslení žádného typu zobrazení molekul. Najde však využití jako obalové těleso, při tvorbě urychlující datové struktury, popsané v kapitole 8. Osově orientovaný kvádr zobrazený na obrázku 5.9 lze definovat dvěma body. Jeho minimálním (min) a maximálním (max) rohem. 5.5.1 Nalezení průsečíku Metoda nalezení průsečíku paprsku s kvádrem popsaná v [11] rozkládá problém nalezení průsečíku s kvádrem na dvoudimenzionální problém nalezení průsečíků s obdélníky. Tyto obdélníky představují průměty kvádru do rovin rovnoběžných s osami souřadného sys­ tému. Body min a max definují množinu rovin rovnoběžných s osami souřadného systému. N a obrázku 5.9 lze vidět, že v každé z těchto rovin leží průměty jednotlivých stran kvádru. Průměty jsou ohraničené přímkami procházejícími body min a max. Nalezením průsečíků s těmito přímkami v daných rovinách budeme schopni určit polohu průsečíku paprsku s kvádrem v prostoru. Obecná přímka je definována vztahem 5.42, kde parametr m představuje sklon přímky a B bod, ve kterém přímka protíná osu y. 38 5. N A L E Z E N Í P R Ů S E Č Í K U y = mx + B (5.42) Přímky definující jednotlivé roviny můžeme vyjádřit pomocí rovnice 5.42. Například přímka procházející bodem min, rovnoběžná s osou y, lze popsat jako: y = minx (5.43) Pro nalezení průsečíku paprsku s touto přímkou dosadíme do rovnice 5.43 rovnici paprsku pro jeho složku x. Dostaneme vztah: 0X + tdx = minx Výpočet vzdálenosti průsečíku paprsku s přímkou y = minx je uveden v rovnici 5.44. minx — Ox tmmx = ; (5.44) dx Obdobně můžeme vypočítat vzdálenosti s průsečíky dalších pěti přímek, definovaných body min a max. Výpočet všech vzdáleností je uveden v rovnicích 5.45 39 5. N A L E Z E N Í P R Ů S E Č Í K U tmin.'X minv—0 tmax X maxx — Ox dx maXy—Oytminy tminz tmax. (5.45) tmaxz Vypočtené vzdálenosti t použijeme k tomu, abychom zjistili, zda paprsek protíná kvádr. N a obrázku 5.9 je znázorněna situace nalezení průsečíku s přímkami v rovině xy. Levý obrázek 5.10a ukazuje situaci, k d y paprsek průmět strany kvádru míjí. N a pravém obrázku 5.10b je zobrazen paprsek procházející stejným průmětem. N a levém obrázku 5.10a paprsek mine obdélník ve d v o u případech. V prvním z nich protne přímku maxy dříve než přímku minx. Ve druhém případě protne nejprve přímku maxx a až poté přímku miriy. To, kterou přímku protne paprsek nejdříve, zjistíme porovnáním vzdáleností t odpovídajícím těmto rovinám. Paprsek míjí obdélník v rovině, p o k u d platí podmínka 5.46. tmaxv < tminx V tmaxx < tmin (5.46) (a) Paprsky míjí kvádr (b) Paprsek prochází kvádrem Obrázek 5.10: Nalezení průsečíku s obdélníkem. 40 5. N A L E Z E N Í P R Ů S E Č Í K U P o k u d podmínka 5.46 není splněna, znamená to, že musí existovat alespoň jeden průsečík paprsku s průmětem kvádru. N a obrázku 5.10b je zobrazen paprsek protínající přímky minx, miriy, maxx a maxy ve vzdálenostech o d počátku paprsku tminx, tminy, tmaxx a tmaxy. Vzdálenost bližšího z průsečíků tl, ve které paprsek vstupuje do obdélníku, odpovídá větší ze vzdáleností tminx a tminy. tl = max(tminx,tminy) (5.47) Naopak vzdálenost tl, ve které paprsek opouští obdélník, odpovídá menší ze vzdáleností tmaxx a tmaxy. tl — min(taxx,tmaxy) (5.48) Nyní jsme nalezli průsečíky paprsku s obdélníkem v rovině xy. Pro rozšíření do trojrozměrného prostoru přidáme podmínku testující vzdálenosti průsečíků tminz a tmaxz, vypočtené v rovnici 5.45, vůči hodnotám tl a tl, které jsme vypočetli v předchozích rovnicích. tmaxz [8] SHIRLEY, P., M O R L E Y , K. Realistic Ray Tracing. A K Peters Ltd., 2003, ISBN 1-56881-198-5. [9] S U F F E R N , K . Ray Tracing from the Fround Up. A K Peters Ltd., 2007, ISBN 978-56881-272-4. [10] W H I T T E D , T. A n Improved Illumination M o d e l for Shaded Display. Commun. ACM, 1980. [11] W I L L I A M S , A . , B A R R U S , S., M O R L E Y , R. K , aj. A n Efficient and Robust Ray-box Intersection Algorithm. 2005. 60 9. ZÁVĚR [12] ŽÁRA, J., BENEŠ, B., S O C H O R , J., aj. Moderní počítačová grafika. Computer Press, 2004, ISBN 80-251-0454-0. 61 Seznam obrázků 2.1 Molekula ledw, zobrazena pomocí V d W 5 2.2 Molekula ledw, zobrazena pomocí tyčinek a koulí. 6 2.3 Molekula ledw, zobrazena pomocí tyčinek. 7 2.4 Povrch molekuly l e d w 8 2.5 Tunel zobrazený pomocí středové linie. 8 2.6 Tunel zobrazený pomocí koulí, představující jeho šířku v daném bodě středové linie 9 2.7 Detailní povrch tunelu 9 3.1 Výpočet barvy pixelu (x,y) 12 3.2 Obecná struktura raytraceru 13 3.3 Struktura raytraceru - třídy a metody 14 4.1 Poloha b o d u na přímce v závislosti na parametru t 15 4.2 Popis parametrů kamery. 16 4.3 Vztah mezi obrazovkou a plátnem 17 4.4 Výpočet směru primárního paprsku 18 4.5 Molekula l e d w renderována jedním paprskem na pixel 20 4.6 Supersampling - ukázka 21 4.7 V z o r k y 22 4.8 Molekula l e d w renderována 16 paprsky na pixel 23 5.1 Barycentrické souřadnice trojúhelníku A B C 25 5.2 První podmínka. Výpočet vektoru oc. 31 5.3 Druhá podmínka. Výpočet tom. 32 5.4 Třetí podmínka. Výpočet d2 . 33 5.5 Třetí podmínka. Výpočet t2 m. 34 5.6 Válec definovaný body A a B 35 5.7 Nalezení průsečíku s válcem. 36 5.8 Výpočet vzdálenosti ÍAM 37 5.9 Kvádr definovaný rohy min max 39 5.10 Nalezení průsečíku s obdélníkem. 40 6.1 Závislost intenzity difúzního osvětlení na velikosti úhlu a 45 6.2 Spekulární složka. 46 6.3 Zobrazení stínových paprsků. 47 62 9. ZÁVĚR 7.1 Výpočet vzdáleností Atx a Atx pomocí podobnosti trojúhelníků 50 7.2 Výpočet počáteční vzdálenosti t 53 7.3 Procházení paprsku mřížkou. 54 7A Ukázka zobrazení dat z mřížky. Jednotlivé pixely nesou hodnotu o součtu dat z mřížky na dráze paprsku. 54 8.1 Obalové těleso koule. 55 8.2 Vložení koule do mřížky. 57 8.3 Určení, z d a průsečík leží ve zpracovávané buňce. 58 10.1 V d W zobrazení molekuly lcqw, rederované v rozlišení 1920x1080 pixelů, 16 paprsků skrz pixel 64 10.2 Povrch molekuly lcqw, rederovaný v rozlišení 1920x1080 pixelů, 16 paprsků skrz pixel 65 63 10 Příloha 10. P Ř Í L O H A