Voxelova´ grafika Software
´ ı voxelove´ grafiky Optimalizace vykreslovan´ ´ Pavel Prochazka KMI
24. listopadu 2014
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Voxelova´ grafika
I
I I
I
ˇ ı rasterove´ grafiky do 3D (zobecnen´ ˇ ı pojmu pixel Zobecnen´ na pojem voxel). Konkurence“ k povrchove´ (polygonove´ reprezentaci). ” V´yhody: skuteˇcna´ hloubka (schopnost zachytit vnitˇrek ´ fraktaly), ´ objektu), zaj´ımave´ vlastnosti (rekurzivn´ı materialy, destruktibiln´ı. Nev´yhody: sˇ patna´ manipulace s objekty (bone animace).
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Vyuˇzit´ı – prakticka´ motivace I I I I
´ u˚ ve stroj´ırenstv´ı. CT, NMR skeny, studium material 3D tisk. Hry. Lze pouˇz´ıt pro Global Illumination – next gen grafika bl´ızˇ ´ıc´ı ´ em ´ cˇ ase. se kvalitou raytracingu vykreslovana´ v realn
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Reprezentace obrazu
Spojity´ 2D obraz ´ ´ Obrazek velikosti (domena) w × h, w, h ∈ R je zobrazen´ı dvojic ´ do barevneho prostoru (rozsahu). Zobrazen´ı, kde se kaˇzde´ ´ pozici v obrazku pˇriˇrazuje barva. I : [1, w] × [1, h] → [0, 1] , kde [1, w] ⊆ R, [1, h] ⊆ R, [0, 1] ⊆ R
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ı 2D obraz Diskretn´ ˇ nen´ı spojit´y – fyzika zna´ diskretn´ ´ ı Ve skuteˇcnosti, ani svet ´ ´ cˇ astice i nejmenˇs´ı velikost – tzv. Planckova delka. Id : [1, w] × [1, h] → [0, cmax ] [1, w] ⊆ N, [1, h] ⊆ N, [0, cmax ] ⊆ N
Pixel – picture element ´ ı obraz. Pixel p je prvek diskretn´ ´ ıho 2D Necht’ Id je diskretn´ ˇ a´ dvojice tvaru hhx, y i , ci. obrazu, cˇ ili p ∈ Id . Je to tedy nejak
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ı 3D obraz Diskretn´ ´ ı 2D obraz muˇ ´ Diskretn´ ˚ zeme intuitivneˇ zobecnit do libovolneho prostoru (tedy i do 3D) I : [1, w] × [1, h] × [1, d] → [0, cmax ] [1, w] ⊆ N, [1, h] ⊆ N, [1, d] ⊆ N, [0, cmax ] ⊆ N
Voxel – volumetric element ´ Voxel je to same´ co pixel, pouze ma´ jinou domenu.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Problemy I I I I
ˇ ’ova´ sloˇzitost O(N 3 ), kde N = max({w, h, d}). Pamet ´ em ´ cˇ ase vubec? Jak to vykreslovat a jde to v realn ˚ ´ Bone animace - prakticky nemoˇzne. ´ (aˇz na velikost). Rasterove´ animace - nen´ı probem
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ zeme zredukovat pamet ˇ ’ovou sloˇzitost? Dokaˇ
Tvrzen´ı: ´ ı 3D I velikosti w × h × d obraz ma´ pamet ˇ ’ovou sloˇzitost Diskretn´ 3 O(N ), kde N = max({w, h, d}). ´ ´ Obraz I je zobrazen´ı, tedy podmnoˇzina kartezsk eho souˇcinu. V ˇ ´ ´ techto zobrazen´ıch nelze obecneˇ naj´ıt zˇ adnou zavislost, ´ protoˇze muˇ e´ obrazy. Z ˚ zeme za obraz povaˇzovat take´ nahodn teorie informace v´ıme, zˇ e takove´ obrazy nelze efektivneˇ komprimovat. ´ jak to vypada, ´ ´ Poznamka: Nen´ı to ale aˇz tak pesimisticke, ˇ ´ ´ nekter e´ obrazy zavislost vykazuj´ı – napˇr´ıklad pˇrirozene´ obrazky.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Reprezentace voxelove´ grafiky
I
3D matic´ı, stejneˇ jako ve 2D.
I
Run-length.
I
SVO (Sparse Voxel Octree) – oktalov´y strom.
I
N 3 tree.
I
Adaptive octree – vlastn´ı invence.
I
kd-stromy, spatial hashing.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ´ ı Maticova´ reprezentace – raw kodov an´
I
Prakticky stejne´ jako .bmp. ˇ e´ pole delky ´ Jednorozmern w · h · d · Bpp bitu, ˚ Bpp znamena´ poˇcet bitu˚ na pixel.
I
Adresace voxelu <x,y,z> pˇr´ıstupem do pole V pomoc´ı
I
V[w*h*z*Bpp + w*y*Bpp + x*Bpp] ˇ Casov a´ sloˇzitost je tedy O(1).
I
ˇ je pˇresneˇ whd · Bpp ∈ O(N 3 ), Ω(N 3 ). Spotˇreba pameti
I
Na 32-bitov´ych stroj´ıch nelze pracovat s maticov´ymi ˇ s´ımi neˇz 10243 , coˇz je malo. ´ modely vetˇ ´ ı pro reprezentaci nahodn´ ´ Idealn´ ych a mal´ych modelu. ˚
I
I
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ´ ı Run-length kodov an´ I
I I I
´ Analogicke´ k run-length ve 2D. Zakladem je 2D obraz ´ (1024 × 1024), kter´y ma´ ukazatele na run-length kodovan e´ sloupce. ´ ´ V praxi implementovano .vxl formatem, muˇ ˚ ze m´ıt ´ zapornou komprimaci. ´ na Build enginu od Kena Pouˇzite´ v dosov´ych hrach Silvermana (Blood, Shadow Warrior, Duke Nukem 3D). ´ Engine VOXLAP, Command & Conquer serie.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
SVO – Sparse Voxel Octree I
ˇ ı prostoru pomoc´ı stromu. Metoda delen´
I
Kaˇzd´y uzel octree pˇredstavuje krychli, ma´ 8 potomku˚ ˇ eˇ del´ ˇ ı prostor (pokud nen´ı listov´y), potomci rovnomern rodiˇce na 8 podkrychl´ı. ´ eˇ kdyˇz Lze optimalizovat tak, zˇ e sjednot´ıme potomky prav ´ maj´ı stejnou barvu nebo jsou prazdn e´ – velka´ uspora ´ ˇ v ˇr´ıdk´ych modelech. pameti
I
I
I
Adresaˇcn´ı metoda kd-shortstack a jej´ı varianty (kd-backtrack, kd-restart). ˇ ’ je ale stale ´ O(N 3 ), octree vˇsak muˇ Pamet ˚ ze vykazovat ´ zapornou komprimaci.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
SVO – Sparse Voxel Octree I
´ O(N 3 )? Oznaˇc´ıme urovn Proˇc ma´ octree sloˇzitost stale eˇ ´ octree l ∈ {0, 1, 2, . . .}, pln´y octree pak ma´ v kaˇzde´ urovni ´ nl = 8l nodu, ˚ celkov´y poˇcet uzlu˚ octree v´ysˇ ky h = log2 N je pak tedy. S=
h X l=0
I
8l =
1 − 8log2 N+1 8N 3 − 1 = ∈ O(N 3 ) 1−8 7
´ Adresace listoveho uzlu ma´ cˇ asovou sloˇzitost O(log2 N), ˇ zne´ modely. coˇz b´yva´ male´ cˇ ´ıslo pro beˇ
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Sestaven´ı oktaloveho stromu optimal_p <- function( node ){ if( each( node->childs , function( child ){ return child == NULL; } ) ) return ’EMPTY; if( each( node->childs , function( child ){ return (child->leaf_p && (child->color == node->childs[0]->color)); })) { return ’SAME; }
return ’FALSE; }
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
optimize <- function( node ){ for( i = 0 ; i < 8 ; i++ ){ optimize( node->childs[i] ); }
switch( optimal_p( node ) ){ case ’SAME: node->color = node->childs[0]->color; memset( node->childs , NULL ); return node; break;
case ’EMPTY: return NULL; break;
default: return node; } }
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
N 3 strom
I
ˇ ı octree, potomku˚ muˇ Zobecnen´ ˚ ze b´yt N 3 pro libovolne´ ´ ı pˇr´ıpad, kdy N = 2. N ∈ N , octree je specialn´ Hluboke´ listove´ oblasti se nahrazuj´ı raw modelem velikosti ´ M 3 opatˇrene´ mipmapou – rychlejˇs´ı prochazen´ ı. ˇ ’ je ale stale ´ O(N 3 ), podobn´y argument jako u octree. Pamet
I
´ Adresace listoveho uzlu ma´ cˇ asovou sloˇzitost O(logN).
I
Hodnoty M a N se vol´ı pˇri kompilaci (pˇrevodu na N 3 strom). ´ ´ ı zavis´ ´ ı na volbeˇ konstant M a N na Efektivita kodov an´ ´ zaˇcatku.
I
I
I
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Adaptive octree I
´ invence. Vlastn´ı (zat´ım nepublikovana)
I
Kompromis mezi raw modely a octree modely (pˇreb´ıra´ pouze dobre´ vlastnosti obou).
I
´ an´ ´ ı na disk, neum´ı Reprezenentace vhodna´ pro uklad mipmapping. ´ i pro rychl´y rendering. Velk´y potencial
I I I I
ˇ ´ Zabranuje zaporn e´ komprimaci. ´ Adresace listoveho uzlu ma´ cˇ asovou sloˇzitost O(log2 N). Ve skuteˇcnosti je adresace v praxi ale vˇzdy lepˇs´ı neˇz u ˇ y faktor (v pˇr´ıpadeˇ realn ´ eho ´ octree o nejak´ renderingu to ´ nen´ı zanedbatelne).
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Adaptive octree – detaily I I I
I I I I
Uzly mohou b´yt podobneˇ jako v pˇr´ıpadeˇ N 3 stromu raw modely, ale bez mipmapy. ´ pˇr´ıpadeˇ jsou uzly beˇ ˇ zne´ octree uzly. V opaˇcnem K degenraci octree podstromu na raw model dojde v ˇ zˇ e jeho celkova´ velikost pˇrekroˇc´ı velikost raw pˇr´ıpade, modelu, pak uˇz totiˇz nen´ı octree v´yhodn´y z hlediska ˇ (a ani cˇ asu – jak uvid´ıme pozdeji). ˇ pameti ´ V extremn´ ım pˇr´ıpadeˇ (pln´y model s nezkomprimovateln´ymi voxely) zdegeneruje na raw model. ´ ˇ v Zamezen´ı zaporn e´ komprimaci a znaˇcna´ uspora pameti ´ ˇ zn´ych ˇr´ıdk´ych modelech. beˇ ˇ s´ı alesponˇ o nejak´ ˇ y Adresace je oproti octree v´yhodnejˇ ´ pevneˇ dan´y faktor zavisl´ y na implmentaci. Ve skuteˇcnosti znamena´ adaptive octree usporu v´ıce neˇz ´ ˇ oproti octree 50% zabrane´ pameti ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ı Adaptive octree – detaily pokraˇcovan´ optimize <- function( node ){ for( i = 0 ; i < 8 ; i++ ){ optimize( node->childs[i] ); } switch( optimal_p( node ) ){ case ’SAME: node->color = node->childs[0]->color; memset( node->childs , NULL ); return node; break; case ’EMPTY: return NULL; break; ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ı2 Adaptive octree – detaily pokraˇcovan´
default: break; } if( octree_memory_sz( node ) > node.bbox.wˆ3*sizeof(ARGB32_color) ) return octree_to_raw( node ); return node; }
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Adaptive octree – vlastnosti ˇ ’ove´ sloˇzitosti mezi octree a adaptive ˇ Veta: Vztah pamet octree ˇ ’ zabrana´ modelem reprezentovan´ym pomoc´ı adaptive Pamet ´ z modelu, kter´y je octree je menˇs´ı nebo rovna temuˇ ´ octree. reprezentovan
ˇ ’ove´ sloˇzitosti mezi raw kodov ´ ´ ım a ˇ Veta: Vztah pamet an´ adaptive octree ˇ ˇ e´ k ∈ N, mnoˇzstv´ı Mejme obraz velikosti 2k × 2k × 2k pro nejak ˇ modelem kodovan´ ´ zabrane´ pameti ym pomoc´ı adaptive octree ´ ´ ´ je menˇs´ı roven tomu samemu modelu kodovan emu pomoc´ı raw metody. ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ´ ı voxeloveho ´ Dusledek: ˚ O kodov an´ obrazu ˇ Mejme obraz I. AOCTREE(I) ≤ OCTREE(I), RAW (I) Zobrazen´ı AOCTREE, OCTREE, RAW pˇriˇrazuj´ı obrazu poˇcet ˇ pˇri danem ´ kodov ´ ´ ı. zabran´ych bajtu˚ v pameti an´
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ a´ data Adaptive octree – realn ´ Nazev testu simple voxlap myhead myhead2
ˇ obrazu Rozmery 1024 × 1024 × 1024 1024 × 1024 × 256 512 × 512 × 512 512 × 512 × 512
´ Raw format 3GB 1GB 512MB 512GB
´ Octree format 4KB 44MB 71MB 64MB
Adaptive octree 4KB 22MB 23MB 20MB
´ ı velikosti souboru˚ podle modelu. Tabulka : Tabulka srovan´ ˚
´ Nazev testu simple voxlap myhead myhead2
Octree/raw
Adaptive octree/raw
0,000000020 0,042965651 0,138260350 0,123718247
0,000000020 0,021837585 0,044120207 0,039568335
ˇ octree variant vuˇ Tabulka : Tabulka kompresn´ıho pomeru ˚ ci raw modelu.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ı voxelove´ grafiky Metody vykreslovan´ I
I
I
I
I
I
Rasterizace – reprezentace voxelu˚ pomoc´ı krychl´ı – 12 polygonu˚ na krychli. ´ ı hˇre Minecraft (vhodna´ Rasterizace se pouˇz´ıva´ v popularn´ ´ pro extremn eˇ pˇribl´ızˇ ene´ modely). Raycasting – poprve´ interaktivn´ı ve hˇre Wolfenstein 3D (1991), vrˇzen´ı paprsku pˇres vykreslovac´ı surface. ˇ y raycasting, poˇc´ıta´ se svetly, ˇ Raytracing – zobecnen´ ´ ´ cne. ´ extremn eˇ naroˇ ˇ ı raytracingu pro octree a Conetracing – vhodne´ zobecnen´ jeho varianty. ´ em ´ cˇ ase Voxelove´ modely lze vykreslovat v realn (GigaVoxels – GPGPU, VoXen – i686). ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Raytracing na SVO I I I I
Algoritmus vykreslen´ı pˇr´ımky – podobne´ jako DDA, Bresenhamuv ˚ algoritmus. Algoritmus mus´ı poˇc´ıtat s t´ım, zˇ e voxely mohou b´yt nestejneˇ velke´ ´ ´ an´ ´ ı pˇr´ımky krychl´ı – Potˇreba rychleho algoritmu oˇrezav vlastn´ı invence. Adresace stoj´ı O(log2 N), v nejhorˇs´ım pˇr´ıpadeˇ stoj´ı vykreslen´ı pˇr´ımky O(N) kroku, ˚ tud´ızˇ celkova´ sloˇzitost je O(Nlog2 N).
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Raycasting, Raytracing Raycasting ´ ı princip sˇ ´ıˇren´ı svetla ˇ do Metoda, ktera´ obrac´ı fyzikaln´ ´ oka/senzoru a trasuje pozpatku fotony, ktere´ mohou dopadnout ´ fotony, kter´ych je vetˇ ˇ sina. Pro na s´ıtnici. T´ım filtruje zbyteˇcne“ ” kaˇzd´y obrazov´y pixel je potˇreba vypoˇc´ıtat jeho barvu. Jakmile ˇ eˇ sˇ ´ıˇren´y foton dopadne na povrch materialu, ´ pˇriˇrad´ı se zpetn ´ tato barva pˇr´ısluˇsnemu pixelu.
Raytracing ´ ke To same´ jako Raycasting, ale pˇri dopadu se pokraˇcuje dale ˇ ˇ ´ ´ svetlum ˚ – lze tak doc´ılit efektu nasvetlovan´ı a st´ınovan´ı.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Optimalizaˇcn´ı aspekty prochazen´ ı nehomogenn´ı mˇr´ızˇ ky I
I
I
I
ˇ s´ı V´ypoˇcet pruseˇ ˚ c´ıku˚ krychle s pˇr´ımkou je nejkritiˇctejˇ v´ypoˇcet pˇri raytracingu voxelov´ych dat. ´ ı modelu na osy Prvn´ı trik“ spoˇc´ıva´ v zarovnan´ ” ´ ´ ´ souˇradnicoveho systemu, t´ım padem nen´ı nutne´ nic ˇ je malo, ´ nav´ıc transformovat (kromeˇ paprsku, ˚ ale tech postaˇc´ı jedna transformaˇcn´ı matice. ´ ´ ı, problem ´ se redukuje pouze na 2 Kdyˇz mame zarovnan´ ´ ˇ ı si muˇ nasoben´ ı (delen´ ˚ zeme pˇredpoˇc´ıtat dopˇredu) a test, ˇ eˇ krychle. zda bod leˇz´ı na sten ˇ podle pravdepodobnosti, ˇ Nav´ıc muˇ ˚ zeme setˇr´ıdit steny ´ ıc´ı sloˇzky ktera´ bude nejsp´ısˇ e zasaˇzena podle pˇrevladaj´ vektoru. ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ ´ ´ pˇr´ımky Prochazen´ ı oktaloveho stromu podel I
I
I
I
ˇ spoˇc´ıtat pruseˇ Staˇc´ı umet ˚ c´ık paprsku s v´ystupn´ı rovinou krychle ˇ adresovat voxel v oktalovem ´ stromeˇ Potom staˇc´ı umet (kd-restart) Nab´ız´ı se optimalizace, protoˇze k sousedn´ım voxelum ˚ ´ (listum) oktaloveho stromu cˇ asto vede podobna´ cesta, ˚ ˇ sinou je v´yhodnejˇ ˇ s´ı si cestu pamatovat a pouˇz´ıvat ji vetˇ (neplat´ı vˇzdy) ´ Tato metoda se jmenuje kd-backtrack, je v´yhodna´ zejmena ´ v pˇr´ıpadeˇ grafick´ych karet, kde je extremn eˇ drah´y pˇr´ıstup ˇ do sd´ılene´ pameti
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Adresace voxelu – kd-restart kd_restart <- function( node , cube = <x,y,z,w> , inpoint ){ if( node->leaf_p ){ return <node , cube>; }
midpoint <- < cube.x + cube.w/2 , cube.y + cube.w/2 , cube.z + cube.w/2 >; path <- < inpoint.x >= midpoint.x , inpoint.y >= midpoint.y , inpoint.z >= midpoint.z >; return kd_restart(
GetChild( path.x , path.y , path.z ), < cube.x + path.x*(w/2) , cube.y + path.y*(w/2) , cube.x + path.z*(w/2) > , inpoint );
}
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Prochazen´ ı homogenn´ı (ekvidistantn´ı) mˇr´ızˇ ky function line(x0, x1, y0, y1) int deltax := x1 - x0 int deltay := y1 - y0 real error := 0 real deltaerr := abs (deltay / deltax) int y := y0 for x from x0 to x1 plot(x,y) error := error + deltaerr if error >= 0.5 then y := y + 1 error := error - 1.0
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Knihovna VoXen
I
Knihovna pro raytracing nad voxelov´ymi modely (dosud implementovane´ modely raw a octree).
I
´ ı pˇr´ısluˇsneho ´ Modely lze doplnit doprogramovan´ interface (Adaptive octree dosud nema´ raytracing). Softwarova´ implementace (i386, AMD64), v´yhledoveˇ ´ GPGPU pomoc´ı OpenCL (infrastruktura je definovana).
I
I
I
´ ´ 2 ovladaˇce SDL a Psano v jazyce C99, implementovany NULL Drv, Unix. ´ ˇ ´ ı pomoc´ı bodoveho ´ Podpora dynamickeho nasvetlov an´ ˇ ˇ osvetlen´ ı a ambientn´ı osvetlen´ ı.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Knihovna VoXen – vlastnosti
I
Jednoducha´ na pochopen´ı, snadne´ napsat jednoduch´y ´ u). program (cca 10 ˇradk ˚
I
Jednoduch´y prohl´ızˇ eˇc voxelov´ych modelu˚ ´ ıch. implementovateln´y v cca 150 ˇradc´ ˇ Rychlost – zhruba 5-40FPS (softwaroveˇ a bez svetel).
I I I
Poˇc´ıta´ s multiplatformnost´ı a svobodnou licenc´ı. V´yhledova´ implementace pomoc´ı GPGPU v´ypoˇctu˚ skrze ˇ ych st´ınu, OpenCL, streamingu, radiozity a mekk´ ˚ lightmapy.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Knihovna VoXen – obrazove´ v´ystupy
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Jak se dostat k obrazov´ym datum ˚
I
I
I
Hry Kena Silvermana Blood, Shadow Warrior, VOXLAP, Voxelstein, Command&Conquer. ´ modelu˚ jsem naˇsel na Par http://graphics.stanford.edu/data/voldata/. ´ Zapojit se do v´yzkumneho programu a nechat si ˇ – muj naskenovat vlastn´ı telo ˚ pˇr´ıpad.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
´ Otazky?
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
Zdroje Mark Agate, Richard L. Grimsdale, Paul F. Lister The HERO Algorithm for Ray-Tracing Octrees, LSI & Graphics Research Group School of Engineering, University of Sussex Brighton BNl 9QT, UK, 1989. John Amanatides, Andrew Woo A Fast Voxel Traversal Algorithm for Ray Tracing, Dept. of Computer Science University of Toronto Toronto, Ontario, Canada M5S 1A4, 2011. Cyril Crassin, Fabrice Neyret, Sylvain Lefebvre, Elmar Eisemann GigaVoxels: Ray-Guided Streaming for Efficient and Detailed Voxel Rendering, LJK / INRIA / Grenoble Universities / CNRS, INRIA Sophia-Antipolis, MPI Informatik / Saarland University, 2009. ´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
R. S. Ferguson Practical Algorithms for 3D Computer Graphics, A K Peters, Ltd., 2001. ISBN: 1-56881-154-3 T. Foley, J. Sugerman KD-Tree Acceleration Structures for a GPU Raytracer, HWWS: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS, 2005. Hall, J.R. Programming Linux Games. No Starch Press, San Francisco, 2001. ˇ ˇ Herout Pavel. Uˇcebnice jazyka C. Kopp, Cesk e´ Budejovice, 1999. Timothy L. Kay, James T. Kajiya Ray Tracing Complex Scenes, California Institute of Technology Pasadena, CA 91125.
´ Pavel Prochazka
´ ı voxelove´ grafiky Optimalizace vykreslovan´
Voxelova´ grafika Software
¨ K. Romisch Sparse Voxel Octree Ray Tracing on the GPU, Master’s Thesis, Department of Computer Science, Aarhus University, Denmark, 2009. Sedgewick Robert. Algorithms in C. Addison-Wesley, Princenton University, 2007. ´ J. Zˇ ara, B. Beneˇs, J. Sochor, P. Felkel Modern´ı poˇc´ıtaˇcova´ ´ ı, Computer Press, 2005. ISBN: grafika, 2. vydan´ 80-251-0454-0 Simple DirectMedia Layerhttp://www.libsdl.org/ [online] 2013, http://www.libsdl.org/ [cit. 2013-2-19]. Ken Silverman’s Voxlap Pagehttp://advsys.net/ken/voxlap.htm [online] 2013, http://advsys.net/ken/voxlap.htm [cit. 2013-4-10]. ´ ´ ı voxelove´ grafiky Pavel Prochazka Optimalizace vykreslovan´