PŘÍRODOVĚDECKÁ FAKULTA UNIVERZITY PALACKÉHO KATEDRA INFORMATIKY
DIPLOMOVÁ PRÁCE
Optimalizace vykreslování voxelové grafiky
2013
Bc. Pavel Procházka
Anotace Voxelová grafika je zobecněním rasterové grafiky do třetí dimenze, představuje tak alternativu k častěji používané polygonové grafice. Voxelová grafika přináší výhody v podobě teorericky vysoké obrazové kvality, avšak za cenu vysoké paměťové a časové náročnosti. Existují však dobré komprimační metody, které dokážou značně zredukovat velikost běžných modelů a čas nutný pro jejich vykreslení. K tomuto účelu se nejčastěji používá metoda dělení prostoru, známá jako oktalový strom – octree a jeho varianty. Text srovnává několik metod z hlediska výkonu i obrazové kvality za použití softwarového vykreslování. Dalším výstupem je řádně napsaná programová knihovna VoXen, která umožňuje vykreslování různých voxelových formátů s použitím jednoduchého nasvětlování.
Poděkování patří zejména mému vedoucímu práce panu Mgr. Eduardu Bartlovi, Ph.D., který mně aktivně a profesionálně pomáhal při řešení problémů, s výběrem vhodné literatury a s opatřením dat. Dále děkuji pracovníkům nemocnice U svaté Anny v Brně za pořízení a poskytnutí dat z magnetické rezonance, jmenovitě zejména paní Janě Nahodilové. Konečně také děkuji své rodině za podporu, která mi byla projevována.
Obsah 1. Úvod
8
2. Polygonová grafika 2.1. Metoda rasterizace . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Metody sledování paprsku . . . . . . . . . . . . . . . . . . . . . .
10 10 12
3. Voxelová grafika 3.1. Rasterizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. DDA a Bresenhamův algoritmus . . . . . . . . . . . . . . . . . . . 3.3. Raytracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 13 13 15
4. Způsoby reprezentace voxelových modelů 4.1. Naivní – raw kódování . . . . . . . . . . . . 4.2. Run-length kódování a .vxl formát . . . . . 4.3. Oktalový strom – octree . . . . . . . . . . . 4.4. Operace v octree . . . . . . . . . . . . . . . 4.4.1. Test optimality a optimalizace octree 4.4.2. Vyplňování oblasti . . . . . . . . . . 4.4.3. Odebrání prvku . . . . . . . . . . . . 4.4.4. Rychlá kompilace a voxelový blitting 4.5. Techniky adresace a procházení octree . . . 4.5.1. Algoritmus kd-restart . . . . . . . . . 4.5.2. Algoritmus kd-backtrack . . . . . . . 4.5.3. Algoritmus kd-shortstack . . . . . . . 4.5.4. Neighbor search . . . . . . . . . . . . 4.5.5. Procházení octree podél přímky . . . 4.6. N 3 strom . . . . . . . . . . . . . . . . . . .
19 19 20 21 22 22 23 23 24 24 25 26 26 26 26 28
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
5. Vlastní optimalizační úvahy – adaptive octree
28
6. Knihovna VoXen 6.1. Architektura . . . . . . . . . . . . . . 6.2. Systém souřadnic . . . . . . . . . . . 6.3. Elementární datové typy . . . . . . . 6.4. Objektový systém VoXen . . . . . . . 6.5. Rozhraní obrazového povrchu . . . . 6.6. Objekt ovladače a proces inicializace 6.7. Matice transformace . . . . . . . . . 6.8. Rozhraní obecného modelu . . . . . . 6.9. Kamera a generátor paprsků . . . . . 6.10. Implementace raw formátu . . . . . . 6.11. Implementace octree formátu . . . .
32 32 32 32 34 34 35 36 36 38 38 39
4
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
6.11.1. Sestavení octree . . . . . . . . . . . . . . . . . 6.11.2. Cube clipping algoritmus – vlastní myšlenky . 6.11.3. Algoritmy procházení octree . . . . . . . . . . 6.12. Nasvětlování a stínování . . . . . . . . . . . . . . . . 6.13. Poznámky k optimalizacím softwarového vykreslování 6.13.1. Akcelerující techniky . . . . . . . . . . . . . . 6.13.2. Vícevláknové vykonávání . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
40 40 42 43 43 44 46
7. Dosažené výsledky 7.1. Sada testů knihovny VoXen . . . . . . . . 7.2. Testovací aplikace . . . . . . . . . . . . . . 7.3. Konverzní utilita . . . . . . . . . . . . . . 7.4. Poznámky ke kompilaci a ke kompatibilitě 7.5. Testování, spuštění a známé chyby . . . . 7.6. Dokumentace knihovny VoXen . . . . . . . 7.7. Licence a kopírování . . . . . . . . . . . . 7.8. Obrazové podklady . . . . . . . . . . . . . 7.9. Srovnání . . . . . . . . . . . . . . . . . . . 7.9.1. Srovnání paměťové náročnosti . . . 7.9.2. Srovnání časové náročnosti . . . . . 7.9.3. Srovnání obrazové kvality . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
47 47 48 51 52 53 54 54 54 56 56 57 59
8. Diskuze 8.1. Srovnání s jinými projekty . . . . . . . . . 8.2. Možnosti využití dosažených výsledků . . . 8.3. Možnosti dalšího rozšíření knihovny VoXen 8.4. Omezení knihovny . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
61 61 61 62 63
Závěr
64
Conclusions
65
Reference
66
A. Obsah přiloženého DVD
67
5
Seznam obrázků 1. 2. 3. 4. 5. 6.
Princip raytracingu (pohled z boku). . . . . . . . . . . . . . . . . Organizace souřadnic v knihovně VoXen. . . . . . . . . . . . . . . Mapování indexů na potomky octree. . . . . . . . . . . . . . . . . Obrázek získaný z magnetické rezonance. . . . . . . . . . . . . . . Vykreslený model hlavy. . . . . . . . . . . . . . . . . . . . . . . . Model z testovací aplikace knihovny VOXLAP (od Kena Silvermana). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7. Pohled na mapu ze hry Voxelstein. . . . . . . . . . . . . . . . . . 8. Jednoduchý testovací model. . . . . . . . . . . . . . . . . . . . . . 9. Rozdíl v kvalitě raycastingu mezi syrovým modelem (velvo) a octree modelem (vpravo). . . . . . . . . . . . . . . . . . . . . . . 10. Obrazový výstup ze článku GigaVoxels. . . . . . . . . . . . . . . . 11. Obrazový výstup z práce Kristofa Römische. . . . . . . . . . . . .
6
16 33 40 55 56 57 58 59 60 60 62
Seznam tabulek 1. 2. 3. 4. 5. 6.
Tabulka srování velikosti souborů podle modelů. . . . . . . . . . . Tabulka kompresního poměru. . . . . . . . . . . . . . . . . . . . . Tabulka srování počtu všech uzlů octree s počtem listových uzlů. . Tabulka srování průměrných FPS v softwarové implementaci vzhledem k různým algoritmům a pouze s ambientním osvětlením. Tabulka průměrných hodnot FPS s jedním dynamickým světlem. . Tabulka nejhorších a nejlepších časových výsledků (v milisekundách), údaje jsou bez dynamických světel. . . . . . . . . . . . . .
7
57 58 59 61 61 62
1.
Úvod
Existuje několik hlavních způsobů reprezentace třídimenzionálního světa, jak ho známe, ovšem jen málokterá reprezentace je tak blízko skutečnosti jako právě reprezentace voxelová. Z toho plynou četné výhody v oblasti zpracování výstupů z výpočetní tomografie, ve strojírenských oborech a také v počítačových hrách. Ve všech těchto oblastech jsou zvýšené nároky na výkon, konkrétně je velmi vhodné, aby se výstup zobrazoval v reálném čase. Na první pohled se může zdát, že zobecnění rastrové grafiky do 3D je ta nejpřímější a také nejvíce duchaprostá varianta. Ihned je patrné, že jakékoliv operace nad voxelovými modely budou extrémně náročné, nehledě na spotřebu paměti. S pomocí jistých optimalizačních technik se však lze dostat na velmi přijatelnou časovou i paměťovou složitost a zajistit tak solidní rychlost vykreslování. Výhodou voxelového vykreslování pak jistě může být velmi vysoká kvalita výstupu a skutečná hloubka, ale také velký potenciál v podobě neomezené úrovně detailů. Nevýhoda voxelové grafiky, zejména oproti polygonové, spočívá v manipulaci s objekty, především jde o animace a afinní transformace. Obecně lze říci, že nevýhody a výhody jsou úplně stejné jako u analogických reprezentací ve 2D. Voxelové modely lze reprezentovat různými způsoby. Nejsnadněji lze voxelový model reprezentovat trojrozměrnou maticí, což je ale současně nejvíce naivní způsob reprezentace, neboť paměťová náročnost zjevně přímo roste s třetí mocninou. Tento formát může být výstupem některých přístrojů pro snímání trojrozměrných objektů. Analogicky k rastrové grafice, lze i voxelové modely komprimovat metodou run-length, která je založena na přeskakování delších úseků stejné barvy. Zcela jiný přístup představuje reprezentace pomocí oktalového stromu, ten umožňuje efektivní procházení, ale za jistých okolností i nižší využití paměti. Jeho optimalizovanou variantou je pak N 3 strom, který dosahuje vyššího výkonu nebo lepšího kompresního poměru v závislosti na volbě programátora. Otázkou však zůstává, jakým způsobem vykreslovat modely. V případě voxelových formátu je nejefektivnější použít raycasting, případně raytracing, přímá rasterizace by vyžadovala zcela jinou reprezentaci. I když i přímá rasterizace se ve výjimečných případech používá. Nejdůležitějším výstupem mé práce je obecná knihovna VoXen, která implementuje některé modely a metody vykreslování. A to jak pomocí softwarového vykreslování, tak výhledově i za použití GPGPU výpočtů na platformě OpenCL. Současně je nad touto knihovnou napsán program pro testování funkcionality ale také výkonu, dále sada testů a konverzní utilita. Knihovna je napsána s ohledem na vysoký požadovaný výkon v jazyce C99, jako zobrazovací knihovna je použita SDL, případně lze dopsat vlastní backend nebo využít přímou rasterizaci do syrového pole pomocí NULLDrv ovladače. Zejména v softwarové části knihovny je použito mnoho zajímavých optimalizačních technik včetně využití vícevláknového vykonávání. První část práce se zabývá teorií a metodami zobrazování grafiky obecně. Ať 8
už je to metoda založená na rasterizaci nebo metoda trasování paprsku. Jsou zde shrnuty výhody a nevýhody obou přístupů s ohledem na rychlost, spotřebu paměti, ale také obrazovou kvalitu výstupů. Čtenář se zde dozví základní pojmy, které jsou nezbytné zejména pro pochopení metody trasování paprsku a pojmy související s 2D rastrovou grafikou. Následují kapitoly, které se zabývají metodami ukládání voxelových dat a operacemi nad takovými modely, zde je vždy uvedena zejména časová i paměťová složitost a porovnání jejich reálného výkonu vzhledem k typickým vstupním datům. Následně shrnuji nevýhody metod dělení prostoru a v hrubých obrysech navrhuji vlastní optimalizační techniku (adaptive octree), která nezhorší paměťovou složitost a zlepší složitost časovou. Dál se text zabývá implementací knihovny VoXen, což je jedna ze ztěžejních částí mé práce. Zde je pouze přehledově zmíněno API knihovny a její pseudo-objektový systém, hlavní důraz je kladen zejména na optimalizační detaily, které tato knihovna obsahuje. Nad knihovnou VoXen jsou pak napsány tři doprovodné programy, které mohou sloužit jako rozsáhlejší tutoriálové příklady, zejména konverzní utilita má však také praktické využití. Závěrem je uvedeno shrnutí výkonu jednotlivých modelů při softwarovém vykreslování a při GPGPU vykreslování. Dále uvádím srovnání kvality obrazových výstupů a doplňuji možnosti využití knihovny, jakož i její případná omezení. Nakonec je v diskuzi má implementace srovnána s jinými podobnými prácemi a výsledky. Pro orientaci v tomto textu je nezbytná alespoň orientační znalost rastrové grafiky na úrovni porozumění pojmu pixel, barevná hloubka, barvová paleta, aliasing, mipmapping apod.
9
2.
Polygonová grafika
Počítačová trojrozměrná grafika se začala široce studovat v 60. letech v Utahu, kde byly položeny základy dnešních běžně používaných metod pro rychlé zobrazování polygonové grafiky. Jako jsou metody vykreslování přímek, kružnic nebo vyplňování mnohoúhelníků. Základním objektem polygonové grafiky je mnohoúhelník, jehož všechny vrcholy leží v jedné rovině. V počítačové grafice se však nejčastěji používá trojúhelník, případně čtyřúhelník. Důvodem je hlavně harwarová podpora. Polygonová grafika je někdy označována jako povrchová (hraniční) reprezentace. Neumožňuje totiž zachytit vnitřek objektů – narozdíl od voxelové grafiky. K promítání na obrazový výstup se nejčastěji používá tzv. perspektivní zkreslení, což je jev, který intuitivně velmi dobře známe. Perspektivní zkreslení, neformálně řečeno, vyjeví vzdálenější objekty menší, než objekty bližší. Existuje několik formalizmů, které tento jev popisují, text se jedním podrobně zabývá v kapitole o metodě trasování paprsků na voxelových modelech.
2.1.
Metoda rasterizace
Jedná se v současnosti o nejpoužívanější a současně hardwarově podporovanou metodu zobrazování 3D polygonové grafiky, tudíž může být velmi rychlá. Příkladem softwarových knihoven, které ji využívají je OpenGL a DirectX. Principielně se tento přístup skládá z několika problémů, které se jako celek nazývají grafická pipeline. Hlavními úkoly grafické pipeline jsou tyto po sobě jdoucí úkoly [4]: • transformace, • ořezání, • scan konverze. V prvním kroku se vypočítá perspektivní zkreslení všech viditelných polygonů – jejich vrcholů. Poté dojde k ořezání polygonů, které zasahují mimo obrazovku – mimo tzv. ořezávací pyramidu. Zde je třeba řešit patrně výpočetně nejnáročnější problém, tím je určení viditelných polygonů – tzv. visibility problem. Hledáme tedy ty polygony, které jsou pro pozorovatele viditelné. Nejjednodušším, ale také současně nejpomalejším algoritmem je tzv. malířův algoritmus, který kreslí polygony odzadu, vzhledem k pozorovateli (kameře). Malířův algoritmus má zjevně lineární časovou složitost vzhledem k počtu polygonů, na počátku je ovšem ještě třeba setřídit objekty podle vzdálenosti od kamery, což lze docílit pomocí známých třídících algoritmů, které pracují nejlépe v čase O(nlog(n)). Jisté vylepšení co do počtu překreslených pixelů, nikoli však navštívených polygonů, je tzv. Zbuffer. Z-buffer je jednoduché obrazové pole, které odpovídá velikosti obrazovky a nese informaci o vzdálenosti posledního vykresleného pixelu, na začátku je vyplněno hodnotami ∞. Při pokusu o vykreslení polygonu se navíc testuje, zda je 10
právě vykreslovaný pixel blíže pozorovateli. Pokud není, nic se nevykreslí. Použitím Z-bufferu se navíc eliminuje nutnost setřídění polygonů podle vzdálenosti vzhledem ke kameře, což je podstatný přínos, pokud se kamera pohybuje. K rychlejšímu nalezení nejbližších polygonů se používá například BSP-strom, případně jiné strukutry dělící prostor (kd-stromy, R-stromy, octree). K tomu, abychom polygon vykreslili, navíc potřebujeme algoritmus na vyplňování polygonů barvou, případně texturou – obrázkem. Těmito algoritmy se text podrobněji nezabývá. Implementací předchozích algoritmů vykreslíme pouze nepřirozeně vypadající modely vlivem chybějícího osvětlení. Rozlišujeme několik základních technik nasvětlování. Nejpřirozenější je zřejmě tzv. flat shading – ploché stínování. Intenzita stínu je pak vypočtena na základě odchylky normálového vektoru polygonu od světelného paprsku. Čím větší odchylka je, tím je polygon temnější. Výsledkem plochého stínování jsou jasně patrné hrany polygonů, tento nedostatek částečně řeší Goraudovo stínování nebo relativně výpočetně náročné Phongovo stínování. Tyto metody osvětlování však řeší pouze osvětlení, ale nikoli stíny vržené jinými objekty, které jsou k reálnému pocitu z 3D scény nezbytné. První metodou je metoda přímého nasvětlování – direct illumination, která počítá s paprsky jdoucí přímo ze zdroje světla. Druhá, výpočetně náročná metoda, je metoda globálního nastvětlování – global illumination, která počítá s odrazy paprsků. Detaily konkrétních implementací nejsou pro pochopení textu ztěžejní. Další technikou ještě zlepšující vizuální dojem se nazývá radiozita. Radiozita pracuje s myšlenkou vyzařování světla ve směru od nasvícených objektů do prostoru. Toto je intuitivně dobře známý jev, který je dobře patrný zejména u matných předmětů. Moderní grafické karty jsou již osazeny plnohodnotnými výpočetními jednotkami – GPU, které spadají do klasifikace SIMD. Grafické karty umožňují díky svému obecnému návrhu programovat další grafické efekty s využitím masivní paralelizace. Současné grafické karty spadající do nejvyššího segmentu jsou osazeny řádově 103 výpočetními jádry. V počítačové grafice se často objevuje pojem shader. Shader je krátký program, který se paralelně spouští na GPU a umožňuje tak uživatelsky programovat grafickou pipeline. Podle určení se rozlišují různé typy shaderů. Na úrovni polygonového modelu jsou to vertex shadery, což jsou jednoduché programy transformující všechny body scény – například simulace vln na vodě. Vylepšením vertex shaderů jsou geometry shadery, které navíc umí přidávat nebo odebírat polygony ze scény, často se tak vytváří třeba travnatý povrch, nebo naopak mohou redukovat počet vzdálenějších polygonů. Pixel (fragment) shadery naopak transformují jednotlivé výstupní body výsledného obrazu. Lze jimi docílit například efektu šumu, ale často se pomocí pixel shaderů implementuje velká část rasterizačního procesu, včetně efektů jako je třeba bump mapping (dojem hloubky díky zvláštnímu nanesení textury). Pomocí fragment shaderů lze také implementovat raytracing [9]. Aktuální etapou vývoje grafických karet je cesta k univerzální programovatelnosti. V současnosti existují tři softwarová prostředí, která to až na jistá omezení 11
umožňují. Jedná se o CUDA, DirectCompute a OpenCL. CUDA i DirectCompute jsou prostředí vyvíjená firmou NVIDIA resp. Microsoft, což je omezující. Naopak OpenCL je prostředí nezávislé na výrobci, každý výrobce může vyvíjet svoji implementaci standardu OpenCL pro své zařízení. Díky tomu může být OpenCL provozováno na grafických kartách, výpočetních kartách i na běžných procesorech. Hlavní omezení těchto technologií je fakt, že nelze definovat rekurzivní funkce a nelze pracovat s ukazately na funkce (to již neplatí pro technologii CUDA provozovanou na grafických kartách řady Fermi).
2.2.
Metody sledování paprsku
Implementace metody sledování paprsku je z algoritmického hlediska oproti rasterizaci výrazně elegantnější, nicméně málo výkonná. Princip sledování paprsku – ray tracing vychází z fyzikálního principu šíření světla, jen je tento proces obrácený. Paprsek se totiž nevysílá ze zdrojů světla, nýbrž z kamery. Tím se docílí výrazné úspory počtu paprsků při zachování stejné kvality. Program implementující ray tracing vysílá paprsek z ohniska kamery přes obrazovku dále do scény [4]. Jakmile paprsek narazí na povrch nějakého polygonu, buď skončí – pak se jedná o ray casting, anebo vyšle další paprsky ke každému zdroji světla, případně může raytracing implementovat další optické zákony, jako je zákon lomu nebo odrazu pro různé materiály. Velkou výhodou je také možnost efektivní paralelizace a to i na grafických kartách.
3.
Voxelová grafika
Pixel si obvykle představujeme jako čtverec vyplněný stejnou barvou nebo jako bod na monitoru [4]. Formálněji se na něj lze dívat jako na nejmenší adresovatelný prvek rastru. V případě přirozených obrazů (fotografií) se na něj díváme jako na jistou diskrétní interpretaci jinak spojitého obrazu[11]. Velmi podobně se díváme i na pojem voxel, pouze s tím rozdílem, že představuje trojrozměrnou krychli v prostoru. Cílem vykreslování by měla být schopnost pracovat v reálném čase, to jest přibližně 25 snímků za sekundu (FPS). Pro vykreslování voxelové grafiky je třeba navrhnout interpretaci, která bude mít co možná nejnižší nároky na paměťové zdroje v řídkých modelech, nebo lépe ve všech modelech. Pojem řídkého modelu bohužel žádný dostupný zdroj formálně nedefinuje, jeho interpretace tak vychází z intuice. Řídké modely splňují tu vlastnost, že obsahují rozsáhlé prázdné oblasti nebo rozsáhlé oblasti stejné barvy. Současně však musí být možné rychle adresovat voxely modelu a maximálně využít řídké povahy modelů k rychlému přeskakování prázdných oblastí. Navíc by model měl umožňovat předcházet aliasingu obrazu, aniž by to mělo nežádoucí dopad na výkon. Formálně lze dvojdimenzionální obraz považovat za zobrazení I : R × R → h0, 1i, na výpočetních strojích je však možné reprezentovat pouze diskrétní mno12
žiny. Tudíž se prakticky obraz uvažuje jako zobrazení I : Zw × Zh → Z256 3 , který může být získán diskretizací ze spojité předlohy (například fotoaparátem). Analogicky můžeme zavést i trojrozměrný obraz R × R × R → h0, 1i, respektive Zw × Zh × Zd → Z256 3 pro nějaká w, d, h ∈ N, kde w je šířka obrazu, h je výška a d je hloubka. Pixel je pak výraz I(x, y) pro jeden bod hx, yi, obdobně i voxel. Poznamenejme, že množina Z256 3 představuje prostor všech true-color barev tak, jak se v počítačové rastrové grafice běžně používají.
3.1.
Rasterizace
Jednou z možností, jak vykreslit voxely, je možnost reprezentovat je jako jednotkové krychle sestavené z polygonů. A poté je zobrazit nějakým běžným rasterizačním softwarem typu OpenGL. To je však nemožné pro velké objekty. Reprezentujeme-li voxely pomocí trojúhelníků, dostáváme 12 trojúhelníků na voxel. Což i pro malé modely (512 × 512 × 512) činí řádově 106 trojúhelníků a to je pro rasterizační metody příliš. Tento způsob se používá v případech, pokud chceme zobrazovat voxelová data extrémně přiblížená, jako je tomu například ve hře Minecraft https://minecraft.net/, v tomto případě se navíc na povrch voxelů nanáší textura.
3.2.
DDA a Bresenhamův algoritmus
DDA (Digital differential analyzer) je scan-conversion algoritmus pro vykreslení přímky do mřížky. Jinými slovy se jedná o lineární interpolaci na jistém intervalu. DDA princip je klíčový pro metody sledování paprsku ve voxelových modelech, což jsou třírozměrné mřížky. Vstupem DDA algoritmu jsou dva body. Počáteční bod A = hx1 , y1 i a koncový bod B = hxn , ym i. Pro každé xi , které splňuje x1 < xi <= xn spočítáme hodnoty xi , yi takto xi = xi−1 + 1s yi = yi−1 + s, kde hodnota s vzniká výrazem s=
ym − y1 . xn − x1
Hodnoty xi a yi reprezentují pozice pixelů. Na první pohled nelze pomocí takto zapsané posloupnosti vykreslit svislou přímku, protože nelze dělit nulou. To lze vyřešit buď předefinováním výrazu s=
ym − y1 0
na s = 1 a předefinováním výrazu 1s na hodnotu 0. Anebo v dané implementaci nejprve porovnat hodnoty ym − y1 a xn − x1 . Řídící osou se pak stane ta osa, 13
ve které nabývají tyto výrazy ym − y1 a xn − x1 vyšší hodnotu. V případě, že to bude osa y zvolíme výraz xn − x1 s= . ym − y1 Samotný algoritmus však nepočítá obě hodnoty, ale pouze jednu. To, kterou hodnotu bude algoritmus počítat, se rozhodne na základě hodnoty s. V případě, že platí s <= 1 nastavíme krok dx = 1 a xi budeme počítat xi = xi−1 + dx a yi = yi−1 + s. V případě s > 1 klademe dy = 1, yi = yi−1 + dy a xi = xi−1 + 1s . V konkrétní implementaci je pak třeba ještě řešit problém se záporným sklonem, který lze elegantně vyřešit například prohozením koncové a počáteční souřadnice nebo výpočtem znaménka. DDA <- function( A = <x1 , y1> , B = <x2 , y2> ){ dx = x2 - x1; dy = y2 - y1; if( dx != 0 && (s = dy/dx) <= 1.0 ){ dx = (dx > 0.0 ? 1.0 : -1.0); y = y1 for( x = x1 ; x <= x2 ; x += dx ){ draw_point( x , y ); y += s; } } else { dy = (dy > 0.0 ? 1.0 : -1.0); s = dx/dy; for( y = y1 ; y <= y2 ; y += dy ){ draw_point( x , y ); x += s; } } } Algoritmus DDA je zejména vhodný pro harwarovou implementaci, lze totiž dobře optimalizovat pro paralelní vykonávání, lze jej ale také implementovat pomocí celočíselné aritmetiky a techniky známé jako fixed point aritmetika. Z algoritmu DDA vychází Bresenhamův algoritmus, který je v současnosti široce implementován v grafických knihovnách a na grafických čipech pro svoji jednoduchost a eleganci. Bresenhamův algoritmus lze rovněž implementovat pomocí celočíselné aritmetiky, ale obvykleji se využívá floating point implementace. Principem floating point verze je spočítání sklonu v obou směrech a následné přičítání sklonu k příslušným složkám. 14
Bresenham <- function( A = <x1 , y1> , B = <x2 , y2> ){ x = x1; y = y1; xlen = x1 - x2; ylen = y1 - y2; len = abs((abs(ylen) > abs(xlen) ? ylen : xlen)); stepx = xlen / len; stepy = ylen / len; for( i = 0 ; i < len ; i++ ){ draw_point( x , y ); x -= stepx; y -= stepy; } }
3.3.
Raytracing
Metody trasování paprsku jsou mnohem přímočařejší, než rasterizační metody. Navíc do značné míry odpovídají skutečnému fyzikálnímu modelu šíření světla, což má také pozitivní vliv na vzhled výsledných scén. Někdy se dokonce metody trasování paprsku označují (nesprávně) jako fotorealistické zobrazování. Sledování paprsku vychází z fyzikálního pojetí světla. Respektive vychází z představy světla jako částice, zanedbává však vlnovou podstatu světla. Tím pádem však nemůžeme tuto metodu považovat za fotorealistickou, neboť v současné fyzice existuje jistý rozpor mezi částicovým pojetím světla a vlnovým pojetím. Některé jevy totiž fyzika umí vysvětlit pouze pomocí částicové teorie (fotoelektrický jev), jiné zase pouze pomocí vlnové teorie (Youngův dvojštěrbinový experiment). Na světlo jako na částice se dívali již starověcí řečtí myslitelé pocházející z Pythagorejské školy. Skutečný formalizmus pohledu na světlo jako částici přinesl až Albert Einstein a Max Planck v první polovině 20. století. Z pohledu částicové teorie je světlo pouze diskrétní tok fotonů, které jsou emitovány oscilujícími ionty (zdroj světla) a šíří se po přímce, zanedbáme-li jev zakřivení světla vlivem gravitace. Samotný obrazový vjem je pak ta část fotonů, která dorazí do oka pozorovatele nebo do kamery. Fotonů, které ovšem dorazí až k pozorovateli je jen zanedbatelný zlomek z celkového počtu fotonů ve scéně. Princip sledování paprsku tento jev obrací a trasuje „fotonyÿ od pozorovatele směrem do scény a následně ke zdrojům světla tak, jak to ukazuje obrázek 1. Z algoritmického hlediska je zapotřebí mechanizmus zvaný generátor paprsků, který bude vysílat paprsky z kamery do scény. Nejčastějším generátorem paprsků je princip vycházející z perspektivního promítání, jehož hlavní myšlenkou je podobnost trojúhelníků. Jeden vrchol trojúhelníka tvoří ohnisko kamery a zbylé dva jsou počáteční a koncový bod obrazovky buď na ose x nebo y. Vzdálenost d 15
Zdroj svtla Projekní rovina Objekt scény
Ohnisko
Obrázek 1. Princip raytracingu (pohled z boku). ohniska od roviny obrazovky se obvykle klade d=
xmax − xmin . 2
Poloha ohniska se pak klade f=
ymax − ymin d, ,0 . 2
Obvyklé hodnoty xmin a ymin jsou 0. Poznamenejme, že hodnota xmin , xmax je minimální x souřadnice, respektive maximální x souřadnice obrazovky, stejná konvence platí pro osu y, navíc uvažujeme souřadný systém, kde osa z ubíhá dále od pozorovatele (konvence levé ruky). Samotný generátor paprsků perspektivního promítání je zobrazení Rg : N × N → R × R × R tak, že Rg(x, y) = hx, y, di − f . Někdy je výhodné generované paprsky normalizovat Rg(x, y) . |Rg(x, y)|
Případně se k nim přičítá vektor 12 , 12 , 0 , aby se zajistilo, že procházejí středem pixelu. Generátor paprsků je však obecný princip, tudíž lze toto zobrazení definovat i jiným způsobem. Například jím lze docílit efektu rybího oka, případně lze jiným způsobem deformovat obraz (efekt rychlé jízdy). Nejjednodušším příkladem promítání je pak pravoúhlé promítání, tehdy bude zobrazení Rg(x, y) = h0, 0, 1i, ale ohnisko pak nebude jedno a bude ležet na rovině kamery. Výstupy generátoru paprsků – trojrozměrné vektory je pak nutné ještě vynásobit transformační maticí, kterou může definovat uživatel. Obvykle však slouží k rotaci kamery. Pak následuje trasování takto získaných vektorů z počátečního bodu kamery, který může být libovolně umístěn do scény. Algoritmus trasování paprsku lze obecně shrnout do následujícího pseudo-kódu, který byl inspirován zdrojem [4]. draw_camera <- function( camera ){ 16
for( y <- 0 ; y <- y_max ; y++ ){ for( x <- 0 ; x <- x_max ; x++ ){ ray <- Rg( x , y ); ray <- ray * camera.matrix; color <- do_ray( camera.position , ray )[1]; set_pixel( x , y , color ); } } } do_ray <- function( pos = <x , y , z> , ray = <xr , yr , zr> ){ min_distance <- INFINITY; intersection <- NIL; out_object <- NIL; /* nelezení nejbližšího průniku s objektem */ foreach( object in scene ){ intersection <- object.intersect( pos , ray ); if( intersection ){ dist <- vector_length( intersection - pos ); if( min_distance > dist ){ min_distance <- dist; out_object <- object; } } } if( !object ){ return
; } if( object.type == LIGHT ){ return ; } /* uživatelsky definované sekundární paprsky */ secondary_rays ; } Funkce draw_camera vysílá pro všechny body kamery paprsky do scény a před tím je transformuje maticí. Výsledek trasovací funkce do_ray pak zapíše do framebufferu. Funkce do_ray pak provádí samotné trasování. Nejprve nalezne průsečík s nejvýše jedním objektem (v případě voxelové grafiky je každý objekt krychle) a paprskem tak, aby průsečík ležel nejblíže kameře ze všech jiných průsečíků. V případě, že průsečík nenalezne žádný, tato funkce vrátí smluvenou barvu FILLING_COLOR, obvykle je to černá. Poznamenejme, že každý objekt musí nést funkci intersect, která vrací průsečík paprsku a daného objektu. Objekt může být například krychle, polygon, koule a další, pokud se nejedná o voxelovou grafiku. V případě, že takto nalezený objekt je typu LIGHT, vrací se ihned jeho barva. V opačném případě se vyšlou sekundární paprsky dále směrem do scény a jejich výsledky se nakonec sečtou po složkách s barvou objektu. Sekundární paprsky jsou generovány v pseudo-kódu uživatelskou funkcí emit_secondary_rays, která může například implementovat ohyb nebo odraz světla v závislosti na materiálu. Nakonec se vyšlou paprsky směrem ke zdrojům světla, pokud ke světlu dorazí smíchá se barva světla s barvou objektu. Výsledná barva se pak vrací do vykreslování kamery. Často se navíc ještě používá tzv. ambientní (rozptýlené světlo), které se smíchá se všemi barvami, které vznikly průsečíkem s nějakým objektem, tehdy však nikdy nedojde k vykreslení zcela černého stínu. V konkrétní implementaci by jistě také bylo vhodné opatřit každý paprsek váhou, která by měla vliv při mixování. Nejnáročnější částí algoritmu je zjevně první smyčka, která prochází všemi objekty ve scéně a provádí časově náročné výpočty průniku. K minimalizaci počtu procházených objektů a s tím spojených výpočtů průniků se používají techniky založené na nelineárních datových strukturách (R-tree, kd-tree, octree) nebo na metodě obalování objektů tzv. bounding boxy. Což jsou jednodušší modely než ty, které obalují. Tímto se docílí lacinějších testů průniků, zejména při použití metody tzv. slabů [8]. V případě voxelové grafiky stačí implementovat testování průsečíků s jednotkovými krychlemi, které jsou obvykle zarovnány do 18 = address( root , bounding_box( root ) , ray_position ); if( color != OPACITY ){ return color; } return ray_traverse( root , box_out_point( ray_position , ray_vect , bbox ) , ray_vect ); } Funkce address z pseudokódu může odpovídat některému z předchozích uvedených algoritmů nebo obecně to může být libovolná funkce, která implementuje zobrazení I. Funkce bounding_box vrací bounding box uzlu. Funkce box_out_point vypočítá výstupní bod paprsku z krychle. Funkce ray_traverse lze pochopitelně velice snadno přepsat do nerekurzivní formy. Toto procházení lze samozřejmě použít i pro implementaci dynamického světla, tehdy se paprsek po dopadu na povrch trasuje ke světlu. Limitní podmínka úspěchu je pak střet s bounding boxem, ve kterém se nachází zdroj světla nebo opuštění modelu. Tento algoritmus je výhodný pro paralelizaci. Lze totiž celý implementovat iterativním způsobem a nepotřebuje tudíž práci se zásobníkem. Práce se zásobníkem je zejména na grafických kartách vysoce neefektivní. Naopak u běžných výpočetních procesorů (CPU) je práce se zásobníkem velmi běžná a dobře optimalizovaná činnost. Zde je naopak vhodnější použít rekurzivní algoritmus, který pracuje zhora a podle článku [5] má časovou složitost O(M ), kde M je počet listových uzlů kd-stromu. V případě octree existuje analogie rekurzivního procházení kd-stromu v podobě výsledku nazvaného HERO (A Hardware Enhancer for Ray-tracing Octrees) [1], což je vysoce optimalizovaný způsob procházení octree, který pracuje rekurzivně. Časová složitost je však stále O(N logN ), ovšem nalezení uzlu restartu je lacinější vzhledem k algoritmům založeným na principu kd-shortstack, ještě o málo výhodnější je metoda udržování sousedních uzlů, avšak za cenu vysoké paměťové náročnosti. Zde si totiž explicitně udržujeme uzly restartu. 27 , box = ) { c = (d - z) / rz; out_pt[3]; out_pt[X] = x + (rx*c); out_pt[Y] = y + (ry*c); out_pt[Z] = d; return <(out_pt[X] < ux) && (out_pt[X] >= lx) && (out_pt[Y] < uy) && (out_pt[Y] >= ly) , out_pt> } Funkce pro jednotlivé osy jsou v knihovně generovány makrem pro zamezení redundance kódu a pro maximalizaci propustnosti. Samotná funkce pro nalezení výstupního průsečíku z kvádru je už velmi jednoduchá. Stačí projít permutaci setřídění vektoru paprsku a kontrolovat, dokud nebude výsledek pravdivý alespoň pro jednu stěnu nebo nepravdivý pro všechny stěny. Poznamenejme skutečnost, že stačí testovat pouze tři stěny podle znaménka, protože nemá smysl testovat stěnu, ke které paprsek ani nesměřuje. Obdobně se implementuje i funkce pro hledání vstupního bodu do kvádru. Dalším zlepšením by mohlo být cachování výsledků dělení nebo jejich předpočítání pro každý paprsek. 6.11.3.
